二维RCA空域映射Petri网时间性能分析

陈乃金

安徽工程大学 计算机与信息学院，安徽 芜湖 241000

二维RCA空域映射Petri网时间性能分析

陈乃金

安徽工程大学 计算机与信息学院，安徽 芜湖 241000

1 引言

在传统的计算系统中，计算机求解的实现主要是两种方法[1]。其一是专用集成电路（Application Specific Integrated Circuit，ASIC）方法，该方法的优点是针对某一特定计算任务，可得到很高的计算速度及效率，但该方法缺点是不可编程的，灵活性差，计算任务一改变，就要改动硬件；其二是单核或多核通用处理器（General Purpose Processors，GPP）方法，通过选择处理器的指令，根据某种算法构成一个新的指令序列，去完成特定的计算，该方法的优点是通过修改软件可达到改变系统功能的目的，不需改动硬件，该方法具有可编程性，并且灵活性好。但缺点是这种可编程性是以牺牲系统的性能和速度为代价换来的。可重构计算恰好弥补上述两种方法缺点[2]，它既具有ASIC高的计算速度及效率，又具有微处理器方法的可编程性和良好的灵活性，可重构系统在高性能计算领域已经显示出了强大的数据处理能力，其中最具代表性的是美国超级计算机研究中心在1992年研制的Splash 2，在基因组的数据计算中比当时SPARC 10工作站的运算速度快2 500倍[3]，而且在实时嵌入式应用[4]等方面，已经展示了巨大的优势。

作为通用可重构器件的FPGA路由结构复杂，一个逻辑块周围的可编程连接点可以达到上千个，提供这样丰富的路由资源主要是为了能够实现任意连接，提高通用性。但是，这带来了系统重构时间和面积的增加、功耗消耗增大等缺陷，而且以FPGA为代表的细粒度可重构体系结构FGRAs（Fine Grained Reconfigurable Architectures）在进行位级运算时具有明显的优势，但是在处理规则和位数宽的字（Word）级算术和逻辑运算时效率较低，为了克服FGRAs的缺点，各种粗粒度可重构体系结构CGRAs（Coarse Grained Reconfigurable com-puter systems）被相继提出，而且给予了相关研究[1-10]。本文针对通用的CGRAs系统芯片通用架构进行了研究，给出了CGRAs通用架构及其简明的编译流程，基于Petri网着重分析允许行有依赖空域映射（文献[11]采用此方法）和行无依赖空域映射的时间特性，为了便于说明问题，本文以下映射均指空域映射。

2 CGRAs通用计算模型

2.1 CGRAs的设计目标

CGRAs的设计目标是针对计算密集型任务（如音视频的编解码、数字图像处理、移动目标的识别、基因运算、解加密算法等）关键循环内核占用大量计算时间的事实，将其关键循环提取并通过不同的划分映射方法，通过主处理器控制使其在RCA上被配置计算，这将大大加快关键循环任务的执行效率，从而获得高的加速比。

2.2 CGRAs的结构及其工作原理

随着高性能计算机体系结构的迅速发展，传统的计算机在执行程序的过程中是按顺序逐条地执行，即取指令→执行指令→……该执行方式效率较低，而且存储器和I/O外设的速度与高速的CPU速度不匹配，这将使得计算机的计算速度大大下降。在这样的背景下，各种追求运算高性能的计算平台（如CGRAs等）被相继提出，本文在结合文献[1-2，9-10]等研究的基础上给出了一种CGRAs较为通用计算模型[1，4-5，10]，其结构如图 1 所示。

CGRAs是由一个主处理器（main processor）、主存储器（main memory）、互连资源、DMA、RPU等构成高性能的混合计算机系统结构，其中RPU包括若干个可配置寄存器（context register，如控制、数据、RC（Reconfigurable Cell）寄存器等）、局部存储器（local memory）、可重构单元阵列RCA（Reconfigurable Cell Array）等组件，为了缓解高速的主处理器、低速主存储器、速度更低的RPU之间矛盾，一般在主处理器、主存储器、RPU之间加一数据缓存（data cache）模块，在主处理器和主存储器之间加一指令缓存（instruction cache）模块，目的是优化系统的运行。

