Optimal subgraph covering for customisable VLIW processors

It is increasingly common to see the combination of single-issue general purpose processors (GPPs) with extensible VLIW processors in many embedded system designs. Compared with GPPs, extensible VLIW processors can exploit instruction-level parallelism, and they are more suitable for computation-intensive tasks. Moreover, they offer the ability of customising instruction-set extensions (ISEs) for an application domain. Many previous works reveal that automated extension generation can greatly improve both performance and design efficiency of instruction-set extensible processors. One of the key steps of automated extension generation is subgraph selection. Since this problem is at least NP-hard, most previous works rely on greedy approaches to address it, whereas an optimal subgraph mapping methodology that customises ISEs for multi-issue/VLIW extensible processors is presented here. Several effective pruning techniques are proposed to ensure that the proposed methodology is tractable, and the optimal method performs 41.02% better than greedy method on average. Besides the optimal subgraph covering methodology, several techniques are also proposed to reduce the area burden that ISEs impose on the processor.