Title :
Buffered routing tree construction under buffer placement blockages
Author :
Chen, Wei ; Pedram, Massoud ; Buch, Premal
Author_Institution :
Univ. of Southern California, Los Angeles, CA, USA
Abstract :
Interconnect delay has become a critical factor in determining the performance of integrated circuits. Routing and buffering are powerful approaches to improve circuit speed and correct timing violations after global placement. This paper presents a dynamic-programming based algorithm for performing net topology construction and buffer insertion and sizing simultaneously under the given buffer-placement blockages. The differences from some previous works are that (1) the buffer locations are not pre-determined, (2) the multi-pin nets are easily handled, and (3) a line-search routing algorithm is implemented to speed up the process. Heuristics are used to reduce the problem complexity, which include limiting number of intermediate solutions, using a continuous buffer sizing model, and restricting the buffer locations along the Hanan graph. The resulting algorithm, named BRBP, was applied to a number of industrial designs and achieved an average of 7.9% delay improvement compared to a conventional design flow
Keywords :
buffer circuits; circuit layout CAD; delays; dynamic programming; integrated circuit interconnections; integrated circuit layout; network routing; network topology; timing; trees (mathematics); BRBP; Hanan graph; buffer placement blockages; buffer-placement blockages; buffered routing tree construction; circuit speed; continuous buffer sizing model; delay improvement; dynamic-programming based algorithm; global placement; industrial designs; interconnect delay; line-search routing algorithm; multi-pin nets; net topology construction; problem complexity; timing violations; Algorithm design and analysis; Circuit topology; Delay; Design automation; Dynamic programming; Heuristic algorithms; Integrated circuit interconnections; Routing; Timing; Wire;
Conference_Titel :
Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.
Conference_Location :
Bangalore
Print_ISBN :
0-7695-1441-3
DOI :
10.1109/ASPDAC.2002.994951