一个通道布线问题的图论算法

周晓娜，耿显亚

(安徽理工大学理学院，安徽 淮南 232001)

一个通道布线问题的图论算法

周晓娜，耿显亚

(安徽理工大学理学院，安徽 淮南 232001)

图论的思想方法在大规模集成电路布线中有广泛的应用。通道布线的线网结构可以用水平约束图和垂直约束图来描述，利用图论的思想可以处理布线轨道高度问题。研究运用图论的方法来解决超大规模集成电路布线中的轨道高度问题。通过寻找并消除临界网的方法给出布线的一个新的算法，该算法能够得到轨道高度的一个下界，并对在含有一个狗腿的情况下如何布线进行了描述，并设计出能运用到实际布线工艺中的两层具有曼哈顿模型的通道布线算法。

通道布线；临界网；狗腿

1 通道布线的线网关系

布线的首要目标是百分之百的完成模块间的互连，其次是完成布线的前提下进一步优化布线结果。在70年代，逐步提出了“通道区布线”与“分级布线”的概念。布线方法由面向线网转为面向通道区，从而引出了通道布线，常见的通道布线算法有Hashimoto和Steven提出的左边算法、Yoshimura和Kuh提出的合并算法以及贪婪算法和匹配算法等。根据通道区域的划分，通道布线算法又可以分为单层布线算法、双层布线算法及多层布线算法，其中，对于双层通道区域的研究较为透彻一些。许多通道布线的研究集中在设计能够减少通道面积的高效的启发式方法。这些算法大部分都能对一些有名的布线问题提供最优轨道数的布线解决方法。……