CGRAs的工作原理简述如下：计算密集型任务通过加标记代码级软硬件划分，将在RCA上执行效率低或者不能执行的代码送到主处理器main processor上执行，将计算任务的循环代码展开，并将其变为中间表示即数据流图DFG（Data Flow Graph）的形式，通过某种划分与映射算法依次将DFG放置到RCA上，然后对RCA中已经用到的重构单元RC（Reconfigurable Cell），若干个控制配置寄存器（several control context registers）组进行配置，控制配置寄存器组中的全局控制寄存器控制RCA的启动，每个RC单元的连接关系及功能通过配置RC寄存器来实现，而且control context registers在main processor和循环控制器loop controller（一般用DMA控制器模块）的控制下，完成基址存取和DMA配置等工作。数据缓冲器（data buffer）实际上为局部存储器，与RCA进行数据的直接输入与输出，避免访问外部的存储器，从而节省通信成本。RCA组件可扩展为若干个RCA模块，RCA的内部可以通过总线、路由、二维网格全互连形式等方式将若干个RC单元连接在一起，RCA是CGRAs加速的主要部件。

3 Petri网的基本概念

有限状态自动机常用于单任务单状态的转换，对于活性、可达性、持续性等问题描述较难，针对实时多任务的复杂系统，系统的并发和动态性等因素均要考虑，Petri网等工具对其描述较为合适，Petri网是一种网状信息流模型，包括库所和变迁两类节点，同时在库所集上添加表示状态信息的托肯分布（标识），可以较好地解决此类问题。相关Petri网的基本定义列举如下：

图1 CGRAs通用计算模型

定义1[12]三元组 N=(P，T;F)称作网，必须满足以下条件：

其中，dom(F)={x∈P∪T|∃y∈P∪T:(x，y)∈F}，cod(F)= {x∈P∪T|∃y∈P∪T:(y，x)∈F}，这里，P 表示库所（Place）集合；T表示变迁（Transition）集合；F是网的流关系（Flow）。

定义2[12-14]四元组 N=(P，T;F，M0)称作Petri网系统当且仅当

（1）N=(P，T;F)为一个网。

（2）映射 M:P→{0，1，2，…}（非负整数集）称为网N的一个标识，其中，M0是初始标识。

（3）引发规则：

