TR#:  CS0812 
Class:  CS 
Title:  DUAL BOUND RETIMING. 
Authors:  O. Lempel and A. Litman 
Not Available  
Abstract: 
Let G be a graph with integral weights on the edges, denoted by w(e), representing a design of a semisystolic 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 semisystolic system by a graph with nonnegative weights on the edges. We show that allowing negative weights simplifies the solutions to some retiming problems.

Copyright  The 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 (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1994/CS/CS0812), rather than to the URL of the PDF or PS 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