Automatic computation and data partitioning on scalable shared-memory multiprocessors
Tarek S. Abdelrahman, Sudarsan Tandri · 1997
Scalable shared memory multiprocessors are becoming increasingly popular platforms for high-performance scientific computing because they both scale to large numbers of processors and support the familiar shared memory abstraction. In order to improve application performance on these machines, it is essential to divide computation among processors and to place data carefully in the distributed shared memory. In particular, relying on only the native operating system page placement policies to manage data often results in poor performance of applications. Computation and data partitioning is necessary for the management of computation and data on shared memory multiprocessors. The primary focus of this dissertation is the automatic derivation of computation and data partitions for regular scientific applications on scalable shared memory multiprocessors. Ideally, such partitions maximize parallelism and cache locality and minimize remote memory accesses, memory contention, synchronization overhead, and false sharing. In general, the problem of deriving optimal computation and data partitions is NP-hard. The complexity results from the combinatorics of possible computation and data partitions and the interdependence of the above optimization objectives. The degree to which these optimization objectives affect the performance of an application also varies, according to the characteristics of the application and the architecture of the scalable shared memory multiprocessor. This dissertation presents a heuristic algorithm called the Computation and Data Partitioning (CDP) algorithm for deriving computation and data partitions on scalable shared memory multiprocessors. The CDP algorithm establishes affinity relationships between where data is located, based on array accesses in the program, and where computations are performed. These data-computation affinity relationships are used as a basis to determine the computation partitions for all the parallel loops, and to determine static and/or dynamic data partitions for all the arrays in the input program. The CDP algorithm takes into account shared memory effects in selecting the appropriate computation and data partitions. Experimental results from the implementation of the CDP algorithm in a prototype compiler demonstrate that the algorithm is computationally efficient and that it improves the performance of a suite of benchmark applications, compared to the native operating system page placement policies for data management.