We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 21 Issue 6
November  2006
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Yi-Ci Cai, Bin Liu, Yan Xiong, Qiang Zhou, Xian-Long Hong. Priority-Based Routing Resource Assignment Considering Crosstalk[J]. Journal of Computer Science and Technology, 2006, 21(6): 913-921.
Citation: Yi-Ci Cai, Bin Liu, Yan Xiong, Qiang Zhou, Xian-Long Hong. Priority-Based Routing Resource Assignment Considering Crosstalk[J]. Journal of Computer Science and Technology, 2006, 21(6): 913-921.
shu

Priority-Based Routing Resource Assignment Considering Crosstalk

  • 1Department of Computer Science, University of Science and Technology of China, Hefei 230027, P.R. China\\1mm2EDA Lab, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China

More Information
  • Received Date: December 24, 2004
  • Revised Date: June 19, 2005
  • Published Date: November 14, 2006
    Abstract
  • Crosstalk has become one of the most critical concerns in verydeep sub-micron era. This paper deals with the problem ofcrosstalk mitigation at both methodological and algorithmiclevels. Noting that intermediate operations between global routingand detailed routing are very effective in crosstalk estimationand reduction, the authors propose to incorporate several intermediatesteps that are separated in traditional design flow into anintegrated routing resource assignment stage, so that theoperations could easily cooperate to fully exert their power oncrosstalk reduction. An efficient priority-basedheuristic algorithm is developed, which works slice by slice. Crosstalkavoidance, and many other aspects that are critical inrouting practice including congestion, vias, layer preference,etc., are taken into account. A track reservation strategy isadopted in the algorithm framework to compensate the undesiredeffects caused by sequential routing. Experimental results on aseries of ISPD98 and industrial benchmarks show that the proposedapproach is able to reduce capacitive crosstalk by about 70\% onaverage without compromising completion ratio compared with apreviously reported graph based algorithm, demonstrating theadvantages of the approach.
    • FullText(HTML)
    • References (27)
  • [1]
    Becer M R, Blaauw D, Panda R \it et al. \rm Early probabilistic noise estimation for capacitively coupled interconnects. -\it IEEE Trans. Computer-Aided Design}, 2003, 22(3): 337--345.
    [2]
    Gao T, Liu C L. Minimum crosstalk channel routing. -\it IEEE Trans. Computer-Aided Design}, 1996, 15(5): 465--474.
    [3]
    Pan S, Chang Y. Crosstalk constrained performance optimization by using wire sizing and perturbation. In -\it Proc. Int. Conf. Computer Design}, Austin, Texas, Sept. 17--20, 2000, pp.581--584.
    [4]
    Lepak K M, Xu M, Chen J, He L. Simultaneous shield insertion and net ordering under explicit RLC noise constraint. -\it ACM Trans. Des. Automat. Elect. Syst.}, 2004, 9(3):290--309.
    [5]
    Gala K, Blaauw D, Zolotov V, Vaidya P M, Joshi A. Inductance model and analysis methodology for high-speed on-chip interconnect. -\it IEEE Trans. VLSI Syst.}, 2002, 10(6): 730--745.
    [6]
    Wu D, Hu J, Maphapatra R, Zhao M. Layer assignment for crosstalk risk minimization. In -\it Proc. Asia and South Pacific Design Automation Conf.}, Yokohama, Japan, Jan. 27--30, 2004, pp.159--162.
    [7]
    Liu B, Cai Y, Zhou Q, Hong X. Layer assignment algorithm for RLC crosstalk minimization. In -\it Proc. Int. Symp. Circuits and Systems}, Vancouver, Canada, May 23--26, 2004, pp.V85--V88.
    [8]
    Tseng H, Scheffer L, Sechen C. Timing and crosstalk driven area routing. -\it IEEE Trans. Computer-Aided Design}, 2001, 20(4): 528--544.
    [9]
    Zhou H, Wang D F. Global routing with crosstalk constraints. -\it IEEE Trans. Computer-Aided Design}, 1999, 18(11): 1683--1688.
    [10]
    Kay R, Rutenbar R A. Wire packing---A strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution. -\it IEEE Trans. Computer-Aided Design}, 2001, 20(5): 672--679.
    [11]
    Batterywala S, Shenoy N, Nicholls W, Zhou H. Track assignment: A desirable intermediate step between global routing and detailed routing. In -\it Proc. Int. Conf. Computer-Aided Design}, San Jose, California, Nov. 10--14, 2002, pp.59--66.
    [12]
    Yao H, Zhou Q, Hong X, Cai Y. Crosstalk aware routing resource assignment. -\it J. Comput. Sci. Technol.}, 2005, 20(2): 231--236.
    [13]
    Xiong J, He L. Full-chip routing optimization with RLC crosstalk budgeting. -\it IEEE Trans. Computer-Aided Design}, 2004, 23(3): 366--377.
    [14]
    Devgan A, Kashyap C. Block-based static timing analysis with uncertainty. In -\it Proc. Int. Conf. Computer-Aided Design}, San Jose, California, Nov. 9--13, 2003, pp.607--614.
    [15]
    Pal R K, Datta A K, Pal S P \it et al. \rm A general graph theoretic framework for multi-layer channel routing. In -\it Proc. 8th Int. Conf. VLSI Design}, Delhi, India, Jan. 4--7, 1995, pp.202--207.
    [16]
    QAPLIB. Available at http://www.opt.math.tu-graz. ac.at/qaplib/.
    [17]
    Shi W, Fang J. Evaluation of closed-form crosstalk models of coupled transmission lines. -\it IEEE Trans. Adv. Packag.}, 1999, 22(2): 174--181.
    [18]
    Nabors K, White J. Fastcap: A multipole accelerated 3D capacitance extraction program. -\it IEEE Trans. Computer-Aided Design}, 1991, 10(11): 1447--1459.
    [19]
    Kamon M, Tsuk M J, White J. Fasthenry: A multipole accelerated 3D inductance extraction program. -\it IEEE Trans. Microwave Theory Tech.}, 1994, 42(9): 1750--1758.
    [20]
    Restle P J, Ruehli A E, Walker S G \it et al. \rm Full-wave PEEC time domain method for the modeling of on-chip interconnects. -\it IEEE Trans. Computer-Aided Design}, 2001, 20(7): 877--886.
    [21]
    http://www.synopsys.com/products/mixedsignal/hspice/hspi\-ce.html. Synopsys Inc.
    [22]
    Hu J, Sapatnekar S S. A survey on multi-net global routing for integrated circuits. -\it Integration, the VLSI Journal}, 2001, 31: 1--49.
    [23]
    Alpert C J. The ISPD98 circuit benchmark suite. In -\it Proc. Int. Symp. Physical Design}, Monterey, California, Apr. 6--8, 1998, pp.85--90.
    [24]
    Su H, Hu J, Sapatnekar S S \it et al. \rm Congestion-driven codesign of power and signal networks. In -\it Proc. Design Automation Conf.}, New Orleans, Louisiana, June 10--14, 2002, pp.64--69.
    [25]
    Saxena P, Gupta S. On integrating power and signal routing for shield count minimization in congested regions. -\it IEEE Trans. Computer-Aided Design}, 2003, 22(4): 437--445.
    [26]
    Hou W, Hong X, Wu W, Cai Y. Fasa: Fast and stable quadratic placement algorithm. -\it J. Comput. Sci. Technol.}, 2003, 18(3): 318--324.
    [27]
    Hong X, Jing T, Xu J, Bao H, Gu J. CNB: A critical-network-based timing optimization method for standard cell global routing. -\it J. Comput. Sci. Technol.}, 2003, 18(6): 732--738.
    • Relative Articles

  • Related Articles

    [1]Kai Liu, Ke-Yan Wang, Yun-Song Li, Cheng-Ke Wu. A Novel VLSI Architecture for Real-Time Line-Based Wavelet Transform Using Lifting Scheme[J]. Journal of Computer Science and Technology, 2007, 22(5): 661-672.
    [2]Li Zhang, Don Xie, Di Wu. Improved FFSBM Algorithm and Its VLSI Architecture for AVS Video Standard[J]. Journal of Computer Science and Technology, 2006, 21(3): 378-382.
    [3]J. M. Gallière, M. Renovell, F. Azais, Y. Bertrand. Delay Testing Viability of Gate Oxide Short Defects[J]. Journal of Computer Science and Technology, 2005, 20(2): 201-209.
    [4]Dian Zhou, Rui-Ming Li. Design and Verification of High-Speed VLSI Physical Design[J]. Journal of Computer Science and Technology, 2005, 20(2): 147-165.
    [5]Hai-Long Yao, Yi-Ci Cai, Qiang Zhou, Xian-Long Hong. Crosstalk-Aware Routing Resource Assignment[J]. Journal of Computer Science and Technology, 2005, 20(2).
    [6]Song Chen, Xian-Long Hong, She-Qin Dong, Yu-Chun Ma, Chung-Kuan Cheng, Jun Gu. Fast Evaluation of Bounded Slice-Line Grid[J]. Journal of Computer Science and Technology, 2004, 19(6).
    [7]LIU Thnpei. Orthogonal Drawings of Graphs for the Automation of VLSI Circuit Design[J]. Journal of Computer Science and Technology, 1999, 14(5): 447-459.
    [8]Chung-Han CHEN. Embedding Binary Tree in VLSI/WSI Processor Array[J]. Journal of Computer Science and Technology, 1996, 11(3): 326-336.
    [9]Chen Qingfang, Wei Daozheng. DLJ:A Dynamic Line-Justification Algorithm for Test Generation[J]. Journal of Computer Science and Technology, 1993, 8(1): 87-91.
    [10]Feng Yulin. Recursive Implementation of VLSI Circuits[J]. Journal of Computer Science and Technology, 1986, 1(2): 72-82.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (23) PDF downloads (1229) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return