A new retiming algorithm for circuit design

Author

Simon, S. ; Bernard, E. ; Sauer, M. ; Nossek, J.A.

Author_Institution

Inst. for Network Theory & Circuit Design, Tech. Univ. Munchen, Germany

Volume

4

fYear

1994

fDate

30 May-2 Jun 1994

Firstpage

35

Abstract

This paper deals with retiming, a register reconfiguration technique, introduced by Leiserson and Saxe (1983 and 1991), to speed up VLSI circuits. Retiming is generally formulated as an optimization problem which is solvable applying linear-programming algorithms. This work presents a different way of considering retiming. A loop analysis, related to network theory, is developed to evaluate all possible retiming solutions. Based on the circuit model used in Leiserson´s paper, the incidence matrix of the circuit is formulated in order to find the linearly independent loops which are needed to represent all register configurations. Finally, the set of all retiming solutions is efficiently reduced to those, which fulfil design and timing constraints and thus, the designer is able to choose an appropriate one for implementation

Keywords

VLSI; circuit CAD; digital integrated circuits; integrated circuit design; timing; CAD; IC design; VLSI circuits; circuit design; incidence matrix; linearly independent loops; loop analysis; register reconfiguration technique; retiming algorithm; Circuit synthesis; Clocks; Costs; Delay; Design automation; Linear programming; Registers; Testing; Timing; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on

Conference_Location

London

Print_ISBN

0-7803-1915-X

Type

conf

DOI

10.1109/ISCAS.1994.409190

Filename

409190