Instruction Set Extension Identification Under Local, Global, and Solver Execution Time Constraints Daniel Shapiro

mbolic-at-site-dot-uottawa-dot-ca The instruction set extension identification problem is the search for a set of custom instructions which can be added to a base processor. A sub-problem is to complete the ISE identification without searching for too long. One aspect of this area of research that needs improvement is the execution time of the sate of the art algorithms which are used to solve this problem. Thus far solutions to large problems are exact but return results too slowly. We propose a non-exact solution in the form of an integer linear program, and proceed to describe our toolchain. We show that heuristics can improve the execution time of the solver by finding an incumbent for each iteration of the ILP. We show the need for a mix of small instructions which are repeated often, and large instructions which although rare provide a large speedup. We propose a method for reducing the execution time of the solver by allowing the user to define a cutoff execution time between improvements in the solution, and a maximum execution time for the solver. Furthermore we define an objective function as the number of cycles saved due to the selection of custom instructions, because this measurement is additive. When identifying ISEs explain how merging identical ones takes advantage of common patterns in the code, and we show how to sum the speedup values now that they are additive. We include in the ISE identification problem some local and global constraints on code defined by the user