Selecting profitable custom instructions for reconfigurable processors

Custom-instruction selection is an essential phase in instruction set extension for reconfigurable processors. It determines the most profitable custom-instruction candidates for implementing in the reconfigurable fabric of a reconfigurable processor. In this paper, a practical computing model is proposed for the custom-instruction selection problem that takes into account the area constraint of the reconfigurable fabric. Based on the new computing model, two heuristic algorithms and an exact algorithm are proposed. The first heuristic algorithm, denoted as HEA, dynamically assigns priorities to the custom instruction candidates and incorporates efficient strategies to select custom instructions with the highest priority. The second heuristic algorithm, denoted as TSA, employs an efficient tabu search algorithm to refine the results of HEA to near-optimal ones. Also, a branch-and-bound algorithm (BnB) is proposed to produce exact solutions for relatively small-sized problems or problems with stringent area-constraints. Experimental results show that HEA can produce more specific approximate solutions with a difference of only about 3% when compared to the optimal solutions produced by BnB. This difference is further reduced to about 0.6% by TSA. In addition, for large-sized problems where the exact algorithm becomes prohibitive, HEA and TSA can still produce solutions within reasonable time.