Automatic partitioning of data and computations on scalable shared memory multiprocessors
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper describes an algorithm for deriving data and computation partitions on scalable shared memory multiprocessors. The algorithm establishes affinity relationships between where computations are performed and where data is located based on array accesses in the program. The algorithm then uses these affinity relationships to determine both static and dynamic partitions for arrays and parallel loops. Experimental results from a prototype implementation of the algorithm demonstrate that it is computationally efficient and that it improves the parallel performance of standard benchmarks. The results also show the necessity of taking shared memory effects (memory contention, cache locality, false-sharing and synchronization) into account---partitions derived to minimize only interprocessor communications do not necessarily result in the best performance.Keywords
This publication has 8 references indexed in Scilit:
- The Stanford FLASH multiprocessorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Automatic partitioning of data and computations on scalable shared memory multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Data and computation transformations for multiprocessorsPublished by Association for Computing Machinery (ACM) ,1995
- Evaluating Compiler Optimizations for Fortran DJournal of Parallel and Distributed Computing, 1994
- Demonstration of automatic data partitioning techniques for parallelizing compilers on multicomputersIEEE Transactions on Parallel and Distributed Systems, 1992
- Compiling communication-efficient programs for massively parallel machinesIEEE Transactions on Parallel and Distributed Systems, 1991
- Exploiting operating system support for dynamic page placement on a NUMA shared memory multiprocessorPublished by Association for Computing Machinery (ACM) ,1991
- Hector: a hierarchically structured shared-memory multiprocessorComputer, 1991