On High Level Characterization of Parallelism

The paper discusses issues pertinent to performance analysis of massively parallel systems. A model of parallel execution based on threads of control and events is then introduced. The key ingredient of this model is a measure of the communication complexity, which gives the number of events E as a function of the number of threads of control P and provides a signature of a parallel computation. Various consequences for speedup and load balancing are presented.