论文部分内容阅读
两层通道布线问题在超大规模集成电路自动布图设计中是关键步骤之一。虽然现在已经有一些通道布线的有效算法,但通常的这些算法不适用于垂直约束图存在闭环的情况。本文提出的算法以垂直约束图的合并算法为基础,但进一步可以处理有环形约束的问题。此算法包括五个子算法,按次序试用这些子算法去解决闭环,直至将其解决。由于第五个子算法利用通道左端或右端的附加垂直走线道,故可以保证一定能使闭环得以解决。本算法已经用PASCAL语言编出程序并在美国伯克利加州大学电气工程与计算机科学系的VAX11/780计算机上运行,得到相当好的结果。
The problem of two-layer channel routing is one of the key steps in VLSI design. Although there are some efficient algorithms for channel routing nowadays, most of these algorithms are not suitable for the closed-loop case of a vertical constraint graph. The algorithm proposed in this paper is based on the merge algorithm of vertical constraint graphs, but it can further deal with the problem of circular constraints. The algorithm consists of five sub-algorithms, which try these sub-algorithms in order to solve the closed-loop until it is resolved. Since the fifth sub-algorithm makes use of the additional vertical alignment of the left or right end of the channel, it is guaranteed that the closed loop will be resolved. The algorithm has been compiled in the PASCAL language and run on the VAX11 / 780 computer in the Department of Electrical Engineering and Computer Science at the University of California, Berkley, and yields quite good results.