Title :
Optimal wire retiming without binary search
Author :
Lin, Chuan ; Zhou, Hai
Author_Institution :
Dept. of Electr. & Comput. Eng., Northwestern Univ., Evanston, IL
Abstract :
The problem of retiming over a netlist of macroblocks to achieve minimal clock period, where block internal structures may not be changed and flip-flops may not be inserted on some wire segments, is called the optimal wire retiming problem. This paper presents a new algorithm that solves the optimal wire retiming problem with polynomial-time worst case complexity. Since the new algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. Experimental results show that the new algorithm is very efficient in practice
Keywords :
circuit complexity; circuit optimisation; flip-flops; logic design; polynomials; system-on-chip; timing; wiring; binary search; circuit modeling; circuit optimization; flip-flops; interconnects; optimal wire retiming problem; optimization techniques; polynomial complexity; wire segments; Circuit optimization; Clocks; Delay; Flip-flops; Frequency; Integrated circuit interconnections; Polynomials; System-on-a-chip; Timing; Wire; Algorithms; circuit modeling; circuit optimization; design methodology; interconnects; pipelining; polynomial complexity; retiming;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2005.858268
