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

摘要

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