一种多核体系并行仿真系统

摘要

一种多核体系并行仿真系统，包括端口模拟模块、数据乱序调度模块、数据转送模块和计时模块。端口模拟模块记录并更新多核体系中各成员输出端口和输入端口的空闲情况，数据乱序调度模块对通信数据进行乱序调度，以提高端口的利用率，数据转送模块对通信数据进行转送，利用局部存储器减少任务等待时间，计时模块记录每个成员的时间进度，为数据的转送模块和乱序调度模块提供时间参考。利用本发明提出的多核体系并行仿真系统，可以快速的搭建出针对定硬件环境的仿真模型，从而加速了对多核体系静态调度算法的验证。

说明书

技术领域

本发明涉及一种多核体系并行仿真系统，适用于对多核处理器或计算机 集群进行静态调度算法的快速验证。

背景技术

并行处理和多核技术已经成为当前计算机发展的主要趋势。要充分发挥 多核体系的计算能力，需要配合以高效的任务调度算法。当前同构多核体系 的任务调度技术已较为成熟，可以使用动态调度对任务的执行进行管理和控 制。而在异构多核处理器和计算机集群中，动态调度技术还不成熟，静态调 度仍然是主要的选择。对静态调度算法的效率进行验证是任务调度中不可缺 少的一步。通常对静态调度算法的验证是直接将算法在硬件上运行或使用硬 件对应的指令集仿真器进行验证。使用硬件进行验证时，算法的运行速度会 非常快，但是由于异构多核处理器或计算机集群的硬件通常不同于常见的同 构多核处理器，在进行验证时操作较为复杂，导致了验证难度增加，效率低 下。使用指令集仿真器进行调度算法验证时，指令集仿真器会模拟每条指令 的执行。而调度算法只关注任务的完成时间，并不关心任务被编译成何种指 令或指令是如何执行的，因而使用指令集仿真器会增加过多的不必要的步骤， 导致验证时间增加。由于现在的调度算法众多，效率不一，要进行调度算法 的对比需要进行大量的验证，这进一步增加了硬件验证和指令集仿真器验证 的成本。

发明内容

本发明的技术解决问题是：提供了一种多核体系并行仿真系统，在保证 可移植性和可配置性的基础上，实现了对多核体系静态调度算法的快速验证， 从而克服了原有的多核体系静态调度算法验证时间成本高、操作复杂等缺点。

本发明的技术解决方案是：

一种多核体系并行仿真系统，包括端口模拟模块、数据乱序调度模块、 数据转送模块和计时模块；所述多核体系是指多核处理器或者计算机集群， 多核处理器中包括多个处理器核心，计算机集群中包括多台计算机，多核体 系的成员是指处理器核心或者计算机；

端口模拟模块记录并更新多核体系中各成员的输出端口和输入端口的空 闲情况；数据转送模块通过转送成员对通信数据进行转送，利用模拟的局部 存储器减少任务等待时间，同时，转送成员记录在数据转送模块中，所述转 送成员是指多核体系中能把自身接收到的通信数据进行转发操作的成员；

数据乱序调度模块根据端口模拟模块提供的各成员的输出端口和输入端 口的空闲情况和数据转送模块中记录的转送成员对通信数据进行乱序调度， 以提高端口的利用率；计时模块记录每个成员的时间进度，为数据转送模块 和数据乱序调度模块提供时间参考。

所述端口模拟模块记录并更新多核体系中各成员的输出端口和输入端口 的空闲情况，具体为：端口模拟模块模拟各成员的输出和输入端口的数据传 送，记录各端口的空闲时间段，即时间窗口，每进行一次通信，端口模拟模 块就会对端口空闲时间窗口进行实时更新，将此次通信占用的时间段从空闲 时间段中剔除。

所述数据乱序调度模块对通信数据进行乱序调度具体为：

数据乱序调度模块在每开始一个数据传输之前，对最初产生这一数据的 成员和转送成员进行检测，如果初始成员和所有的转送成员中有任意一个与 目标成员是同一成员，那么令这个成员作为通信数据的传送源；如果目标成 员与初始成员和所有的转送成员都不同，那么对端口模拟模块中初始成员和 所有转送成员的输出端口的空闲时间段进行检测，查找这些成员中通信数据 可用时间与目标成员时间之间的可用窗口，使用其中最小的窗口进行数据通 信，如果没有可用窗口，则使用通信数据可用时间之后的首组窗口进行数据 通信，所述目标成员是指待接收通信数据的成员。

