Page 106 - 《软件学报》2021年第12期

3770 Journal of Software 软件学报 Vol.32, No.12, December 2021

的差异,实时处理器可调电压边界、对应不同负载启用粒度的电压和频率级别构成以及工作频率与动态能耗相
互之间影响规律非常复杂 [3,4,8] ,因此,面对计算资源异构性,仅靠调频核心技术之“负载→频率”应答机制,还存在
诸多节能约束;而对异构集群主要耗能部件的实时动态功耗,从测量方法到预估模型现在都面临一系列挑战.
大规模实时调度一般要求在性能不降低的情况下减少能耗值.现有的实时调度研究大多关注同构系统的
两类简单任务对象:周期任务和静态任务.在这两种类型中,假定“任务”是不能被抢占的最小单位,作业都被假设
[7]
为无限调用任务序列;且模型中不存在作业内并行性,即在任意时刻,每个作业实例最多在一个处理器上执行 .
异构实时调度,重点介绍 4 个代表性新成果.文献[12]提出的 EEVS 引擎在调度目标中引入通信成本参数
K:设定好 K 值后,把当前任务映射到某处理单元,如果增加的通信量边大于平均通信量与 K 值的积,则更改映射;
K 的最优取值与具体任务图相关,可通过实验确定.文献[13]提出了求解最佳处理单元数目算法,实现了处理机
数目和时钟频率的有效平衡,但由于处理机数目的上下界范围过宽,使用二分查找和线性查找确定处理机数目
的方式增加了算法执行时间和复杂度.GOA(greedy online algorithm)及 TOAA(2-approximation online algorithm)
是文献[14]分别面向同构、异构系统提出的实时动态任务引擎的最新研究.TOAA [14] 面对计算资源的异构性,对
每个任务组反复查找最小化能耗的最佳匹配,但任务分配完全基于静态分组和复制结果.文献[15]提出了异构
系统下并行应用引擎 p-BFF(power-aware backfilling-first-fit):p-BFF [15] 忽略调频处理器动态能耗量化,仅优化静
态功耗,不适合数据密集应用.
另外,上述调度算法大多为基于启发式算法(heuristic algorithm).对 QoS 高维指标需求,启发式调度会将多
目标归一聚合至单目标函数,得到决策空间的一个可行解:降低了最终解的质量,缺乏灵活性和扩展性 [16−18] .
近年来,模拟达尔文“适者生存”自然进化论或生物免疫等机制的一类仿生智能算法(如遗传算法、人工免疫
算法等),被广泛应用于云调度优化问题 [5,6] .这类方法基于仿生个体(候选解)特征编/解码,元启发式(meta-
heuristics)搜索解空间,具体包括遗传算法(genetic algorithms,简称 GA)、人工免疫算法(artificial immune
algorithms)、粒子群算法(particle swarm optimization,简称 PSO)、模因算法(memetic algorithms,简称 MA)和细
胞模因算法(cellular MA,简称 cMA)等,以及元启发式算法与其他一些技术的融合,比如神经网络(neural
networks)、变邻域搜索(variable neighborhood search)和列表调度技术(list scheduling techniques) [19,20] .
元启发式算法的并行与分布式设计具体可划为主从模型(master-slave model)、细粒度模型(fine-grained
model)和粗粒度模型(coarse-grained model),其中,粗粒度模型也称为孤岛模型(island model),被广泛应用在众核
CPU+GPU 混合结构的超计算机调度服务器上,孤岛模型相关研究主要集中在选择函数、替代函数、迁移率或
拓扑结构的设计上 [21−23] .
前期成果 [11] 为解决异构资源管理存在问题以适应新环境、新应用、新需求及新特征,围绕节能减排及调度
协同等热点,尝试将一些硬件特性结合到异构调度中间件的目标评测中.对比实验结果显示:调度引擎在节能等
方面优势明显,但由于技术、时间及资金等方面限制,调度模型中的能耗参数仅是凭借先验大体预估.

2 软硬件节能原理深度融合的绿色异构调度算法

通常,云体系包含用户层、中间件层、虚拟资源层和基础设施层(如图 1 所示).用户作业可解析产生若干并
行依赖任务集,一般建模为 DAG(directed acyclic graph)集合;中间件负责作业调度、执行,也是压力最集中组件.
鉴于 CPU 和 GPU 都是并行计算资源,本文在称谓上不作区分,采用统一标识并进行异构属性说明.
调度 QoS 评价指标体系与相应元启发式(meta-heuristics)算法(如遗传算法、人工免疫算法等)是调度引擎
核心;受达尔文“适者生存”进化论启发的遗传算法,通常直接用 QoS 多目标多约束函数评价个体适应度;类似地,
在模拟生物免疫系统的人工免疫算法(artificial immune algorithms)中,导致系统产生抗体的抗原也被定义为调
度 QoS 评价函数.