基于图论模型的一类集成电路布线算法-计算机工程与应用
Computer Engineering and Applications 计算机工程与应用 2015 ，51(1) 21
基于图论模型的一类集成电路布线算法
耿显亚，许 峰
GENG Xianya, XU Feng
安徽理工大学 理学院，安徽 淮南 232001
School of Science, Anhui University of Science and Technology, Huainan, Anhui 232001, China
GENG Xianya, XU Feng. Graph theoretic approach for routing problem in VLSI. Computer Engineering and Appli-
cations, 2015, 51 (1)：21-25.
Abstract ：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.
Key words ：directed graph; channel routing; shorting routing path
摘 要：针对具有曼哈顿模型的一类通道布线，提出了一个依据图论模型的最优轨道高度布线算法。算法根据通道
上结点的水平约束图和垂直约束图，依次安排好每一个结点的布线轨道，进而通过通孔可以把所有的结点在2 层轨
道上布线完成。通过计算分析，该算法相对以前的算法能够达到更优的布线高度，并且其复杂性保持不变。
关键词：有向图；通道布线；最短路径
文献标志码：A 中图分类号：O 157 doi ：10.3778/j.issn. 1002-8331.1402-0274
1 引言 足轻重的作用。在集成电路设计的每个环节和整体设
集成电路从20 世纪60 年代开始，到目前为止已经 计中都普遍使用CAD 技术，随着集成度的提高，芯片内
发展到超大规模集成电路。目前我国集成电路的发展 部集成的晶体管数目越来越多，集成电路设计的复杂性
非常迅猛，但是和发达国家的水平相比还是有很大的差 也越来越高，要在几十平方毫米的硅片上完成数百万个
距。一般来说一个国家电子工业的增长速率是国家经 器件的电子系统的设计，只靠人工设计是完全不可能
济增长速率的3 倍，而集成电路的增长速率又可以达到 的，借助计算机辅助设计工具进行电路设计势在必行。
电子工业的2 倍。这样估算，再过几十年我国的集成电 由于芯片及其之间的关系可以用图的结构来表示，这样
路的市场总额将达到世界集成电路市场份额的四分之 图论的思想方法就可以用到超大规模集成电路设计中。
一。因此，集成电路的发展任重而道远，只有把集成电