分区内存体系结构片选指令优化方法

J4 ›› 2016, Vol. 38 ›› Issue (02): 195-201.

• 论文 • 下一篇

分区内存体系结构片选指令优化方法

陈勇1,袁梦霆2,李清安2

（1.中国电子科技集团公司第十四研究所,江苏南京 210039;2.武汉大学计算机学院,湖北武汉 430072）

收稿日期:2015-03-25 修回日期:2015-08-19 出版日期:2016-02-25 发布日期:2016-02-25
基金资助:
湖北省自然科学基金青年基金（2015CFB338）

A bank selection instruction optimization
method in partitioned memory architecture

CHEN Yong1,YUAN Mengting2,LI Qingan2

（1.The 14th Research Institute,CETC,Nanjing 210039;
（2.School of Computer,Wuhan University,Wuhan 430072,China）

Received:2015-03-25 Revised:2015-08-19 Online:2016-02-25 Published:2016-02-25

摘要/Abstract

摘要：

在分区内存体系结构中,如何尽可能少地插入片选指令是研究的热点。根据该问题的特点,构建了片选优化的图划分模型,并在该模型的基础上,提出了一种二阶段启发式搜索算法求解该问题。该算法首先根据节点自身的大小与图中分区大小快速获得一个初始可行解,然后在该可行解基础上利用节点之间边的权值和分区之间的权值作为启发式参数,搜索更优的解。通过对MiBench用例集和实际嵌入式系统的测试,验证了该模型及相应启发式算法的有效性,相对于VPAB算法,平均优化率达到37.99%,略优于成熟的商用编译器PICC,大幅度减少了片选指令的数量。

关键词: 分区内存, 图模型, 启发式搜索, 嵌入式系统

Abstract:

It is a research hotspot to minimize the number of bankselection instructions in the partitioned memory architecture. Analyzing the features of this problem, we construct a graph partition model for bank selection and propose a twostage heuristic search algorithm. This algorithm uses the size of nodes and partition capacity to get an initial solution quickly, and then uses the edge weights between nodes and the weighs between partitions as the heuristic parameters to search for the better solution. Experiments on MiBench benchmark and a real embedded system validate the effectiveness of the proposed model and algorithm. Compared to the VPAB algorithm, the proposal can achieve an average optimization rate of 37.99%, which is slightly better than the mature commercial compiler PICC, and can reduce the number of bank selection instructions largely.

Key words: partitioned memory;graph model;heuristic search;embedded system

陈勇1,袁梦霆2,李清安2. 分区内存体系结构片选指令优化方法[J]. J4, 2016, 38(02): 195-201.

CHEN Yong1,YUAN Mengting2,LI Qingan2. A bank selection instruction optimization
method in partitioned memory architecture [J]. J4, 2016, 38(02): 195-201.

参考文献［15］

［1］	MCU 20122016 sales, sales and average unit price analysis［EB/OL］.［20140814］.http://info.ec.hc360.com/2014/08/140912771373.shtml.(in Chinese)
［2］	Scholz B,Burgstaller B,Xue J.Minimizing bank selection instructions for partitioned memory architecture［C］∥International Conference on Compilers,Architecture and Synthesis for Embedded Systems,2006:201211.
［3］	Scholz B,Burgstaller B,Xue J.Minimal placement of bank selection instructions for partitioned memory architectures ［J］.Transactions on Embedded Computing Systems,2008,7(2):132.
［4］	Li M,Xue C.J,Liu T,et al.Analysis and approximation for bank selection instruction minimization on partitioned memory architecture［C］∥ Proc of the ACM SIGPLAN Conference on Languages,Compilers,and Tools for Embedded Systems,2010:18.
［5］	Yuan Mengting,Wu Guoqing,Yu Chao.Optimizing bank selection instructions by using shared memory［C］∥Proc of the 2008 International Conference on Embedded Software and Systems,2008:447450.
［6］	Liu T,Li M,Xue C J.Joint variable partitioning and bank selection instruction optimization on embedded systems with multiple memory banks［C］∥Proc of 2010 15th Asia and South Pacific Design Automation Conference,ASPDAC,2010:113118.
［7］	Guthaus M R,Ringenberg J S,Ernst D,et al.MiBench:A free,commercially representative embedded benchmark suite ［C］∥Proc of the 4th Annual IEEE International Workshop on Workload Characterization,2001:314.
［8］	Mengting Y,Xue C J,Yong C,et al.Minimizing code size via page selection optimization on partitioned memory architectures［C］∥Proc of International Conference on Compilers,Architecture and Synthesis for Embedded Systems,2013:110.
［9］	Karp R M.Reducibility among combinatorial problems ［M］∥50 Years of Integer Programming,Berlin:SpringerVerlag Berlin Heidelberg, 2010:219241.
［10］	Hajiaghayi M T,Leighton T.On the maxflow mincut ratio for directed multicommodity flows［J］.Theoretical Computer Science,2006,352(1):318321.
［11］	Nowozin S,Jegelka S.Solution stability in linear programming relaxations:Graph partitioning and unsupervised learning［C］∥Proc of the 26th Annual International Conference on Machine Learning,2009:769776.
［12］	VazquezMartin R,Nunez P,Bandera A,et al.Spectral clustering for featurebased metric maps partitioning in a hybrid mapping framework［C］∥IEEE International Conference on Robotics and Automation,2009:18681874.
［13］	CojaOghlan A.Graph partitioning via adaptive spectral techniques［J］.Combinatorics Probability & Computing,2010,19(2):227284.
［14］	Yalamanchili H K,Parekh N.Graph spectral approach for identifying protein domains［C］∥Proc of the 1st International Conference on Bioinformatics and Computational Biology,2009:437448.
［15］	C compiler tool chain HRCC［EB/OL］.［20150813］.http://www.ichaier.com/downfa.php?thiks=YWF1cGxvYWRmaWxlLzIwMTUvMDMxMy8yMDE1MDMxMzAxMjAyMzc2MC56aXBiYg==&n=QyAg57yW6K+R5Zmo5bel5YW36ZO+IEhSQ0MgVjEuMC4wLjY2.(in Chinese)
	附中文参考文献：
