A Novel Approach to Compute Spatial Reuse in the Design of Custom Instructions

In the automatic design of custom instruction set processors, there can be a very large set of potential custom instructions, from which a few instructions are required to be chosen, taking into account their spatial as well as temporal reuse and cost. Using the existing pattern matching techniques, finding complete reuse of every identified pattern in the entire application would be very slow and may even be computationally infeasible. Due to this, the existing selection methods employ pattern matching techniques at a very later stage of selection process on a small set of patterns, compromising the quality of selected candidates. In this paper, we propose a method by which each pattern´s reuse information can be derived at an early stage of selection process even when there are very large number of potential patterns. The novel contributions of this paper include a simple and efficient algorithm for finding all the isomorphic convex subgraphs (termed as Recurring Pattern Information(RPI)) of the given application´s Control Data Flow Graph (CDFG). The proposed technique is integrated into the estimation phase of the Instruction Set Extension (ISE) automation. Experimental results show the efficiency of the proposed algorithm and demonstrate its utility in generating high quality custom instructions.