数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  重点论文 |  在线办公 | 
数值计算与计算机应用  2018, Vol. 39 Issue (4): 265-273    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
基于整数线性规划的后布图线长优化方法
张凯, 杜世民, 杨润萍
宁波大学科学技术学院, 宁波 315212
A POST-FLOORPLANNING WIRE LENGTH OPTIMIZATION ALGORITHM BASED ON INTEGER LINEAR PROGRAMMING
Zhang Kai, Du Shimin, Yang Runping
College of Science & Technology, Ningbo University, Ningbo 315212, China
 全文: PDF (489 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 针对可切分布图,提出了一种同时考虑模块交换、模块翻转和空白面积再分配减少线长的新方法.对给定布图相应的切分树,引入一组二进制变量来表示切分树中每个运算符下的两个子树是否发生交换,然后对切分树进行遍历,将所有模块位置表示为这些二进制变量的线性函数.在此基础上,将模块翻转和空白面积再分配考虑进来,将这一问题构建为一个整数线性规划模型.实验结果表明,所提出方法较已有文献可以获得更大的线长改进,这为布图之后进一步提高布图质量提供了一种有效的方法.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词布图规划   线长优化   模块交换   模块翻转   空白面积再分配   整数线性规划     
Abstract: 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.
Key wordsfloorplanning   wirelength optimization   block swapping   block flipping   white space redistribution   Integer Linear Programming (ILP)   
收稿日期: 2018-01-23;
基金资助:

国家自然科学基金(No.61501268);浙江省自然科学基金(No.LY15F030008);宁波大学大学生科技创新(SRIP)项目(No.2016046).

通讯作者: 杜世民     E-mail: dushimin@nbu.edu.cn
引用本文:   
. 基于整数线性规划的后布图线长优化方法[J]. 数值计算与计算机应用, 2018, 39(4): 265-273.
. A POST-FLOORPLANNING WIRE LENGTH OPTIMIZATION ALGORITHM BASED ON INTEGER LINEAR PROGRAMMING[J]. Journal on Numerical Methods and Computer Applicat, 2018, 39(4): 265-273.
 
[1] Chen Guolong, Guo Wenzhong, Chen Yuzhong. A PSO-Based Intelligent Decision Algorithm for VLSI Floorplanning[J]. Soft Computing, 2010, 14(12):1329-1337.
[2] Anand S, Saravanasankar S, Subbaraj P. A Multiobjective Optimization Tool for Very Large Scale Integrated Non-slicing Floorplanning[J]. International Journal of Circuit Theory and Applications, 2013, 41(9):904-923.
[3] Adya S N, Markov I. L Fixed-outline foorplanning:enabling hierarchical design[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2003, 11(6):1120-1135.
[4] 徐宁. 超大规模集成电路物理设计理论与算法[M]. 北京:清华大学出版社, 2009.
[5] Chen Tung-Chieh, Chang Yao-Wen. Modern Floorplanning Based on B*-Tree and Fast Simulated Annealing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(4):637-650.
[6] 杜世民, 夏银水, 储著飞等. 面向软模块的稳定固定边框布图规划算法[J]. 电子与信息学报, 2014, 36(5):1258-1265.
[7] Sivaranjani P, Senthil Kumar A. Thermal-Aware Non-slicing VLSI Floorplanning Using a Smart Decision-Making PSO-GA Based Hybrid Algorithm[J]. Circuits, Systems, and Signal Processing, 2015, 34(11):3521-3542.
[8] Hao X, Brewer F. Wirelength optimization by optimal block orientation[C]. IEEE/ACM International Conference on Computer-Aided Design, IEEE, 6-10 Nov, 2005:64-70.
[9] Tang X P, Tian R Q, Wong M D F. Optimal redistribution of white space for wire length minimization[C]. Proceedings of ASP-ACM/IEEE Design Automation Conference, IEEE 18-21 Jan, 2005, 1:412-417.
[10] Chiu-WingSham, EvangelineF.Y.Young. Block flipping and white space distribution for wirelength minimization[J]. INTEGRATION, the VLSI journal, 2009, 42(2):246-253.
[11] He Xu, Dong Sheqin. Pin assignment for wire length minimization after floorplanning phase[C]. IEEE 8th International Conference on ASIC, Changsha, China. IEEE, 20-23 Oct, 2009, 1294-1297.
[12] Dipanjan Senguptaa, Andreas Veneris, Steve Wilton, et al. Multi-Objective Voltage Island Floorplanning Using Sequence Pair Representation[J]. Sustainable Computing:Informatics and Systems, 2012, 12(2):58-72.
[13] Wong D F, Liu C L. A New Algorithm for Floorplan Design[C]//Proceedings of the 23rd ACM/IEEE Design Automation Conference. Las Vegas, IEEE Computer Society Press, 1986, 101-107.
[14] Jackey Z. Yan, Chris Chu. Defer:deferred decision making enabled fixed-outline floorplanning algorithm[J]. IEEE Transactions on Computer-aided design of integrated circuits and systems, 2010, 29(3):367-381.
[15] Gurobi Optimization.Gurobi5.62[CP/OL]. (2013)[2015-03-01]. http://www.edgestone-it.com/gurobi.htm.
没有找到本文相关文献
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10