Technical Report CS0812

Authors: O. Lempel and A. Litman
PDFNot Available

Let G be a graph with integral weights on the edges, denoted by w(e), representing a design of a semi-systolic circuit, and let \underline{w}(e) and \overline{w}(e) denote lower and upper bounds on the weight of each edge, respectively, representing constraints on the design. We solve the problem of finding a retiming G' of G such that for every edge e, \underline{w}(e) \leq w'(e) \leq \overline{w}(e), where w'(e) are the weights in G'. In addition, we present and solve two problems for optimizing circuits subject to dual bound constraints. We show that applying the retiming algorithm of Leiserson and Saxe on a graph G=(V,E,W), could yield a graph G' which has edges with weights proportional to |V|. This outcome of the retiming algorithm is possible even when there exists a different retiming of G in which all weights are bound by some constant. We apply dual bound constraints on the retiming to overcome this inherent property of the retiming algorithm, increasing the complexity by only a logarithmic factor. It is common practice to model a semi-systolic system by a graph with nonnegative weights on the edges. We show that allowing negative weights simplifies the solutions to some retiming problems.

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 1994
To the main CS technical reports page

Computer science department, Technion