所述数据转送模块通过转送成员对通信数据进行转送，利用模拟的局部 存储器减少任务等待时间，具体为：数据转送模块模拟出局部存储器，将当 前成员接收到的所有通信数据进行存储，当后续任务使用相同通信数据时， 可由该成员转送。

所述最小可用时间窗口是指查找所有的满足通信要求的时间窗口，使用 其中能进行通信的最小的窗口，即时间最短的窗口。

本发明与现有技术相比的有益效果是：

(1)提供了一种快速搭建多核并行仿真系统的方法，这种系统能对多核 静态调度算法进行高效的验证。

(2)本发明提供的仿真系统可用软件方法实现模拟硬件环境，降低了时 间成本和使用复杂度。

(3)仿真系统模块功能可配置，能实现对不同多核体系硬件的仿真。

附图说明

图1为本发明系统架构示意图；

图2为本发明使用的任务依赖关系表示方式；

图3(a)为通信的最早可用时间乱序调度示意图；

图3(b)为通信的最小可用时间乱序调度示意图；

图4为本发明最小可用时间调度中的时间窗口种类；

图5为本发明通信乱序调度中数据可用时间与通信窗口的关系示意图。

具体实施方式

下面结合附图对本发明的具体实施方式进行进一步的详细描述。

如图1所示，本发明提供了一种多核体系并行仿真系统，包括端口模拟 模块、数据乱序调度模块、数据转送模块和计时模块；所述多核体系是指多 核处理器或者计算机集群，多核处理器中包括多个处理器核心，计算机集群 中包括多台计算机，多核体系的成员是指处理器核心或者计算机；

端口模拟模块记录并更新多核体系中各成员的输出端口和输入端口的空 闲情况；数据转送模块通过转送成员对通信数据进行转送，利用模拟的局部 存储器减少任务等待时间，同时，转送成员记录在数据转送模块中，所述转 送成员是指多核体系中能把自身接收到的通信数据进行转发操作的成员；所 述端口模拟模块记录并更新多核体系中各成员的输出端口和输入端口的空闲 情况，具体为：端口模拟模块模拟各成员的输出和输入端口的数据传送，记 录各端口的空闲时间段，即时间窗口，每进行一次通信，端口模拟模块就会 对端口空闲时间窗口进行实时更新，将此次通信占用的时间段从空闲时间段 中剔除。最小可用时间窗口是指查找所有的满足通信要求的时间窗口，使用 其中能进行通信的最小的窗口，即时间最短的窗口。

所述数据转送模块通过转送成员对通信数据进行转送，利用模拟的局部 存储器减少任务等待时间，具体为：数据转送模块模拟出局部存储器，将当 前成员接收到的所有通信数据进行存储，当后续任务使用相同通信数据时， 可由该成员转送。

数据乱序调度模块根据端口模拟模块提供的各成员的输出端口和输入端 口的空闲情况和数据转送模块中记录的转送成员对通信数据进行乱序调度， 以提高端口的利用率；计时模块记录每个成员的时间进度，为数据转送模块 和数据乱序调度模块提供时间参考。

数据乱序调度模块在每开始一个数据传输之前，对最初产生这一数据的 成员和转送成员进行检测，如果初始成员和所有的转送成员中有任意一个与 目标成员是同一成员，那么令这个成员作为通信数据的传送源；如果目标成 员与初始成员和所有的转送成员都不同，那么对端口模拟模块中初始成员和 所有转送成员的输出端口的空闲时间段进行检测，查找这些成员中通信数据 可用时间与目标成员时间之间的可用窗口，使用其中最小的窗口进行数据通 信，如果没有可用窗口，则使用通信数据可用时间之后的首组窗口进行数据 通信，所述目标成员是指待接收通信数据的成员。

在进行静态调度算法验证时，调度结果已经给出。为表示清晰，对每个 任务进行编号且用匹配串和调度串表示一个调度，如图2所示，s0、s1等表 示任务，Com0、Com1等表示任务间的通信。匹配串指明了任务到成员的 分派，如s4：1表示4号任务被分派到了成员1上。调度串指明了任务被调度 的顺序(调度串中任务的顺序必须满足依赖关系)。各任务在每个成员上的 运行时间是已知的。任务间依赖关系存储在邻接矩阵Adj中，如果Adj的行 标对应的任务向列标对应的任务有数据传输，则Adj的元素为1，否则为0。 任务的输出存放在数组Output中，Output[i]中存放的是任务i的输出。假设 任务数量为T，多核体系中成员数量为M。假设以上数据已知是做静态调度 验证的前提。

端口模拟模块的功能由以下三种数据结构实现：

