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

author:

Huang, Xing (Huang, Xing.) [1] | Liu, Genggeng (Liu, Genggeng.) [2] (Scholars:刘耿耿) | Guo, Wenzhong (Guo, Wenzhong.) [3] (Scholars:郭文忠) | Niu, Yuzhen (Niu, Yuzhen.) [4] (Scholars:牛玉贞) | Chen, Guolong (Chen, Guolong.) [5] (Scholars:陈国龙)

Indexed by:

Scopus SCIE

Abstract:

Obstacle-avoiding Steiner minimal tree (OASMT) construction has become a focus problem in the physical design of modern very large-scale integration (VLSI) chips. In this article, an effective algorithm is presented to construct an OASMT based on X-architecturex for a given set of pins and obstacles. First, a kind of special particle swarm optimization (PSO) algorithm is proposed that successfully combines the classic genetic algorithm (GA), and greatly improves its own search capability. Second, a pretreatment strategy is put forward to deal with obstacles and pins, which can provide a fast information inquiry for the whole algorithm by generating a precomputed lookup table. Third, we present an efficient adjustment method, which enables particles to avoid all the obstacles by introducing some corner points of obstacles. Finally, an excellent refinement method is discussed to further enhance the quality of the final routing tree, which can improve the quality of the solution by 7.93% on average. To our best knowledge, this is the first time to specially solve the single-layer obstacle-avoiding problem in X-architecture. Experimental results show that the proposed algorithm can further shorten wirelength in the presence of obstacles. And it achieves the best solution quality in a reasonable runtime among the existing algorithms.

Keyword:

adjustment Algorithms Design Obstacle avoiding particle swarm optimization (PSO) pretreatment strategy refinement Steiner tree

Community:

  • [ 1 ] [Huang, Xing]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China
  • [ 2 ] [Liu, Genggeng]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China
  • [ 3 ] [Guo, Wenzhong]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China
  • [ 4 ] [Niu, Yuzhen]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China
  • [ 5 ] [Chen, Guolong]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China

Reprint 's Address:

  • 郭文忠

    [Guo, Wenzhong]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

Source :

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS

ISSN: 1084-4309

Year: 2015

Issue: 2

Volume: 20

0 . 8 2

JCR@2015

2 . 2 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:175

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 56

SCOPUS Cited Count: 60

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Online/Total:93/10016568
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