Modeling parallel communication

The LogP model provides a framework for analyzing the performance of algorithms on distributed-memory multiprocessors. The model takes into account both the cost of computation and the cost of communication. It describes a multiprocessor in terms of four parameters, representing computation power, communication bandwidth, communication latency and the degree of overlap between computation and communication. In this paper we discuss the rationale for the different features of the LogP model. We then compare the model with other models having similar aims, such as network-based models, Valiant´s BSP model, and the PRAM(m) model. Finally, we call upon the work of a number of students at Berkeley to illustrate the application of the model to problems of broadcasting, sorting, FFT computation, summing, prefix summing and solution of triangular and tridiagonal systems