基于最优虚拟截止日期多处理器混合时序调度

高启明，吴莉莉

(1.邯郸学院 机电学院，河北 邯郸 056005；2.燕山大学 机械工程学院，河北 秦皇岛 066000)

0 引 言

随着现代科学技术的进步，半导体工艺水平的提升可有效提高处理器计算性能约20倍，处理器生产厂家可在单个处理器中实现更强的计算性能[1,2]。但是对于个别大数据量运算情形，仍然需要用到多处理器协调配合。在多核处理器诞生以前，多处理器计算是最为常用的大数据处理方式[3]。

文献[4]采用可迁移算法对运行任务进行调度处理，实现了任务运行调度的动态调整。文献[5]基于公平博弈理论对多处理器的资源调度过程进行设计，相对于现有算法实现了算法处理性能有效提升。文献[6]提出一种基于分组策略的提高多处理器使用效率的调度算法，可有效确保多任务计算过程中的截止时间问题。文献[7]提出一种基于遗传算法的多处理器任务调度算法，但是算法计算复杂度过高。文献[8]提出一种多处理器互连网络负载均衡算法，实现了网络负载的均衡配置，获得了良好的效果。文献[9]提出基于全局队列调度的多处理器任务迁移调度算法，但是多处理器之间数据的频繁迁移过程会造成算法计算复杂度大幅提升。而文献[10]提出基于局部队列调度的多处理器任务调度算法，解决了上述任务需要在处理器间进行迁移的问题，但是处理器内部单核的处理能力有限。

本文提出基于最优虚拟截止日期的多处理器混合时序调度算法，采用新的时序保证技术，以确保系统在两个不同临界值之间进行过渡，并将所提可调度性测试扩展到混合临界系统，设计一种最优虚拟截止日期分配策略。

1 问题描述

1.1 系统模型

(1)在调度算法方面，考虑全局非抢占调度，其中任务的一个作业可以在与任务的另一个作业不同的处理器核心上并行执行，任务在算法执行期间具有相对独立性，所占用处理器不能在执行任务调度的同时被任何作业抢占，并且如果至少有一个作业准备好执行，则处理器不能处于空闲状态。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1.2 可调度条件

图1 PS(τ)的工作运行机制

W(NP-EDF(τ),J(τ,q),[0,t+YTR))≥
W(PS(τ),J(τ,q),[0,t))

(10)

式中：J(τ,q) 表示τ中任务调用的q作业集合，其中q是最早的绝对截止日期。为解决PS(τ) 在LO和HI模式下的执行速率过低的问题，考虑满足以下条件任务集

(11)

(12)

2 多处理器混合临界最优分配

2.1 可调度性分析

(13)

(14)

图2 无虚拟截止日期PS(τ)运行机制

(15)

(16)

(17)

2.2 最优虚拟截止期分配

(18)

算法1： 系统级参数的最优虚拟截止时间分配

输入：m，n，U，CF，CP，ui，Ti

(2) ifLj=HI then

(4) else

(7) ifj≠j2then

(8)α←

(9) endif

(10) endif

(11) if 式(16)-式(17)成立 then

(12) return可调度；

(13) endif

(14) return不可调度；

(19)

(20)

(21)

算法1使用这3种情况计算α， 最终检查可调度性(第(11)行-第(14)行)。然后，以下定理给出了算法1中α的虚拟截止时间分配的最优性。

定理1 如果算法1返回不可调度结论，则对于任务τi∈τ|Li=HI情形下的αi=α和任务τi∈τ|Li=LOτi∈τ|Li=HI情形下的αi=1， 不存在α使得式(16)-式(17) 成立。

3 实验分析

3.1 实验设置

为验证所提多处理器任务调度算法的有效性，选取实验平台为Revealer处理器，系统编译软件选取MPMD构建实验平台的前端编译环境，同时选取GPU开源系统revealerel-gcc构建实验平台的后端编译环境。本实验中所采用的硬件开发平台如图3所示。其中，共有10台笔记本电脑，每个电脑模拟多个处理器实体，参与时序调度过程。选取第一排左侧第一个电脑作为管理员主机，负责调度程序的运行和过程调度，其余9台电脑模拟任务处理过程，按照从前往后、从左至右的顺序分别执行任务如下：DCT、FFT、Gauss(Gau)、Histogram(His)、imgsmth(img)、MatricMult(Mat)、mergesort(mer)、shortEng(shor)、aveMotion(ave)。

图3 实验平台

对比算法：①程序流图模块多处理器调度算法(SGM)；②启发式表多处理器调度算法(Heuristic)；③基本块多处理器调度算法(Block)。其中，SGM算法本质上是采用线性规划策略的多处理器优化调度算法，主要优化目标是多处理器任务处理的均衡，对于数据通信开销指标考虑较少；Heuristic算法采用的是一种表调度策略，考虑处理器承担任务处理的优先级问题，是一种多处理优化调度的排队策略。Block算法主要应用在多处理器的流式处理系统开发中，基本特征是对基本块设定了不能重复调度的限制。

3.2 实验对比

本实验中选取的对比指标主要有4种：①启动时间；②实际执行时间；③通信开销；④存储性能。实验对比结果如下：

