基于随机Petri 网的可重构核心单元建模与分析

1、基于随机Petri 网的可重构核心单元建模与分析    基于随机Petri 网的可重构核心单元建模与分析曾国荪，王福焕*基金项目：863 项目(2009AA012201)，国家自然基金(90718015)，NSFC-微软亚洲研究院联合资助项目(60970155)，教育部博士点基金(20090072110035)，上海市优秀学科带头人计划项目(10XD1404400)，高效能服务器和存储技术国家重点实验室开放基金项目(2009HSSA06)作者简介：曾国荪，男，教授，主要研究领域：并行分布计算，可信软件，信息安全.  5 （同济大学计算机科学与技

2、术系，上海 200092）摘要：可重构体系结构是当前高性能并行计算的一个重要发展方向。可重构核心单元是新概念高效能新型计算机研制的原型系统的关键部分，该原型系统目前正在处于可行性分析和实验研究阶段。本文利用随机Petri 网对可重构核心单元进行建模，对其结构特性，如可达性、有界性、安全性等，进行逻辑正确性验证。并且，对其性能特性，如稳态概率、变迁概率、10 吞吐量等，开展数量化求解。特别，在三种不同情况下，讨论了动态重构对计算任务完成时间的影响。本文工作对新型计算机体系结构研究和分析具有一定的参考意义。关键词：重构计算，核心单元，随机Petri 网，结构分析，性能分析 0 引言传统计

3、算的实现方式有专用ASIC 和通用微处理器两种方法。ASIC 方法使用专用特定35 的集成电路, 以完全硬件的方式来实现计算任务，这种方法可得到很高的运算速度及效率,但它几乎没有任何灵活性和适应性, 或者说是不可编程的, 任务稍有变化就必须修改电路。通用微处理器方法通过修改软件来达到改变系统功能的目的, 硬件无需做任何改动, 这种方法灵活性强, 或者说是可编程的, 然而这种可编程性是以牺牲系统的性能和速度为代价换来的。基于FPGA 的可重构技术介于硬件和软件计算模式之间，既有专用硬件ASIC 计算实现40 方式的性能优势，同时具有通用处理器软件实现的灵活性。利用FPGA 可重编程技术，无论&#

4、160;是逻辑功能模块，还是模块之间的通信连接，都可以被反复重新编程，即硬件电路可以随时根据需要而改变1，因而正在成为高性能计算体系结构的研究热点。早在上世纪60 年代，美国加州大学的Estrin2等就提出了重构计算的概念，并研制了原型系统，由非柔性但可编程的处理器、以及柔性的由程序控制重构的数字逻辑部件两部分组成，奠定了以后可重构计算系统的基础45 。70 年代末，Kartashev 等3提出了动态可重构系统的概念，真正意义上实现了系统能兼有硬件的效率和软件的灵活性。1986年Xilinx 公司开发出世界上第一片现场可编程门阵列FPGA 芯片，并在实践中获得了很好的应用效果，后来出现高密度的

5、可整合完整系统的FPGA，可重构芯片在技术上和商业上存在的潜在价值才逐渐得到人们的重视。但是很长一段时间，人们对FPGA 的认识仍存在很大的局限性，一般把它50 作为系统设计中的一种补充，或者主要用来做功能验证。90 年代初期，出现了以FPGA 为核心开发的面向某一类应用的计算设备，它们在一些特殊的应用领域显示出了超强的计算性能和数据处理能力，尤其对于算法内部蕴涵很大并行性和流水性的应用表现尤为出色，表明FPGA技术在高性能并行计算领域有巨大的潜力。近年来，基于FPGA的可重构技术发展更为迅速，世界上许多大学和公司机构都开展了相应的研究计划。美国加州大学伯克利分校55 Hauser 4等研制了

6、一个MIPS 微处理器和细粒度组合在一起的Garp 系统，将可重构计算单元嵌入到传统的RISC 处理器中。PACT 公司研制的XPP 用构令流代替指令流，实现了粗粒度的实时可重构数据处理技术，开创了粗粒度可重构优化的先河。南加州大学Kiran 等5提出了可重构网格模型和混合系统结构模型，将可重构应用到计算机体系结构中。但是这些体系结构通用计算效率不高，缺少统一的计算模型，重构时间长，存储小，数据传输功耗大。60 我国科研机构也在不断的努力，试图提出了一种新概念高效能计算机体系结构，即超混合新型的可重构体系结构，希望应用在高性能计算方面，取得良好的效果和突破。1 新概念高效能计算机体系结构中的可

