Automatic Computation and Data Decomposition for Multiprocessors
Monica S. Lam, Jennifer-Ann M. Anderson · 1997
Memory subsystem efficiency is critical to achieving high performance on parallel machines. The memory subsystem organization of modern multiprocessor architectures makes their performance highly sensitive to both the distribution of the computation and the layout of the data. A key issue in programming these machines is selecting the computation decomposition and data decomposition, the mapping of the computation and data, respectively, across the processors of the machine. A popular approach to the decomposition problem is to require programmers to perform the decomposition analysis themselves, and to communicate that information to the compiler using language extensions. This thesis presents a new compiler algorithm that automatically calculates computation and data decompositions for dense-matrix scientific codes. The core of the algorithm is based on a linear algebra framework for expressing and calculating the computation and data decompositions. Using the linear algebra model, the algorithm generates a system of equations that specifies the conditions the desired decompositions must satisfy. The decompositions are then calculated systematically by solving the system of equations. Since the best decompositions may change as different phases of the program are executed, the algorithm also considers re-organizing the data dynamically. The analysis is performed both within and across procedure boundaries so that entire programs can be analyzed. We have incorporated our techniques into the SUIF parallelizing compiler system. We evaluated the effectiveness of the algorithm by applying the compiler to a suite of benchmark programs, and compared the performance of the resulting code to the performance obtained without using our techniques. We found that our decomposition analysis and optimization can lead to significant increases in program performance.