Identification of Application Specific Instructions Based on Sub-Graph Isomorphism Constraints

This paper presents a new method for computational patterns identification that forms basis for application specific instruction selection. The new algorithm is radically different from previous proposed methods. It is based on graph isomorphism constraint and constraint programming that makes it very flexible and provides opportunity to mix graph isomorphism constraints, other constraints and heuristic search for patterns in one formal environment. This algorithm takes into account graph structure and frequency of occurrence of patterns in application graphs. We have extensively evaluated our algorithm on MediaBench benchmarks. The experimental results indicate very good performance of our algorithm. It provides very high coverage for most graphs with a small number of identified computational patterns in a short amount of time.