利用公共子序列求解固定边框布图问题  

Fixed-Outline Floorplanning Based on Common Sub-sequence

作　　者：刘荣[1] 董社勤[1] 洪先龙[1] 

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

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

基　　金：国家自然科学基金(60473126);国家"八六三"高技术研究发展计划(2004AA1Z1050)

摘　　要：提出一种新的固定边框的布图算法.该算法采用SP表示方法,以公共子序列为基础,在随机搜索过程中限定布图宽度的变化,从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致.与现有的固定边框布图算法相比,文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间.此外,文中算法在布图初始阶段就可以对固定边框的合理性进行评估,避免了因给定的边框不合理而带来的时间上的浪费.A simple but efficient algorithm addressed for fixed-outline floorplanning is presented in this paper. The proposed algorithm takes sequence pair as representation. It first selects certain modules which have a total width little less than or equal to the width of the given outline, and then transforms these modules into common sub-sequences of sequence pairs. During the process of simulated annealing, the proposed algorithm uses these common sub-sequences to limit the widths of the floorplans while minimizing the areas. Experimental results on MCNC benchmarks show that the proposed algorithm can achieve a highly successful probability, even when tight outlines and large aspect ratios are given. Furthermore, the proposed algorithm takes less time than other fixed-outline floorplanning algorithm, and the feasibility of the given outline will he evaluated at the beginning of floorplanning.

关 键 词：布图规划 固定边框 序列对 公共子序列 

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