.Abstract LogP: Towards a Realistic Model of Parallel Computation

A vast body of theoretical research hea focused either on overly SimpKStiC 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 techrdques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called lLogP, that reflects the critical technology trends underlying parallel computers. It is intended to serve as a basis for developing fas~ portable parallel algorithms and to offer guidelines to machme 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 couplimg 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