基于FPGA 的有色Petri 网仿真系统设计*

陈成官，张小军，周韬略，张德学，郭 华

(山东科技大学电子信息工程学院，山东 青岛266590)

Petri 网(Petri Net，PN)是一种适合于描述异步、并发、分布式系统的抽象描述方式，可用图形表示法和代数表示法分别表示，具有直观性[1]。 由于这些特点，Petri 网的理论得以快速发展和应用，其中有色Petri 网(Colored Petri Net，CPN)已经被广泛用于系统仿真与验证[2-4]、工作流分析[5-7]、性能分析[8-9]与算法错误检测[10-11]等工作中。 对于PN 工具的设计与开发，目前已经取得了许多研究成果[12]。 但是，这些项目主要集中于通用计算机系统下对P/T 网(库所/变迁网)进行的建模及模型的仿真验证；并且在通用计算机系统上，存在模拟PN 并发性低效与仿真速度慢的问题。

现场可编程门阵列(FPGA)提供了一种新的建模方法。 FPGA 与通用计算机系统相比具有速度快、可重构和能效比高的优势，并且可直接描述Petri 网异步并发的特性。 随着Petri 网规模的扩大与复杂度的增加，FPGA 的速度优势会越来越明显。目前对基于FPGA 的PN 仿真系统的研究较少，且大多数涉及Petri 网的研究，都是以Petri 网在实际问题的应用研究为导向的，例如，Petri 网在逻辑控制器设计与离散事件系统监控理论中的应用[13]；并且现有的基于FPGA 的PN 实现方法不支持CPN 的仿真[14-15]。

本文实现基于FPGA 的CPN 仿真系统解决了两个问题:CPN 的硬件架构设计、CPN 硬件模型的自动生成。 由于CPN 的一般定义与描述特别抽象，使得无法直接利用已有描述自动生成硬件模型，因此本文设计了“CPN 描述文档”的内容及格式，并实现了CPN 硬件模型的自动生成工具，该工具根据“CPN 描述文档”自动生成相应CPN 模型与仿真控制器的Verilog 代码描述。 系统设计与验证方案如图1 所示，在已知CPN 模型的基础上，将CPN 用“CPN 描述文档”进行描述，通过自动生成工具生成Verilog 代码描述；经过RTL 级仿真验证后，建立Quartus 工 程， 经 过 编 译， 在 Altera Cyclone V 5CSEMA5F31C6N FPGA 平台上运行测试。

图1 设计与验证方案

本文内容安排如下:首先介绍了CPN 的基本概念与定义，并设计了CPN 描述文件的内容格式与结构，然后制定了CPN 元素到Verilog 描述的映射规则，给出了自动生成工具的程序流程，最后结合实例进行了运行测试。

1 有色Petri 网与描述

1.1 定义

每个PN 都由三部分组成:表征状态的库所、表征动作的变迁以及表征流关系的有向弧。 库所用于存储托肯(token)；流关系是权向量，方向与有向弧相同，其大小是权值，变迁的发生通过权值对库所产生影响。 在CPN 中，每个库所中可包含多种颜色的token；每个变迁可存在多种激活条件，称为变迁的发生颜色；每个有向弧可包含多个流关系，每个流关系又对应变迁的一种或多种发生颜色。

一个经典CPN 可定义为一个9 元组N ＝〈P，T，A，Σ，V，C，G，E，I〉[16-17]。 其中:

· P 是库所的有穷集合，在图形表示法中，每个库所用一个圆形(○)表示；

· T 是变迁的有穷集合，在图形表示法中，每个变迁用一个矩形(□)表示；

· A⊆P×T∪T×P 是一个有限的“有向弧”集合，用单向箭头(→)表示一个有向弧，Petri 网中用有向弧表征变迁与库所之间的流关系；

· Σ 是一个非空有限的颜色集的集合，集合元素是颜色集；

· V 是变量的集合，∀v∈V，Type[v]∈Σ，变量的类型由颜色集限定，Type[a]表示a 的类型；

· C 是库所的颜色集函数，每个库所与Σ 中的一个颜色集对应，库所中token 的颜色与颜色集中的元素一一对应；

· G 是从变迁T 到变量表达式集EXPRV的映射函数，表征变迁的发生受到变量表达式的约束，∀expression∈EXPRV，Type[expression]∈Σ；

