有环形约束的两层通道布线的一种算法

两层通道布线问题在超大规模集成电路自动布图设计中是关键步骤之一。虽然现在已经有一些通道布线的有效算法,但通常的这些算法不适用于垂直约束图存在闭环的情况。本文提出的算法以垂直约束图的合并算法为基础,但进一步可以处理有环形约束的问题。此算法包括五个子算法,按次序试用这些子算法去解决闭环,直至将其解决。由于第五个子算法利用通道左端或右端的附加垂直走线道,故可以保证一定能使闭环得以解决。本算法已经用PASCAL语言编出程序并在美国伯克利加州大学电气工程与计算机科学系的VAX11/780计算机上运行,得到相当好的结果。     

通孔最小化的三层不规则边界通道布线

提出了一种以连通孔和布线区域最小化为目标的三层不规则边界通道布线算法。算法将通道边界的凹陷区域看成固定障碍,利用填充和压缩方法,使线网绕过障碍,实现互连。算法已用PASCAL语言编程,并在XT/286机上实现。结果表明,该算法不仅使通孔数减少,而且由于利用了各凹陷区域之间的面积进行布线,通道宽度也相应减小。     

一种积木块布图的优化二维压缩算法

研究积木块布图的二维压缩问题,提出一种采用分枝定界法的真正的二维压缩算法。该算法以空余空间面积为研究对象,直接以压缩的目的——芯片面积最小化为目标。定义一种压缩树作为分枝定界法的基础。力图将所有的积木块尽可能向芯片的一个角压缩。实验结果表明算法是可行的。     

一种L型通道布线算法

近年来,通道布线问题引起了人们广泛的重视。但至今研究L型通道布线的文章很少。本文提出了一种以减少信号网冲突数为主要目标的L型通道布线算法。该算法从一种总体的考虑出发,把L型通道分解为两个相关的四边通道进行布线,提高了布线成功率。