• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Lin, Disi (Lin, Disi.) [1] | Chen, Chuandong (Chen, Chuandong.) [2] (Scholars:陈传东) | Wei, Rongshan (Wei, Rongshan.) [3] (Scholars:魏榕山) | Liu, Qinghai (Liu, Qinghai.) [4] (Scholars:刘清海) | He, Huan (He, Huan.) [5] | Zhu, Ziran (Zhu, Ziran.) [6] | Lin, Zhifeng (Lin, Zhifeng.) [7] (Scholars:林智锋) | Chen, Jianli (Chen, Jianli.) [8]

Indexed by:

EI Scopus SCIE

Abstract:

The Ordered Escape Routing (OER) problem, which is an NP-hard problem, is critical to PCB design. Primary methods based on integer linear programming (ILP) work well on small-scale PCBs with fewer pins. However, when dealing with large-scale instances, traditional ILP strategies frequently cause time violations as the number of variables increases due to time-consuming preprocessing. In addition, heuristic algorithms have a time advantage when dealing with specific problems. In this paper, We propose an efficient two-stage escape routing method that employs LP for global routing and uses a heuristic algorithm to deal with the path intersection problem to minimize wiring length and runtime for large-scale PCBs. We first model the OER problem as a min-cost multi-commodity flow problem and use ILP to solve it. Then, we relax the non-crossing constraints and transform the ILP model into an LP model to reduce the runtime. we also construct a crossing graph according to the intersection of routing paths and propose a heuristic algorithm to locate congestion quickly. Finally, we reduce the local area capacity and allow global automatic congestion optimization. Compared with the state-of-the-art work, experimental results show that our method can reduce the routing time by 60% and handle larger-scale PCB escape routing problems.

Keyword:

Heuristic algorithm Linear programming Min-cost multi-commodity flow Ordered escape routing

Community:

  • [ 1 ] [Lin, Disi]Fuzhou Univ, Coll Comp & Data Sci, Fuzhou 350108, Peoples R China
  • [ 2 ] [Chen, Chuandong]Fuzhou Univ, Sch Microelect, Fuzhou 350108, Peoples R China
  • [ 3 ] [Wei, Rongshan]Fuzhou Univ, Sch Microelect, Fuzhou 350108, Peoples R China
  • [ 4 ] [Liu, Qinghai]Fuzhou Univ, Ctr Appl Math Fujian Prov, Fujian Sci & Technol Innovat Lab Optoelect Informa, Fuzhou 350108, Peoples R China
  • [ 5 ] [Liu, Qinghai]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China
  • [ 6 ] [He, Huan]Hangzhou Huawei Enterprises Telecommun Technol Co, Hangzhou 310000, Peoples R China
  • [ 7 ] [Zhu, Ziran]Southeast Univ, Natl ASIC Syst Engn Ctr, Nanjing 210096, Peoples R China
  • [ 8 ] [Lin, Zhifeng]Fuzhou Univ, Ctr Discrete Math & Theoret Comp Sci, Fuzhou 350108, Peoples R China
  • [ 9 ] [Chen, Jianli]Fudan Univ, Sch Microelect, Shanghai 200433, Peoples R China

Reprint 's Address:

  • [Chen, Chuandong]Fuzhou Univ, Sch Microelect, Fuzhou 350108, Peoples R China;;

Show more details

Related Keywords:

Source :

INTEGRATION-THE VLSI JOURNAL

ISSN: 0167-9260

Year: 2025

Volume: 100

2 . 2 0 0

JCR@2023

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:272/9648144
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1