Systolic algorithms/architectures for division-free linear system solving

Division-free algorithms for solving the linear algebra problems and its applications in signal/image processing have attracted interests for parallel processing. In this paper the design of systolic array processors for solving linear systems of equations using division-free Gaussian elimination method is presented. The design is based on a systematic approach which constructs array processors systematically by first investigating parallel versions of the division-free algorithm and their three dimensional dependency graphs, and then generating the planar systolic array processors by projecting the dependency graph along properly selected directions. The resulting array processors are synthesized and analyzed. It is shown that some array processors are optimal. The key for designing an optimal array processor Is to design a parallel algorithm whose dependency graph is a well-structured. The array processors are optimal in terms of number of processing elements, number of input/output ports, time of processing and pipelining period