基于Petri网的FPGA软件缺陷分析与改进设计

齐杏林， 马继存， 余春华

(军械工程学院弹药工程系， 河北 石家庄 050003)

基于Petri网的FPGA软件缺陷分析与改进设计

齐杏林， 马继存， 余春华

(军械工程学院弹药工程系， 河北 石家庄 050003)

为了在FPGA软件开发过程的早期发现设计缺陷并进行修改，以降低设计成本，提出了应用Petri网技术进行缺陷分析的方法。对FPGA软件开发过程中形成的工作流程和实现流程进行了分析，并在发现缺陷的基础上进行了改进设计。在某引信安全与起爆控制系统的设计过程中应用了该方法，结果表明：该方法能够发现并准确定位软件缺陷，而且在Petri网模型基础上能够迅速地进行软件改进设计。

FPGA；Petri网；缺陷分析；软件设计

随着微电子技术的发展，在国防领域应用FPGA进行信息处理与控制越来越多。FPGA本身虽为硬件，但是其设计是以软件编程的形式进行。在FPGA软件设计过程中，人工出错会导致软件中残留缺陷，及时发现这些缺陷并进行改进设计是降低软件设计成本的重要方法。软件设计按照工作流程设计、实现流程设计、代码编写的顺序进行，在每一步之后都应进行相应的分析，以便及时发现本步骤内的错误。

1962年，C.A. Petri提出了适合描述并发、异步、分布式软件系统规格的形式化方法Petri网[1]。与普通软件相比，PFGA软件采用了并行的设计思想[2]，整个软件是分模块进行设计的，各个模块之间通过信号相互关联。因此，Petri网非常适合描述FPGA软件，而且Petri网是从整个系统的角度，使用图形表现形式进行直观的描述，且对软件能够做到深入代码级别的表示。本文将研究在FPGA软件设计过程中，基于Petri网进行缺陷分析与改进设计的方法。

1 Petri网及建模

1.1 Petri网[3]

Petri网定义为一个六元组(P，T，F，K，W，M0)，其中：P为站(或称为位置)集合；T为迁移集合；F为有向弧集；K为对应位置中能够容纳令牌的最大数量；W为权函数，表示有向弧的权值；M0为初始标志。站代表状态，迁移代表活动。

系统当前的状态可以用Petri网的标志表示，标志即Petri网中令牌的分布情况。如图1中的(Pi，Ti，Pj)网，它含有2个站，其中:迁移触发前的标志为M0=(2，0)，代表站Pi中含有2个令牌，站Pj中没有令牌；迁移发射后的状态变为标志M1=(0，1)，代表站Pi中没有令牌，站Pj中含有1个令牌。

图1 标志示意图

1.2 基于软件流程的Petri网建模

1.2.1 软件相关单元的Petri网建模

软件相关单元是指会影响软件运行过程或受软件运行影响的变量、寄存器和外部元器件等。因为这些单元具有保持自身状态不变的特性，如果直接在整个系统网中对其进行建模，就会造成整体Petri网过于复杂。下面，以标志变量为例对软件相关单元的Petri网建模进行说明。

标志变量是标志某过程是否已经发生的变量，该过程的发生将影响标志变量的值，其通常含有0和1两个值。设计标志变量的Petri网模型如图2所示，标志变量的示意图如图3所示。图2模型中共包含2个站，分别代表标志变量的值为0和1。图3在软件的整体Petri网中使用，通过在其输入弧上添加置0或者置1的命令，来明确软件对标志变量值的影响。

图2 标志变量的Petri网模型

图3 标志变量的示意图

标志变量的Petri网模型在软件整体Petri网模型中受Ti和Tj的输入站控制。通过分析标志变量的物理性质，对其运行规则进行如下规定：

1)在Ti或Tj迁移的输入站中有令牌出现时，迁移立即发射，并且在软件Petri网模型中存在冲突迁移时，Ti或Tj优先发射；

2)在标志变量的当前值为0、Ti的输入站中含有令牌时，或在标志变量的当前值为1、Tj的输入站中含有令牌时，输入站中的令牌自动消失，标志变量的值保持不变；

3)其他运行规则与Petri网的基本运行规则相同。

1.2.2 系统完整的Petri网建模

根据软件流程，结合相关单元模型建立总的Petri网模型。软件流程转换成Petri网模型遵循如下3个规律[4-5]：

