The cut theorem—a tool for design of systolic algorithms
Kevin McEvoy, Peter M. Dew · International Journal of Computer Mathematics · 1988
This paper describes a thorough mathematical treatment of retiming transformations, and discusses the advantages which they provide for the design of systolic algorithms. This approach to synchronous design originated with Leiserson and Saxe [14], but more complete and accurate statements of the retiming results are presented here. This is achieved through a precise formulation of the model of computation. The importance of the Cut Theorem in systolic design has been emphasized on many occasions (e.g. S. Y. Kung and others at the First International Workshop on Systolic Arrays [23]), but the statements and proofs of this theorem have so far been somewhat imprecise. An exact and general formulation of the Cut Theorem is given, and there is discussion of its use as a design tool (including the design of two-level pipelined arrays). This approach provides some insight into the definition of the term systolic, and into the classification of systolic array algorithms on their communication pattern and dataflow properties.