One-dimensional processor arrays for linear algebraic problems
Roman Wyrzykowski, Juri Kanevski, Henryk Piech · IEE Proceedings - Computers and Digital Techniques · 1995
Using isomorphic embedding of the original dependence graphs in another graph before its space-time mapping onto array architectures, two linear processor arrays are designed for the Gauss-Jordan algorithm with partial pivoting and Cholesky decomposition. Each of these arrays comprises only (n+1)/2 processing elements (PEs), where n is the number of columns in the input matrices. The block pipelining period is n(n-1) cycles for the first array and n(n+1)/2 cycles for the second. If the matrices are processed sequentially, systems of linear equations are solved by the Gauss-Jordan algorithm with almost full processor utilisation, whereas for the Cholesky decomposition the utilisation of PEs is approximately two-thirds.