用链表数组t_list InPortldle[M]表示各成员的输入端口，其中存放所有 成员输入端口的空闲时间段(空闲时间窗口)。数组的每个元素表示一个链 表。每个链表对应一个成员的输入端口。链表每个节点中含有两个值，分别 表示此链表对应端口的一个空闲时间段的起始时间和结束时间。

用链表数组t_list OutPortIdle[M]表示各成员的输出端口，其中存放所有 成员的输出端口空闲时间段。数组的每个元素表示一个链表。每个链表对应 一个成员的输出端口。链表每个节点中含有两个值，分别表示此链表对应端 口的一个空闲时间段的起始时间和结束时间。

用大小为M×M的二维组CommFctr存储不同路径的通信延迟因子。

当分派到成员m上的任务i向分派到成员n上的任务传输数据时，延迟为：

Delay＝Output(i)^＊CommFctr(m，n)

两个端口数组能模拟各成员通信端口的忙闲状态，从而能对可用通信窗 口进行搜索和选择，实现通信数据的乱序调度。在端口数组中，每个链表最 后一个节点的结束时间应设置为所使用编程语言的正整数上限。其作为哨兵 来表示成员端口最后一个空闲时间窗口的时间上限为正无穷大。

数据乱序调度模块负责对所有的通信数据进行乱序调度。通信的乱序调 度能减少所有任务的执行完成时间。通信的乱序调度分为最早可用窗口乱序 调度和最小可用窗口乱序调度。假设有2个成员m0和m1，要验证的任务 调度结果如图2所示。对通信数据Com2进行乱序调度，选择最早可用窗口 时的调度结果如图3(a)所示，对Com2使用最小可用窗口乱序调度的结果如 图3(b)所示。对比两幅图可以发现，图3(b)前10秒钟m0的输出端口出现 了一个长度为3(3到6秒)的空闲时间段，而图3(a)中m0的输出端口在 前10秒内却没有大小为3的端口空闲时间。从统计学角度看，最早可用窗 口调度时间相对于最小可用窗口调度会产生更多的小窗口，这会减小输出端 口和输入端口的窗口交叠区间长度，不利于端口空闲时间段的集中使用。因 而，总体而言，最小可用窗口乱序调度会有更好的调度结果。本发明的仿真 系统中使用了最小可用窗口乱序调度。乱序调度会增加调度算法本身的运行 时间(编译时间)，但会减小所有任务的执行完成时间。

为了对单个通信数据查找最合适的传输窗口，本发明使用了如下的单个 通信数据最小可用窗口乱序调度方法，步骤如下：

A1：[查找可用窗口]查找初始成员和转送成员的输出端口链表和目标成 员的输入端口链表，如果在此通信数据可用时间之后和目标成员时间之前两 个端口中有同时可用的通信窗口，那么找到其中最小的，作为最终选择的可 用通信窗口，转到A3。否则(在通信数据可用时间之后及目标成员时间之前 无可用窗口)，转到A2。

A2：[使用首组窗口]使用查找到的首组可用窗口进行数据传输。

A3：[返回]返回当前进行传输的两个窗口、窗口的交叠类型、源任务 所在成员及通信数据传输完成时间。

根据算法A的返回结果，更新进行数据传输的两个端口的空闲时间链表。 更新端口链表时，不同的窗口交叠种类要对端口链表进行不同的处理。图4 中显示了可用窗口与通信数据可用时间avlTime不相交时，9类窗口交叠情 况。例如，针对图4中(a)的情形，更新输出端口和输入端口链表时，应将 两个窗口的顶部都加上通信数据的传输时间。对于图4中(d)的情况，更新端 口链表时，应更新左窗口顶部和右窗口底部，并在输入端口空闲时间链表中、 右窗口之后添加一新的窗口，这个窗口对应通信数据传输后将原右窗口新分 割出来的窗口。对于图4中(e)的情况，两个窗口中较小的窗口恰好与通信数 据传输时间相同，那么在更新这个窗口所在的链表时，要将这个窗口对应的 节点删除，表明此窗口被完全使用，无剩余空闲时间。

处理窗口交叠时，除了要考虑窗口的交叠种类，还要考虑被选择进行数 据传输的一组窗口是否是离通信数据可用时间avlTime最近的可用窗口。 avlTime可能与窗口相交、与窗口顶部相切(底部相切时，此窗口肯定不可 用)、与窗口顶部相离三种情况。由于相切和相离时对链表进行相同的处理， 可以不做区分。因而，根据相交和相离(相切)，avlTime与窗口的关系可 以分为图5所示的4种情形，在更新链表时，这4种情况要与图4的9种情 形综合考虑。

