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.