Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.sysarc.2010.04.004 | Journal of Systems Architecture - Embedded Systems Design |
Keywords | Field | DocType |
heuristic,custom instruction candidate,branch-and-bound algorithm,selection algorithm,custom-instruction selection,branch-and-bound,profitable custom instruction,custom instruction,exact solution,reconfigurable processor,heuristic algorithm,reconfigurable processors,exact algorithm,reconfigurable fabric,efficient tabu search algorithm,computer model,branch and bound algorithm,profitability,branch and bound | Heuristic,Branch and bound,Exact algorithm,Computer science,Instruction set,Heuristic (computer science),Parallel computing,Selection algorithm,Custom instruction,Tabu search | Journal |
Volume | Issue | ISSN |
56 | 8 | Journal of Systems Architecture |
Citations | PageRank | References |
6 | 0.50 | 27 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tao Li | 1 | 38 | 7.33 |
| Wu Jigang | 2 | 764 | 86.18 |
| Siew-Kei Lam | 3 | 99 | 14.60 |
| Thambipillai Srikanthan | 4 | 927 | 104.05 |
| Xicheng Lu | 5 | 1276 | 110.03 |