A linear complexity algorithm for the automatic generation of convex multiple input multiple output instructions

Abstract

The instruction-set extensions problem has been one of the major topics in recent years and it consists of the addition of a set of new complex instructions to a given instruction-set. This problem in its general formulation requires an exhaustive search of the design space to identify the candidate instructions. This search turns into an exponential complexity of the solution. In this paper we propose an efficient linear complexity algorithm for the automatic generation of convex multiple input multiple output instructions, whose convexity is theoretically guaranteed. The proposed approach is not restricted to basic-block level and does not impose limitations either on the number of input and/or output, or on the number of new instructions generated. Our results show a significant overall application speedup (up to ×2.9 for ADPCM decoder) considering the linear complexity of the proposed solution and which therefore compares well with other state-of-art algorithms for automatic instruction-set extensions.

Keywords:

• HW/SW partioning
• algorithms
• reconfigurable
• architecture

Acknowledgement

This work was supported by the European Union in the context of the MORPHEUS project Num. 027342.

Notes

Notes

1. For example two subgraphs with set of nodes {1, 2, 4} and {1, 3, 5} respectively overlap at node 1 and then only one of them is enumerated.

2. ℘(G) is the set of all subgraphs of G, including the empty graph ∅ and G.

3. A path is a sequence of nodes and edges, where the vertices are all distinct.

4. G* has to be a proper subgraph of G. A graph itself is always convex.

5. Clearly A ₁ ∩ A ₂ = ∅.

6. LEV(A ₁)–LEV(A ₂) = 0 is a particular case studied in Galuzzi et al. (2006).

7. More specifically, the number of processed elements is at most n + m, where n is the order of G and m is the number of MAXMISOs in G.