Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Lars Allan Arge
  • Michael T. Goodrich, Chancellor's Professor, Department of Computer Science, Bren School of Information & Computer Sciences, University of California, Irvine, United States
  • Michael Nelson, Department of Computer Science, Bren School of Information & Computer Sciences, University of California, Irvine, United States
  • Nordari Sitchinava, Department of Computer Science, Bren School of Information & Computer Sciences, University of California, Irvine, United States
  • Department of Computer Science
In this paper, we study parallel algorithms for private-cache chip multiprocessors (CMPs), focusing on methods for foundational problems that are scalable with the number of cores. By focusing on private-cache CMPs, we show that we can design efficient algorithms that need no additional assumptions about the way cores are interconnected, for we assume that all inter-processor communication occurs through the memory hierarchy. We study several fundamental problems, including prefix sums, selection, and sorting, which often form the building blocks of other parallel algorithms. Indeed, we present two sorting algorithms, a distribution sort and a mergesort. Our algorithms are asymptotically optimal in terms of parallel cache accesses and space complexity under reasonable assumptions about the relationships between the number of processors, the size of memory, and the size of cache blocks. In addition, we study sorting lower bounds in a computational model, which we call the parallel external-memory (PEM) model, that formalizes the essential properties of our algorithms for private-cache CMPs.
Original languageEnglish
Title of host publicationACM Symposium on Parallelism in Algorithms and Architectures : Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures.
EditorsFriedhelm Meyer auf der Heide, Nir Shavit
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2008
Pages197-206
ISBN (print)978-1-59593-973-9
DOIs
Publication statusPublished - 2008
EventAnnual symposium on Parallelism in algorithms and architectures - Munich, Germany
Duration: 14 Jun 200816 Jun 2008
Conference number: 20

Conference

ConferenceAnnual symposium on Parallelism in algorithms and architectures
Nummer20
LandGermany
ByMunich
Periode14/06/200816/06/2008

    Research areas

  • parallel external memory, pem, privae-cache cmp

See relations at Aarhus University Citationformats

ID: 13227348