A Memory-Constrained Scalability Metric

A performance evaluation metric called CMP scalability is introduced This metric is useful in analyzing performance of a parallel algorithm as the number of processors grows but the memory size per processor is fixed. The CMP scalability metric is derived for the parallel Matrix Multiplication (MM). Gauss Jordan Elimination (GJE), and Fast Fourier Transform (FFT). These examples show that the CMP scalability metric and the isoefficiency metric really address different aspects of scalability and could lead to very different conclusions. According to the CMP scalability analysis FFT is more scalable than GJE. Interestingly, conclusions drawn from the isoefficiency analysis are quite the opposite. The CMP scalability metric, and so also the isoefficiency metric, is a function indicating the asymptotic behavior as the number of processors becomes large. However, the CMP analysis can also help to analyze the performance of an algorithm on a given architecture with a limited number of processors. We present such an analysis of the three algorithms on a 16K processor MasPar MP-1 machine.