基于Petri网多核映射任务分析及在torus架构中的应用

方 冉

(安徽工商职业学院电子信息系, 安徽 合肥 230041)

基于Petri网多核映射任务分析及在torus架构中的应用

方 冉

(安徽工商职业学院电子信息系, 安徽 合肥 230041)

多核任务映射是高性能计算领域的研究热点。基于torus互连的多核架构，本文提出了行资源映射和行优化资源映射两种算法，行资源映射算法首先以torus的最左边位置作为起点映射，然后按入度值从大到小的次序依次映射其后继，每映射完一个后继就映射其相应的前驱，以此类推，映射完所有的节点。行优化资源映射首先把出度最大的点放在torus最左边位置，把入度最大的点放在torus同一行最右边位置，然后映射出度最大的点的其他后继和入度最大的点其他前驱，以此类推，映射完所有的节点。利用时延petri网软件工具包对两种映射方法进行了分析和比较，实验结果表明，基于相同的循环任务数据流图和硬件架构，行优化资源映射算法获得的吞吐量是行资源映射算法的2倍，并且每个映射块运行时间减少近似一半，行优化资源映射算法具有合理性和可行性。

时延Petri网; 多计算单元；任务调度；torus互连网络

随着国内外高性能计算技术的迅速发展，传统的单核、顺序运算已经不能满足计算密集型或计算规模大任务等的要求，在这样的背景下，各种多核混合结构的片上网络系统被相继提出，面对复杂的结构，多核任务的调度问题显得尤为重要，该类问题是优化多核结构性能的关键，相关的研究成果很多。典型的研究列举如下：文献[1] 对有向无环图的并行实时调度进行了研究，该文提出了一种通用无环图任务分解转换为顺序图的方法，通过该种方法，对于抢占式最早截止时间优先算法而言，增加了4倍的资源成本，对于非抢占式最早截止时间优先算法而言，增加了4倍以上的资源成本。文献[2]研究了共享实时系统的调度边界利用和映射问题，与已经有的任务映射算法相比，该文提出的同步认知任务映射算法(synchronization-cogniz ant task mapping algorithms SC-TMA) 获得了较为优化的调度率和平均系统负载。文献[3]对可以同时利用线程级并行(thread-level parallelism TLP)和指令级并行(instruction-level parallelism ILP)自适应多核架构进行了研究，构建了离线和在线调度器，对内核的应用程序进行了智能化配置和分配，相比较静态和非对称多核体系结构，自适应多核架构减少了任务完成时间。文献[4]研究了多核片上系统(multiprocessor system on chip MPSoC)的核与核之间互相通信问题，该文对运算数据流图进行了数据依赖转换，并提出了启发式调度算法，该算法减少了任务调度长度，改进了内存的使用。文献[5] 提出了一种温度预报和任务分配同时进行的解决方案，结果获得了调度长度为5%～10%区间优化的调度方案。但是上述工作均没有对多核系统中映射成功的运算节点进行性能分析。如何对实际系统进行建模?如何结合系统模型来分析片上多核系统的运行机制显得极为重要。Petri网具有并发性、可达性、活性等特征，适合多核系统的描述与分析。

1 相关定义与网建模转换

为了便于问题研究，下面给出时延Petri网等相关定义。

定义1[6]四元组N=(P，T，F，M0)称作Petri网系统的引发规则为：

1) 变迁t.∈T称为使能的当且仅当

∀p∈·t：M(p)≥1，记作M[t>；

2) 在M下使能的变迁t可以引发，引发后得到一个新的标识M′，记作M[t>M′，对p∈P，

定义2 多核互连背景下的时延petri网TPN(timedpetrinet)可表示为一个七元组，具体包括以下两种情况：

1) 执行延迟TPN1：TPN1=(P，T，F，M，I，O，D1)，P∪T≠Φ，P∩T=Φ，F⊆(P×T)∪(T×P)，库所P为一个有限集合，表示可以存放运算操作输入或输出值的单元集合；变迁T为一个有限集合，表示计算执行的单元集合；F表示P和T数据传输的流关系；I是j种颜色输入的一个有限集合I={i1，i2，…，ij}；D1是定义在某个t∈T，在变迁集合T上的执行延迟函数，D1(x)表示当M[t>发生时，变迁t就触发了，并且执行延迟为x个时间单位，O={o1，o2，…，ok}表示任一运算任务在多核阵列所有输出集合。

2) 等待延迟TPN2：TPN2=(P，T，F，M，I，O，D2)，其他说明同3.1，唯一不同的是D2是定义在某个t∈T，在变迁集合T上的等待延迟函数，D2(y)表示当M[t>发生时，变迁t就触发了，并且等待延迟为y个时间单位，TPN2包括不同步和过渡等待延迟。本文涉及的其他相关理论详见文献[6-8]。

2.2 任务数据流图与时延petri网TPN之间的转换

2.2.1TPN网的建模基本单元图 为了便于问题的讨论，乘法运算的执行时延约定为2cycles，其他算术逻辑运算的执行时延约定为1cycle。图1给出了TPN网建模所用的基本单元关系图。

由图1(d)可知，约定来自库所pi的同一数据可被两个变迁共享被同时使用，由图1(e)可知，来自库所pi和pi+1的数据如果具有同步性，那么可以进行融合计算；若不具有同步性，则要进行转换。

2.2.2 相关转换

1) 不同步转换。在多处理器系统中，变迁执行数据的不同步情况常常发生，在这种情况下，要用到存取转换变迁，一个变迁需要耗时2cycles。以二目运算为例，运算的输入放在两个库所里，因为两个库所的数据来源具有不同步性，所以要有一个存储等待ti1变迁和一个库所pi配合完成，具体如图2所示。