· E 是从弧A 到变量表达式集EXPRV的映射函数；每个“有向弧”由一个变量表达式限定流关系，通常，变量表达式的所有取值对应该弧表示的所有流关系，∀a∈A，Type[E(a)]＝C(p)，库所p 与弧a 相连；

· I 是CPN 的初始化函数，为CPN 中每个库所分配一个初始化表达式及该表达式对应token 的数量，∀p∈P，Type[I(p)]＝C(p)。

1.2 描述文档设计

CPN 与一般P/T 网不同，其复杂的流关系无法使用单一前后关联矩阵表示。 为了描述CPN 中的流关系，本文提出了“库所的全局关联矩阵W”概念。为库所Pn定义一个描述其与变迁的流关系的矩阵:

Wn＝NCT-MAX×NT(1)

式中:n∈[1，NP]，NP是CPN 中库所的数量；列数NT是变迁的数量；行数NCT-MAX是单个变迁发生颜色数量的最大值。 矩阵Wn中的每一项用常数“0”表示颜色C(p)下变迁发生对库所p 没有影响，常数“1”表示颜色C(p)下变迁发生会导致该库所中一种或几种颜色的token 的数量增加，常数“-1”表示颜色C(p)下变迁发生会导致该库所中一种或几种颜色的token 的数量减少，常数“2”表示颜色C(p)下变迁发生会导致使该库所中一种或几种颜色的token 的数量增加的同时使该库所中token 减少。

为增强CPN 描述文档的可读性，并清晰地描述变迁与库所间的流关系，本文将库所的全局关联矩阵W 拆成前向Wpre与后向Wpost两个矩阵进行描述，前向表征有向弧从变迁指向库所，后向表征有向弧从库所指向变迁。 将W 中所有“-1”项置为0，“2”项置为1 得到Wpre；将W 中所有“1”项置为0，“2”项置为-1 得到Wpost。 描述文档包括7 个部分:

(1)库所与变迁的个数描述:

(2)变迁发生颜色的个数描述:

(4)Pre 描述:

定义表示流关系(权向量)的基本元素为字符串“颜色标识符:权值”，颜色标识符是流关系对应库所token 的颜色，权值表示此流关系发生时对相应颜色token 数量的影响；将Wpre的每一项用基本元素表示，不同项之间用空格隔开，同一项内的不同流关系之间用“+”连接；如，Wpre的“0”项用“0:0”替换，“1”项用“sand:2+cement:1”替换；得到Wspre。描述格式如下:

图2 给出了CPN 的Verilog 模块的映射架构设计，共4 种模块:顶层模块、控制器模块、库所模块、变迁模块；通过模块中的判断、判决与更新逻辑实现CPN 的状态更新；reg 存储库所的token 数。

上述描述中，NP是库所的个数，NT是变迁的个数；NCTi是变迁i 发生颜色的个数；NCPj是库所j 包含token 的颜色的个数；L 是库所对该颜色token 的最大容量；M 是在CPN 的初始状态下库所中该颜色token 的数量。

2 自动生成工具设计

2.1 CPN 的映射

本文将CPN 状态的更新分成3 步:变迁的预激活、变迁的激活与库所token 的更新，每一步消耗一个时钟完成。 变迁的预激活是根据库所中当前token 数判断满足激活条件的变迁；在变迁的激活阶段对满足激活条件的变迁进行冲突的判断，并激活符合条件的变迁；在库所token 的更新阶段，根据激活的变迁更新库所中token 的数量，实现一次CPN状态的更新。

表1 描述了从CPN 描述到Verilog 描述的映射规则。 在Verilog 设计中，将库所和变迁分别定义为一个module 模块；将token 定义为库所模块中的output reg 类型的变量，位宽由库所的token 容限描述确定；在CPN 顶层模块中，为描述文档的Pre/Post描述中每个基本元素定义一个wire，连接库所模块与变迁模块，并将权值定义为库所模块中的parameter 参量。

表1 映射

图2 映射架构设计

2.2 工作流程

自动生成工具的工作流程如图3 所示，主要包括描述文件读取、参数分析、Verilog 描述文件打印和测试文件打印4 个部分。 测试文件包括用于RTL仿真的testbench 文件和用于Verilog 编译的自动综合脚本。 参数分析过程会生成分析文件，可用于检验读取文件得到的CPN 参数的正确性。

图3 工作流程

3 测试

3.1 测试案例

