A EFFICIENT TWO-LAYER ROUTER BASED ON UNCONSTRAINED VIA MINIMIZATION-FOREST
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [9]
  • |
  • Related [20]
  • |
  • Cited by [1]
  • | |
  • Comments
    Abstract:

    FOREST is a new double-layer channel router based on Unconstrained Via Minimization. It partitions the routing procedure into two parts: Topological routing and Physical routing. As a heuristic algorithm, it tries to consider the routing completion rate, area, vias and wire length as a whole. It allows horizontal segments and vertical segments to route on one layer and allows over lapping of segments on different layers. FOREST is useful for general channels, especially for irregular channels. Some examples show that it is efficent,especially in reducing vias.

    Reference
    [1] Hsu,c.-P.,“Mininm-Via Topological,Routing”,IEEE Traits.on CAD,Oct.1983.
    [2] Malgorzata,M.-S,,“An Unconstrained Topological Via Minimization Problem for Two Layer Routing",1EEE Trans.on CAD.July 1984.
    [3] Chang,K.C.and Du,D.H—C.,“Efficient Algorithins for Layer Assignment Problem”,IEEE Trans.on CAD,Jan.1987.
    [4] x.-M.,Xiong,“A New Algorithm for Topological Routing and Via Minimization”,IC-CAD88.
    [5] 应昌胜,洪先龙.王尔乾,“一个基于整体优化分析的区域布线算法-DRAFT”,半导体学报, 1988,11.
    [6] Y.K.Chen attd M.L.Liu,“Double-Layer Channel Routing with Irregulex Boundaxes”,Memorandum No.M81 79.Electronics Research Lab.,UC Berkeley,Oct.1981.
    [7] Charles H.Ng,“An Industrial World Channel Router for Nonp-Rectahgular Channels”,23th Design Automation Conf.,490-494.1986.
    [8] T:Yoshimura and E.S.Kuh,“Efficient Algorithms for Channel Routing”,IEEE Trans.on CAD,Jan.1982.
    [9] Rostam Jorbbani,Daniel P.Siewiorek,“WEAVER:A Knowledge-Based Routing Expert”,The 22th DAC,266-272. [lO] R.L.Rivest and C.M.Fiduceia“A Greedy Channel Router”,The t9th DAc,418-424. [11] D.Deutsch,“A Dogleg Channel Router”,Proc.13th DAC,425-433. [12] M.Burstein and R.Pelavin,“Hierarchieal Wire Routing”,IEEE Trans.on CAD,Vol.CAD-2,No.4,1983. [13] A.Hashimoto and J.Stevens,“Wire Routing by Optimizing Channel Assignfiaent Within Large Apertures”Proc.8th D.A.Workshop,1971,155—159. [14] James Reed,Alber to Sangioanni-Vncentelli and Mauro Santomauro,“A New Symbolic Channel Router:.Yacr2”IEEE Trans.on CAD,July 1985.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

何江安,洪先龙.一个基于无约束通孔优化的双层布线算法—FOREST.软件学报,1992,3(1):8-16

Copy
Share
Article Metrics
  • Abstract:3480
  • PDF: 4610
  • HTML: 0
  • Cited by: 0
History
  • Received:August 02,1989
  • Revised:May 16,1990
You are the first2032746Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063