RETIMING REVISITED AND REVERSED

Retiming is a very promising transformation of circuits which preserve s functionality and improves performance, Its benefits are especially promising in automatic synthesis of circuits from higher-level descrip tions. However, retiming has not been widely included in current desig n tools and methodologies, One of the main obstacles is the problem of finding an equivalent initial state for the retimed circuit. In this paper, we introduce a simple modification of the retiming algorithm of Leiserson and Saxe, The modified algorithm helps minimize the effort required to find equivalent initial states and reduces the chance that the network needs to be modified in order to find an equivalent initi al state, This algorithm is the kernel of a new efficient retiming met hod, which searches for optimal retimings while preserving the initial state condition. The paper also presents an improved method to perfor m the initial state calculation.