实时仿真并行调度算法研究

贾燕成，黎 英,2

(1.云南大学信息学院，昆明 650091；2.昆明理工大学信息工程与自动化学院，昆明 650093)

1 概述

随着计算机技术和网络的高速发展，仿真技术越来越显得重要，尤其是实时的并行仿真。研究大型的电力系统和构造真实的三维空间模型时，仿真是其研究的重要手段和工具。仿真在电力系统领域已被广泛应用，如用于系统规划、运行优化、故障分析等，并且可帮助有关人员做出合理的决策以避免或减少系统运行中可能出现的问题[1]。而视景仿真[2-3]采用计算机图形图像技术，构造仿真对象的三维模型并再现真实环境，达到非常逼真的仿真效果。

随着仿真任务复杂性的增加，单处理机的性能几乎已经发挥到极致，不能体现仿真的实时性。因此，文献[4]提出了多机并行仿真的概念，主要针对电力系统、视景仿真提出了一些并行仿真的算法，在一定程度上体现了对实时性的需求。

由于并行系统的广泛应用，文献[5]提出了基于嵌入式以太网的并行仿真计算的概念。并行计算是指用多个处理器并发地执行不同的任务，其高效的计算潜能依赖于对并行任务的调度方法。网格计算[6]中常用的调度方法就是并行调度，但在网格计算的调度中一般针对有向无环的任务图(Directed Acyclic Graph,DAG)[7]，任务图中的每个任务都是非周期的，因此提出的调度算法具有一定的局限性。

针对一种有向带环且交叉反馈的DAG任务图，任务且具有周期性的特点，本文提出了一种基于负载均衡性的任务动态组合调度方法。

2 任务图描述

2.1 系统调度的结构图

为了分析基于有向带环且具有复杂交叉反馈任务图的并行调度算法的可行性，采用异步电机的动态数学模型[8]为实例进行研究，其异步电机的动态模型如图1所示。

图1 异步电机在同步旋转坐标系下的结构

2.2 概念和定义

在建立任务图时，可借助图论的方式对任务图进行描述。将任务的有向有环图用五元组 TG=(V,E,W,C,T)来表示[9]。其中：

V=[Vi]表示任务图中节点(任务图中的节点是指任务)的集合，Vi表示第 i个任务，|V|表示图中节点数目。

E=[ei,j]表示任务图中边(任务图中的有向边是指2个任务之间存在消息传递)的集合；ei,j是指节点 i指向节点j的有向边，表示任务i和任务j存在相关性；|E|表示图中边的数目。由于每条边是有向的，因此用“<”表示任务之间的依赖关系，即Vi

W=[Wi]表示任务的粒度，即子任务计算量的集合，Wi表示任务Vi的计算量。

C=[Ci,j]表示任务之间通信数据量的集合；Ci,j表示任务i发送给任务j的数据量。

T=[ti]表示任务的Vi的循环周期。

2.3 任务图的构建

由异步电机的结构，可根据DAG任务图[10]的构图思想建立异步电机并行仿真的任务图。从结构图可知，整个电机由6个惯性环节和1个积分环节构成，首先对结构图进行化简，把反馈系数进行有效的合并。在任务图的构建中可以把7个环节看作是7个节点，不改变节点间数据的连接关系。构建的任务图如图2所示。

图2 异步电机任务图

在以上节点任务图中节点 1～节点 6的基本任务是对惯性环节的求解，而节点7是对积分环节的求解，这样也就转换成对一个微分方程组的求解。在对任务图的构建过程中，需考虑各子任务的均衡性，这也是对任务的合并与分解的重要参考依据。由于结构图具有一定的对称性和相似性，其化简过程也就相对简化了。

其中，节点1、节点4所包含的任务是为惯性环节G1( s)、系数RFe、L1σ和固定输入W1；节点2、节点5所包含的任务为惯性环节G2(s)、系数Lm、C；节点 3、节点 6所包含的任务为惯性环节G3( s)、系数、D、A；节点7包含任务为一个积分环节、系数E及固定输入T1。

3 调度算法设计

定义 1 连接矩阵 Cn×n表示各任务关系图中各子任务之间的连接关系：

