电压岛驱动的多级布图规划优化算法

doi:10.3969/j.issn.1001-2400.2015.06.031

J4 ›› 2015, Vol. 42 ›› Issue (6): 184-190.doi: 10.3969/j.issn.1001-2400.2015.06.031

• 研究论文 • 上一篇

电压岛驱动的多级布图规划优化算法

杜世民1,2;夏银水1;储著飞1;杨润萍2

(1. 宁波大学信息科学与工程学院，浙江宁波 315211;
2. 宁波大学科学技术学院，浙江宁波 315212)

收稿日期:2015-03-17 出版日期:2015-12-20 发布日期:2016-01-25
通讯作者: 杜世民
作者简介:杜世民(1976-), 男, 讲师, 宁波大学博士研究生, E-mail: dushimin@nbu.edu.cn．
基金资助:
国家自然科学基金重点资助项目(61131001)；“十二五”浙江省高校重点学科-计算机应用技术资助项目(20121114)；宁波市自然科学基金资助项目(2013A610003)；浙江省教育厅科研资助项目(Y201016754)

Voltage island-driven multilevel floorplanning optimization algorithm

DU Shimin1,2;XIA Yinshui1;CHU Zhufei1;YANG Runping2

(1. Department of Information Science and Engineering, Ningbo Univ., Ningbo 315211, China;
2. College of Science ＆ Technology, Ningbo Univ., Ningbo 315212, China)

Received:2015-03-17 Online:2015-12-20 Published:2016-01-25
Contact: DU Shimin

摘要/Abstract

摘要：

针对多电压布图算法速度较慢、空白面积较高这一问题，提出了一种电压岛驱动的多级布图规划优化方法．首先，以功耗为优化目标，应用线性整数规划分配模块电压，将相同电压的模块划分至同一电压岛; 其次，提出一种基于枚举和形状曲线相加的快速方法对所得各电压岛进行布图;最后，构建一个线性规划模型来求解通过交换布图解中模块位置来减少线长的问题，对线长做进一步优化．实验结果表明，和已有方法相比，该方法在算法速度和芯片空白面积率方面有较明显优势．

关键词: 低功耗, 布图规划, 多电压, 电压岛, 多级优化

Abstract:

Since the existing multiple voltage floorplanning algorithms are slower and generate a higher white space, a voltage island-driven multilevel floorplanning optimization algorithm is proposed. Firstly, an ILP(Integer Linear Programming)-based approach is used to assign the voltage to each module aiming at minimizing power consumption, and all modules are divided into different voltage islands according to their voltage assignment results. Secondly, a rapid method based on enumeration and shape curve adding techniques is proposed to determine the shape and position of each voltage island. Finally, an LP(Linear Programming) model is constructed to solve the wirelength optimization problem by exchanging blocks' positions. Experimental results show that our algorithm outperforms previous methods in runtime and chip area usage ratio.

Key words: lower power, floorplanning, multiple supply voltage, voltage islands, multilevel optimization

中图分类号:

TP391

杜世民;夏银水;储著飞;杨润萍. 电压岛驱动的多级布图规划优化算法[J]. J4, 2015, 42(6): 184-190.

DU Shimin;XIA Yinshui;CHU Zhufei;YANG Runping. Voltage island-driven multilevel floorplanning optimization algorithm[J]. J4, 2015, 42(6): 184-190.

参考文献

