Formal description of systolic algorithms and an analysis of the information flow
Hirotome Aso, Yasuyoshi Inagaki · Systems and Computers in Japan · 1988
Abstract Due to the development of VSLI fabrication technologies systolic algorithms are now being implemented as practical hardware. As a result, it is becoming more important to know their design methodologies and the scope of their object problems. In this paper as a basis to know the scope of the object problems we formalize systolic algorithms as mathematical objects in a strict manner. In other words, it is formalized by a triple systolic array, a data location space, and a set of timing functions. Moreover, equivalence between systolic arrays is defined. Under this formulation we define a data dependency graph as a tool for analyzing the flow of information, and show that wiring structures can be classified into several types. We give a condition that it is reduced equivalently to a simple memory‐type one. Finally, we consider the data flow processed in a systolic array and give not only an equation for data flow, but also the initial arrangement for a necessary encounter for interaction between data flows.