A NEW ALGORITHM FOR STANDARD CELL GLOBAL ROUTING

被引：6
作者：
CONG, J [1 ]
PREAS, B [1 ]
机构：
[1] XEROX CORP,PALO ALTO RES CTR,PALO ALTO,CA 94304
来源：
INTEGRATION-THE VLSI JOURNAL | 1992年 / 14卷 / 01期
基金：
美国国家科学基金会;
关键词：
GLOBAL ROUTING; STANDARD CELL DESIGN; SPANNING FORESTS;
D O I：
10.1016/0167-9260(92)90010-V
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we present a new algorithm for standard cell global routing. The algorithm considers all of the interconnection nets simultaneously; this produces superior results since information about all of the nets is available throughout the global routing process. We formulate the global routing problem as one of finding the optimal spanning forest on a graph that contains all of the interconnection information. The results of an important theorems allow us to prune many non-optimal connections before the global routing process begins. This approach successfully solves the net ordering and congestion prediction problems which other approaches suffer. The new algorithm was implemented as part of the DATools system at Xerox PARC. The benchmarks from the Physical Design Workshop are used as part of the comparison suite. The new algorithm achieves up to 11% area reduction compared to the previous global routing package used in the DATools system and obtains up to 17% reduction in the total channel density compared to the Timberwolf 4.2 package.
引用
收藏
页码：49 / 65
页数：17
相关论文
共 19 条
  • [11] MOWCHENKO JT, 1987, MAY P IEEE INT S CIR, P27
  • [12] PREAS B, 1986, STANDARD CELL PACKAG
  • [13] PREAS B, 1987, 24TH P DES AUT C, P319
  • [14] Preparata Franco P, 2012, COMPUTATIONAL GEOMET
  • [15] Reingold E. M., 1977, COMBINATORIAL ALGORI
  • [16] ROBERTS KA, 1984, P IEEE INT C COMP AI, P224
  • [17] Rose J., 1988, 25th ACM/IEEE Design Automation Conference. Proceedings 1988 (Cat. No.88CH2540-3), P189, DOI 10.1109/DAC.1988.14757
  • [18] Sechen C., 1986, 23rd ACM/IEEE Design Automation Conference. Proceedings 1986 (Cat. No.86CH2288-9), P432, DOI 10.1145/318013.318083
  • [19] SUPOWIT KJ, 1983, 20TH P DES AUT C
12