基于FPGA的Petri 网模拟器设计与实现

周韬略，张小军，陈成官，曾庆田，张德学

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

0 引言

Petri网是一种抽象规范语言特别适用于并发系统建模，不仅可以用常规语言描述，还能使用可视化图形表示。这些特性使得Petri 网作为实现工具被广泛应用。国内外学者一直保持着对其理论研究［1-3］。Petri网被认为是对离散事件系统并发行为建模的有效方法。具有充分的模拟能力和丰富的分析方法，是一种适合描述和分析具备异步性、并发性、并行性等特点的形式化语言［4-5］，Petri 网的应用领域也随着理论的发展而不断拓宽。尽管它们被广泛使用［6-8］，也主要集中在建模、验证和系统模型验证上，硬件发展的同时促进了Petri网的应用［9-10］，但基于FPGA 设计Petri网硬件模拟器的研究较少。Gomes等［11-13］已经用硬件描述语言VHDL设计Petri 网，但用Verilog HDL 描述的研究方面甚少。Verilog HDL 语言具有行为描述能力及与硬件行为无关的优势，可实现硬件电路与软件设计相结合，适合用于描述异步并发系统，是Petri 网硬件实现的有力工具［14］。

本文研究Petri网关联矩阵到Verilog HDL语言编译程序设计的方案，实现基本Petri 网的P／T 系统到Verilog HDL语言转换的自动编译程序，采用Verilog HDL来对系统的Petri网模型、控制器模块和存储器模块进行描述。并在EDA 软件平台下（Modelsim 和Quartus II）对综合模块的Verilog HDL 语言描述进行综合、仿真、适配，并下载到FPGA 中。最后将指令信号写入寄存器，使得运行结果在Quartus软件中的信号逻辑分析仪（SignalTap II Logic Analyzer）内显示。

1 基本理论

1.1 Petri网理论

图1 为一个基本Petri 网，其中s1、s2、s3、s4为库所，t1、t2、t3、t4为变迁。在使用Petri网模拟系统时，M0来描述其初始状态。在初始状态时，因为可能有不止一个变迁具备发生权，使得系统存在着多种可能性。只要有变迁发生，系统就会进入一个新的状态，同时得到新的标识M1。在新标识M1下可能也会存在有发生权的变迁。网系统就是伴随着变迁的发生而运行的。

图1 典型的基本Petri网

Petri网可看作是对状态机的一种推广：变迁起源于多个活动状态，若干状态可能需要处于活动状态才能使能变迁。Petri网是一种并发模型，可同时触发多个变迁。Petri网可用简单的图形表示：被动实体（例如状态或资源），命名库所，表示为圆或椭圆；活动实体（例如动作或函数），命名变迁，表示为矩形或条形。库所只能连接变迁，变迁只能连接到库所。库所内的资源命名为托肯（token），可删减和增加，有向弧指向的每个变迁只能在所有输入弧连接到的库所内托肯个数满足条件才能工作［15］。

根据变迁规则，给出网系统（net system）的变换规律。一个标识网Σ ＝（S，T；M，F）的网系统（S 中的元素为库所，T 中的元素为变迁，M 是状态标识，F 是一个有向边的集合），具有以下发生规则：

（2）若M［t ＞，则在标识M 下，变迁t 可以发生，从标识M发生变迁t得到一个新标识M′（记做M［t ＞M′］），对于∀s∈S，

1.2 关联矩阵

关联矩阵分为输入和输出矩阵，输入和输出矩阵的每行和每列分别为一个库所和一个变迁，矩阵的长度和宽度分别为该Petri 网库所和变迁的数量，输入、输出矩阵的每行和每列非零值的个数分别为该库所和该变迁的出度和入度，矩阵中非零元素的位置和数值分别为弧的连接置位和权值，输入和输出矩阵分别为弧的方向。

以图1 中的Petri网为例，s1～s4表示4 个库所，其关联矩阵的列数为4。t1～t4为4 个变迁，其关联矩阵的行数为4。若某库所与某变迁间有输出弧，则输入矩阵的对应位置的元素为该弧的权值，因为s1有一个指向t2的弧，假如图中弧上权值都等于1，则输入矩阵的第2 行第1 列为1；若某变迁与某库所间有输出弧，则输出矩阵对应位置为该弧的权值，例如t2有一个指向s2的弧，因此输出矩阵的第2 行第2 列为1；若某库所与某变迁之间没有连接关系，则对应位置元素为0。根据以上规则，图1 中Petri 网的输入和输出矩阵分别为

2 Petri网硬件设计

每个Petri 网具有不同的形状和规模，如果采用Verilog HDL 针对每个Petri 网进行编程，将会面临庞大的代码工作量，本文运用基本Petri网理论和关联矩阵理论来设计一个自动代码生成器。

