Efficient timing-driven incremental routing for VLSI circuits using DFS and localized slack-satisfaction computations

被引:0
作者
Dutt, Shantanu [1 ]
Arslan, Hasan [1 ]
机构
[1] Univ Illinois, Dept ECE, Chicago, IL USA
来源
2006 DESIGN AUTOMATION AND TEST IN EUROPE, VOLS 1-3, PROCEEDINGS | 2006年
关键词
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In current very deep submicron (VDSM) circuits, incremental routing is crucial to incorporating engineering change orders (ECOs) late in the design cycle. In this paper, we address the important incremental routing objective of satisfying timing constraints in high-speed designs while minimizing wirelength, vias and routing layers. We develop an effective timing-driven (TD) incremental routing algorithm TIDE for ASIC circuits that addresses the dual goals of time-efficiency, and slack satisfaction coupled with effective optimizations. There are three main novelties in our approach: (i) a technique for locally determining slack satisfaction of the entire routing tree when either a new pin is added to the tree or an interconnect in it is re-routed-this technique is used in both the global and detailed routing phases; (ii) an interval-intersection and tree-truncation algorithm, used in global routing, for quickly determining a near-minimum-length slack-satisfying interconnection of a pin to a partial routing tree; (iii) a depth-first-search process, used in detailed routing, that allows new nets to bump and re-route existing nets in a controlled manner in order to obtain better optimized designs. Experimental results show that within the constraint of routing all nets in only two metal layers, TIDE succeeds in routing more than 94% of ECO-generated nets, and also that its failure rate is 7 and 6.7 times less than that of the TD versions of previous incremental routers Standard (Std) and Ripup&Reroute (R&R), respectively. It is also able to route nets with very little (3.4%) slack violations, while the other two methods have appreciable slack violations (16-19%). TIDE is about 2 times slower than the simple TD-Std method, but more than 3 times faster than TD-R&R.
引用
收藏
页码:766 / +
页数:2
相关论文
共 11 条
  • [1] [Anonymous], ICCAD
  • [2] A depth-first-search controlled gridless incremental routing algorithm for VLSI circuits
    Arslan, H
    Dutt, S
    [J]. IEEE INTERNATIONAL CONFERENCE ON COMPUTER DESIGN: VLSI IN COMPUTERS & PROCESSORS, PROCEEDINGS, 2004, : 86 - 92
  • [3] NEAR-OPTIMAL CRITICAL SINK ROUTING TREE CONSTRUCTIONS
    BOESE, KD
    KAHNG, AB
    MCCOY, BA
    ROBINS, G
    [J]. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1995, 14 (12) : 1417 - 1436
  • [4] CONG J, 1997, FRONTIERS SEMICONDUC
  • [5] CONG J, 2000, INT S PHYS DES, P84
  • [6] DUTT S, 1999, ICCAD, P173
  • [7] DUTT S, 2002, ACM T DES AUTOMAT EL, P664
  • [8] EMMERT JM, P IEEE INT ASIC C EX
  • [9] HOU H, 1998, ISPD, P205
  • [10] WANG D, 1997, IEEE MCMC, P89