应用于大规模集成电路非线性布局的二元结群算法  

A Dyadic Cluster Algorithm Used for VLSI Nonlinear Placement

作　　者：高文超[1,2] 周强[2] 钱旭[1] 蔡懿慈[2] 

机构地区：[1]中国矿业大学(北京)机电与信息工程学院,北京100083 [2]清华大学计算机科学与技术系,北京100084

出　　处：《计算机辅助设计与图形学学报》2013年第7期1083-1088,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金项目(61176035)

摘　　要：针对平面模式下非线性布局算法的设计能力远远跟不上集成电路发展速度的现状,将连接紧密的单元结合作为整体参与布局,提出一种应用于大规模非线性布局的二元结群算法,以减小电路规模和复杂度,进而提高布局算法速度、优化布局算法结果质量.该算法按2个单元之间对内连接度与对外连接度的比值排序,并按比值从大到小对单元进行结群,然后更新网表;如果其中一个单元已经被结群或是它们合并后总面积会大于目标结群面积,则放弃这2个单元的组合.将文中算法嵌入之前实现的平面非线性布局器中,可使运行时间相对于平面模式减少40%,布局结果的质量提高了12%.该布局器详细布局后的结果比当前流行的同样采用结群算法的布局器Capo,FastPlace,Fengshui和mPL5-fast算法分别优化了7%,9%,7%和5%,显示了其有效性和高效性.The Design capability of nonlinear layout algorithm in plat mode is far behind the pace of integrated circuit design development, a clustering algorithm used for VLSI （Very-Large-Scale Integration） nonlinear placement is proposed reducing the circuit size and complexity in order to improve the speed and optimize the quality. The new cluster technique takes the ratio of internal and external connection degrees of two cells into account. And, it adds the area constraints to balance every cluster. It has been embodied into a nonlinear placement algorithm. The clustering based placement run-time explicitly decreases by 40% and the quality improves by 12% compared to the flatten mode. The half-perimeter wire-length of the placer after detailed placement outperforms current state-of-the-art placers Capo, FastPlace, Fengshui and mPL5-fast by 7%, 9%, 7%, and 5% respectively.

关 键 词：二元结群 多层结构 非线性布局 大规模集成电路 

分 类 号：TP302.1[自动化与计算机技术—计算机系统结构] TN47[自动化与计算机技术—计算机科学与技术]