A systolic helix for matrix triangularisation with partial pivoting

Abstract

A helical systolic array for triangularising a dense matrix using Gaussian elimination with partial pivoting is proposed. The design uses 2n − 1 real processors, (n −1)2 intelligent switching cells and requires O(n2) time. The design is then extended to a modified triangular array which uses O(n3) basic cells with O(n2) true processors the rest switches. The latter design improves the array throughput, accelerates the speedup, and follows from a space-time unrolling of the helical array.