TL;DR
This paper introduces a methodology to automatically assign instruction op-codes in low-power processors to minimize power consumption during instruction fetching and decoding. By analyzing instruction sequences from typical software, they create a "low-power" instruction set that reduces bit transitions, leading to significant power savings, especially for embedded systems.
What Problem Does This Paper Address?
As electronic devices become more pervasive and power-constrained (think smartphones, wearables, and embedded systems), minimizing power consumption is paramount. A significant portion of a processor's power is consumed by its internal circuitry, particularly during instruction fetching and decoding. When instructions are loaded into registers and processed, the transitions of bits on the bus and within the registers contribute to dynamic power dissipation. The authors identify that the specific binary patterns assigned to instruction op-codes can directly influence these bit transitions. Therefore, the problem is to find an optimal assignment of these binary patterns to instruction op-codes that minimizes these transitions, thereby reducing power consumption, without sacrificing performance. This is particularly relevant for core processors and microcontrollers that execute fixed code sequences repeatedly.
Methods
The core of the methodology involves two main phases:
- Instruction Adjacency Analysis:
- Instruction-level simulation is performed on typical software applications to collect "instruction adjacency statistics." This means tracking how often one op-code immediately follows another.
- These statistics are stored in a KxK matrix (where K is the number of distinct op-codes), representing the count of transitions between any two op-codes.
- This matrix is then used to construct a weighted undirected graph. Each vertex represents an op-code, and the weight of an edge between two vertices is the sum of the transition counts between the corresponding op-codes.
- Low-Power Op-Code Assignment:
- The goal is to assign a binary code of a specific length (determined by the number of op-codes) to each vertex (op-code) in the graph.
- This assignment is driven by minimizing a cost function that is proportional to the sum of Hamming distances between the assigned codes of adjacent op-codes, weighted by their adjacency frequency. In simpler terms, op-codes that frequently appear together should be assigned binary codes that are "close" in terms of Hamming distance (few bit differences).
- The paper mentions two heuristic algorithms for this assignment:
- An explicit algorithm based on integer linear programming, which is more accurate but computationally intensive for larger problems.
- An implicit algorithm using Binary Decision Diagrams (BDDs) and Algebraic Decision Diagrams (ADDs), which is less accurate but scales better for larger graphs.
Datasets
The paper uses the following:
- Software Applications: Eight software applications were used for instruction-level simulation. These included DBMSs, word processors, data compression tools, and logic synthesis tools.
- Target Microprocessor: The MIPS R4000 RISC microprocessor was used as a case study for experimental evaluation. The instruction set architecture (ISA) of the MIPS R4000 was the basis for the op-code re-encoding.
- Instruction Traces: Generated from executing the selected software applications on a DEC-Station 5000/200 running Ultrix.
No new benchmarks were introduced; rather, existing typical applications were used to generate realistic instruction traces.
Key Insights and Ideas
- Op-code assignment is a power optimization knob: The paper demonstrates that the choice of binary encoding for op-codes isn't just an arbitrary decision but has a direct impact on dynamic power consumption in the instruction fetching and decoding logic.
- Instruction adjacency is key: The frequency with which op-codes appear together is the primary driver for determining optimal assignments. Frequently co-occurring op-codes should have similar binary representations.
- Graph embedding for power: The problem is elegantly framed as a graph embedding problem, where the goal is to map graph vertices (op-codes) to binary codes to minimize a weighted Hamming distance cost function.
- Heuristics are necessary for practicality: Due to the NP-hard nature of the optimal solution, heuristic algorithms (explicit and implicit) are crucial for finding near-optimal solutions in a reasonable time.
- Embedded systems are prime targets: The technique is particularly well-suited for embedded systems and IP cores where instruction sequences are often fixed and predictable, allowing for highly optimized, application-specific op-code assignments.
- Minimal hardware overhead: The proposed re-encoding can be applied by a simple filter that translates legacy op-codes to the new low-power ones, requiring no significant hardware changes and only minor limitations for self-modifying code.
Key Results
- Significant Power Savings: The re-encoding of instruction streams resulted in substantial reductions in switching activity in the op-code bits.
- Explicit algorithm: Savings between 30% and 42%.
- Implicit algorithm: Savings between 15% and 33%.
- Extended Op-codes: Re-encoding of extended op-codes (for SPECIAL instructions) yielded smaller savings (around 5% on average) due to additional constraints imposed by non-SPECIAL instructions.
- Global Savings: For general-purpose applications, a "Global" average saving of over 30% was observed when considering all eight programs.
Limitations and Future Work
- Software Dependency: The effectiveness of the op-code assignment is heavily influenced by the specific software used to compute instruction adjacency statistics. This makes the technique best suited for dedicated processors or specific application domains.
- Self-Modifying Code: The re-encoding procedure cannot be applied to self-modifying code, as the op-code mapping would need to change dynamically.
- Future Work: The authors suggest that the methodology can be extended to general-purpose processors by collecting statistics across a wider range of applications to find an average "best" encoding. Further research could explore more sophisticated encoding algorithms or investigate the impact on other parts of the processor pipeline.
Summary updated