（3.1）变迁 t∈T 称为使能的当且仅当：∀p∈·t: M(p)≥1，记作 M[t＞ 。

（3.2）在M 下使能的变迁t可以引发，引发后得到一个新的标识 M′，记作 M[t＞M′，对 p∈P，有：

定义3可重构运算阵列的运行可形式化为一个十元组表示为含k种颜色时延Petri网，即CTdPN=(P，T; F，IC，M，W，H，OC，D，CON)，其中 (P，T;F)是一个网（其满足的条件见定义1），IC是颜色的一个有限集合IC={ic1，ic2，…，ick}，颜色库所输入集 IC 表示每次输入到RCA的数可以是实数，二进制数的原、反、补码，定点或浮点数等；有色标识 M:P→L(C)；权函数W:F→L(C)+；颜色变迁H:T→L(C)+；L(C)表示定义在颜色集IC上的一个实数等类型数的线性函数，L(C)+表示系数不全为0的 L(C)，即 L(C)=a1c1+a2c2+…+akck；L(C)+= b1c1+b2c2+…+bkck；其中，ai，bi(i=1，2，…，k)均为非负整数，且b1+b2+…+bk≠0，初始标识为 M0，对∀t∈T，如果 p∈·t→ M(p)≥W(p，t)，那么变迁 t在标识 M 有发生权(M[t＞)，在标识M 下发生变迁t，产生一个新的标识 M′(M[t＞ M′)：

颜色库所输出集 OC={oc1，oc2，…，ock1}表示任一运算任务DFG在RCA阵列所有输出集合即有色库所集IC表示每次输入到RCA的数可以是实数，二进制数的原、反、补码，定点或浮点数等，经过有色变迁集会产生相应的实数，进制数的原、反、补码，定点或浮点数等输出，OC=T′×P′，×为笛卡尔积，其中，P′为有色库所集合，T′为有色变迁集合，T′=是定义在颜色变迁集T上的时间函数，即 D:T→R∪Ω1∪Ω2，R表示一个实数集，Ω1表示二进制数的原、反、补码的集合，Ω2表示定点或浮点数的集合；D是定义在变迁集T上的时间函数，对于t∈T，D(t)=c表示变迁t的发生需要c个单位时间来完成。CON为任一DFG在RCA运行所耗费的配置时间。

为了便于比较行有依赖和无依赖映射完成后在RCA上的任一任务DFG的总执行时间，若RCA的互连方式相同，颜色库所输入集IC或输出集OC的数据类型及输入输出次数均相同，配置时间也相同。在此条件下，定义3就退化为时延Petri网，具体见定义4。

定义4[12]时延Petri网是一个五元组TdPN=(P，T; F，M，D)，其中 (P，T;F，M)为一个原型Petri网，D 是定义在变迁集T上的时间函数，具体同定义3。

4 CGRAs的RCA内部最大运行并行度分析

4.1 CGRAs编译流程

开发有效的SoC（System on Chip）芯片硬件任务编译器是软硬件逻辑高层综合的一个重要方面，这项工作不但具有理论意义，而且具有重要的实际意义和应用价值。本节结合文献[2]给出了一个通用CGRAs简明编译流程，如图2所示。

图2 通用CGRAs简明编译流程模型

由图2可知计算任务的划分与映射是CGRAs获得高的加速比的一个重要方面，故对RCA映射结果的研究及其重要。

4.2 行无依赖空域映射

CGRAs中的RCA运算阵列可以看作一个通过不同互连资源互连的多指令流多数据流（MIMD）的并行计算系统，计算任务的调度是其设计关键要素之一，本节不对具体逻辑、时序、算术等运算带抑止弧的增广Petri网进行建模，而是研究基于RCA阵列运算，把计算任务直接分配给具体的RC单元，分析其运行机理，以便找到一个最佳调度并行执行方案使其计算任务总的执行时间尽可能达到最短。

一般而言，矩阵运算含有的循环次数较多，且较具代表性，所以本文矩阵运算为例，分析相关映射算法的性能。一个4×4矩阵运算的循环内核（共有16次循环）经过SUIF软件展开并优化后[15-16]，可获得4×4矩阵运算一次循环的任务子图（见图3（a）），各圆圈斜线上的英文字母表示任务的序号，横线下的数字表示任务的执行时间。一个4×4矩阵运算的循环内核展开获得16个任务子图，将这16个任务子图分8次依次映射到一个全互连的 RCA4×4上（RCA的互连形状如图3（a）所示），若要求一次循环必须在同一块RCA上运行，则一块RCA每次可配置运行两个完整的任务子图，行无和有依赖映射结果如图3（c）（d）所示。

图3 说明两种映射方法的例子

为了便于说明问题，本文做出以下约定：有符号和无符号乘法任务的执行时间为2 cycle；其他算术与逻辑运算任务均为1 cycle。表1中的a，b，d的任务为乘法任务，故其执行时间为2 cycle，c，e，f，g为加法任务，故其执行时间为1 cycle。

表1 图3（a）的顺序关系表述

基本的CTdPN网的图形单元建模工具如图4所列。

图4 CTdPN网的建模基本单元关系图

4.3 基于时延Petri网的任务调度映射的时间特性分析

任务图被划分并映射到CGRAs中的RCA上时，就转变为一个肯定型工程问题，下面用CTdPN网对此进行分析，因为本节主要关注RCA运行的时间特性，且没有关注不同的资源（即用不同颜色的托肯（token）表示）使用问题，所以分析方法与文献[12]关于任务调度肯定型问题类似。

下面本节可用CTdPN网对图3两种映射的时间特性进行分析，由图3可知，RCA的互连方式相同，颜色库所集合IC输入次数均为16，集合OC的输出次数均为2，并且两种映射的输入出的数据类型一样，配置时间也一样。在此条件下，CTdPN网简化为时延Petri网即TdPN网，具体见定义4。所以为了便于说明问题，图5和图6中的网模型均采用时延Petri网对基于两种映射方案的一个任务DFG运行的时间特性进行分析和验证。

需要说明的是：全局时间不是Petri网的组成部分，因为全局时间对于大系统而言并非实时可知，也不能用于准确的控制。所以，用TdPN网分析得出的时间性能结论会有误差，在此假设行无依赖映射和有依赖映射统一不考虑这个误差。

图5 行无依赖映射分析

表2 Σ1各个库所 pi的 ASAP(pi)和 ALAP(pi)的值

图3（c）的两个映射成功的任务子图可以按行流水线并行执行，采用的是行无依赖映射算法，对此可以将两个子图看作一个任务图进行讨论，其网模型和可达标识图见图5（a）和（b），网中每个库所有两个时间函数即最早发生时间ASAP(si)和最晚发生时间ALAP(si)，其值如表2所列。从Σ1网模型可知，在不改变任务工序之间的衔接关系的前提下，增加了零权库所 p1和 p2，这样就获得行无依赖映射的Petri网模型。由图5（a）和表2可得出的行无依赖映射主关键工序为（除去任务图起点的虚库所 p0和任务图终点的虚库所 pe）：a1→c1→e1→g1；b1→c1→e1→g1；a2→c2→e2→g2；b2→c2→e2→g2。依据图3（b）RCA4×4硬件的实际，这四条主关键工序可以按行并行执行，同时考虑非关键工序的花费时间较长的任务 d1，d2，f1，f2可以得出行无依赖映射算法在 RCA4×4运行总的花费时间为7 cycle，由Σ1网可达标识图可知，该Σ1网模型具有可达性、活性、持续性等性质。

对于图3（d）的两个映射成功的任务子图仅可以部分按行并行执行（如 a1，b1，d1，f1的并行），故将其看作两个独立子图讨论（因为相同，所以只讨论一个），其中一个任务子图网模型和可达标识图如图6（a）（b）所示，网中每个库所的ASAP(si)和ALAP(si)如表3所列。

表3 Σ2各个库所 pi的 ASAP(pi)和 ALAP(pi)的值

由图6（a）和表3可得出的行有依赖映射主关键工序为（除去任务图起点的虚库所 p0和任务图终点的虚库所 pe）：a1→ c1→e1→ g1；b1→ c1→e1→g1。依据图3（b）RCA4×4硬件的实际，这两条主关键工序不可以按行并行执行，仅是部分的关键工序和非关键工序部分任务按行执行，如 a1，b1，d1，f1等，从而可以得出一个子图按行有依赖映射算法在RCA4×4运行总的花费时间为5 cycle，两个子图共需花费的时间为10 cycle，由 Σ2网可达标识图可知，该Σ2网模型也是满足可达性、活性等性质。

图6 行依赖映射分析

一个4×4矩阵运算的循环内核展开共有16个的任务子图，如果分8次在全互连的RCA4×4按行无依赖和行有依赖进行映射和运行，发现行无依赖映射执行完一个4×4矩阵运算总的耗时为56 cycle，而行有依赖映射执行耗时为80 cycle，相比较行有依赖映射而言，行无依赖映射的执行耗时少了24 cycle，所以行无依赖映射算法的优势明显。

5 结束语

本文结合Petri网通过实例对行无依赖映射和行有依赖映射的时间特性进行分析和比较，相比于文献[11]提出的允许行有依赖映射算法而言，本文提出的行无依赖映射算法具有可行性和合理性。

[1]Compton K，Hauck S.Reconfigurable computing：a survey ofsystemsandsoftware[J].ACM ComputingSurveys，2002，34（2）：171-210.

[2]Cardoso J M P，Diniz P C，Weinhardt M.Compiling for reconfigurablecomputing：asurvey[J].ACM Computing Surveys，2010，42（4）：1301-1365.

[3]Arnold J M，Buell D A，Hoang D T，et al.The splash 2 processor and applications[C]//IEEE International Conference on Computer Design：VLSI in Computers and Processors，1993：482-485.

[4]Hasan M Z，Sotirios S G.Customized kernel execution on reconfigurable hardware for embedded applications[J]. Microprocessors and Microsystems，2009，33（3）：211-220.

[5]Giovanni A，Paolo B，Laura P.EGRA：a coarse grained reconfigurable architectural template[J].IEEE Transactions on Very Large Scale Integration Systems，2011，19（6）：1062-1074.

[6]Pranav V，John L J.A novel multicontext coarse-grained reconfigurable architecture for accelerating column-oriented databases[J].ACM Transactions on Reconfigurable Technology and Systems，2011，4（2）：1-30.

[7]Giovanni A，Kazuyuki T，Laura P，et al.Integrated kernel partitioning and scheduling for coarse-grained reconfigurable arrays[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2012，31（12）：1803-1816.

[8]Yongjoo K，Jongeun L，Toan X M.Improving performance ofnested loopson reconfigurable array processors[J]. ACM Transactions on Architecture and Code Optimization，2012，8（4）：1-22.

[9]Mei B F，Vernalde S，Verkest D，et al.ADRES：an architecture with tightly coupled VLIW processor and coarsegrained reconfigurable matrix[C]//Proceedings of the 13th InternationalConference on Field-Programmable Logic and Applications.Lisbon，Portugal：IEEE CS Press，2003：61-70.

[10]Singh H，Lee M H，Lu G M，et al.MorphoSys：an integrated reconfigurable system for data parallel and computation intensive applications[J].IEEE Transactions on Computers，2000，49（5）：465-481.

[11]Yoon J W，Shrivastava A，Park S，et al.A graph drawing based spatial algorithm for coarse-grained reconfigurable architectures[J].IEEE Transactions on Very Large Scale Integration Systems，2009，17（11）：1565-1578.

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

[13]曾庆田，吴哲辉.无界Petri网的进程表达式[J].计算机学报，2003，26（12）：1629-1636.

[14]苏国军，汪雄海.半导体制造系统改进Petri网模型的建立及优化调度[J].系统工程理论与实践，2011，31（7）：1372-1377.

[15]Moon S，So B，Hall M W.Evaluating automatic parallelization in SUIF[J].IEEE Transactionson Paralleland Distributed Systems，2000，11（1）：36-49.

[16]Hall M W，Amarasinghe S P，Murphy B R，et al.Interprocedural parallelization analysis in SUIF[J].ACM Transactions on Programming Languages and Systems，2005，27（4）：662-731.

CHEN Naijin

College of Computer and Information Engineering,Anhui Polytechnic University,Wuhu,Anhui 241000,China

In order to more effectively optimize the mapping acceleration performance of coarse grained Reconfigurable Cell Array（RCA）,a method of row nodes no-dependency spatial mapping scheduling constraint is put forward.Timed Petri nets are used to analyse several data flow subgraphs which have been partitioned and mapped on RCA by constraint based on the same conditions.The running results of row nodes dependency mapping and row nodes no-dependency mapping are compared by an example.The experimental results show that this spatial mapping method is feasible.

Coarse Grained Reconfigurable computer systems（CGRAs）;Petri net;reconfigurable cell array;data flow graph

为了更有效地优化粗粒度可重构单元阵列映射加速性能，提出了一种行节点无依赖约束的空域映射调度方法，基于相同条件下，采用时延Petri网对若干个按约束已经被划分映射到可重构单元阵列的数据流子图的运行情况进行了分析，通过一个实例比较了行节点有依赖和无依赖的运行结果，结果表明该种空域映射方法具有可行性。

粗粒度可重构计算机系统；Petri网；可重构单元阵列；数据流图

A

TP302

10.3778/j.issn.1002-8331.1302-0038

CHEN Naijin.Spatial mapping time performance analysis based on two dimension RCA and Petri net.Computer Engineering and Applications,2014,50（23）：41-46.

国家自然科学基金（No.61203034）；安徽省自然科学基金面上项目（No.1408085MF124）；安徽省高等学校省级自然科学基金（No.KJ2012B010）；芜湖市科技计划自然科学基金重点项目（No.芜科计字[2012]95号）。

陈乃金（1972—），男，博士，副教授，研究领域为可重构计算、时空域划分与映射等。E-mail：cnj@ahpu.edu.cn

2013-02-05

2013-05-03

1002-8331（2014）23-0041-06

CNKI网络优先出版：2013-05-21,http://www.cnki.net/kcms/detail/11.2127.TP.20130521.1027.007.html