2) 过渡转换。受限于多处理器系统的不同的互连方式，两个处理器之间的数据传输如果不可达，这时需要插入过渡节点进行数据传输，这时处理器节点功能为数据过渡传输，tn+1变迁和pi+3配合完成数据过渡传输，需要耗时2cycles(见图3)。

混合异构多核系统主要处理对象之一是循环任务子图，本文采用petri网工具对已经被映射到torus网络处理器系统的任务子图进行TPN网的转换，并进行相关的性能分析和讨论。

3 二维torus多核互连网络可调度性分析

3.1 二维torus网络简介

二维torus网络是一种常用的片上系统，这种结构的网络克服了共享介质网络的可扩展性难题，文中给出torus网络节点均可编译程序。torus网络节点之间的互连形式如图4所示，每个节点包含一个路由器网络接口模块和一个可计算和存储的IP 内核，路由器网络接口信道可以是输入类型，输出类型，双向类型。图4给出了二维torus网络的互连方式，torus在主处理器的控制下完成映射成功任务的编译与传输，主存储器来存储运算的中间和最后结果数据。

一个展开循环任务子图含有六种计算任务(见图5)，任务a的执行时间为2cycles，任务b、c的执行时间均为4cycles，任务d、e、f的执行时间均为1cycle。

3.2 torus多核互连结构的任务映射

一个循环任务子图(见图5)任务间的关系描述见表1，说明本文只讨论最大出(入)度为4的情形。

表1 循环任务子图间顺序关系描述

采用按行资源映射RRM (row resource mapping)和行优化资源映射RORM(row optimum resource mapping)两种方法对图5的循环子任务进行了映射。

RRM算法流程：

输入：一个任务子图

输出：一个任务子图执行周期和坐标

约束：4×4 torus；任务节点入(出)度最大值为3

Step1读入数据表。

Step2按行扫描数据表获得任务子图第一层的第一个节点，获得入度为0且节点号最小的点，以此点作为起点，并把该点调度映射到torus第一行最左边位置，其坐标为 (0，0)。

Step3比较已经映射成功的当前点直接后继的入度，可分为三种情况：

(1) 若当前点有多个后继，且后继的入度值不等

选择当前点入度值最大的直接后继，按行增加一路由点，映射该直接后继点；按节点号从大到小的次序扫描已经映射成功后继点的直接前驱点，把节点号大的点放入当前行；torus的行row+1；直接映射节点号小的前驱；若节点号大前驱的后继入度为1直接映射；若节点号大前驱的后继入度大于1加路由节点映射。选择入度值较大的直接后继，转(1)，以此类推。

(2) 若当前点有多个后继，且后继的入度值相等，优先选择节点号进行映射，其他同(1)。

(3) 若当前点只有一个后继，直接映射，其他同(1)。

所有的任务点全部映射完成转Step4。

Step4 End RRM。

RORM算法流程：

输入：一个任务子图

输出：一个任务子图执行周期和坐标

约束： 4×4 torus；任务节点入(出)度最大值为4

Step1读入数据表。

Step2按行扫描数据表获得任务子图第一层的第一个节点，首先获取出度最大的点放在torus互连网络第一行最左边位置，其坐标为 (0，0)；然后获取入度最大的点放在torus互连网络第一行最右边位置，依次映射。

Step3 处理出度最大的点其他后继：

若有一个后继，直接映射到当前行紧邻位置；若有两个后继，一个直接映射到当前行紧邻位置，torus的行row+1，映射放入另外一个后继。

Step4 处理入度最大的点其他前驱：