1)将流程图中用矩形框表示的进程转变成Petri网中的迁移；

2)将流程图中的连接弧转变成Petri网中的站；

3)将流程图中的判断节点转变成起判断作用的站及该站的2个迁移后集。

2 基于Petri网的软件缺陷分析方法

2.1 软件设计过程分析

软件设计的过程为：1)依据软件需求进行工作流程的设计[6]，工作流程代表的是软件要干什么，对于FPGA软件，其对应的是软件的输入和输出是什么；2)根据工作流程，对软件的实现流程进行分析，实现流程是指软件怎么运行，即要得到所需的输入、输出,软件自身是如何动作的；3)根据软件实现流程进行代码的编写。

对于复杂的软件，由工作流程设计实现流程，可以先根据软件功能将工作流程划分为相对独立的流程段，然后分别对各个流程段的软件实现流程进行设计。在工作流程正确的前提下，如果各个流程段的实现流程都正确，则能够说明系统完整的实现流程是正确的。

由于实现流程与代码基本一致，所以对代码的分析与对实现流程的分析基本相同。因此在进行软件的缺陷分析时，只需对工作流程和实现流程进行分析即可。

2.2 Petri网缺陷分析方法

对于一个Petri网，在其初始标志下，通过使能的迁移，会触发Petri网产生新的标志，在新的标志下又有新使能的迁移，如此反复，将得到更多的标志，这一系列的标志可以用树结构来表示，被称为覆盖树[7-11]。覆盖树以初始标志作为根节点，经过使能的迁移，由初始标志得到的新标志作为树中的节点；树的叶子节点为无使能迁移的标志或者重复出现的标志。这样,覆盖树就覆盖了Petri网的所有可达标志。因为Petri网的标志表示系统的状态，所以覆盖树也就覆盖了系统可能出现的全部状态，通过分析覆盖树就能够分析整个系统的状态。

通过前面的分析，在软件设计过程中利用Petri网技术进行缺陷分析，可以按照以下过程进行：

1) 进行需求分析，进而设计软件的工作流程；

2) 建立软件工作流程的Petri网模型，并构建相应的覆盖树；

3)通过分析覆盖树,对软件工作流程进行分析，并在发现错误的前提下进行改进设计；

4)划分工作流程为相对独立的功能模块；

5)对软件各功能模块分别建立详细的实现流程；

6)根据软件实现流程，建立相应的Petri网模型，并构建覆盖树；

7)通过分析覆盖树，对软件的实现流程进行分析，并在发现错误的前提下进行改进设计。

3 基于Petri网的FPGA软件改进设计

3.1 内锁

系统中出现的含有错误的状态可能是在同一个标志中同时出现了会导致错误的2个站，为了避免这种情况出现，可以在Petri网中加入限制它们同时出现的内锁。加入内锁的Petri网如图4所示，为了避免P3和P2同时出现，向其中加入一个新站Padd，这样T1的发射必须在T2之后，保证了P3中丢掉令牌以后，P2才能获得令牌，从而在同一个标志中不可能同时出现P2和P3。内锁在软件中通常采用监控程序来实现。

图4 加入内锁的Petri网

3.2 标志变量

在覆盖树构造过程中，Petri网中某一部分可能会意外重复地运行。为了避免这种情况发生，可以向Petri网中添加标志变量，并以该变量作为意外重复运行部分运行的前提条件。如：某FPGA软件的一个功能是在FPGA复位后，首先进行10 s的定时，在定时结束后发送“计时结束信息”，设计其Petri网模型如图5所示。通过分析发现：在晶振信号的驱动下，定时器会重复计时，并在每一次计时结束后，重复发送远距离接电计时结束信息。为了避免这种情况发生，向Petri网模型中引入r_restrict标志变量，如图6所示。在复位后置r_restrict为0，在控制远距离接电时间的计数器之前，加入判断r_restrict是否为0的条件，并在一次定时后置r_restrict为1，从而防止了远距离接电计数器的重复计时。

图5 意外重复发射T8的Petri网

图6 加入标志变量后的Petri网

4 实例应用

