Fundamental parallel algorithms for private-cache chip multiprocessors

ABSTRACT

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.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Bradley C. Kuszmaul, Concurrent cache-oblivious b-trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074009]
• 3: Guy E. Blelloch , Rezaul A. Chowdhury , Phillip B. Gibbons , Vijaya Ramachandran , Shimin Chen , Michael Kozuch, Provably good multicore cache performance for divide-and-conquer algorithms, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.501-510, January 20-22, 2008, San Francisco, California
• 4: Shimin Chen , Phillip B. Gibbons , Michael Kozuch , Vasileios Liaskovitis , Anastassia Ailamaki , Guy E. Blelloch , Babak Falsafi , Limor Fix , Nikos Hardavellas , Todd C. Mowry , Chris Wilkerson, Scheduling threads for constructive cache sharing on CMPs, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248396]
• 5: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 6: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 7: Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
• 8: Thomas H. Cormen , Michael T. Goodrich, A bridging model for parallel computation, communication, and I/O, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996 [doi>10.1145/242224.242490]
• 9: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 10: P. de la Torre , C. P. Kruskal, A structural theory of recursively decomposable parallel processor-networks, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.570, October 25-28, 1995
• 11: F. Dehne, W. Dittrich, D. Hutchinson, and A. Maheshwari. Bulk synchronous parallel algorithms for the external memory model. Theory of Computing Systems, 35(6):567--598, 2002.
• 12: David Geer, Industry Trends: Chip Makers Turn to Multicore Processors, Computer, v.38 n.5, p.11-13, May 2005 [doi>10.1109/MC.2005.160]
• 13: Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Deterministic sorting and randomized median finding on the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.223-232, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237561]
• 14: Michael T. Goodrich, Communication-Efficient Parallel Sorting, SIAM Journal on Computing, v.29 n.2, p.416-432, Oct. 1999 [doi>10.1137/S0097539795294141]
• 15: Michael T. Goodrich , S. Rao Kosaraju, Sorting on a parallel pointer machine with applications to set expression evaluation, Journal of the ACM (JACM), v.43 n.2, p.331-361, March 1996 [doi>10.1145/226643.226670]
• 16: M. T. Goodrich , Jyh-Jong Tsay , D. E. Vengroff , J. S. Vitter, External-memory computational geometry, Proceedings of the Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, p.714-723, November 03-05, 1993 [doi>10.1109/SFCS.1993.366816]
• 17: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 18: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 19: Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165250]
• 20: G. Lowney. Why Intel is designing multi-core processors. https://conferences.umiacs.umd.edu/paa/lowney.pdf.
• 21: Mark H. Nodine , Jeffrey Scott Vitter, Deterministic distribution sort in shared and distributed memory multiprocessors, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.120-129, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165247]
• 22: Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995 [doi>10.1145/210332.210343]
• 23: Justin Rattner, Multi-Core to the Masses, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.3, September 17-21, 2005 [doi>10.1109/PACT.2005.31]
• 24: John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 25: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 26: U. Vishkin, A PRAM-on-Chip Vision (invited abstract), Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), p.260, September 27-29, 2000
• 27: Jeffrey Scott Vitter, External Memory Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.1-25, August 24-26, 1998
• 28: Jeffrey Scott Vitter , Mark H. Nodine, Large-scale sorting in uniform memory hierarchies, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.107-114, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1008]
• 29: J. S. Vitter , E. A. M. Shriver, Optimal disk I/O with parallel block transfer, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.159-169, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100234]
• 30: J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Algorithmica, 12(2--3):110--147, 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory

Keywords:
parallel external memory, pem, private-cache cmp