在连接矩阵中，每行或每列代表一个子任务与其他子任务的数据传递关系。在矩阵中，每行表示一个节点任务的输入关系，若其他节点对该节点有数据输入关系，则 Ci×j=1，反之，则 Ci×j=0；每列表示一个节点任务的输出关系，若该节点对其他节点有数据输出关系，则 Ci×j=1，反之则 Ci×j=0。

定义2 任务组是任务图中多个相关任务的合并，且被映射到同一个处理机执行的任务集合。

规则 1 任务组组建规则：实验环境采用 BF538作为节点机，具有双网口，可允许各节点机有2个数据输入或输出。由于在并行调度过程中会产生一定的通信开销，因此组建的任务组其执行开销应优于通信开销，也即各节点机的执行开销应满足weight /2 ＜ xi＜ 2weight ，其中，weight为从机之间的通信开销，并且根据连接矩阵中各个任务之间的连接关系应尽量减少任务之间通信开销。

规则 2 负载动态均衡规则：在任务的调度过程中，根据处理器不断地记录整个系统状态信息，将执行开销较大的任务组进行分解动态映射到其他节点机上。与该节点机上的原始任务组进行组合形成该节点机上的后继任务组，且其组合的原则按照规则1进行，原始任务组和后继任务组在该节点机上循环执行，使各个节点机上的任务组达到动态平衡，以避免节点机的空闲等待时间，同时也缩短了各个节点机的通信开销，最大化提高了并行机的效率。

由于是基于以太网进行的并行调度，且各个节点机互联，因此处于一个小型的局域网内。根据任务图建立的连接矩阵，查询各个节点之间的数据传递关系，在进行数据的交换过程中，处理机通过广播数据帧，相应的MAC地址的处理机接受数据即可完成通信。对整个系统每个子任务的执行开销为：

经实际通信测试：

任务调度算法的主要思想：由于研究的任务图是有向有环且带交叉反馈，在任务的并行调度过程中，每个任务都具有依赖关系，因此应根据结构图初始建立的任务图构建连接矩阵，根据连接矩阵计算各节点的输入、输出关系。

按照任务组的构建规则建立并行调度的任务组，再依次将各任务组映射到各个节点机上，通过比较各个任务组的执行开销，进行任务的动态组合，以选取最优的从机数目完成任务的调度。

算法步骤如下：

(1)开始；

(2)输入：输入连接矩阵Cij；

//根据连接矩阵中每行之和

(4)while(节点任务不为空)

{取出其中一个节点作为当前节点；

if(Ci>2) //Ci代表一个节点与其他节点的连接//关系

for(j=1; j≤n; j++) //取连接矩阵的列

{if(Cji!=0) 将此时对应的节点与 Ci所对应的节点任务组合，在连接矩阵中查询组合节点所对应的局部关系并求和G，取其max(G)进行组合；

if(G相等) 将组合的该任务组与其他节点任务之间建立局部连接关系并求和G’，取其min(G’)进行组合；

分别记录任务组合的各个任务编号；

}

}

(5)输出：重新计算任务组的连接关系，输出连接矩阵 Pij；

(7)if(Pi≤2) break; //继续判断各任务组是否双//输入、输出关系

else do{将其他节点任务与Pi所对应的节点任务重新组合；}while(该任务组的输入和输出小于或等于 2)；

(8)计算每个任务组的执行开销Xi；

(9)if (Xi>weight/2&&Xi<2×weight) break；

//条件满足查询下个节点任务

else do{将其他节点任务与该节点任务重新组合；}

while(该任务或者任务组输入和输出小于或等于2&& Xi>weight/2&& Xi<2×weight)；

(10)初始化各节点机的执行开销：fi=0，将各任务组依次映射到各个节点机上；

(11)for(j=1; j≤p; j++) //p为组合的任务组数

{在节点机上依次运算各任务组，并记录各任务组的执行开销 costi, i ∈ (1,2,···,p )}

(12)循环比较各任务组的执行开销；

if (各个节点机任务均衡) exit；

else {取出max(c osti, i ∈ （1 ,2,···, p） )，将其任务组进行分解；

while(子任务不为空)

{取其一个子任务与其他节点机上的任务组进行组合，并建立各自的局部链接矩阵，并求其和 Mi,i∈(1,2,…,P−1)；

if(max(Mi)) 将其子任务与该节点机上的任务组组合；

}

go to (12)；

}

(13)算法结束。

