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

Fast Module Packing Algorithm Using Corner Contour Based on O-Tree Representation

作　　者：李康[1] 虞厥邦[1] 于永斌[1] 

机构地区：[1]电子科技大学电子工程学院570教研室

出　　处：《计算机辅助设计与图形学学报》2008年第10期1297-1302,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家“八六三”高技术研究发展计划(2006AA01Z173,2007AA01Z131)

摘　　要：在VLSI物理设计中,O-Tree是一种高效简洁的布局表示法,但其对应的模块放置算法因为基于水平和垂直约束图及其操作而复杂且费时(算法时间复杂度为O(n2)).文中算法利用模块放置过程中右上端边沿形成的角轮廓结构的阶梯下降性,结合O-Tree编码结点间的父子关系,快速确定模块的放置位置.在模块的放置过程中不需要约束图,只保持一个角轮廓,使模块的放置更加简单高效,算法时间复杂度降低为O(nlogn).在MCNC Benchmark上的实验结果验证了该算法的有效性.In VLSI physical design, O-Tree is regarded as one of the most effective and efficient placement/floorplan representations. However, its induced packing algorithms are complicated and time-consuming, because of their horizontal and vertical constraint graphs and involved operations. Based on stairway up-down characteristic of corner-contour, the proposed algorithm in this paper utilizes parent-son relationship embodied in a given O-Tree code to facilitate module placement. There is only one corner-contour being kept during packing, no constraint graphs and related operations are required. The time complexity of the proposed algorithm can be reduced to O（n log n）. Experimental results on MCNC Benchmarks verified the effectiveness of the our algorithm.

关 键 词：VLSI物理设计 布局 O-Tree表示法 角轮廓 放置算法 

分 类 号：TP391.7[自动化与计算机技术—计算机应用技术]