A Cost Model for Communication on a Symmetric MultiProcessor

Nancy M. Amato
Texas A&M University
Andrea Pietracaprina
University of Padova
Geppino Pucci
University of Padova

Lucia K. Dale
Texas A&M University
Jack Perdue
Texas A&M University


In this paper we conduct an in-depth study of the communication costs of programs when run on a typical Symmetric MultiProcessor, the SGI Power Challenge, characterized by powerful off-the-shelf microprocessors communicating through a shared memory via a shared-bus interconnect. Our study is based on an extensive set of experiments designed to assess the relative impact of a number of parameters on the cost of shared memory accesses. We provide evidence that interaction with the memory hierarchy affects communication in such a substantial way that none of the models previously considered in the literature can guarantee a reasonable level of accuracy since they do not take this interaction into account. We then determine two prediction functions that are very accurate predictors of best and worst performance with respect to the memory hierarchy. These functions provide a prediction interval that can be employed to obtain lower and upper bounds on the actual communication cost of an application, and to evaluate the degree of locality of the memory access patterns involved.

Technical Report 98-004, Department of Computer Science, Texas A&M Univerity, January 1998. Full Paper (postscript)