An analytical model for predicting the performance of algorithms on a shared-memory multiprocessor is presented. The experiments use synthetic programs and four algorithms: for binary search, random permutation, sparse matrix multiplication, and finding connected components of a graph. The model predicts the performance of these programs quite well on the Cray C90 and J90 machines. One of the major limitations of the model, as the authors point out, is the lack of cache effects. This limitation reduces the accuracy and applicability of this model for current and near-future shared-memory machines. For practical purposes, the model should be extended.

This research paper fulfills its basic purpose of including memory contention and delay in the model. Its best features include the authors’ intuitive description of the theorems and clear explanation of the algorithms. The paper is well presented, and people in the area of performance analysis will find it useful.