在该算法中，采用了构建连接矩阵建立数据的连接关系，并通过各任务组的计算量和通信量将各任务组进行动态组合，实现了各负载的均衡。由于仿真任务的周期性，使各个节点机上的原任务组和后继任务组循环执行，充分利用了有限资源，使系统总的执行开销最小，进而使系统获得了较好的并行效率。

4 实例分析讨论

4.1 任务图的重构与动态组合

按照以上连接矩阵的构建方法，根据异步电机的任务图按照任务图中的节点顺序 1～7建立相关的连接矩阵，如下所示：

根据以上调度算法，具体执行如下：

(2)根据以上计算节点的输入或输出关系不满足实验的硬件条件(BF538为双网口)，取第1个节点，根据连接矩阵的行、列关系，节点1与节点2、节点4关系紧密，建立局部的连接矩阵及组合后内部连接矩阵，并求其和值比较，则取最小值将节点1与节点2进行组合。

(3)取节点 3，查询该节点的输入、输出关系(即连接矩阵中节点3的非零元素)，由于节点1与节点2已组合，则节点3与节点6、节点7存在连接关系，并建立节点3与节点6、节点7的内部连接矩阵和局部连接矩阵，则取其最小值将节点 3与节点 7进行组合。

(4)取出节点4，根据连接矩阵查询节点4的连接关系，删除已经组合的节点，则节点4与节点5、节点6存在连接关系，建立节点4与节点5、节点6的内部连接矩阵。比较得出组合后内部连接矩阵和值G不相等，取出max(G)(减少节点间的通信开销)，则取其最大值将节点4与节点5进行组合。

(5)取出节点6，则查询连接矩阵中节点6的连接关系，节点6与已组合任务组3、任务组7和任务组4、任务组5存在连接关系，则建立节点6与2个任务组的内部连接关系。比较得出组合后内部连接矩阵和值 G不相等，取出 max(G)。则取其最大值将节点6与任务组3、任务组7进行组合。

根据以上任务的组合建立相关的连接矩阵，进行循环查询并计算连接矩阵中每行每列之和(再次判断是否满足硬件条件)，根据如下矩阵得出每个节点为双输入、输出关系，满足条件。

组合的任务图如图3所示。

图3 重构的任务图

(6)将各任务组映射到各节点机上计算，查询到节点机3#上的执行开销大于节点机1#、2#，任务的不均衡造成节点机之间的相互等待，需按照调度算法中的负载均衡原则将节点机3#上的子任务进行动态分配。可根据任务的组合规则建立局部的连接矩阵，经过调度算法中的循环查找最终将任务 3映射到节点机 1#上与原始任务组组合成后继任务组1～任务组3，任务6映射到节点机2#上组合成后继任务组4～任务组6。由于任务7保持在该节点机上，此时各个节点机上的任务组执行达到动态平衡。则按照此调度算法进行并行调度的进程如图4所示。

图4 并行调度的进程

根据图4中的并行调度进程可知，各个节点机上的任务都是同时开始执行，但节点机3上的任务组合3、组合6、组合7需要节点机1、节点机2的输出数据，又需避免节点机之间的空闲等待时间，则节点机3开始运算的初始数据为 0，造成该系统在并行仿真计算中的两步滞后，但是在一定程度上提高了该并行系统的效率。

根据以上调度进程得到最终的分配结果如表 1所示。

表1 任务分配结果

4.2 数据测试分析及对比

在并行仿真运算的过程中，由于各从机的负载量较小，采用 46个字节的通信时间作为从机之间互通消息的基准。因此影响系统并行效率的是各从机的执行开销，对并行系统而言加速比和效率是衡量并行计算系统性能最重要的评价标准，这也体现了在并行计算系统上解决实际问题所能获得的好处。

并行加速比：

其中，Ts是单处理机串行执行时间；Tp(q)是指并行使用q台处理机执行所用的时间。则并行效率为：

根据以上关系可知，随着各从机执行开销的增加，并行效率会适当提高，但是执行开销受仿真精度和仿真环节滞后性的约束，并行效率不会随之无限增大，而是无限趋于某个值。由于整个系统由几个典型的环节构成，因此可采用通用的数字仿真的方法把每个环节编制单独程序作为单个任务执行。在并行计算系统的基础上结合RK4原理实现对单个任务的运算。按照图4中的调度进程进行调度。

