直角多边形布图区域内的二次布局算法  

Quadratic-Place Algorithm DPRR for Standard Cell Placement in Rectilinear Region

作　　者：杨长旗[1] 洪先龙[1] 蔡懿慈[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机辅助设计与图形学学报》2005年第7期1407-1414,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(90407005);美国国家自然科学基金(CCR-0096383);国家"八六三"高技术研究发展计划(2005AA1Z1230);高等学校博士学科点专项科研基金(SRFDP-20020003008)

摘　　要：提出了一种直角多边形布图区域内的基于动态划分的二次布局算法———DPRR·通过在传统的二次布局算法中引入一种新的圆盘划分和分布约束生成策略,解决了直角多边形布图区域里的单元布局问题,并且由于该算法在迭代优化过程中动态地划分电路并生成分布约束,且不限制单元在布图区域的不同部分间自由移动,所以它可以在一定程度上避免优化过程中出现的“局部最优”,从而达到更高的布局质量·对一些电路实例的测试和比较结果也证明DPRR是一种高效优良的布局算法,并且它十分适用于解决非矩形的直角多边形布图区域内的标准单元布局问题·In this paper, a aquadratic-place algorithm based on dynamic partition—DPRR is addressed to solve the problem of placement in rectilinear region. It involves new policies of circle-partitioning and distribution-constraints generation into the traditional frame of quadratic-place and solves the problem of placement in rectilinear region properly. And its new approach for generating distribution constraints by dynamic partitioning allows cells moving freely among the sub-regions. Thus, it can result in better placement performance by somewhat avoiding the “local optimum”. Testing on cases proves that DPRR is an efficient algorithm for the standard cell placement in rectilinear region.

关 键 词：直角多边形布图区域 二次布局 动态划分的直角多边形区域布局 动态划分 圆盘划分 

分 类 号：TN47[电子电信—微电子学与固体电子学] TP302[自动化与计算机技术—计算机系统结构]