Instruction Selection in ASIP Synthesis Using Functional Matching

In embedded systems, Application Specific Instruction Set Processors (ASIPs) are used commonly with the aim to get high performance without losing flexibility. A crucial operation required during ASIP synthesis (in particular, selection of custom instructions) as well as code generation for ASIPs is identifying portions of an application program that can be executed by custom functional units (CFUs). Most existing solutions achieve this by matching structure of patterns corresponding to CFUs with sub-graphs of application data flow graphs. Often it happens that the computations performed by the two are equivalent, but due to structural dissimilarities the match is missed. What is needed is a method that can match two graphs functionally rather than structurally. In this paper, we present a novel method to do this and give implementation results to show its effectiveness.