实验1：(启动时间)多处理任务调度中，启动时间指标越低，表明多处理器任务协调调度性能越好，此时多处理器进行调度算法具有更高的线程执行效率。图4为选取的几种对比算法在实验仿真平台上的启动时间指标实验结果对比情况。为了更清晰表征算法之间的实验结果差别，图中所示数据为本文算法相对于对比算法在启动时间上降低的幅度比例。

图4 启动时间指标对比

根据图4启动时间指标对比实验结果，从整体启动时间上看，本文算法在多处理任务调度的任务程序启动时间上，相对于选取的SGM算法、Heuristic算法以及Block算法分别降低4.3%-13.7%，4.6%-13.9%和12.5%-35.4%。从上述9种测试任务实验结果对比数据上看，在Histogram等相对简单的测试任务上，本文算法相对于选取的SGM以及Heuristic两种对比任务调度方案的启动时间性能提升幅度相对有限，仅约3.6%-5.9%，但是相对于选取的MatricMult、imgsmth等计算较为复杂的对比任务调度算法，其性能提升幅度相对更为明显，所提算法具有更加优异的性能表现。原因是这些任务程序具有更为复杂的计算流，可为本文算法提供更大的性能提升空间。

实验2：(执行时间)该指标主要测试所提算法的计算效率，对于多任务处理器任务调度算法，实时性指标具有非常重要的实际应用价值。图5为选取的几种对比算法在选取的实验仿真平台上的执行时间指标实验结果对比情况。为了更清晰表征算法之间的实验结果差别，图5数据为本文算法相对于对比算法在执行时间上降低的幅度比例。

图5 执行时间指标对比

根据图5执行时间指标对比结果，本文算法在测试平台上的执行时间指标要分别比选取的SGM算法、Heuristic算法以及Block算法降低6.5%-41.7%，7.6%-20.7%和40.3%-69.5%。主要原因是本文算法相对于SGM算法、Heuristic算法以及Block算法，在任务可调度性方面进行了优化设计，数据冗余计算现象降低，可获得更小的计算开销支出。SGM调度算法仅对多处理器任务调度的计算负载问题进行考虑；Block算法在处理不同迭代过程中的线程处理时，并未统筹流水化操作，导致算法调度计算过程的开销较大；与Heuristic算法相比，本文算法在处理器协调调度上具有一定优势，执行时间指标更加优异，算法具有更佳应用价值。

实验3：(通信开销)多处理器间任务调度主要面临的问题是不同处理器间数据的频繁通信问题，合理的处理器调度算法可降低整体处理器协调调度的通信量，进而降低通信带宽的负担。图6为选取的几种对比算法在选取的实验仿真平台上的通信开销指标实验结果对比，为了更清晰表征算法之间的实验结果差别，图6数据为本文算法相对于对比算法在通信开销上降低幅度比例。

图6 通信开销指标对比

根据图6通信开销指标对比实验结果可知，本文算法在测试平台上的通信开销指标要分别比选取的SGM算法、Heuristic算法以及Block算法降低24.5%-79.7%，24.3%-77.8%，22.4%-75.3%。其中，在Gauss、FFT等任务程序调度上，本文算法相对于对比算法的通信开销指标性能提升幅度并不大，大约仅可实现10%左右的性能提升，主要是因为这些任务程序的操作本身就不复杂，所需要的通信开销不大，因此算法提升幅度不是很明显。而在aveMotion等指标上，本文算法相对于选取的对比算法具有显著的性能提升，体现了算法的有效性。

实验4：(存储性能)存储性能是验证所提算法性能优势的重要指标，其对任务程序的流水性能具有直接限制。实验中，选取存储容量的变化范围是2 kB到64 kB，然后利用算法在64 kB存储容量下的存储性能指标作为基准，对实验结果进行归一化。图7为选取的几种对比算法在选取的实验仿真平台上的存储性能指标实验结果对比，为了更清晰表征算法之间的实验结果差别，图中所示数据为本文算法相对于对比算法在存储性能上降低的幅度比例。

图7 存储性能指标对比

根据图7存储性能指标对比实验结果，随着存储容量的增加，选取的几种对比算法的性能均呈现出单调递增的趋势。主要原因是，如果存储容量有限，会导致算法执行过程中，部分数据存储在片外存储器上，片外存储器相对于片内存储器在数据的存储速度上要慢很多，这会导致算法数据传输存在较大的延迟现象，会直接影响任务程序的流水性能。此外，shortEnergy、DCT等任务程序随着存储容量的变化幅度较小，主要原因是这些程序需要的操作较为简单，需要的数据存储量本身不大，造成片外存储器与片内存储器性能差别不是非常明显，因此存储容量增加对于算法的性能提升幅度相对更为有限。

4 结束语

本文针对混合临界多处理器系统开发了可调度性测试方法，主要贡献总结如下：①将已有可调度性测试推广到混合临界系统，得到了混合临界多处理器系统非抢占调度的第一个可调度性测试；②对所提问题模型进行可调度性测试扩展，并提出了一个虚拟期限分配问题；③提出了一种基于系统级截止期缩减参数的最优虚拟截止期分配策略。后续工作中，计划针对混合临界多处理器系统的非抢占式调度的其它现有可调度性测试，并为混合临界多处理器系统开发更严格的可调度性测试。同时，在多处理器运行过程中的协调调度算法研究上进一步提升算法性能。