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

作     者：李康 虞厥邦 于永斌 Li Kang;Yu Juebang;Yu Yongbin

作者机构：电子科技大学电子工程学院570教研室 

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：2008年第20卷第10期

页      面：1297-1302页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

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

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