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

由于可扩展处理器能够在设计周期、灵活性、性能以及功耗等方面提供良好的折中，近年来，可扩展处理器大量地在嵌入式系统和电子设备中使用.自定义指令自动识别是可扩展处理器设计的关键.针对自定义指令自动识别问题，提出并实现了从给定的应用程序代码中自动识别最大凸自定义指令(maximal convex subgraphs, MCSs)的迭代设计流程.提出的设计流程解决了2个关键问题：MCSs自动枚举问题和MCSs自动选择问题.针对MCSs枚举问题，提出了一种夹心方式枚举所有候选最大凸自定义指令，该算法结合了自下而上和自顶向下方式的优点.与最新算法相比，提出的算法可以实现数量级的加速.针对MCSs选择问题，提出了一种利用候选指令之间的重叠关系建立兼容图，并应用非重叠规则来修剪大量的搜索空间的精确选择算法.实验结果表明：利用提出的精确算法，在大多数情况下可以找到用于最大化提升性能的MCSs.

Iterative Identification of Maximal Convex Custom Instruction for Extensible Processors

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.6x to 47.3x. 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.