7、重构核心单元1.1 863 项目的研究目标和任务2009 年批准的国家863 重点项目：“新概念高效能计算机体系结构及系统研究开发65 （2009AA012201）”，旨在根据国内外高效能计算机最新发展现状与趋势，深入研究高效能计算机系统体系结构新概念、新理论，提出高效能计算机系统构建的新技术和新方法，探索高效能计算机系统体系结构创新之路。具体的研究任务是通过对多领域应用需求的分析，深入研究现有高效能计算机体系结构，特别是各种混合/异构体系结构6，提出一种面向多领域应用、基于多种加速处理部件、多层次可重构的新概念体系结构，即超混合可重构计算机体70 系结构HRCA。同时根据应用的需要，构建面向

8、超混合深度可重构体系结构的新型计算模型，寻找合适的超混合体系结构优化设计方法，研究支持超混合深度可重构体系结构的编译优化技术，对超混合深度可重构节点内各种资源的虚拟化和高效管理，构建面向超混合深度可重构体系结构的新型应用模式。1.2 超混合可重构计算机体系结构HRCA75 随着计算机硬件处理能力和制造工艺的发展，应用需求显现出广泛性、复杂性和不可预测性，构筑于冯·诺 伊曼体系结构理论上的传统的计算机体系结构在高性能计算领域面临着难以逾越的发展障碍：数据计算时间远远小于数据搬运时间，即“计算墙”，系统结构失衡，存储器性能与处理器性能差距越来越大，本地带宽及延迟、全局带宽及延迟发展不一致

9、即“内存墙”，系统从I/O 输入到I/O 输出的不均衡带宽设计，让系统吃得进，吐不出，即“I/O”墙。80 “计算墙”，“内存墙”，“I/O 墙”等问题导致现有体系结构下的实际应用性能仅有峰值性能的 5 10，可用性差。另一方面，体系结构单一固定，不能满足和适应客观世界中应用的多样性，用户无法自主参与计算资源的配置和计算过程的控制，必须“削足适履”，适用性差。因此，我们提出了超混合可重构计算机体系结构HRCA 的构想，如图1 所示，以求达到计算机系统适应性强、实际应用平均性能高的效果。85图1 超混合可重构体系结构原理图超混合可重构体系结构HRCA 由多个可重构单核、可重构互连单元和

10、可重构I/O 单元组成。其中最重要的是可重构单核结构，它可以通过硬件可重构来支持不同的计算需求，从而满足应用需求的多元化。可重构互连单元在HRCA 中可以组成具有一定拓扑结构的片上90 异步通信网络，实现单核之间以及同I/O 之间的数据交换。可重构I/O 单元主要负责单核同片外的通信，通过提供对片外的高通信带宽来平衡芯片内部计算速度和对片外存储的大数据量需求。HRCA 基本思想是动态配置HRCA 中的单核、存储单元和互联单元。对各种不同的应用算法进行分析，提取基本核心算法，如浮点运算、排序、向量计算、FFT 等基本算法，然后将这些典型算法直接映射到体系结构中，消除了传统处理器的取指令和指令译码

11、的开95 销，大幅提高执行效率。最后通过体系结构中的高度可扩展的可重构单核对这些应用算法进行处理，从而能在一个很宽的应用范围内达到高性能，提高HRCA 中硬件资源的利用率。1.3 可重构核心单元目前，超混合可重构计算机体系结构HRCA 还处于可行性分析研究阶段，我们期望构造小规模的原型试验系统，即可重构核心单元，来分析验证整个项目的设计方法的正确性和100 可行性。经过项目组的不断探索、反复实验和深入研究，设计出原型实验系统如图2 所示：多种不同应用可重构体系结构计算执行部件 图2 可重构核心单元组成结构原理图其中，DDR2(Double Data Rate 2)表示双倍速率同步同态

