This paper describes an AL compiler for the Warp systolic array. AL is a programming language in which the user programs a systolic array as if it were a sequential computer and relies on the compiler to generate parallel code. This paper introduces the notion of data relations in compiling programs for systolic arrays. Unlike dependence relations among statements of a program, data relations define compatibility relations among data objects of a program. The AL compiler uses data relations to compute data compatibility classes, determine data distribution, and distribute loop iterations. The AL compiler can generate efficient parallel code almost identical to what the user would have written by hand. For example, the AL compiler generates parallel code for the LINPACK LU decomposition (SGEFA) and QR decomposition (SQRDC) routines with a nearly 8-fold speedup on the 10-cell Warp array for matrices of size 180 × 180.

An architecture called an orthogonal multiprocessor (OMP) is proposed. This OMP architecture has a simplified busing structure and partially shared memory and compares very favorably with fully shared-memory multiprocessors using crossbar switches, multiple buses, or multistage networks. The higher performance comes mainly from significantly increased memory bandwidth, fully exploited parallelism, reduced communication overhead, and lower hardware control complexities. Parallel algorithms being mapped include matrix arithmetic, linear system solver, FFT, array sorting, linear programming, and parallel PDE solutions. In most cases, linear speedup can be achieved on the OMP system. The OMP architecture provides linearly scalable performance and is well suited for building special-purpose scientific computers.>