基于图论模型的一类集成电路布线算法  

Graph theoretic approach for routing problem in VLSI

作　　者：耿显亚[1] 许峰[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001

出　　处：《计算机工程与应用》2015年第1期21-25,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11401008);安徽省教育厅自然科学基金重点项目(No.KJ2014A064);安徽理工大学硕博基金(No.11167)

摘　　要：针对具有曼哈顿模型的一类通道布线,提出了一个依据图论模型的最优轨道高度布线算法。算法根据通道上结点的水平约束图和垂直约束图,依次安排好每一个结点的布线轨道,进而通过通孔可以把所有的结点在2层轨道上布线完成。通过计算分析,该算法相对以前的算法能够达到更优的布线高度,并且其复杂性保持不变。For a channel in 2-layer Manhattan model, this paper aims at interconnecting the terminals of each net by wires such that the circuit elements and the interconnecting wires are embedded into two planar layers by the methods of graph theory. Furthermore, the width（number of tracks required for routing） of a channel should be minimized. The constraints of a channel routing problem can be represented by a Horizontal Constraint Graph（HCG） and a Vertical Constraint Graph （VCG）. Considering the two constraints, the paper improves the upper bound, it shows that this algorithm is better than the best known algorithm.

关 键 词：有向图 通道布线 最短路径 

分 类 号：O157[理学—数学]