Studying Of Fast Retiming Algorithm For Clock-Period Optimization

With the growing of the scale of Integrated Circuits and popularizing of its application, it is very necessary to shorten the design period and decrease design complexity. High-Level Synthesis (HLS) systems for digital IC are playing such a role. Beacouse circuitry net list which is synthesized by synthesizer may not achieve the demand of the designer, the sequence circuit which is synthesized must be optimized under require of speed. Retiming is one of the important techniques of optimizing sequence circuit. In retiming registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. By retimng we can optimize the speed, area or power of the circuit.In this paper, we improve FEAS algorithm that exhibits high time complexity to decrease the running time. Then we propose a retiming algorithm by which we can reduce the number of period constraints. This algorithm is bases on that the number of period constraints of a circuit is great larger than that of non-negativity constraints on pracitical circuits. At first, we classify the pathes, and then compute the bounding of the retiming value. At last, the retiming values can be computed by decrease the range of the bounding.In this paper, we have conducted some experiments on the ISCAS89 benchmarks that are in form of EDIF. We compare FEAS algorithm, FEAS plus algorithm and algorithm based on classify paths on running time. Those algorithms are implemented in C language. At last we conclude that our algorithms can achieve retiming transforming quickly.