基于图论算法的单元上布线

Pal等提出一个纯粹的图论算法体系TAH（Track Assignment Heuristic），该算法用理想的或接近理想的轨道数解决了许多非常有名的通道布线的例子，其中有两层VH通道布线模型、三层HVH通道布线模型、多层Vi-Hi和ViHi＋1通道布线模型，这种算法推广应用到了两层和三层的单元上布线中，实验结果表明取得了良好的效果。     

一种基于非曼哈顿结构的Over-The-Cell布线算法研究

提出了一种基于非曼哈顿结构的单元上（Over-The-Cell，OTC）布线算法。算法第一次在单元上布线中采用非曼哈顿布线结构，并根据算法特点提出了线网和边相关系数的概念。实践证明，得益于单元区线网选择时对线网和边相关系数的应用，算法和传统标准单元详细布线算法相比，可以进一步降低通道高度和减少通孔数量。     

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

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