A static performance estimator to guide data partitioning decisions

Abstract

The choice of the data domain partitioning scheme is an important factor in determining the available parallelism and hence the performance of an application on a distributed memory multiprocessor. In this paper, we present a performance estimator for statically evaluating the relative efficiency of different data partitioning schemes for any given program on any given distributed memory multiprocessor. Our methlod is not based on a theoretical machine model, but ixnstead uses a set of kernel routinea to "train" the estimator for each target machine. We also describe a prototype implementation of this technique and discuss an experimental evaluation of its accuracy.