［1］ Lee W P, Liu H Y, Chang Y W. Voltage-Island Partitioning and Floorplanning under Timing Constraints ［J］. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2009, 28(5): 690-702.
［2］ Chu Z F, Xia Y S, Wang L Y, et al. Efficient Nonrectangular Shaped Voltage Island Aware Floorplanning with Nonrandomized Searching Engine ［J］. Microelectronics Journal, 2014, 45(4): 382-393.
［3］孙强, 孙兴奇, 马光胜. 一种高层次多电压功耗优化方法［J］. 西安电子科技大学学报, 2009, 36(5): 933-939.
Sun Qiang, Sun Xingqi, Ma Guangsheng. High-level Power Optimization Method for Multiple Supply Voltage Using the Multi-objective Genetic Algorithm ［J］. Journal of Xidian University, 2009, 36(5): 933-939.
［4］ Ma Q, Young E F Y. Multivoltage Floorplan Design ［J］. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2010, 29(4): 607-617.
［5］ Lin J M, Hung Z X. SKB-Tree: a Fixed-outline Driven Representation for Modern Floorplanning Problems ［J］. IEEE Transactions on Very Large Scale Integration Systems, 2012, 20(3): 473-484.
［6］ Meng Z, Chen S, Huang L. Irregularly Shaped Voltage Islands Generation with Hazard and Heal Strategy［C］//Proceedings of the International Symposium on Quality Electronic Design. Piscataway: IEEE, 2015: 310-315.
［7］ Lin J M, Wu J H. F-FM: Fixed-outline Floorplanning Methodology for Mixed-size Modules Considering Voltage-island Constraint［J］. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2014, 33(11): 1681-1692.
［8］ Mak W K, Jr Chen W. Voltage Island Generation under Performance Requirement for Soc Designs ［C］//Proceedings of the Asia and South Pacific Design Automation Conference. Piscataway: IEEE Computer Society, 2007: 798-803.
［9］杜世民, 夏银水, 戚利侠. 基于遗传算法的电压岛感知的多电压分配［J］. 浙江大学学报(理学版), 2013, 40(1): 56-61, 66.
Du Shimin, Xia Yinshui, Qi Lixia. Voltage Island-aware Multiple Voltage Assignment Based on Genetic Algorithm ［J］. Journal of Zhejiang University (Science Edition), 2013, 40(1): 56-61, 66.
［10］ Wang K, Dong S Q. Post-floorplanning Power Optimization for MSV-driven Application Specific NoC Design ［C］//Proceedings of the IEEE International Symposium on Circuits and Systems. Piscataway: IEEE, 2014: 994-997.
［11］ Chen T C, Chang Y W. 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.
［12］杜世民, 夏银水, 储著飞, 等. 面向软模块的稳定固定边框布图规划算法［J］. 电子与信息学报, 2014, 36(5): 1258-1265.
Du Shimin, Xia Yinshui, Chu Zhufei, et al. A Stable Fixed-outline Floorplanning Algorithm for Soft Module ［J］. Journal of Electronics ＆ Information Technology, 2014, 36(5): 1258-1265.
［13］ Senguptaa D, Veneris A, Wilton S, et al. Multi-objective Voltage Island Floorplanning Using Sequence Pair Representation［J］. Sustainable Computing: Informatics and Systems, 2012(2): 58-72.
［14］ Yan J Z, Chu C. 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］. ［2014-12-22］. http://www.edgestone-it.com/gurobi.htm, 2013.

[1]	陈迪平, 应韬, 董刚. 一种适用于移动芯片的低功耗低温漂LDO电路[J]. 西安电子科技大学学报, 2018, 45(6): 57-62.
[2]	陈珍海, 魏敬和, 于宗光, 苏小波, 薛颜, 张鸿. 高精度电荷域ADC共模电荷误差前台校准电路[J]. 西安电子科技大学学报, 2018, 45(6): 137-143+149.
[3]	蔡江铮;黑勇;袁甲;陈黎明. 近阈值非预充静态随机存储器[J]. 西安电子科技大学学报, 2018, 45(1): 106-111.
[4]	李娅妮;孙亚东;王旭. 一种低失调高PSRR的带隙基准电路[J]. 西安电子科技大学学报, 2017, 44(5): 92-96.
[5]	孟凡振;刘宏;汪明亮;林水样;田彤. 用于物联网的带滤波CMOS低功耗欠采样器设计[J]. 西安电子科技大学学报, 2017, 44(3): 108-113.
[6]	孟凡振;刘宏;汪明亮;林水样;田彤. 用于物联网通信的低功耗唤醒接收机设计[J]. 西安电子科技大学学报, 2017, 44(2): 95-100.
[7]	唐伟童;汪鹏君;王谦. 一种CNFET的多位三值比较器设计[J]. J4, 2016, 43(1): 139-143+156.
[8]	张艺蒙;张玉明;张义门. 传感器网络应用的低功耗实时计数器[J]. J4, 2015, 42(6): 66-69+112.
[9]	臧明相;王勐;周文宏;陈会仓. 改进混合蛙跳优化的片上网络低功耗映射算法[J]. J4, 2015, 42(1): 118-123.
[10]	臧明相;王婷;周文宏. 类电磁优化的片上网络低功耗映射算法[J]. J4, 2014, 41(4): 82-86+93.
[11]	张丽;庄奕琪;赵巍胜;汤华莲. 一种适用于自旋磁随机存储器的低压写入电路[J]. J4, 2014, 41(3): 131-137.
[12]	刘毅;陈博;杨银堂;刘刚. 一种高速低功耗的NoC时钟网络设计[J]. J4, 2013, 40(3): 115-120.
[13]	杜永乾;庄奕琪;李小明;景鑫;戴力. 一种新型无源UHF RFID带隙基准电路[J]. J4, 2013, 40(2): 148-152+200.
[14]	袁博;汪斌强;王志明. 并行多流水绿色路由查找架构和算法[J]. J4, 2012, 39(2): 145-152+167.
[15]	唐龙飞;庄奕琪;刘伟峰;靳钊. 用于UHF RFID标签的低功耗BLF产生电路[J]. J4, 2011, 38(5): 152-158+164.

电压岛驱动的多级布图规划优化算法

Voltage island-driven multilevel floorplanning optimization algorithm

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0