Compiling Parallel Loops for High Performance Computers: Partitioning, Data Assignment and Remapping(200 The Springer International Series in Engineering and Computer Science)

The exploitation of parallel processing to improve computing speeds is being examined at virtually all levels of computer science, from the study of parallel algorithms to the development of microarchitectures which employ multiple functional units. The most visible aspect of this interest in parallel processing is the commercially available multiprocessor systems which have appeared in the past decade. Unfortunately, the lack of adequate software support for the development of scientific applications that will run efficiently on multiple processors has stunted the acceptance of such systems. One of the major impediments to achieving high parallel efficiency on many data-parallel scientific applications is communications overhead, which is exemplified by cache coherency traffic and global memory accesses. This book presents compile-time techniques to reduce the overhead of interprocessors with a logically shared address space and physically distributed memory. Such techniques can be used by scientific application designers seeking to optimize code for a particular high-performance computer. In addition, these techniques can be seen as a necessary step toward developing software to support efficient parallel programmes. In multiprocessor systems with physically distributed memory, reducing communication overhead involves both data partitioning and data placement. "Adaptive Data Partitioning" (ADP) reduces the execution time of parallel programmes by minimizing interprocessor communication for iterative data-parallel loops with near-neighbour communication. Data placement schemes are presented that reduce communication overhead. Under the loop partition specified by ADP, global data is partitioned into classes for each processor, allowing each processor to cache certain regions of the global data set. In addition, for many scientific applications, peak parallel efficiency is achieved only when machine-specific tradeoffs between load imbalance and communication are evaluated and utilized in choosing the data partition. The techniques in this book evaluate these tradeoffs to generate optimum cyclic partitions for data-parallel loops with either a linearly varying or uniform computational structure and either neighbourhood or dimensional multicast communication patterns. This tradeoff is also treated within the CPR (Collective Partitioning and Remapping) algorithm, which partitions a collection of loops with various computational structures and communication patterns. Experiments that demonstrate the advantage of ADP, data placement, cyclic partitioning and CPR were conducted on the Encore Multimax and BBN TC2000 multiprocessors using the ADAPT system, a programme partitioner which automatically restructures iterative data-aparallel loops.

Table of Contents:
1 Introduction.- 1.1 Model Assumptions.- 1.2 Related Work.- 1.3 Overview.- 2 Contiguous Loop Partitions for Neighborhood Communication.- 2.1 Introduction.- 2.2 Quantifying Communication.- 2.3 Compensation for Cache Line Size.- 2.4 Partition Construction.- 2.5 Experimental Evaluation of ADP.- 2.6 Conclusion.- 3 Contiguous Data Assignments for Neighborhood Communication.- 3.1 Introduction.- 3.2 Data Assignments.- 3.3 Exploiting Overlap.- 3.4 Software Redundancy.- 3.5 ADAPT.- 3.6 Experimental Results.- 3.7 Conclusion.- 4 Cyclic Loop Partitions for Linearly Varying Loops.- 4.1 Introduction.- 4.2 Code Segments.- 4.3 Determining Communication Parameters.- 4.4 Multicast Communication Overhead.- 4.5 Partitioning.- 4.6 Experimental Results.- 4.7 Conclusion.- 5 Collective Partitioning and Remapping for Multiple Loop Nests.- 5.1 Introduction.- 5.2 Program Enclosure Trees.- 5.3 The CPR Algorithm.- 5.4 Experimental Results.- 5.5 Conclusion.