执行一个任务前要完成所有依赖数据的传输。在本发明中，将某个任务 的所有依赖任务都存储到一个链表中。用dpndTaskNum表示被依赖的任务 号。当计算单个任务执行完成时间时，步骤如下：

B1[建立依赖链表]扫描邻接矩阵Adj中以本任务号为列标的列，如果 此列中所有元素都为0(表明当前任务无依赖)，转到B5。否则，建立一个 依赖任务链表。当某元素的值为1时，新建一个依赖任务节点，将此元素的 行标赋值给dpndTaskNum，并将此节点加入依赖链表。用IeastCom表示所 有Com中能最早完成的时间。

B2[查找最早完成的Com]将IeastCom值设置为最大正整数。扫描依 赖链表，若依赖链表为空(表明所有依赖数据都传送完成)，转到B5，否则， 对链表中的每个节点表示的任务，以此任务为初始任务，当前的任务为目标 任务执行算法C(得到所有依赖Com的传送完成时间及对应的传输窗口和 数据传送的源成员)，如果算法C的完成时间在目标成员时间之前或者算法 C得到的源成员与目标成员相同，那么调度这个Com，转到B4。否则(所 有Com的传送完成时间都在目标成员时间之后，且所有的依赖任务及依赖 任务的转送任务都与当前目标任务不在同一成员上)，转到B3。

B3[查找最早完成的Com]计算所有依赖Com的传送完成时间，找到能 最早的Com，将其传输完成时间赋值给IeastCom，调度此Com。

B4[更新端口链表和依赖链表]更新当前调度的Com对应的输出端口和 输入端口空闲时间链表，在依赖链表中删除当前Com的源任务号对应的节 点(此Com调度完成)。转到B2。

B5[执行任务]将目标成员的成员时间加上当前任务在相应成员上的执 行时间，算法结束。

数据转送模块用链表数组t_list forward[T]来实现数据转送功能，转送 数组的索引与任务号相对应。若任务无输出，对应数组的元素为空。否则 forward[i]表示的链表中存放到当前时间为止，能转送任务i输出的所有任务。 链表节点中用taskNum表示转送任务的任务，avlTime表示依赖数据的传输 完成时间，即此通信数据在目标任务所在成员上的开始可用时间。每当完成 一个数据传输，就在初始任务(其输出被转送的任务)的转送链表中加入一 新的节点，新节点的taskNum为通信通信数据传输的目标任务，新节点的 avlTime为数据开始传传输时间与数据传输花费的时间之和。下面给出数据 转送模块实现时的步骤：

C1[查找是否在同一成员上]查找初始任务和初始任务对应转送链表中 的转送任务，如果初始任务或某个转送任务与目标任务在同一成员上(查看 匹配串)，则使用这个传输，返回源成员号，算法结束。否则转到C2。

C2[计算初始任务传输完成时间]计算使用初始任务传输时的传输完成 时间(调用算法A)。如果完成时间小于目标成员时间，使用这个传输，转 到C5，否则转到C3。

C3[使用转送任务传输]依次计算使用各转送任务作为源任务进行传输 时的完成时间。如果某个转送任务完成传输的时间(考虑了乱序调度，见算 法A)在目标成员之前，就使用这个传输，转到C5。否则转到C4。

C4.[使用最早可用窗口](此时不论初始任务还是转送任务的传输完成 时间都比目标成员时间大，目标成员要等待传输完成)对比初始任务和各转 送任务的传输完成时间，以其中最早完成传输的任务作为此次传输的源任务。

C5.[更新转送链表]将目标任务对应的节点加入初始任务的转送链表。 节点中taskNum为目标任务的任务号，节点中avlTime为传输的完成时间， 算法结束。

步骤C1中目标任务和源任务(初始任务或转送任务)在同一成员上时， 完成传输却没有将目标任务加入到初始任务转送链表中的原因是源任务已经 能对相同数据进行转送，且数据可用时间较目标任务更早。

计时模块记录每个成员的成员时间和通信数据传输完成时间，在处理 器核心上每执行完成一个任务，则更新此核心的时间。每完成一个数据传输， 则更新数据在目标成员上的可用时间。数据乱序调度模块中进行对比的目标 成员时间就取自于计时模块。

端口模拟模块、数据乱序调度模块、数据转送模块和计时模块协同工作， 对调度串中的任务按照调度顺序依次执行算法B，直到最后一个任务。找到 所有成员时间中的最大值，即所有任务的最终完成时间。

本发明未详细说明部分属本领域技术人员公知常识。