Space-time transformations of parallel microprograms (Q1115577)

We propose a formal transformation of parallel and pipelined computational processes which fits the process in a given space by stretching it in time. We determine the necessary and sufficient conditions that the original microprogram should satisfy in order to ensure equivalence and determinism of the transformation. The application of the proposed transformation is illustrated for three typical examples: a cellular adder, a dynamic processor, and a systolic convolver.