12、随机存储器，用作内存，每个105 时钟能够以4 倍外部总线的速度读写数据，并且能够以内部控制总线4 倍的速度运行。CPLD(Complex Programmable Logic Device)是复杂可编程逻辑部件，可以根据处理节点各自需要自行构造逻辑功能，即用于可重构配置。LVDS(Low-Voltage Differential Signaling)通道用于实现FPGA 芯片之间数据传送和内存共享，实现低噪音和低功耗。RPC 网络用于用户传送处理的数据，它向远程的计算机程序请求传送服务，而不需要了解底层网络技术的协议。110 OMC 网络用于传送用户需要功能的信息。EMAC(E-Motion

13、 Multi Axis Controller)主要用户配置信息的传送。 MCU(Micro Control Unit)是微控制单元，为不同的应用做不同组合控制，嵌入每个FPGA 中，进行FPGA 内部的初始化系统控制和数据搬运。ARM(Advanced RISCMachines)是处理器，耗电少、功能强、16 位/32 位双指令集，内嵌到其中一个FPGA 中。GTX/GTP (General Data Transfer Platform)是面向分布式应用的数据传输平台，实现FPGA 芯115 片之间的高速互连。可重构核心单元主要功能为：重构配置和计算任务执行。当计算任务到来后，可重构核心单元启

14、动，静态重构配置信息从OMC 网络首先传到FPGA0，其它FPGA 进行协同处理，然后FPGA0 的配置信息接口EMAC 将配置信息传送到CPLD，进一步传送到协同处理的其它FPGA 的配置信息接收接口EMAC，最后四个FPGA 由各自的控制处理器进行静态重构120 配置。另外，在计算任务执行过程中，程序功能可能发生变化，可重构核心单元需要进行动态重构配置，此时OMC 将动态配置信息传入FPGA0，同静态配置一样，其它FPGA 得到相应的动态配置信息，各FPGA 进行动态重构配置。可重构核心单元的数据传输是依靠RPC网络和LVDS 通道来实现的，当数据从RPC 网络传输到FPGA0 时，FPG

15、A0 要通过LVDS 通道，将数据分配给协同处理的其它FPGA，各FPGA 对分配到的数据进行计算处理后，处理125 结果汇总到RPC 网络，返回给上级单元或系统。CPLDEMACGTPMCUDDR2EMACGTXARMDDR2EMACGTPMCUEMACGTXMCUDDR2可重构配置网络 可重构配置网络可重构配置网络 可重构配置网络LVDS LVDSLVDS LVDSLVDSLVDSOMC 网络RPC 网络FPGA0FPGA3FPGA1FPGA2可重构核心单元重配置信息计算任务DDR2 1.4 问题分析要求(1)逻辑结构正确性验证逻辑结构正确性是可重构核心单元的基本要求。对于正确性

16、的分析，主要是分析可重构核心单元处理任务过程中是否出现资源溢出、冲突、死锁等现象，因此正确性验证就是对可130 重构核心单元的结构特性进行分析。可重构核心单元的结构特性分析主要是分析可重构核心单元的可达性、有界性、安全性、活性等。可达性是指可重构核心单元的一个状态经过一系列变化后能够到达另一个状态。假设Mbegin 表示可重构核心单元的初始状态，Mend 表示可重构核心单元的终态，如果可重构核心单元在处理任务时，能够从Mbegin 状态经过一系列的状态变化后能够达到Mend，那么可重构135 核心单元就是可达的。有界性是指可重构核心单元在任务处理过程中，各器件或接口中要存储的数据不会超出各器件

17、或接口所容纳的界限，即可重构核心单元不会发生资源溢出现象。安全性是指可重构核心单元不会因为资源竞争而出现死锁现象，即可重构核心单元不会出现停滞不前的情况。140 活性是是指可重构核心单元在任务处理过程中，任何规定的操作，如静态重构配置，动态重构配置，通信操作，计算处理等事件都能如期、正常发生。(2)性能评价可重构核心单元的吞吐量、重构时间和任务处理时间等性能特性也是影响可重构核心单元工作运行的重要因素，特别是可重构核心单元应用于多种不同需求处理时，更应该考虑这145 些因素影响，找出可能的性能瓶颈，改善可重构核心单元的设计方法。可重构核心单元的吞吐量表示在计算任务处理过程中，可重构核心单元所能

18、处理任务的能力，记为TH。重构时间表示计算任务处理过程中，由于重构配置而花费的时间，记为RTr；其包括由静态重构时间，记为RTs；以及动态重构时间，记为RTd；重构时间RTr=RTs+RTd。150 计算任务完成时间表示可重构核心单元处理计算任务最终得到运算结果而花费的时间，记为RTtask；任务完成时间包括任务传输时间，记为RTt，等待时间，记为RTw，任务时间，记为RTc，任务完成时间 RTtask=RTt+RTw+RTc。2 可重构核心单元的随机Petri 网模型2.1 随机Petri 网的概念155 Petri 网最早在1962 年由Carl Adam Petri 的博士论文中提出来，

