1 Search Results for "Salinger, Alejandro"


Document
Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)

Authors: Alejandro Lopez-Ortiz, Reza Dorrigiv, and Alejandro Salinger

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)


Abstract
We propose a new model with small degreee of parallelism that reflects current and future multicore architectures in practice. The model is based on the PRAM architecture and hence it inherits many of its interesting theoretical properties. The key observations and differences are that the degree of parallelism (i.e. number of processors or cores) is bounded by O(log n), the synchronization model is looser and the use of parallelism is at a higher level unless explicitly specified otherwise. Surprisingly, these three rather minor variants result in a model in which obtaining work optimal algorithms is significantly easier than for the PRAM. The new model is called Low-degree PRAM or LoPRAM for short. Lastly we observe that there are thresholds in complexity of programming at p=O(log n) and p=O(sqrt(n)) and provide references for specific problems for which this threshold has been formally proven.

Cite as

Alejandro Lopez-Ortiz, Reza Dorrigiv, and Alejandro Salinger. Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM). In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:DagSemProc.08081.3,
  author =	{Lopez-Ortiz, Alejandro and Dorrigiv, Reza and Salinger, Alejandro},
  title =	{{Optimal Speedup on a Low-Degree Multi-Core Parallel Architecture (LoPRAM)}},
  booktitle =	{Data Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.3},
  URN =		{urn:nbn:de:0030-drops-15315},
  doi =		{10.4230/DagSemProc.08081.3},
  annote =	{Keywords: PRAM, multicore architectures, parallelism, algorithms, dynamic programming, divide and conquer}
}
  • Refine by Author
  • 1 Dorrigiv, Reza
  • 1 Lopez-Ortiz, Alejandro
  • 1 Salinger, Alejandro

  • Refine by Classification

  • Refine by Keyword
  • 1 PRAM
  • 1 algorithms
  • 1 divide and conquer
  • 1 dynamic programming
  • 1 multicore architectures
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail