Compiling data-parallel programs for efficient execution on shared-memory multiprocessors
Siddhartha Chatterjee · 1992
Data parallelism is well-suited from algorithmic, architectural, and linguistic considerations to serve as a basis for portable parallel programming. However, the fine-grained parallelism characteristic of data-parallel programs makes the efficient implementation of such languages on MIMD machines a challenging task due to the high overheads these machines incur at small grain sizes. We claim that compile-time analysis can be used to reduce these overheads, thereby allowing data-parallel code to run efficiently on MIMD machines. This dissertation reports on the design, implementation, and evaluation of an optimizing compiler for an applicative nested data-parallel language called V scCODE. The target machine is the Encore Multimax, a coherent-cache shared-memory multiprocessor. The source language allows nested aggregate data types, and provides a variety of aggregate operations including elementwise forms, scans, reductions, and permutations. Such features greatly expand the range of applications that can be cast into a data-parallel model. We present a small set of powerful compile-time techniques that reduce the overheads on MIMD machines in several ways: by increasing the grain size of the output program, by reducing synchronization and storage requirements, and by improving locality of reference. The two key ideas behind these optimizations are the symbolic analysis of loop structures, and the hierarchical clustering of the program graph, first by loop structure, and then by loop traversal patterns. This localizes synchronization and work distribution actions to well-defined points in the output code. Loop traversal patterns are then used to identify parallel loops and to eliminate unnecessary intermediate storage. The most significant aspect of the analysis techniques is that they are symbolic in nature and work in the presence of control constructs such as conditionals and recursion. A compiler has been implemented based on these ideas and has been used to compile a large number of benchmarks. The benchmark suite covers a variety of problem domains, including dense and sparse matrix operations, tree and graph algorithms, dynamic and data-dependent algorithms, and low- and medium-level image processing applications. The performance results substantiate the claim that data-parallel code can be made to run efficiently on MIMD machines, and demonstrate that compiler optimizations are essential for good performance.