LogP: towards a realistic model of parallel computation

ABSTRACT

A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of formal loopholes, rather than rewarding development of techniques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. it is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers. Such a model must strike a balance between detail and simplicity in order to reveal important bottlenecks without making analysis of interesting problems intractable. The model is based on four parameters that specify abstractly the computing bandwidth, the communication bandwidth, the communication delay, and the efficiency of coupling communication and computation. Portable parallel algorithms typically adapt to the machine configuration, in terms of these parameters. The utility of the model is demonstrated through examples that are implemented on the CM-5.

REFERENCES

• 1: A. Aggarwal , A. K. Chandra , M. Snir, On communication latency in PRAM computations, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.11-21, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72937]
• 2: Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
• 3: B. Alpem, L. Carter, E. Feig, and T. Selker. The Uniform Memory Hierarchy Model of Computation. Algorithmica, 1993. (to appear).
• 4: Amotz Bar-Noy , Shlomo Kipnis, Designing broadcasting algorithms in the postal model for message-passing systems, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.13-22, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140903]
• 5: Gordon Bell, Ultracomputers: a teraflop before its time, Communications of the ACM, v.35 n.8, p.26-47, Aug. 1992 [doi>10.1145/135226.135227]
• 6: G.E. Blelloch. Scans as Primitive Parallel Operations. In Proceedings of lnternational Conference on Parallel Processing, pages 355-362, 1987.
• 7: R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72954]
• 8: J.M. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex Fourier series. Math. Comp, 19:297- 301, 1965.
• 9: David E. Culler , Richard M. Karp , David A. Patterson , Abhijit Sahay , Klaus E Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: Towards a Realistic Model of Parallel Computation, University of California at Berkeley, Berkeley, CA, 1992
• 10: W. et al Dally. The J-Machine: A Fine-Grain Concurrent Computer. In IFIP Congress, 1989.
• 11: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 12: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 13: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 14: P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72953]
• 15: J. L. Hennessy. MIPS R4000 Overview. In Proc. of the 19th lnt'l Symposium on Computer Architecture, Gold Coast, Australia, May 1992.
• 16: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 17: IEEE. Symposium Record-- Hot Chips IV, August 1992.
• 18: P. C. Kanellakis , A. A. Shvartsman, Efficient parallel algorithms can be made robust, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.211-219, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72996]
• 19: Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
• 20: Richard M. Karp , Abhijit Sahay , Eunice Santos, Optimal Broadcast and Summation in the LogP Model, University of California at Berkeley, Berkeley, CA, 1992
• 21: Z. M. Kedem , K. V. Palem , P. G. Spirakis, Efficient robust parallel computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.138-148, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100231]
• 22: C.U.Martel andA. Raghunathan.Asynchronous PRAMs with memory latency. Technical report, University of California, Davis, Division of Computer Science, 1991.
• 23: Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
• 24: Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
• 25: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
• 26: A.G. Ranade. How to emulate shared memory.in Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science, pages 185-194, 1987.
• 27: Abhijit Sahay, Hiding Communication Costs in Bandwidth-Limited Parallel FFT, University of California at Berkeley, Berkeley, CA, 1992
• 28: Lawrence Snyder, Type architectures, shared memory, and the corollary of modest potential, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
• 29: R. Subramonian. The influence of limited bandwidth on algorithm design and implementation. In Dartmouth Institute for Advanced Graduate Studies in Parallel Computation (DAGS/PC), June 1992.
• 30: 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]
• 31: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Performance

Keywords:
PRAM, complexity analysis, massively parallel processors, parallel algorithms, parallel models