Topological transformations as a tool in the design of systolic networks

AbstractWe introduce the notion of computational network (CN) which is a general model of an arbitrary (finite or infinite) system of parallel synchronized processors (systolic network). Our basic and very useful tools are topological transformations of the space-time diagrams (unrollings) of computations on CN. We show that the topological transformations on unrollings can be used to design systolic networks, to give simple proofs of their correctness, and to demonstrate the equivalence of different networks. For example, we usedthe transformation technique to give a concise proof of a strengthened version of Leiserson's and Saxe's Retiming lemma and Systolic Conversion Theorem. As a practical application we show the correctness of a simple algorithm for distributed sorting on a systolic ring. Many other examples are given