具体程序流程如图2 所示。

用户输入关联矩阵的长度和宽度（即Petri网的规模），根据输入的信息，程序读取关联矩阵，若成功读取，用户界面将会输出该Petri 网的基本信息，之后程序继续读取延时矩阵信息生成延时文件。若延时信息成功读取，用户可继续输入Petri网的初始标识和库所容量。程序根据以上读取的信息，分别生成控制器文件、存储器文件、顶层文件和测试文件的Verilog代码。

图2 程序流程图

2.1 从关联矩阵到Verilog HDL 编译程序的自动生成

将2 个关联矩阵分别写入2 个文本文件中，利用C语言读取文件内的矩阵信息，存入2 个二维数组，输入容量函数和初始标识并将其存入2 个一维数组。再用C语言解析以上信息，根据Verilog HDL 的语法和Petri网硬件建模的方法，建立Verilog 文件并打印Verilog代码，自动生成Petri网的硬件架构。本设计不止局限于2 个8 ×10 的输入、输出矩阵，随着库所、变迁个数的增加，可根据不同的输入、输出矩阵生成数据宽度以及加载初始值的深度同时改变的Verilog文件。

2.2 基本Petri网库所和变迁的实现

对于基本Petri网，其库所内的标识数只有0 和1两种状态，且所有弧的权值为1。对于基本Petri网，只对库所、变迁两个行为可进行如下描述。

图3 是一个基本Petri网库所模块。库所名为s1，有两个前驱变迁t1和t2，一个后继变迁t3。若前驱变迁t1和t2只发生1 个，库所s1内的托肯数加1；若前驱变迁t1和t2都发生，库所s1内的托肯数量加2；因库所s1内托肯数量大于0 而满足变迁t3发生条件，t3发生，同时消耗掉s1内的一个托肯。

图3 Petri网的库所实现

图4 是一个基本Petri网变迁模块。变迁名为t1，有3 个前驱库所s1、s2和s3，两个后继库所s4和s5。当前驱库所s1、s2和s3内托肯数同时满足条件即3 个库所内托肯数都不为0 时，变迁t1发生，同时消耗s1、s2和s3内各1 个托肯；变迁t1发生后，s4和s5获得1 个托肯。

图4 Petri网的变迁实现

在Verilog语言中，可以将每个库所和变迁作为单独模块连接起来。每个库所模块的输入信号为所有前驱变迁模块的信号和后继变迁模块的反馈信号，输出信号为托肯个数；变迁模块的输入信号为所有前置库所模块的托肯个数，若变迁发生，则向后继库所模块输出1，若变迁不发生，输出0。每当库所模块接收到所有的前驱变迁模块发生信号都为1 时，库所模块输出的托肯数加1；每当变迁模块的所有前驱库所模块皆满足变迁发生条件时，该变迁模块发生，同时向前驱库所模块发送反馈信号，前驱库所模块根据反馈信号将托肯数减1。库所的硬件结构如图5 所示。

图5 库所的硬件架构

该模块有一个前驱变迁，两个后继变迁。其中：load、p＿init、clk、p＿in、p＿T1、p＿T2均为输入信号；out 和conflict为输出信号；clk 为时钟信号；load 为加载信号。当load 为1 时，该库所模块的托肯数等于赋初值输入信号p＿init 的值。若load 信号为0，则当前库所托肯数根据p＿in、p＿T1和p＿T2进行修改，p＿in 是前驱变迁的输入值，p＿T1和p＿T2分别为2 个后继变迁的资源请求值，修改内容是：当前值加上来自前驱变迁的输入值p＿in，减去2 个来自后继变迁的输入值p＿T1和p＿T2。在修改前，先判断库所内部资源是否足够进行修改操作，若不足则不修改。模块内还有一个比较器，将2 个资源请求值p＿T1、p＿T2的和与当前库所值和p＿in的和比较，若资源请求过大，即该库所模块的资源不足以满足2 个后继变迁的需求而产生冲突，冲突信号conflict向控制器模块输出1，令控制器模块来解决冲突。

变迁的硬件结构如图6 所示，该模块有2 个前驱库所，1 个后继库所。其中t＿inp1、t＿inp2、t＿enp1、t＿enp2均为输入信号，t和T为输出信号。2 个前驱库所模块传递过来的输入信号t＿inp1 和t＿inp2 经过一个与门，产生t信号，t 信号表示变迁是否有发生的条件。还需要2 个来自库所控制器的使能信号与t信号通过与操作，最终产生真正表示变迁的发生信号T。

图6 变迁的硬件架构

2.3 存在冲突的P／T系统

