Graph Covering for generating instruction specific application instructions: an overview of some existing methods

Abstract

The execution time of an application can be considerably reduced by implementing parts of the application in hardware instead of software. Graph Theory can be used for selecting which parts of the application are suitable for an hardware implementation. To this purpose, the application is represented as a directed graph, called a subject graph, and the selection problem can then be described as the search and selection of subgraphs having particular properties. The subgraph identification problem requires the evaluation of two separate issues: a coverage problem of the subject graph and a selection problem of the subgraphs. The complexity of the problems involved has led researchers to provide both exact solutions as well as heuristic solutions representing a trade-off between the goodness of the solution provided and the resources used to obtain it. Although a heuristic solution is usually used to limit the search space, how much is left uncovered is what influences the goodness of the solution. This depends on the parameters that are taken in consideration to evaluate the solution as area, delay, etc. In this paper we provide an overview of the main issues related to the coverage of the search space pointing out the goodness of the solutions provided as well as the main features of the method applied to obtain it.

Topics

1 Figures and Tables

Download Full PDF Version (Non-Commercial Use)