Modeling Communication Locality in Multiprocessors

Locality of reference is an important aspect of many computer operations. It is often exploited to optimize the performance of computer functions. In this paper, we apply the locality concept to the communication patterns of parallel programs operating over an interconnection network with a fixed communication latency between any pair of attached nodes. Unbuffered multistage networks and all-optical networks are examples of these. We quantify the notions of spatial and temporal locality in this context, and combine them in a locality measure. This measure is used as the basis for identifying the communication working sets of a parallel program. We focus on programs with a looping structure and investigate conditions under which each working set consists of the complete set of paths required by a single loop.