(1)对异步电机进行串行仿真计算一步需要111 μs，运算 10次需 1 110 μs。

(2)按照以上并行调度算法进行仿真计算两步需要 83 μs，运算 10 次需 445 μs。

则该系统的并行加速比为：

并行效率为：

若采用流水线调度，将图2分成2条流水线的形式，一条流水线依次求解1、2、3环节，另一条流水线求解 4、5、6、7环节，当求解完整个结构图后系统达到并行。此方式将整个并行仿真任务分解到多个并行节点上求解，这样每个节点机上的负载量较小，在一定程度上提高系统效率。按照多条流水线并行运算的方式对任务进行调度，则整个系统的并行时间将取决于最后一个环节的运算时间。

(1)对异步电机进行串行仿真计算一步需要111 μs，运算 10次需 1 110 μs。

(2)按照流水线调度进行仿真计算，运算10次需538 μs。

并行效率为：

实时性数据测试：

系统实际运行时间 t=步长×运算次数=0.000 044×18 000=0.792 s

按照图4调度并行系统运算时间t=0.747 030 s。

通过对比以上实验数据及系统的性能指标分析可知，该负载均衡的动态调度算法使用较少的处理机完成相应的任务，优于流水线调度，提高了系统效率。系统实际运算时间大于并行系统运算时间，证明了该并行系统满足实时性的要求。与串行运算相比，在时间复杂度上有了大幅度的降低。这一点可说明该并行计算系统比较适合用于通信量小但运算量大的场合。

5 结束语

本文针对有向带环且交叉反馈任务图提出了一种并行调度方法。充分考虑实验的硬件环境及各节点机上负载的均衡性，采用任务的重组及动态分配的方式对任务进行调度，以选取最优的从机数目完成任务的调度。此并行调度算法既节省了节点机之间的通信开销，又避免了节点机的空闲等待时间。通过并行效率分析，此方法对运算量较大的系统具有很好的并行调度效果。

但是该并行仿真方法无法避免仿真的滞后现象，下一步的工作是优化提高仿真的精度。由于通信条件及实验硬件环境的限制，在无限制地增加执行任务数的时候，节点机之间的通信需通过节点机的转发，因此今后将改善实验的运算环境，优化节点机之间的通信时间。

[1]Huang Zhenyu, Kosterev M, Guttromson R, et al.Model Validation with Hybrid Dynamic Simulation[C]//Proc.of IEEE Power Engineering Society General Meeting.[S.l.]:IEEE Press, 2006: l-9.

[2]Cui Rongxin, Xu Demin, Xu Zhe, et al.Simulation of Autonomous Underwater Vehicles Formation Control Based on Simulink and VRML[J].Journal of System Simulation, 2007, 19(13): 2881-2884.

[3]Xu Zhe, Yan Weisheng, Gao Jian.Simulation of 6DOF AUV Based on Matlab[J].Journal of System Simulation,2007, 19(10): 2241-2243.

[4]Li Yalou, Zhou Xiaoxin, Wu Zhongxi.Personal Computer Cluster Based Parallel Algorithms for Power System Electromechanical Transient Stability Simulation[J].Power System Technology, 2003, 27(11): 6-12.

[5]Wang B, Zha G C.A General Sub-domain Boundary Mapping Procedure for Structured Grid CFD Parallel Computation[C]//Proc.of the 25th Applied Aerodynamics Conference.Miami, USA: [s.n.], 2007.

[6]Andronikos T, Koziris N.Optimal Scheduling for UETUCT Grids into Fixed Number of Processors[C]//Proc.of the 8th Euromicro Workshop on Parallel and Distributed Processing.[S.l.]: IEEE Press, 2000: 237-243.

[7]Ahmad I, Kwok Y K.Benchmarking and Comparison of the Task Graph Scheduling Algorithms[J].Journal of Parallel and Distributed Computing, 1999, 59(3): 381-422.

[8]黎 英, 时维国, 谭昆玲.考虑铁损时异步电动机的数学模型及其仿真研究[J].电气传动, 1998, (3): 7-9.

[9]何 琨, 赵 勇, 黄文奇.基于任务复制的分簇与调度算法[J].计算机学报, 2008, 31(5): 733-740.

[10]杜 杰.网格环境中基于DAG的并行任务调度算法研究[D].上海: 上海交通大学, 2009.