TY - GEN
T1 - LogP
T2 - 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993
AU - Culler, David
AU - Karp, Richard
AU - Patterson, David
AU - Sahay, Abhijit
AU - Erik Schauser, Klaus
AU - Santos, Eunice
AU - Subramonian, Ramesh
AU - Von Eicken, Thorsten
N1 - Funding Information:
Computational support wss provided by the NSF Infrastructure Grant number CDA-8722788. David Culler is suppotted by an NSF Presidential Faculty Fellowship CCR-9253705 and LLNL Grant UCB-ERL-92/172. Klaus Erik Schauser is supported by an IBM Graduate Fellowship. Richard Karp and Abhijit Sahay are supported by NSF/DARPA Grant CCR-9005448. Eunice Santos is supported by a DOD-NDSEG Graduate Fellowship. Ramesh Subramonian is suppted by Lockheed Palo Alto Research Lalmratories under RDD 506. Thorsten von Eicken is supported by the Semiconductor Research Corporation.
Publisher Copyright:
© 1993 ACM.
PY - 1993/8/1
Y1 - 1993/8/1
N2 - 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.
AB - 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.
KW - Complexity analysis
KW - Massively parallel processors
KW - Parallel algorithms
KW - Parallel models
KW - PRAM
UR - http://www.scopus.com/inward/record.url?scp=0027838760&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027838760&partnerID=8YFLogxK
U2 - 10.1145/155332.155333
DO - 10.1145/155332.155333
M3 - Conference contribution
AN - SCOPUS:0027838760
T3 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
SP - 1
EP - 12
BT - Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 1993
PB - Association for Computing Machinery,
Y2 - 19 May 1993 through 22 May 1993
ER -