Automatic generation of systolic programs from nested loops
Hudson Benedito Ribas · 1990
Many applications with challenging performance requirements and a high potential for parallelization can be found in the area of numerical computing. These applications, such as matrix computations, signal processing algorithms, and finite-difference methods, consist mainly of computationally intensive nested loops. While many problems in these fields have been successfully implemented on a wide variety of parallel computers, the process of programming these machines still remains tedious and ad hoc. The parallel computation model based on regularly interconnected arrays of processors with high-bandwidth neighbor-to-neighbor communication (systolic arrays) has been shown to be a highly efficient means of parallelization for this application domain. However, this efficiency is accompanied by an increased difficulty in programming arrays of processors. Among the main factors that make the programming of these machines difficult and error prone are: managing multiple threads of control in disjoint address spaces, explicitly coordinating communication between processors, and tailoring the implementation of an algorithm to machine dependent characteristics such as the number of processors and communication channels. The main contribution of this work is the reduction of the difficulty in programming systolic array computers by automatically generating programs from high-level language nested loops for a given programmable systolic array of processors. The techniques used for generating code are based on linear transformations of the same kind used for automatic synthesis of special purpose systolic arrays from algorithms with uniform dependencies. The work has been evaluated and validated on the Warp, a 10-cell programmable linear systolic array. Each Warp cell is a VLIW 10 MFLOPS processor with two communication channels to each of its neighbors. Code has been automatically generated and performance measurements have been taken for benchmark programs such as matrix multiplication, LU decomposition, QR decomposition, shortest path, transitive closure, and the Livermore loops. With the ideas and techniques introduced in this thesis, efficient parallel code can be generated and it has been shown that the performance benefits of the systolic communication programming model can be achieved from a high-level algorithm description. For instance, for the matrix computations, speedups from 7.4 to 7.9 have been obtained on 8 cells for matrices of size 120 x 120. Also, very good performance has been achieved for most of the benchmark programs, e.g., on 8 cells: 64 MFLOPS for matrix multiplication, 21 MFLOPS for LU decomposition, and 37 MFLOPS for QR decomposition.