An efficient algorithm for buffered routing tree construction under fixed buffer locations with accurate delay models

Author

Zhang, Yiqian ; Hong, Xianlong ; Cai, Yici

Author_Institution

Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing, China

fYear

2005

fDate

23-26 May 2005

Firstpage

97

Abstract

This paper studies the problem of buffered routing tree construction under fixed buffer locations with accurate delay models. In our approach, we firstly construct a timing-driven and buffer-aware Steiner tree, based on which each furcation buffer is searched in a bounding box. Then, a buffered routing tree is constructed by a dynamic programming method from the bottom up. The experimental results show that our algorithm performs well.

Keywords

buffer circuits; circuit optimisation; dynamic programming; integrated circuit interconnections; integrated circuit layout; trees (mathematics); buffer insertion; buffer-aware Steiner tree; buffered routing tree construction; dynamic programming; fixed buffer locations; furcation buffers; interconnect delay models; interconnect optimization techniques; timing-driven Steiner tree; Circuit topology; Delay effects; Delay estimation; Dynamic programming; Heuristic algorithms; Integrated circuit interconnections; Propagation delay; Routing; Space technology; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on

Print_ISBN

0-7803-8834-8

Type

conf

DOI

10.1109/ISCAS.2005.1464533

Filename

1464533