ISSN 1000-1239 CN 11-1777/TP

• 系统结构 •

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

1. (辽宁工程技术大学软件学院 辽宁葫芦岛 125105) (celine.shanshan.wang@gmail.com)
• 出版日期: 2018-07-01
• 基金资助:
国家自然科学基金项目(61404069)；辽宁省教育厅科学研究一般项目(LJYL048)；辽宁省科技厅博士启动基金项目(20141140)

### Iterative Identification of Maximal Convex Custom Instruction for Extensible Processors

Wang Shanshan, Liu Wanjun, Xiao Chenglong

1. (School of Software, Liaoning Technical University, Huludao, Liaoning 125105)
• Online: 2018-07-01

Abstract: 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.