［1］	20122016年MCU销售额、销售量及平均单价分析［EB/OL］.［20140814］.http://info.ec.hc360.com/2014/08/140912771373.shtml.
［15］	C 编译器工具链 HRCC［EB/OL］.［20150813］.http://www.ichaier.com/downfa.php?thiks=YWF1cGxvYWRmaWxlLzIwMTUvMDMxMy8yMDE1MDMxMzAxMjAyMzc2MC56aXBiYg==&n=QyAg57yW6K+R5Zmo5bel5YW36ZO+IEhSQ0MgVjEuMC4wLjY2.

[1]	马瑛超, 张晓滨. 基于主题关系的中文短文本图模型实体消歧[J]. 计算机工程与科学, 2023, 45(01): 154-162.
[2]	龚锐, 石伟, 刘威, 张剑锋, 王蕾. 基于NAND Flash的CPU安全启动设计与实现[J]. 计算机工程与科学, 2022, 44(06): 971-978.
[3]	陈祥国, 尚凡, 宋君强. 嵌入式系统安全防护方案比较与应用案例分析[J]. 计算机工程与科学, 2022, 44(03): 417-426.
[4]	王会举, 李孟萱, 黄卫卫, 周秋怡. 基于隐马尔可夫模型的多真值发现算法[J]. 计算机工程与科学, 2021, 43(03): 518-524.
[5]	邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(02): 258-265.
[6]	蒋亚芳, 严馨, 徐广义, 周枫, 邓忠莹, . 融合多信息句子图模型的多文档摘要抽取[J]. 计算机工程与科学, 2020, 42(03): 535-542.
[7]	周明进1,卢再奇2. 基于ARM的嵌入式数据录取设备研制[J]. 计算机工程与科学, 2018, 40(09): 1556-1561.
[8]	李攀1,2，田泽1,2，蔡叶芳1,2，张亦姝3，杨海波1,2,霍卫涛1,2,王玉欢1,2. FC-AE-ASM协议优化设计[J]. 计算机工程与科学, 2017, 39(02): 280-284.
[9]	卢灿举，张云峰，高春颖，刘俊. 案例教学下嵌入式系统课程的改革与实践[J]. 计算机工程与科学, 2016, 38(增刊): 248-251.
[10]	池鹏可，苏成悦，谢广泉，柳丁. Android平台上的多用户无线投影控制系统设计[J]. J4, 2015, 37(11): 2148-2153.
[11]	刘雪1,胡军1,2, 黄志球1,马金晶1,程桢1，石娇洁1. 模型驱动的嵌入式系统设计安全性验证方法研究[J]. J4, 2015, 37(08): 1498-1509.
[12]	武小平. 面向系统综合能力培养的“嵌入式系统”教学探讨[J]. J4, 2014, 36(A2): 238-241.
[13]	王苏峰，陆洪毅，肖侬. 前后台系统渐进式比较教学方法探索[J]. J4, 2014, 36(A1): 100-102.
[14]	宋丽华,战颖,简阳,张鑫磊,鲍世昆. 基于S3C6410的嵌入式系统休眠与唤醒策略设计与实现[J]. J4, 2014, 36(05): 790-796.
[15]	吕晖1，丁亚军2，郑方1，吴东1，谢向辉1. 支持跨步访问的嵌入式存储系统[J]. J4, 2014, 36(02): 211-215.

分区内存体系结构片选指令优化方法

A bank selection instruction optimization
method in partitioned memory architecture

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［15］

相关文章 15

编辑推荐

Metrics

本文评价

分区内存体系结构片选指令优化方法

A bank selection instruction optimization method in partitioned memory architecture

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［15］

相关文章 15

编辑推荐

Metrics

本文评价

A bank selection instruction optimization
method in partitioned memory architecture

参考文献［15］