On the systematic design of systolic arrays

This paper describes a general technique for the design of systolic arrays. Various attempts have been made in the past to design systolic arrays from computational algorithms. However, most of these methods have their limitations. In this paper, a technique based on dependence graphs is presented. Starting from the algorithm itself, steps are outlined which enable the designer to extract parallelism from the program constructs. The method further outlines steps to detect and incorporate pipelining into the yet unrealized systolic architecture. Next, dependence graphs corresponding to the data items, which are now arranged in a parallel and pipelined fashion, are drawn. This is followed by a procedure for `systolizing´ the dependence graphs. Finally, steps are outlined for mapping the systolic dependence graph onto a systolic architecture. The technique is illustrated by designing systolic arrays for computing position velocities and accelerations