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

当前的数字信号处理器(DSP)利用超长指令字(VLIW)体系结构风格，该体系结构风格通过并行执行独立指令来提供高性能，并且与其他并行处理器体系结构概念相比，由于硅面积小而降低了功耗。为此，VLIW编译器负责将输入程序的独立指令重新安排为非常长的指令。然而，由于问题的复杂性(高达n！N个操作的调度)和体系结构限制(例如，硬件资源冲突)。传统上，这些问题是通过基于启发式的算法来处理的，这些算法是根据特定的处理器体系结构手动定制的，并且只考虑单个调度目标(例如代码压缩)。本项目将研究在VLIW编译器中使用多目标进化算法(MOEA)方法来组合指令调度、寄存器分配和代码选择。通过进化一组解决方案，该方法提供了用于不同目标体系结构(可重定向的编译器)的灵活性，并且还克服了基于静态启发式算法的局限性。使用并行计算技术可以减少长编译时间的权衡。此外，MOEA方法可以考虑不同的编译目标(代码压缩和功耗)，因为不同的代码调度会产生不同的内部切换活动，这是导致动态功耗的主要原因。此外，将研究一种机器学习方法来识别重要的代码特征(特征挖掘)，以自动生成特定于体系结构的启发式函数，以增强传统的基于启发式的调度器，利用它们的低编译时间和确定性行为。最后，在四个不同的商业和研究VLIW DSP上对这两种方法进行了评估，并与最先进的基于启发式的指令调度算法(即列表调度算法)进行了比较。通过使用两种不同的DSP评估板，还将测量和研究指令调度对功耗的影响。

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.