在某引信安全与起爆控制系统的设计中，对FPGA软件的工作流程进行了设计，并对其进行了缺陷分析，结果发现：在工作流程中没有缺陷。划分了FPGA软件的功能模块，设计了各功能模块的实现流程，并对其进行了缺陷分析，结果发现：在转速突降环境判断模块存在缺陷。该模块的Petri网模型如图7所示，其中a、b、c、d代表输入的电平量，其值取1时为高电平，取0时为低电平，复位后初始化为abcd=0000。图7中虚线框内为改进后添加的部分。

对改进之前设计的实现流程构建覆盖树，如图8所示。图中标志Mp+5和Mp虽然相同，但根据实际的时序运行情况可知：Mp+5和Mp此时所表示的系统状态已经发生改变，Mp到Mp+4的所有标志均是由上一次时钟的变化引起的。而在Mp+5到Mp+7这一标志处，则表示系统马上进入下一个时钟周期，以及由下一个时钟周期的开始时刻所引起的系统状态变化。所以在标志Mp+5处还要继续进行分析。图中带箭头虚线代表的是从标志Mp到Mp+7的重复变迁过程；所不同的只是随着循环次数的增加，P105中的令牌数ω在逐渐增加。

根据图8可知：在充电结束时，系统又意外地返回了系统运行的中间状态，即图中最后一个标志(P24，P4，P106，P104，P108)处，这将使K2不能正常打开，发火电容持续充电，这是由r_env_2被重复地置1造成的。

图7 转速突降环境判断模块Petri网模型

图8 转速突降环境判断模块Petri网覆盖树

为了消除该软件缺陷，向Petri网中添加一个标志变量r_env_2_rstr，如图7中虚线框所示。复位时将r_env_2_rstr置0，只有在r_env_2_rstr=0的情况下，才能控制K2闭合，发火电容充电。在T15发射时，将r_env_2_rstr置1，这样在T15发射后r_env_2置0，并且不能再回到r_env_2=1的状态，从而T25发射，K2正常打开，发火电容停止充电。

[1] Lv Y Q, Lee C K M, Wu Z, et al. Priority-based Distributed Manufacturing Process Modeling via Hierarchical Timed Color Petri Net[C]. Washington, DC: IEEE Computer Society, 2013.

[2] 马克斯菲尔德. FPGA权威指南[M]. 杜生海,译.北京:人民邮电出版社,2012.

[3] 孙海春, 杜玉越. 基于程序Petri网的新型软件开发方法研究[J]. 系统仿真学报, 2009, 20(增刊): 55-58.

[4] 张贤彪, 尚雅玲. 引信安全系统信息控制逻辑分析[J].四川兵工学报, 2010, 31(1): 32-35.

[5] 吴越, 王宏伟, 史长虹, 等. 引信安全系统惯性保险技术研究[J].中北大学学报: 自然科学版, 2012, 33(3): 257-261.

[6] 马海云. 面向过程的软件设计及优化技术[M].北京：国防工业出版社, 2013.

[7] 赵静丽.基于Petri网的构件软件系统的安全性分析[D].太原：太原科技大学,2011.

[8] 林红, 杨瀚程. 基于Petri网的软件故障树分析[J]. 火控雷达技术, 2013,42(4):40-43.

[9] 雷军环. 利用广义随机Petri网分析软件系统可靠性[J].计算机测量与控制, 2013,21(2):433-435, 444.

[10] 赵成贵, 普兆斌. 一种软件可靠性评估模型及其Petri网描述[J].计算机应用与软件,2012,29(1):141-144.

[11] 王佳慧, 王书锋. 随机Petri网可视化软件的设计与实现[J].计算机工程与设计,2011,32(5):1845-1848.

(责任编辑:尚彩娟)

Defect Analysis and Improvement Design of FPGA Software Based on Petri Net

QI Xing-lin, MA Ji-cun, YU Chun-hua

(Department of Ammunition Engineering, Ordnance Engineering College, Shijiazhuang 050003, China)

In order to discover the design defect of FPGA software and improve the software in the early stage of development process to decrease the cost of development, the method of using Petri net in defect analysis is proposed. The working flow and realization flow are analyzed, and on the basis of defects discovered, the software is improved. This method is used in a design process of safety and detonating control system, results prove this method can discover and locate defects exactly, based on the Petri net model, software improvement can be gained easily.

FPGA; Petri net; defect analysis; software design

1672-1497(2015)01-0090-05

2014- 11- 18

齐杏林(1964-)，男，教授，博士。

TP306+.3

A

10.3969/j.issn.1672-1497.2015.01.018