Automatic Identification of Custom Functions for Embedded Processors with MIMO Extensions

Commercially available configurable processors nowadays offer opportunities to accelerate embedded applications by implementing customized functions. Previous studies have shown that more speedup can be achieved if these functions are allowed to have more than two inputs and one output. However, automatic identification of multiple-input, multiple-output (MIMO) custom functions is usually slow due to the large exploration space. In this paper, we propose a fast algorithm to enumerate all convex subgraphs that satisfy the input/output constraints from the dataflow graph (DFG) of a basic block. The algorithm can be tuned to determine all subgraphs or only those connected subgraphs. This allows a choice between a better instruction set extension or a faster design space exploration. The algorithm´s run time can be orders of magnitude better than previous algorithms when a custom function is allowed to have two or more outputs