可扩展处理器中最大凸自定义指令迭代识别研究  

Iterative Identification of Maximal Convex Custom Instruction for Extensible Processors

作　　者：王珊珊 刘万军[1] 肖成龙[1] Wang Shanshan;Liu Wanjun;Xiao Chenglong(School of Software,Liaoning Technical University,Huludao,Liaoning 125105)

机构地区：[1]辽宁工程技术大学软件学院,辽宁葫芦岛125105

出　　处：《计算机研究与发展》2018年第7期1584-1596,共13页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61404069);辽宁省教育厅科学研究一般项目(LJYL048);辽宁省科技厅博士启动基金项目(20141140)~~

摘　　要：由于可扩展处理器能够在设计周期、灵活性、性能以及功耗等方面提供良好的折中,近年来,可扩展处理器大量地在嵌入式系统和电子设备中使用.自定义指令自动识别是可扩展处理器设计的关键.针对自定义指令自动识别问题,提出并实现了从给定的应用程序代码中自动识别最大凸自定义指令(maximal convex subgraphs,MCSs)的迭代设计流程.提出的设计流程解决了2个关键问题:MCSs自动枚举问题和MCSs自动选择问题.针对MCSs枚举问题,提出了一种夹心方式枚举所有候选最大凸自定义指令,该算法结合了自下而上和自顶向下方式的优点.与最新算法相比,提出的算法可以实现数量级的加速.针对MCSs选择问题,提出了一种利用候选指令之间的重叠关系建立兼容图,并应用非重叠规则来修剪大量的搜索空间的精确选择算法.实验结果表明:利用提出的精确算法,在大多数情况下可以找到用于最大化提升性能的MCSs.As extensible processors can provide good trade-offs among design cycle,flexibility,performance and power consumption,extensible processors are used more and more in embedded systems and electronic devices in recent years.Automatic identification of custom instructions is the key to the design of extensible processors.In this paper,we present and implement an iterative design flow for identifying maximal convex custom instructions（MCSs）from a given application code.The design flow addresses two essential problems： MCSs enumeration problem and MCSs selection problem.In order to solve the MCSs enumeration problem,we propose a very efficient algorithm for enumerating all maximal convex subgraphs using a sandwich manner that combines the advantage of the bottom-up manner and the top-down manner.Compared with the latest algorithms,our algorithm can achieve orders of magnitude speedup.Experimental results show that the achieved speedup ranging from 5.6 xto 47.3 x.In the process of selecting MCSs,we observe that the number of candidates is usually small.Furthermore,a large number of search space can be pruned by applying the non-overlapping rule.Therefore,it is more interesting to use an exact algorithm for selecting MCSs.With the proposed exact algorithm,optimal solutions for maximizing the performance improvement can be found in most cases.

关 键 词：可扩展处理器 最大凸自定义指令 数据流图 自定义指令枚举 自定义指令选择 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]