Tradeoff routing resource, runtime and quality in buffered routing

ABSTRACT

With the wide use of hard macros and IP blocks in design, buffered routing (simultaneous routing and buffer insertion) becomes inavoidable. Routing resource allocation and distribution are serious concerns in buffered routing of deep submicron design. The capability of capturing the tradeoff between routing resource cost and signal delay is crucial in practice since the resource overuse of min-delay solution may cause congestion problem (congestion also means over-inserting buffers). However, many existing algorithms are mainly designed to minimize signal delay. In the paper, we first study the problem of minimizing the linear combination of delay and cost, and extend the graph-based algorithm in [10] to solve it. We then show that a variant of the algorithm can solve other problems such as maximizing delay reduction to cost ratio, minimizing routing cost subject to a delay constraint, and minimizing delay subject to the cost not exceeding a given budget. We also develop a hierarchical approach to buffered routing construction for problems with large number of sinks to tradeoff solution quality and runtime.

REFERENCES

• 1: C. J. Alpert , Miloš Hrkić , J. Hu , A. B. Kahng , J. Lillis , B. Liu , S. T. Quay , S. S. Sapatnekar , A. J. Sullivan , P. Villarrubia, Buffered Steiner trees for difficult instances, Proceedings of the 2001 international symposium on Physical design, p.4-9, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369699]
• 2: Miloš Hrkić , John Lillis, S-Tree: a technique for buffered routing tree synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514066]
• 3: Jason Cong , Xin Yuan, Routing tree construction under fixed buffer locations, Proceedings of the 37th conference on Design automation, p.379-384, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337502]
• 4: Ashok Jagannathan , Sung-Woo Hur , John Lillis, A fast algorithm for context-aware buffer insertion, Proceedings of the 37th conference on Design automation, p.368-373, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337496]
• 5: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 6: Minghorng Lai , D. F. Wong, Maze routing with buffer insertion and wiresizing, Proceedings of the 37th conference on Design automation, p.374-378, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337500]
• 7: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
• 8: Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
• 9: Amir H. Salek , Jinan Lou , Massoud Pedram, A simultaneous routing tree construction and fanout optimization algorithm, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.625-630, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289098]
• 10: Xiaoping Tang , Ruiqi Tian , Hua Xiang , D. F. Wong, A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 11: Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1997.
• 12: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal Elmore delay", ISCAS-90, pp. 865--868, 1990.
• 13: 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]