LogP: Towards a realistic model of parallel computation

David Culler, Richard Karp, David Patterson, Abhijit Sahay, Klaus Erik Schauser, Eunice Santos, Ramesh Subramonian, Thorsten Von Eicken

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993
PublisherAssociation for Computing Machinery,
Pages1-12
Number of pages12
ISBN (Electronic)0897915895
DOIs
StatePublished - Aug 1 1993
Externally publishedYes
Event4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993 - San Diego, United States
Duration: May 19 1993May 22 1993

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
VolumePart F129677

Other

Other4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993
CountryUnited States
CitySan Diego
Period5/19/935/22/93

Keywords

  • Complexity analysis
  • Massively parallel processors
  • Parallel algorithms
  • Parallel models
  • PRAM

ASJC Scopus subject areas

  • Software
  • Engineering(all)

Fingerprint Dive into the research topics of 'LogP: Towards a realistic model of parallel computation'. Together they form a unique fingerprint.

  • Cite this

    Culler, D., Karp, R., Patterson, D., Sahay, A., Erik Schauser, K., Santos, E., Subramonian, R., & Von Eicken, T. (1993). LogP: Towards a realistic model of parallel computation. In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993 (pp. 1-12). (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP; Vol. Part F129677). Association for Computing Machinery,. https://doi.org/10.1145/155332.155333