Performance estimation in a massively parallel system

A statistical model for analyzing the performance of synchronized iterative algorithms on a multiprocessor system is presented. Key ideas are illustrated using logic simulation as an example problem. The authors introduce activity as a relevant parameter and analyze the behavior of the parallel processing system using an analytical method. The statistical performance results agree with and satisfactorily explain empirical observations on production VLSI circuits obtained by other researchers. It is shown that as the number of processors is increased, the speedup rapidly changes from p to a×p, where a is the activity and p is the number of processors. Low activity reduces speedup. A lower bound on the speedup of the parallel processing system is presented. For high activity, this lower bound is quite close to the actual speedup