Concurrent flip-flop and buffer insertion with adaptive blockage avoidance

ABSTRACT

Given a routing tree for a multi-pin net, two algorithms extending the van Ginneken algorithm [3] for concurrent flip-flop and buffer insertion were presented in [5]. One algorithm called MiLa targets at minimizing the latency, and the other algorithm called GiLa aims to find a feasible solution subject to given latency constraints imposed on sinks. However, they both do not consider the case where buffer/flip-flop blockages are present. In this paper, we enhance the MiLa algorithm and GiLa algorithm to consider blockage avoidance by finding alternative registered-buffered paths between each internal node inside a blockage and its parent node. The experimental results show that in comparison to the MiLa algorithm, our approach is able to find a solution with the same latency (for about half of the test cases) or even better latency (for the remaining test cases) and the same wirelength, while the buffer/flip-flop usage and CPU time are comparable or acceptable. In comparison to the GiLa algorithm, our approach is able to find a feasible solution for each test case while the Gila algorithm fails to do so for several test cases.

REFERENCES

• 1: L. Lev, and P. Chao, "Down to the wire: requirements for nanometer design implementation," Cadence White Paper.
• 2: J. Cong, "Challenges and opportunities for design innovations in nanometer technologies," SRC Design Sciences Concept Paper, 1997.
• 3: L. P. P P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal Elmore delay," Proc. IEEE International Symposium on Circuits and Systems, pp. 865--868, 1990.
• 4: Hai Zhou , D. F. Wong , I-Min Liu , Adnan Aziz, Simultaneous routing and buffer insertion with restrictions on buffer locations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.96-99, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309885]
• 5: Pasquale Cocchini, Concurrent flip-flop and repeater insertion for high performance integrated circuits, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.268-273, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774612]
• 6: Soha Hassoun , Charles J. Alpert , Meera Thiagarajan, Optimal buffered routing path constructions for single and multiple clock domain systems, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.247-253, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774609]