|
|||||
|
|
| 给定水平约束图的一类集成电路布线算法 | |
| 引用本文： | 耿显亚,房明磊,刘斌,张晓亮. 给定水平约束图的一类集成电路布线算法[J]. 漳州师院学报, 2014, 0(3): 29-33 |
| 作者姓名： | 耿显亚 房明磊 刘斌 张晓亮 |
| 作者单位： | 安徽理工大学理学院数学系,安徽淮南232001 |
| 基金项目： | 国家自然科学基金（11401008）; 安徽省教育厅自然科学基金重点项目（KJ2014A064）; 安徽理工大学青年教师科学研究基金（2012QNY37,QN201329） |
| 摘 要： | 针对水平约束图为星图的具有曼哈顿模型的通道布线,提出了一个依据图论模型的最优轨道高度布线算法.该算法根据通道上结点的水平约束图和垂直约束图特点,依次安排好每一个结点的布线轨道,进而通过通孔可以把所有的结点在2层轨道上布线完成.通过计算分析,该算法能够达到最优的布线高度. |
| 关 键 词： | 有向图 通道布线 水平约束图 |
An Algorithm for Routing Problem with Given Horizontal Constraint Graph |
|
| GENG Xian-ya,FANG Ming-lei,LIU Bin,ZHANG Xiao-liang. An Algorithm for Routing Problem with Given Horizontal Constraint Graph[J]. Journal of ZhangZhou Teachers College(Philosophy & Social Sciences), 2014, 0(3): 29-33 | |
| Authors: | GENG Xian-ya FANG Ming-lei LIU Bin ZHANG Xiao-liang |
| Affiliation: | (School of Science, Anhui University of Science and Technology, Huainan, Anhui 232001, China) |
| Abstract: | For a channel in 2-layer Manhattan model with horizontal constraint graph be star, we aim 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 （I-ICG） and a vertical constraint graph （VCG）. Consider the two constraints, we improve the upper bound, we show that our algorithm can be obtain the best width. |
| Keywords: | directed graph channel routing horizontal constraint graph |
| 本文献已被 维普 等数据库收录！ | |