Instruction identification algorithm of instruction-set extensions based on relationship matrix

A novel instruction identification algorithm of instruction-set extensions based on a relationship matrix is proposed. Through using a relationship matrix the infeasible regions in the complete search space are pruned and the search speed for subgraphs of the application data flow graph is accelerated greatly. Compared with Atasu´s algorithm, the experiments prove that the search number of valid nodes is the same but the search number of invalid nodes is decreased by about 40-82%.