Efficient Heuristic Algorithm for Rapid Custom-Instruction Selection

Custom-instruction selection is an essential phase in custom-instruction generation. It determines the most profitable custom instruction candidates for hardware implementation. In this paper, a practical computing model is proposed for the problem of custom-instruction selection that takes into account the hardware area constraint. Based on the new computing model, a novel heuristic algorithm is presented to rapidly generate high quality approximate solutions. The overlapping information of custom-instruction instances is utilized in the algorithm to instruct the selection process. Simulation results show that the proposed heuristic algorithm runs fast even for the large-sized problems. The proposed heuristic algorithm produces high-quality approximate solutions. Experimental results show that the difference between the approximate solutions and the optimal ones is only about 3%.