基于整数线性规划的后布图线长优化方法

A POST-FLOORPLANNING WIRE LENGTH OPTIMIZATION ALGORITHM BASED ON INTEGER LINEAR PROGRAMMING

针对可切分布图,提出了一种同时考虑模块交换、模块翻转和空白面积再分配减少线长的新方法.对给定布图相应的切分树,引入一组二进制变量来表示切分树中每个运算符下的两个子树是否发生交换,然后对切分树进行遍历,将所有模块位置表示为这些二进制变量的线性函数.在此基础上,将模块翻转和空白面积再分配考虑进来,将这一问题构建为一个整数线性规划模型.实验结果表明,所提出方法较已有文献可以获得更大的线长改进,这为布图之后进一步提高布图质量提供了一种有效的方法.

A post-floorplanning wire length optimization algorithm is proposed for slicing floorplan,which considers block swapping, block flipping and white space redistribution simultaneously.For each operator in the slicing tree corresponding to a given floorplan, a binary variable is introduced to decide whether its two children are swapped. Then, we traverse the slicing tree and represent the positions of each block as linear functions of these binary variables.On the basis of this, we formulate the problem as an Integer Linear Programming(ILP)model which takes block flipping and white space redistribution steps into consideration.Experimental results show that our approach can obtain a better wirelength than previous works. Thus, it provides an effective way to further improve the quality of floorplan.