A Systolic Array Parallelizing Compiler

1 Introduction.- 2 Systolic array programming.- 2.1 The Warp machine.- 2.2 The W2 programming language.- 2.3 The AL programming language.- 2.4 Related work.- 3 Data relations.- 3.1 Linear data relations.- 3.2 Joint data compatibility classes.- 3.3 Scope of data compatibility classes.- 3.4 Summary.- 4 Loop Distribution.- 4.1 Intercell communication.- 4.2 The basic loop distribution scheme.- 4.3 Distributed loop parallelism.- 4.4 Optimization.- 4.5 Related work.- 5 Implementation.- 5.1 External interface.- 5.2 Compiling DO* loops.- 5.3 The ALIGN* statement.- 5.4 Parallel accumulation.- 5.5 Program debugging.- 6 Evaluation.- 6.1 Matrix computations.- 6.2 2D Fast Fourier Transform.- 6.3 Partial differential equation solvers.- 6.4 Summary.- 7 Conclusions.- A Linear data relations in Livermore Loops.- B Benchmark programs.- B.1 LU decomposition.- B.1.1 Single cell.- B.1.2 Multiple cells.- B.2 QR decomposition.- B.2.1 Single cell.- B.2.2 Multiple cells.- B.3 Singular value decomposition.- B.3.1 Single cell.- B.3.2 Multiple cell.- B.4 2D Fast Fourier Transform.- B.4.1 Single cell.- B.4.2 Multiple cell.- B.5 Partial differential equation solvers.- B.5.1 SOR.- B.5.2 Line SOR.- B.5.3 Two-color SOR.