Technical Report CS0766

Authors: S. Even and A. Litman

This paper studies transformations of systems into systolic systems with related functionality. It distinguishes two antithetical transformation methods: one syntactic, the other semantic. The syntactic method considers the topology of the system, but ignores its behavior and the behavior of its combinational units. We introduce two basic syntactic techniques: tiling and bypassing. Based on them, we present syntactic transformations that perform the following: conversion of a semisystolic system into a systolic one; elimination of either broadcast or instant-accumulation from a system that is otherwise systolic; and speeding up a systolic system by any constant factor. Leiserson and Saxe [9] have developed transformations to accomplish the first two tasks, but failed to preserve the behavior of the system. Our transformations leave the behavior of the system intact. The semantic method considers the functionality of the system as a whole, but ignores its internal structure. A system is called \Psi-homogeneous if all its combinational units are identical and equal to the given unit \Psi. We show that every semisystolic system can be transformed into a \Psi-homogeneous systolic system, where \Psi depends only on the alphabet used by the system to communicate with the external world. As a special case, any regular language L \subset \sum^* is defined by some \Psi-homogeneous systolic system, where \Psi depends only on \sum. For binary systems, this technique produces a systolic system with a feasible clock period of O(i+\log(o)), where i and o are the numbers of input and output ports of the system. This clock period is independent of the size and complexity of the given system.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion