2008 · 119 citations · 24 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingCachingExternal Memory AlgorithmsMemory HierarchyMemory Hierarchy OptimizationParallel ArchitecturesParallel SortingLower BoundsMemory Hierarchy AlgorithmsMemory Hierarchy ModelingScalable Parallel Algorithms
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.
24
A bridging model for parallel computation
Leslie G. Valiant · Communications of the ACM · 1990 · 3.7K citations · Full text
LogP: towards a realistic model of parallel computation
David Culler, Richard M. Karp, David A. Patterson et al. · 1993 · 1.5K citations
The input/output complexity of sorting and related problems
Alok Aggarwal · Communications of the ACM · 1988 · 1.2K citations · Full text
Richard Cole · SIAM Journal on Computing · 1988 · 734 citations
Chip makers turn to multicore processors
D. A. Geer · Computer · 2005 · 445 citations