19、它是描述分布、并发、异步系统行为的有效工具7。但是，人们在分析动态系统时，不仅关心系统的结构性质, 还关心系统的性能时态性质，在Petri 网的基础上将时间因素引入扩展成为随机Petri 网（SPN）8, 9，相关定义如下：定义1（Petri 网 PN）：是一个五元组 (S,T; F,W,M0)，其中S 是库所，T 是变迁，F 是160 库所和变迁之间的关系映射函数，W 是弧F 的权值，M0 是初始标识。定义2(随机Petri 网SPN): 是一个六元组(S,T; F,W,M0,)，其中S, T, W, F, M0 与PN 相同。=1,2m是变迁平均实施速率集合。设变迁tiT 以随机概率i 进

20、行实施，i 表示tiT 在可实施情况下单位时间内平均实施次数，平均实施速率的倒数1/i 称为变迁的平均实施延时，或平均服务时间。165 随机Petri 网与时间连续的马尔科夫链是同构的，因此可以根据SPN 的可达集构造马尔 科夫链，求解状态稳定概率，根据稳定状态概率可以求出每个变迁ti 的实施概率i，从而可以进行逻辑结构正确性验证及性能指标分析。2.2 模型的建立一般来说，把系统结构中的处理器或接口看作Petri Net 中的库所，把处理器之间、接口之间、或处170 理器与接口之间的操作看作Petri Net 中的有向边，将一个处理器对任务的处理（传送和计算）用一个变迁来描述，其处理

21、的数据量用一个token 来表示，因而可以采用PetriNet 理论对系统结构进行描述和分析。为了方便建模，给出以下假设或约定：(1) 四个FPGA 节点有等同的行为，所执行的操作是类似的。(2) FPGA1，FPGA2，FPGA3 为FPGA0 提供内存，内部搬运数据的速率都一样。175 (3) 四个FPGA 进行初始化、处理的速率都一样。(4) 假设FPGA 只进行2 次重构配置，即1 次静态重构配置和1 次动态重构配置，以便刻画FPGA 在计算任务执行之前，以及计算任务执行期间，改变逻辑电路和功能，适应多应用任务变化的需求。(5) 每次处理的任务用一个token 来表示。180 基于随机

22、Petri 网对可重构核心单元建模时，要先将可重构核心单元中的资源和操作用相应的库所和变迁表示，然后根据资源之间的操作，构造资源之间的流关系。可重构核心单元中的资源用库所描述如表1 所示，可重构核心单元中的操作用相应的变迁描述如表2 所示。表1 资源描述表资源 库所 初始Token启动装置 s1 1OMC 网络 s2 0FPGA0 的EMAC s3，s5 0FPGA0 的ARM s4 0CPLD s6 0FPGAi 的EMAC si，1 i 3 0FPGAi 的MCU si+9，1 i 3 0RPC 网络 s13，s29 0FPGA0 的GTX s15， s16，s21，s28 0FPGAi

23、的GTX si+16, si+21, si+24, 1 i 3 0控制装置 s14 ，s20 0185表2 操作描述表操作 变迁 速率实施概率开始操作 t1 1 1静态配置信息传送 t2 ，t4 ，t5 2 2,4, 5启动ARM t3 3 3启动MCU t7 4 7FPGAi 进行重构配置 t6 5 6动态配置信息传送 t10 6 10数据输入 t8 7 8数据LVDS 传送 t9 ，t16 8 9, 16控制转移速率 t11 9 11FPGAi 数据处理 ti+12，1 i 3 10 i+12结果综合并传送 t17 11 17 以下重点阐述静态重构和动态重构的建模过程。可重构核心

24、单元在处理计算任务之前要对各FPGA 进行静态重构，即利用变迁t1 将静态重构配置信息通过OMC 网络(s2)传送给FPGA0，通过FPGA0 将配置信息传送190 给其它各个FPGA（s10 ,s11 ,s12），然后四个FPGA 实施静态重构配置（t6）。当可重构核心单元的各个FPGA 完成静态重构后，可重构单元开始进行数据处理（t8），将FPGA0 收到的数据通过LVDS 通道将数据分配（t9）给其它三个FPGA（s17 ,s18 ,s19）。数据分配完毕并进行计算处理之后，我们假设应用处理需求发生了变化，要求改变FPGA 的逻辑功能，也就是说需要对各FPGA 进行动态重构（t10），此

