A parallelizing compiler for distributed memory parallel computers
Ping-Sheng Tseng · 1989
Distributed memory parallel computers provide an attractive approach to high speed computing because their performance can be easily scaled up by increasing the number of processor-memory modules. To use these computers, we have to design parallel algorithms and produce parallel programs. In many cases, parallel algorithm design is a mapping of existing algorithms to parallel architectures. In this thesis, we study such a mapping process and present a parallelizing compiler which can: (1) automate the program mapping, and (2) generate efficient parallel code. There are three key components in our program mapping: data decomposition, loop distribution and data relations. Data decomposition maps data structures to the distributed memory system; loop distribution maps the computation to processors; and data relations determine the interprocessor communication. The compiler applies data flow analysis and data dependence analysis to minimize interprocessor communication overhead and parallelize program execution. Based on these ideas, we have implemented the AL parallelizing compiler for the Warp machine. AL is a generic programming language for the prototype implementation. The target machine, Warp, is a programmable linear systolic array of 10 processors. AL has been successfully used to program many applications on Warp. These applications include matrix computations, image processing, finite element analysis, and partial differential equations. The AL compiler is able to generate efficient parallel code. For example, for the LINPACK routines such as LU decomposition, QR decomposition, and singular value decomposition (SVD), the AL compiler generates parallel code which achieves 8-fold speedup on the 10-processor array for small matrices of size 180 x 180. This thesis makes contributions to the research area of parallelizing compilers by introducing a model for mapping programs to distributed memory parallel computers. This thesis also makes contributions to the research area of parallel programming by introducing an approach to programming distributed memory parallel computers.