Abstract
Retiming, introduced by Leiserson and Saxe, is a powerful transformation of circuits that preserves functionality and improves performance. The ASTRA algorithm proposed an alternative view of retiming using the equivalence between retiming and clock skew optimization and also presented a fast algorithm for minimum period (minperiod) retiming. Since minperiod retiming may significantly increase the number of flip-flops in the circuit, minimum area (minarea) retiming is an important problem. Minarea retiming is a much harder problem than minperiod retiming, and previous techniques were not capable of handling large circuits in a reasonable time. This work defines the relationship between the Leiserson-Saxe and the ASTRA approaches and utilizes it for efficient minarea retiming of large circuits. The new algorithm, Minaret, uses the same basis as the Leiserson-Saxe approach. The underlying philosophy of the ASTRA approach is incorporated to reduce the number of variables and constraints generated in the problem. This allows minarea retiming of circuits with over 56 000 gates in under 15 min.
Original language | English (US) |
---|---|
Pages (from-to) | 74-83 |
Number of pages | 10 |
Journal | IEEE Transactions on Very Large Scale Integration (VLSI) Systems |
Volume | 6 |
Issue number | 1 |
DOIs | |
State | Published - 1998 |
Bibliographical note
Funding Information:Manuscript received February 11, 1997. This work was supported in part by the National Science Foundation Award MIP-9502556, a Lucent Technologies DAC Graduate Scholarship, and an Iowa State University Computation Center Grant.
Keywords
- Circuit optimization
- Design automation software
- Linear programming
- Logic synthesis
- Sequential logic circuits
- Very large scale integration