ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (7): 1584-1596.doi: 10.7544/issn1000-1239.2018.20170384

Previous Articles    

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.

Key words: extensible processors, maximal convex custom instruction, data flow graph, custom instruction enumeration, custom instruction selection

CLC Number: