Selecting most profitable instruction-set extensions using ant colony heuristic

Due to the combination of flexibility and runtime performance, extensible processors have been widely used in embedded systems in last decade. Extensible processors extend the instruction set of a general purpose processor by a set of customized instructions. In general, the instruction set extension generation includes two crucial steps: subgraph (graph representation of custom instruction) enumeration and subgraph selection. In this paper, we have formally proved that the upper bound of the number of feasible solutions for the subgraph selection problem is 3n/3, where n is the number of subgraph candidates. We also propose an ant colony optimization algorithm (ACO) and a version of modified ACO algorithm (MACO) for solving the subgraph selection problem that aim at minimizing the application execution time while satisfying non-overlapping constraint (and area constraint). Experimental results show that the MACO algorithm outperforms the ACO algorithm, the well-known tabu search algorithm and the heuristic algorithm [6] on average 2.7%, 5.9% and 15.1% respectively.