Page 346 - 《软件学报》2020年第9期

赵姗 等:S-Bridge:性能非对称多核处理器下负载均衡代理机制 2967

同 CPU 核配置和 IPC 组成的性能矩阵作为线程分配和迁移的依据.文献[13,14]通过指令执行由于访存被阻塞
的时间建立栈模型,通过大小核的加速比模型作为调度的依据.
文献[15,24]针对动态异构多核处理器,根据应用的运行时状态进行处理器参数的动态调整.文献[15]基于
CFS 提出新的 HFS(heterogeneity-aware fair scheduler)算法,增加集中式任务队列支持逻辑核的快速分配和调
整,同时,进行公平性决策时增加核计算性能的因素,实现在利用异构多核性能优势的基础上保证公平性.但是
文献[15]没有考虑不同特征应用计算资源的需求,而且异构的适配需要在 CFS 算法的基础上进行修改.其余工
作主要针对静态性能非对称异构多核处理器,以下主要针对性能优化目标的工作进行分析.文献[16]提出基于
稳定匹配算法的调度技术,维护动态的线程任务和核的优先级表,作为调度的依据.文献[17]提出一种迭代启发
式调度算法,在满足功耗线程的情况下提高吞吐量.
以上工作主要是针对调度算法本身,程序分析和调度决策本身具有较强的耦合度,缺乏通用性.而且 HASS
虽然对于有稳定执行状态的负载,尤其是异构度明显的负载有较好的效果,但最主要的限制是无法感知程序变
化的执行阶段,而且无法考虑运行状态(比如共享内存状态)的影响.文献[7,19]都是 IPC 驱动的动态调度算法,需
要通过 IPC 采样获取在不同核上的性能数据,信息获取依赖于不同微架构的硬件支持,而且随着核类型的增加,
可扩展性也比较差.文献[11]的性能预测模型从 PMC 单元无法直接获取,需要增加额外硬件支持.同时,文献[7]
虽然通过很少的代码修改可以在多数 Linux 调度器上实现,但是仅对负载均衡时任务选择的策略进行改进和增
强.文献[25]虽然是负载均衡算法的优化,但是需要通过修改 Linux 内核的负载均衡算法加入处理器利用率信
息,使动态调频和负载均衡更好地协同工作.而不同于以上工作提出或者优化具体调度算法的方法,本文从另外
一个角度提供一种代理机制,为各种调度算法提供异构的支持.这种机制跟以上工作最显著的不同是不需要直
接修改调度算法本身,而是基于运行时信息形成规则影响负载均衡决策,同时提供架构无关的接口与调度器进
行交互,适配不同的调度器,可以做到平台无关性和通用性.
同时,HMP(heterogeneous multi processing)是 Linaro 针对 big.LITTLE 架构开发的异构感知的调度算法,在
实现上与 CFS 调度算法具有相同的入口,重新定义调度域为大小核两个域,在此基础上改进负载均衡策略,将负
载重的任务迁移到大核域内执行,将负载轻的任务迁移到小核域内执行,采用任务处于可运行状态所占用 CPU
时间比率作为负载轻重的依据.由于 HMP 这套机制在 2014 年后的成功商业化,目前大部分 big.LITTLE 设计的
移动终端设备上(比如三星 Exynos5430 和 5433 等)都采用了 HMP 机制.因此,本文实验部分将优化工作与此主
流的异构调度器进行比对.由于 HMP 调度器在 Linux 内核原有负载计算方法上扩展,对于任务特性的感知在
HMP 中没有考虑,将通过本文的工作对 HMP 进行扩展.

2 异构多核处理器下的负载均衡问题

2.1 传统负载均衡的设计

在主流的 Linux 操作系统中,调度器中的负载平衡针对同构多核系统(SMP)设计,目标是通过在各个核之间
均匀分配负载,使各个核之间处于平衡的状态.传统负载均衡的实现采用 pull 和 push 两种方式进行负载均衡,
以 pull 方式为例:当前 CPU 运行队列为空的时候,触发负载均衡,调度器将找到负载最重的 CPU,并移动该 CPU
运行队列中的任务到空闲核上.其中,所有 CPU 都被对称对待,默认具有相同的处理能力(sched_capacity_scale).
每个 CPU 工作负载是指运行队列(runqueue)中所有的线程负载的总和.每个线程负载的度量方法随着调度算法
的发展而不断演化,最初定义为线程的负载权重(根据线程的优先级定义权重值),后来发展为负载跟踪度量标
准(load track metric) [28] ,根据历史负载的衰减来跟踪负载,但是基础的负载依然是线程的负载权重.该度量方法
主要基于线程的优先级和平均 CPU 利用率统计线程的负载.传统的负载均衡主要基于 CPU 对称性和任务对称
性的假设,在 CFS 调度算法中,假定相同优先级的任务具有相同的基础负载权重,而不会考虑任务属性.对于相
同优先级而且一直占用 CPU 的任务,将具有相同的负载、但是优先级相同的任务由于对 CPU 资源需求的不同
(比如计算密集型和内存密集型),在负载均衡的过程中,如果被选择迁移,不能一视同仁地分配在所有不同类型
的目标核上.因此在异构多核环境下,CPU 的处理能力和任务特性不同对 CPU 造成的负载不同且变化.