用角轮廓结构实现基于O-Tree表示法的模块快速放置算法

在VLSI物理设计中,O-Tree是一种高效简洁的布局表示法,但其对应的模块放置算法因为基于水平和垂直约束图及其操作而复杂且费时(算法时间复杂度为O(n2)).文中算法利用模块放置过程中右上端边沿形成的角轮廓结构的阶梯下降性,结合O-Tree编码结点间的父子关系,快速确定模块的放置位置.在模块的放置过程中不需要约束图,只保持一个角轮廓,使模块的放置更加简单高效,算法时间复杂度降低为O(nlogn).在MCNC Benchmark上的实验结果验证了该算法的有效性.

基于O-TREE树表示的总线约束在VLSI/PCB布局中的应用(英文)

布局是VLSI物理设计的关键环节,采用了O TREE的编码表示方法来解决在超大规模集成电路布局中,具有预定义坐标结群约束模块的布局问题(简称PCA问题)。目前,存在一些成功的算法来解决PCA问题,然而,它们的算法有些复杂,有些耗时。由此提出了一种新的布局算法来解决这个问题,该算法是基于O TREE结构,旨在减少总的运行时间且简便。通过对MCNC的标准例子ami33和ami49上仿真实验表明:与参考文献5提到的结果相比,新算法是可行的并且很有效。它不仅使芯片面积利用率得到改善,而且节约了一半以上的时间开销。