存在冲突的P／T系统相较于基本的Petri网，需要判断可能产生冲突的位置、时间以及冲突产生后资源分配等问题。本文引入了控制器（controller），每个可能发生冲突的库所模块都配备一个控制器模块，且在变迁模块中引进了一个变迁使能信号，变迁模块满足发生的条件便可使能，库所模块根据变迁模块的使能信号判断是否会发生冲突，若存在冲突，资源的分配问题交由控制器来处理，获得资源的变迁模块才能获得发生权。

控制器模块负责存在冲突的变迁资源分配，即变迁发生权选择模块。本文将控制器分为两种，轮换型和随机分配型，用户可根据处理冲突的机制进行选择。两种控制器通过不同的方法解决存在冲突的变迁资源分配问题。根据上述改进后的库所模块所给出的冲突发生信号，若信号为1，则启用资源分配机制，选出可以发生的变迁，并将该变迁的控制信号置1，其他变迁控制信号置0；若信号冲突发生为0，则该控制器控制的所有的变迁控制信号均置1。

轮换分配控制器定义一个种子，复位时种子的值为0，每发生一次冲突种子的值加1，当种子的值超过n－1 时（假设该控制器控制n个变迁）种子的值置0，以此循环。当种子的值为i－1 时，则该控制器控制的第i 个变迁的控制信号为1，其他变迁的控制信号为0。

随机分配控制器采用线性反馈移位寄存器（linear feedback shift register，LFSR）伪随机数发生器，伪随机数等概率产生，可能产生的伪随机数平均的映射到该控制器控制的每一个变迁。若冲突发生，伪随机数发生器产生一个伪随机数，映射到对应的变迁获得发生权。

2.4 控制器模块的实现

该控制器区别于2.3 节中用于处理冲突的控制器，是输出控制信号控制整个Petri网的运行状态的模块。此模块通过检测按键的上升沿来选择Petri 网的运行模式，各模式及其功能见表1。

表1 Petri网模式和功能

状态转换图如图7 所示。IDLE为空闲状态，是系统启动时的初始状态；CONFIG＿P 状态下可以接收外部库所初始值数据的输入；LOAD＿OUT状态下各库所加载上阶段接收到的值；START为系统进入调试的准备阶段，此时可通过键值选择4 种调试模式；调试结束后进入STOP状态。

图7 有限自动状态机

2.5 存储器模块的硬件实现

为准确地加载的库所初始值以及将得到的P／T结果值回传，需要存储器模块提供缓冲的空间，存储结构如图8 所示。

图8 RAM存储结构

加载初始值在使能信号有效时，根据读写地址将128 bit的value值加载给库所，初始值的bit数可根据库所的个数改变。以10 个库所、8 个变迁为例，从最上层开始依次往下保存p1、p2～p10 的初始值，多余部分则忽略。在Petri网运行过程中，s10～s1内储存实时采集到的库所内托肯数，t8～t1储存实时采集到的变迁状态。“count”内保存实时运行步数。

3 基于FPGA的Petri网测试系统

在Modelsim仿真平台测试的基础上，本文采用QuartusⅡ15.0 进行综合测试。采用Altera Stratix V（5SGXEA7N2F45C2）器件综合，并下载到开发板中进一步测试。其工作频率为300 MHz，ALMs 资源量为477，Registers资源量为1 034。

3.1 测试方案

在Quartus编译、综合并下载到开发板后，通过检测按键上升沿，将指令信号写入寄存器中。button［0］对应复位键，可使Petri网进入初始状态。button［1］控制状态机转换到加载库所初始值的状态。数据加载后用button［2］将状态机转换到START 状态，启动Petri网的调试模式。

3.2 测试结果

此处以Continue模式为例，按下button［5］切换到该模式下，如图9 所示，在Quartus软件的SignalTap II Logic Analyzer中可看见，在时刻4，各库所第一次被初始化（加载入初始托肯数值），P1 内部托肯数为4，P2为2，P3 为5，P4 为1，P5 为1，P8 为2，P9 为2。同时库所的初始化使得变迁发生，由图中可见，变迁T3 和T4 发生。变迁发生后，在时刻9，可以看到P4 和P5 内托肯被消耗，P6 和P7 内托肯个数加1，P10 因有2 个前驱变迁而托肯个数加2，此时变迁T1 和T2 因满足条件而发生。Petri 网保持运行，直到状态机转换到STOP状态下才停止运行。

图9 CONTINUE模式下运行的Petri网

4 结语

本文对Petri网的硬件模拟进行了研究，设计了基于FPGA的Petri网硬件仿真器，采用C语言实现代码自动生成器。该生成器根据输入的关联矩阵，以库所和变迁作为基本模块，同时引入controller 模块解决冲突问题，最终生成整个Petri 网的硬件架构，并编译下载到FPGA 中。该仿真器可运行150 M／s 步仿真，实现了较快的仿真速度。