Comparison of Evolutionary and Machine Learning-Based Algorithms for Energy-Aware Instruction Scheduling

• Applicant: Professor Dr.-Ing. Guillermo Paya Vaya, Ph.D.
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems ; Electronic Semiconductors, Components and Circuits, Integrated Systems, Sensor Technology, Theoretical Electrical Engineering
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 415838871

Current digital signal processors (DSP) take profit of a very long instruction word (VLIW) architecture style, which provides high performance by executing independent instructions in parallel, and reduced power consumption due to the small silicon area requirement compared to other parallel processor architecture concepts. For that, VLIW compilers are in charge of rearranging independent instructions of the input program into very long instructions. However, instruction scheduling can generally not be performed optimally due to problem complexity (up to n! schedules for n operations) and architecture constraints (e.g. hardware resource conflicts). Traditionally, these problems are handled with heuristic-based algorithms, which are manually tailored to a specific processor architecture and only consider a single scheduling objective (e.g. code compaction).This project will research the use of a Multi-Objective Evolutionary Algorithm (MOEA) approach within a VLIW compiler for combined instruction scheduling, register allocation, and code selection. By evolving a population of solutions, this approach provides flexibility to be used for different target architectures (re-targetable compiler) and also overcomes the limitations of static heuristic-based algorithms. The trade-off of long compile times can be reduced with parallel computing techniques. Moreover, the MOEA approach can take different compiling objectives (code compaction and power consumption) into account, considering that different code schedules produce different internal switching activity, which is the main cause for dynamic power consumption. Moreover, a machine-learning approach for identifying significant code features (feature mining) for automatic generation of architecture-specific heuristic functions will be researched to enhance traditional heuristic-based schedulers, taking profit of their low compile time and deterministic behavior. Finally, both approaches will be evaluated and compared to a state-of-the-art heuristic-based instruction scheduler (i.e. list scheduling algorithm) on four different commercial and research VLIW DSPs. By using two different DSP evaluation boards, the impact of the instruction scheduling on the power consumption will also be measured and studied.

• DFG Programme: Research Grants