基于图论模型的两类通道布线算法研究  

Channel Routing Algorithms for Two Types of Channel Routing Based on Graphic Model

作　　者：周晓娜[1] 耿显亚[1] ZHOU Xiao-na GENG Xian-ya(School of Science, Anhui University of Science and Technology, Huainan, Anhui 232001, China)

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

出　　处：《闽南师范大学学报（自然科学版）》2016年第2期13-17,共5页Journal of Minnan Normal University：Natural Science

基　　金：国家自然科学基金(11401008)

摘　　要：通道布线问题是VLSI物理设计中的一个关键问题,本文从结点的两类约束图入手来研究布线算法.对垂直约束图中含有有向圈的一类通道布线问题进行研究,设计出包含一对和两对空结点情况下的布线算法,该方法能够得到更好的轨道高度.Channel routing problem is a key problem in the design of VLSI ships. In this paper, based on two kinds of constraint graph of nodes, two routing algorithms including a pair of and two pairs of empty nodes can be designed to solve the vertical constraint graph problems. The better width can be obtained by using the proposed methods.

关 键 词：垂直约束图 水平约束图 通道布线 有向圈 

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