25、时OMC 网195 络将新的重构配置信息传送过来，四个FPGA 进行动态重配置，从而实现新的逻辑功能。重新配置后，各个FPGA 进行新一轮的数据处理和计算任务执行（t12 ,t13 ,t14 ,t15），然后将处理结果汇总传给RPC 网络（s29）。整个可重构核心单元的Petri 网模型如图3 所示：200 图3 可重构核心单元的SPN 模型3 可重构核心单元的结构特性分析逻辑结构正确性是可重构核心单元最基本的要求。本文逻辑正确性的分析主要就是对结构正确性的分析。基于随机Petri 网（SPN）的可重构核心单元结构特性分析方法是：可重构状态之间的可达关系，对应于SPN 可达图中状态可达性分析；

26、可重构核心单元中某些参205 数（器件、接口）是否有界，对应于SPN 中的有界性理论。可重构核心单元中安全性、活性对应于SPN 的活性、死锁、陷阱等理论。可重构核心单元处理计算任务过程中，各器件或接口所包含token 的情况表示了可重构核心单元运行期间的各种状态，例如初始情况下，只有启动装置S1 中有一个token，那么可重构核心单元的初始状态为M0(s1(1)。通过实施不同的变迁ti，可重构核心单元的各器件或210 接口中的token 发生变化，运行期间的各种状态Mi 随着发生变化。这些由变迁引发的不同状态构成了可达图如图4 所示。s1 s2 s3s4s5 s6s7s8s9s10s11s12

27、s13s14s15s16s17s18s19s20s21s22s23s24s25s26t1 t2 t3t4 t5t6t7t10 t9 t8t11t12t13 t14t15t16s27s28 s29 t17静态重构配置启动动态重构配置启动1 22 2547869101010108 113开始计算任务传送开始任务计算结果汇总传送 图4 可重构核心单元SPN 的可达图其中，M0 表示初始状态，M35 表示结束状态， Mi(sj(m)表示在状态Mi 时，库所sj 的token为m,其余库所token 为0。初始状态M0 经过变迁t1 215 t2 t3 t4 t5 t7 t6 到达状态M7，表

28、示可重构核心单元的静态重构过程。状态M7 经过变迁t8 t9 到达状态M9，表示数据传送和任务分配过程。状态M9 经过变迁t10 t2t3 t4 t5 t7 t6 到达状态M17，表示了动态重构过程。状态M17 到最终状态M35 表示计算任务处理过程。在可达图的基础上进行可重构核心单元的结构特性分析，我们得出以下结论：220 结论1： 可重构核心单元是可达的，即可重构核心单元从初始状态经过一系列操作后能够到达终态。证明： 可重构核心单元的初始状态是指s1 的token 数为1，其余为0 的状态，即可达图中的状态M0，最终状态是指s29 的token 为 1，其余为0 的状态，即可达图中的状态M

29、35。在可达图中无论状态怎样变化， M0 总能到达M35，即可重构核心单元状态无论怎样变化，225 总是能从初态顺利到达终态。结论2：假定可重构核心单元中的器件或接口容量是有限的，那么在计算任务处理过程中，可重构核心单元是有界的，即器件或接口不会发生资源溢出现象。证 明：库所token 数表示了在计算任务处理过程中，各器件或接口所包含的资源数。在可达图中计算任务处理过程为状态M17 到状态M35，各状态库所的token 数都小于某一个230 固定的值，不会出现无限增多的情况，因此可重构核心单元的器件或接口不会出现资源溢出现象。结论3：假定系统中如果每个变迁至少实施一次，不会因为其中一个变迁的实

30、施导致其它变迁无法实施，即死锁现象，则该系统是安全的，那么可重构核心单元是安全的，在计算任务处理过程中不会发生死锁现象。235 证明： 从可重构核心单元可达图来看，初始状态M0 到结束状态M35，当变迁序列t1t2 t3 t4 t5 t7 t6 t9 t10 t2t3 t4 t5 t7 t6 t11 发生后，无论走哪一条分支，t12 t15 t13 t14 t16 t17、t12 t15 t14 t13 t16t17、t12 t14 t15 t13 t16 t17、t12 t14 t13 t15 t16 t17，每个变迁都至少发生了一次，不会因为一个变M0M1M2M3M4M5M6M7M8M9M

31、10M11M12M13M14M15M16M17M18M19M20M21M22M24M27M23M25 M26M29 M28M30 M31M33 M32M34M35t1t2t3t4t5t7t6t8t9t2t3t4t5t10t7t6t11 t15t12 t13 t14t14t12 t13 t15 t13t12t15t14t15 t14 t12t13t13t12t14 t12t14t13t15 t12t15 t13t15t14t14 t13 t12 t16t15t16 t12t17M0(s1(1)M1(s2(1), s14(1)M2(s3(1), s14(1).M17(s21(1), s22(1),

32、 s23(1), s24(1)M18(s21(1), s22(1), s23(1), s27(1)M19(s21(1), s22(1), s24(1), s26(1)M20(s21(1), s23(1), s24(1), s25(1)M21(s23(1), s24(1), s22(1), 28(1)M33(s25(1), s26(1), s27(1), s28(1)M34(s28(2)M35(s29(1) 迁的发生而使其他变迁无法发生，因此可重构核心单元具有安全性，不会因为资源竞争而发生死锁现象。同理，系统还具有活性，240 公平性，持续性，可重复性，守恒性，且不存在陷阱，在此不再详

33、述。4 可重构核心单元的时间特性分析时间特性是可重构核心单元的另一个重要特性。对于可重构核心单元的时间特性分析，需要根据可重构核心单元的SPN 模型的可达图，将变迁转换成马尔科夫链，然245 后求解出可达图中的稳定状态概率10，从而求解出可重构核心单元中的变迁实施概率和吞吐量，这样就可以分析可重构核心单元执行计算任务的完成时间。4.1 三种情况下的稳定状态概率稳定状态概率是打开可重构核心单元的性能分析大门的钥匙，求解稳定状态概率是分析可重构核心单元时间特性的前提条件。可重构核心单元FPGA 之间由GTX/GTP 收发器实现250 FPGA 芯片高速互连，传输速率为100Mbps6.5Gbps。

34、FPGA 之间采用多通道LVDS 实现FPGA 芯片之间数据传输，单通道LVDS 的速率为1Gbps，多通道最多能达到1.25Gbps。各FPGA 进行数据处理的速率为1Gbps。因此在图3 中，变迁t1, t2, t3, t4, t5, t6, t7, t8, t10 的平均实施速率1, 2, 3, 4, 5, 6, 7, 11 的范围在0.16.5(Gbps)之间，变迁t9, t16 的平均实施速率8的范围在11.25(Gbps)之间，变迁 t12, t13, t14, t15 的平均实施速率11 为1Gbps。为了较好地分255 析可重构核心单元的时间特性，我们分差、中、好三种情况讨论，

35、省略速率单位，不妨假设如下：情况1（速率极差）：1, 2, 3, 4, 5, 6, 7, 11 为0.1，8 为1，10 为1。情况2（速率一般）：1, 2, 3, 4, 5, 6, 7, 11 为2，8 为1，10 为1。情况3（速率极高）：1, 2, 3, 4, 5, 6, 7, 11 为6.5，8 为1.25，10 为1。260 要将可重构核心单元可达图构建系统的马尔科夫链，可使可达图4 中的变迁换成相对应的变迁速率。令状态Mi, 1 i 21 的稳定状态概率为xi, 1 i 21，根据马尔科夫链的平衡状态方程(j)xi=(k xk)，那么在可重构核心单元SPN 模型的可达图中，各状态的

36、稳定状态概率求解结果如下：情况1 时，可达图中各状态的稳定状态概率为xi=0.0594，0 i 7 && 9 i 16，265 x8=0.00594 ，xi=0.0004 ，18 i 27， x28=0.0007, x17= x29= x30= x31=0.0015, x32=0.0007,x33=0.0022，x34=0.0297。情况2 时，可达图中各状态的稳定状态概率为xi=0.04，0 i 7&&8 i 16，x8=0.08，xi=0.0067，18 i 27，x28=0.01, x17= x29= x30= x31=0.02, x32=0.01, x3

37、3=0.0468，x34=0.04。情况3 时，可达图中各状态的稳定状态概率为xi=0.026，0 i 7&&9 i 16，x8=0.1356，270 xi=0.0141，18 i 27，x28=0.0057, x17= x29= x30= x31=0.0424, x32=0.007, x33=0.1063，x34=0.0175。4.2 变迁的实施概率和吞吐量变迁的实施概率和吞吐量是可重构核心单元的重要性能指标。变迁ti 的实施概率i 反映了可重构核心单元中操作发生的概率。在可达图中，变迁ti 的实施概率i 等于使变迁ti 实施的稳定状态概率之和。可重构核心单元的吞吐量表征计算

38、任务完成情况9，它是可重构核心275 单元处理数据过程中各个变迁吞吐量的总和。而变迁的吞吐量是变迁的实施概率i 与变迁的实施速率i 乘积，即TH(ti)= i×i。根据三种情况下可达图的不同稳定状态概率，我们得到变迁的实施概率如表3 所示，变迁的吞吐量如表4 所示。 表3 变迁实施概率表变迁ti 实施概率i情况1 情况2 情况3t1 ,t3 ,t8 , t9, t10,t11 0.0594 0.04 0.288t2 ,t4 ,t5 ,t6 ,t7 0.1188 0.08 0.576t12 0.0529 0.0802 0.144t13 t14 t15 0.00538 0.08

39、02 0.144t16 0.0029 0.0568 0.1152t17 0.0297 0.04 0.0239280 表4 变迁吞吐量表变迁ti 变迁吞吐量TH情况1 情况2 情况3t1 ,t3 ,t8 , t10,t11 0.00594 0.08 0.169t2 ,t4 ,t5 ,t6 ,t7 0.01188 0.16 0.338t9 0.0594 0.04 0.0325t12 0.0053 0.0802 0.1397t13 t14 t15 0.0054 0.0802 0.1694t16 0.0029 0.0568 0.14t17 0.00297 0.08 0.1138从上述两个表中的数据可以

40、看出，变迁的实施概率直接影响了变迁的吞吐量，当实施概率较大时，吞吐量就越大。也就是说，当可重构核心单元各操作发生概率较大时，可重构核心单元对这些操作处理能力就越强，如表中变迁t10, t12, t13, t14, t15， t10, t12, t13, t14, t15 的实施285 概率越大，t10, t12, t13, t14, t15 的吞吐量越大。t10 表示动态重构的实施，t12, t13, t14, t15 表示任务计算。也就是说，动态重构发生的概率越大，动态重构过程的吞吐量就越大，可重构核心单元动态重构的能力也就越强，同样，任务被FPGA 处理的概率越大，可重构核心单元进行任务处

41、理的能力越强。动态重构概率反映了可重构核心单元及时响应多应用需求能力，任务计算概率反映了各290 FPGA 进行处理任务的能力， 因此上述分析在一定程度上反映了可重构核心单元响应多应用需求越及时，各重构器件进行重构的能力就越强，计算执行部件进行多应用任务处理的能力越强。4.3 重构时间和计算任务完成时间可重构核心单元的重构时间和计算任务处理完成时间是可重构核心单元的另外两个重295 要性能指标。可重构单元的重构时间是指可重构核心单元重构所花费的时间，重构时间包括静态和动态重构时间。静态重构时间等于静态重构过程中的平均标记数和吞吐量的比值，动态重构时间等于动态重构过程中的平均标记数和吞吐量的比值

42、。计算任务完成时间是指可重构核心单元处理任务所花费的时间，包括计算任务传送时间、任务等待时间、任务处理执行时间。计算任务传送时间等于任务传送过程中的平均标记数和吞吐量的比值。当任务传送后，300 逻辑功能需求发生变化，计算任务要等待各FPGA 进行动态重构配置，任务等待时间就是动态重构时间。任务处理执行时间等于任务处理执行过程中的平均标记数和吞吐量的比值。在可重构核心单元随机Petri 网模型中，库所的平均标记数D(si)=P(MM(si)，其中M(si)表示库所si 能取到的token 数，P(MM(si)表示在可达图中所有满足库所si 的 token 为M(si)时 的稳定状态概率和。可重构核心单元静态重构过程包括库所si，1 305 i 12，变迁ti，1 i 7，因此静态重构过程的平均标记数Ds=D(si) , 1 i 12，吞吐量THs=TH(ti)，1 i 7。动态重构过程包括库所si，2 i 12，变迁ti，2 i 7，i=10，因此动态重构过程的平均标记数Dd=