本文选用一个描述通信中“包传输”的CPN 模型[18]作为测试案例，如图4 所示，其颜色集和变量如表2 所示。 模型可以分为3 个部分:Sender、Network 和Receiver。 库所Send 存储要发送的字符串包及其编号，用颜色为(n，p)的token 表示，如(1，“Modellin”)。 变迁SendPacket 的发生根据库所NextSend 中字符串包的编号将字符串包发送到Network 端的A 库所。 库所E、F 与变迁Ok 用来模拟网络50%的丢包率，本文假设丢包率为50%。 变迁Update 根据库所NextRec 中包的编号进行包的验证，若通过验证(n ＝k)，则将包中字符串与库所Received 中原有字符串拼接得到的字符串更新到库所Received 中，同时将C 库所和NextRec 库所中token颜色更新为下一个待传输包的编号。 最后依次通过变迁TransmitAck 和变迁ReceiveAck 将下一个待传输包的编号更新到NextSend 库所中，使变迁Send-Packet 开始发送一个新的字符串包。

表2 “包传输”CPN 模型的颜色集和变量

图4 “包传输”CPN 模型

假设待传输包有3 种，为(1，“Modellin”)、(2，“g and An”)和(3，“alysis”)，分别记为包1、包2 和包3，视为库所Send 中3 种不同颜色的token，分别对应表4 中Send 行的颜色标识C1、C2 和C3；库所E、 F 包 含 2 种 ok-token， 分 别 用 于 变 迁TransmitPacket 与变迁TransmitAck；将变量n 和k 的每种取值(1，2，3)都视作库所NextSend、NextRec、C和D 中一种颜色的token。 本例中所有变迁的发生对token 的数量消耗都是1。 本文根据该“包传输”CPN 模型得到表3 所示的参数，并以此设计了描述文档。 库所容限与CPN 初始状态如表4 所示。

表3 “包传输”CPN 模型的参数

为了简化表述，本文采用p1、p2 等字符区分不同的库所，采用t1、t2 区分变迁，采用C1、C2 等字符作为token 的颜色标识，区分库所中不同的token，对应关系见表3 与表4。 其中p1、p3、p7 的颜色标识的含义对应相同，p2、p4、p8、p9 的颜色标识的含义对应相同，如p1 的C1 与p3 的C1 都指包1，p2 的C3 与p8 的C3 都指数字“3”。

表4 CPN 的库所容限与初始状态

在Received(p10)库所中，C1-token 是指空字符token，即未接收到任何字符包时的token，是CPN 初始状态下的p10 库所包含的token；C2-token 是接收包1 后的token；C3-token 是在C2-token 的基础上接收包2 后的token；C4-token 是在C3-token 的基础上接收包3 后的token。 Received 库所中出现C4-token标志着3 个包的成功发送。

3.2 测试结果

在Altera Cyclone V 5CSEMA5F31C6N 平台上进行综合，综合频率为156.37 MHz，ALMs 资源占用781，Register 资源占用2 027。 CPN 状态每秒更新5.2×107次。 并采用Quartus 18.1 的Signal tap 逻辑分析仪监控设计的运行，得到图5 所示的信号波形图，图中color2＿of＿place3 信号表示库所p3 的C2 颜色token，其值是库所中该token 的数量。

如图5 所示，rst＿n 信号置为高电平后(图中虚线)，测试从表4 第3 列所示的CPN 初始状态开始，此时库所p1 中有1 个C1-token，库所p2 中有1 个C1-token，满足变迁t1 的发生条件，而其他变迁的发生条件不充足；因此从图中虚线后在outclk＿2 信号第3 个时钟上升沿时只有color1＿of＿place3 信号变高电平，而其他信号数值不变，表示变迁t1 的发生在库所p3 中产生了一个C1-token 并且其他库所的token 数量不发生变化。 测试成功的标志，如图5 中最下方4 条信号波形所示，库所p10(Received)的4种token 从C1-token 到C4-token 依次出现，表示库所从空字符依次接收了3 个字符包的过程，进一步对其他信号进行分析，信号的变化过程与CPN 模型的规定一致，验证了自动生成工具的正确性。

图5 Signal tap 逻辑分析仪结果

4 结论

为了加速CPN 模型的仿真，本文设计基于FPGA 的系统进行加速。 本文完成了CPN 的模块到硬件结构的映射逻辑，设计了基于C 语言的CPN模型的Verilog 自动生成工具，实现了基于FPGA 的有色Petri 网仿真系统设计。 Signal tap 逻辑分析仪采集得到的信号验证了仿真系统的正确性。