若有一个前驱，直接映射到当前行紧邻位置；若有两个前驱，一个直接映射到当前行紧邻位置，torus的行row+1，映射放入另外一个前驱。

所有的任务点全部映射完成转Step5

Step5 End RORM

分别采用RRM和RORM两种算法获得了图5的一个循环子图映射结果，具体如图6～图7所示。

3.3 基于TPN网的任务映射时间性能特性分析

图6和图7(a)是针对同一个任务子图映射成功的结果，RRM执行时间次序图和映射的网模型∑1具体如图8～图9所示。

RORM执行时间次序图和映射的网模型∑2具体如图10和图11所示，其中tw1和w1用来表示一次不同步转换。

由上述分析可知，RORM执行一块的时间为5cycles，RRM执行一块的时间为9cycles，更为重要的是采用RORM算法一次可以映射2个图5形状的循环子图，然而RRM只能映射一个子图，并且增加了6个路由节点，产生6次数据过渡延迟，同时产生3次不同步数据延迟，但是RORM算法只有1次不同步数据延迟，RORM算法优势明显。

4 结语

对于二维多核torus互连网络及类似结构而言，要充分利用其互连资源，特别是任务图出入度数较大情况。运用petri网工具包对RRM和RORM分析可知，对于具有图5性质的及类似的循环子图，相比较RRM， RORM在一个4*4结构的torus互连多核结构可以映射两个子图，且运行时间为5cycles，而RRM只能映射一个子图，且运行时间为9cycles，假设任务图按块执行，且任务图不能被分割(理由是考虑通信成本的较小化)，RORM算法任务的吞吐量是RRM算法的2倍，且每个映射块运行时间减少近似一半，RORM算法具有可行性。

[1] SAIFULLAH A，FERRY D，LI J， et al. Parallel real-time scheduling of DAGs[J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 25(12)： 3 242-3 252.

[2] HAN J J， ZHU D K，WU X D，et al. Multiprocessor Real-Time Systems with Shared Resources： Utilization Bound and Mapping[J]. IEEE Transactions on Parallel and Distributed Systems，2014，25(11)：2 981-2 991.

[3] PRICOPI M， MITRA T.Task Scheduling on Adaptive Multi-Core[J].IEEE Transactions on Computers， 2014，63(10)： 2 590-2 603.

[4] WANG Y， SHAO Z L， CHAN H C B， et al. Memory-Aware Task Scheduling with Communication Overhead Minimization for Streaming Applications on Bus-Based Multiprocessor System-on-Chips[J]IEEE Transactions on Parallel and Distributed Systems， 2014，25(7)： 1 797-1 807.

[5] GANESHPURE K， KUNDU S.Performance-Driven Dynamic Thermal Management of MPSoC Based on Task Rescheduling[J]ACM Transactions on Design Automation of electronic Systems， 2014，19(2)：11：1-11：33.

[6] 吴哲辉.Petri网导论[M].北京：机械工业出版社，2006：.

[7] 蒋昌俊.Petri网的行为理论及其应用[M].北京：高等教育出版社，2003：.

[8] 袁崇义.Petri网原理及应用[M].北京：电子工业出版社，2005：.

(责任编辑：李 丽，范 君)

Multi-core Task Mapping Analysis Based on Petri Net and Torus Architecture Applications

FANG Ran

( Department of Electronic Information, Anhui Vocational College of Commerce and Industry, Hefei Anhui 230041, China)

Multi-core task mapping is a hot research topic in the field of high performance computing tasks. Based on torus interconnect multi-core architecture, the RRM (row resource mapping) algorithm and RORM (row optimum resource mapping) algorithm were proposed. The mapping starting point of RRM is the leftmost position in torus at first. Then its successors are mapped in the order of indegree values. Corresponding predecessors are mapped after mapping a successor and so on. Finally, all of the nodes are mapped completely. The maximum outdegree node is the mapping starting point of RORM, and it is mapped onto the leftmost position of torus at first, and the maximum indegree node is mapped onto the rightmost position of torus. Then the other successors of the maximum outdegree node and the other predecessors of the maximum indegree node are mapped onto torus. Finally, all of the nodes are mapped completely. Two mapping methods were analyzed and compared by time petri net software tool kits. Based on the same cyclic data flow graph and hardware architecture, the results of experiment showed that the throughput of RORM is 2 times of RRM. Compared with RRM, the running time of each mapping blocks by RORM reduced approximately 50%. RORM is rational and feasible.

time petri net; multi-computing units; task schedule; torus interconnection network

2015-03-22

安徽省自然科学基金项目( 1408085MF124)

方冉(1983-)，男，安徽芜湖人,讲师，硕士，研究方向：控制工程及原理。

TP301

A

1672-1098(2015)03-0030-06