在异构电压频率岛屿上的可扩展、能源感知任务调度：从最优整数线性规划到实际启发式方法，并通过真实世界数据进行验证

《IEEE Access》：Scalable Energy-Aware Task Scheduling on Heterogeneous Voltage Frequency Islands: From Optimal ILP to Practical Heuristics with Real-World Validation

　　

摘要：

本文提出了一种在电压频率岛（VFI）架构上实现能效优化的有向无环图（DAG）调度方法，该方法结合了最优整数线性规划（ILP）公式和一种新颖的基于能量感知的列表调度与动态时隙重用（EALS-DSR）启发式算法。该研究通过智能任务分配、电压/频率分配以及调度优化，解决了最小化任务完成时间和总体能耗的关键问题。我们的贡献包括：（1）具有理论最优解保证的详细ILP公式；（2）EALS-DSR启发式算法，能够在多项式时间复杂度O(n2p)内获得接近最优的解决方案；（3）在LUD、FFT和随机DAG上的全面实验验证；（4）实际分子动力学仿真案例研究。为了最小化任务完成时间和总体能耗，可以在电压频率岛上对有向无环图进行调度，首先将可用处理单元划分为具有不同电压和频率水平的多个岛屿。本文提出了一种结合整数线性规划（ILP）和新型能量感知列表调度与动态时隙重用（EALS-DSR）启发式算法的综合性方法。所提出的方法包括四个主要组成部分：（a）DAG建模；（b）基于时隙的任务分配；（c）为每个时隙分配电压/频率；（d）调度优化。我们对原始ILP公式进行了理论分析，并通过全面实验验证和实际案例研究（包括分子动力学仿真）进行了验证。结果表明，与现有方法相比，ILP方法性能提高了10-24%，而EALS-DSR方法在节能方面实现了15-25%的改进，并且具有出色的大规模问题处理能力。分子动力学案例研究显示，该方法能耗降低了37.4%，效率提高了3.86倍，证明了其实际应用价值。