摘 要：Petri网已经逐渐成为异步并发现象建模的重要工具，Petri网的硬件实现将为网系统性能分析以及并行控制器的设计提供一种有效的途径。首先介绍了Petri网C／E系统的特点，然后讨论了硬件实现的基本结构模块。最后以哲学家晚餐为例子，用VHDL语言对结构进行了描述，使用了ALTERA公司的CPLD集成开发工具Max＋PlusⅡ，并给出了软件仿真的结果。
关键词：Petri网；CPLD；并发；VHDL
1 引 言
Petri网越来越成为研究离散事件动态系统的一种有力工具，适用于异步并发现象的建模。他的2个成功的应用领域是系统性能评价和通信协议分析，其他很有前途的应用领域包括分布式软件系统、分布式数据库系统、并发和并行计算、柔性制造与工业制造系统、离散事件系统、多处理机系统、数据流计算、容错与故障诊断系统、逻辑推理、办公自动化系统、形式语言、人-机系统、神经网络和决策模型等。
Petri网的硬件实现将为并行控制器的设计提供又一条有效的途径。相对于软件实现，Petri网的硬件实现有他的优越性。用软件编程语言来描述Petri网，虽然具有很大的灵活性，成熟的语言工具也比较多，但是，所有的软件编程语言都不能很好的反映Petri网的异步并发特性，这就等于丢弃了Petri网的最大优点。而逻辑电路的信号传递方式常常是异步并发的，他与Petri网有天然的对应关系。所以，用Petri网来描述硬件设计，以及用硬件来实现Petri网功能，这两方面的 工作都是非常有意义的。
在目前已有的一些Petri网的硬件实现研究［1］中，一般侧重于解决具有抑制弧和允许弧的Petri网系统。这种系统中的并发冲突通过人为的加入抑制弧、允许弧而得到解决，从而破坏了系统运行的独立性。因此，在很多要求不能有人为干扰的场合，这种方法就无能为力了。本文通过一个随机选择器的设计，以非人为的方式消解了冲突，使这个问题得到了很好的解决。
本文在具体设计中，选用了VHDL语言。相对于其他计算机语言，如C语言、汇编语言，VHDL具有明显的特点。VHDL作为一种硬件描述语言，他描述的对象始终是客观的电路系统。由于电路系统内部的子系统乃至部分元件的工作状态和工作方式可以是相互独立、互不相关的，也可以是互为因果的和相互冲突的。这表明，在任一时刻，电路系统可以有许多相关和不相关的事件同时并行发生，这种并行工作方式是任何一种基于CPU的软件程序语言所无法描绘和实现的。传统的软件编程语言只能根据CPU的工作方式，以排队式指令的形式来对特定的事件和信息进行控制或接收，在CPU工作的任何一个时间段内只能完成一种操作。因此，任何复杂的程序在一个单CPU的计算机中的运行，永远是单向和一维的。VHDL则不同，他是适应实际电路系统的工作方式，以并行和顺序的多种语句方式来描述在同一时刻中所有可能发生的事件。
由于FPGA和CPLD的问世，及其在应用方面的迅速推广，各种EDA软件工具相继出现，并且功能不断增强。硬件设计软件化，这就为Petri网的硬件实现提供了方便的工具。
国际上对这方面的研究也很重视。首先是法国于1975年成立了逻辑控制器标准表示委员会，为越来越复杂的逻辑控制器寻求一种标准化的描述工具，以促进微处理器的发展。最后他们选中了以Petri网为基础的逻辑控制器图形表示工具，命名为GRAFCET。国际电工委员会（IEC）于1988年正式颁布了国际标准IEC848《控制系统功能表图的绘制》，这一标准的颁布，迅速为各工业国家所采用，并且在可编程逻辑控制器中得到广泛应用，使得Petri网的应用得到工业界的支持。我国于1993年颁布了“GB/T6988.6-93”，等效采用IEC848。
2 基本Petri网简介
K，W，M0依次是N上的容量函数、权函数和标识，M0称为∑的初始标识。基本Petri网就是K=1,W=1，这时库所内的标识数要么是1，要么是0，而且所有的弧权都是1。
3 基本并发Petri网的模块结构
基本Petri网系统经常会遇到的一种情况是如图1所示的冲突。
变迁T1，T2发生的条件都满足，如T1发生T2就不可能再发生，反之，若T2先发生，则T1就失去发生的条件。实际中T1，T2究竟哪个发生具有随机性。系统实现的难点就是在众多满足条件的变迁当中随机地选择一个使之发生。
本文将基本并发Petri网采用硬件来描述，硬件设计分为3个基本逻辑模块：
（1）Place 实现库所的模块。
（2）Transition 实现变迁的模块。
（3）RandomChoice 实现随机选择的模块。
如图2所示。
库所与变迁之间的信号通道：
up＿tr 指示该库所的上级变迁发生标识数满足。
down＿tr 指示该库所的下级变迁发生标识数满足。
tr＿fire 变迁发生，库所内标识数加1或减1。
整个设计是模块结构，模块之间的信号传递是固定的，所以模块的重新设计和改进相互独立，可重用性强。下面就各子模块的工作原理进行如下分析。
3．1 “Place”模块
结构图如图3所示。Place模块是实现库所的模块，他的主体部分是一个计数器。计数器的计数值表示库所的标识数，当与这个库所相关的变迁发生以后，变迁模块通过引脚tr＿fire发出一个信号，这个信号作用在计数器的加减控制端，高电平时加，低电平时减，以此来控制计数器的状态。在系统时钟的作用下，计数值加1或减1。这样，计数值表示的标识数就改变了。
这里的计数值还用来判断库所的标识数是否满足与之直接相关的上级和下级变迁发生的条件。本文只讨论基本并发Petri网，所有的弧权都是1，也就是说只要标识数为1，down＿tr是高电平，相关的上级变迁不能发生，下级变迁可能发生。反之，标识数为0的时候，up＿tr是高电平，相关的上级变迁可能发生，下级变迁不能发生。up＿tr和down＿tr的信号输出将要被变迁模块接收，用来判断哪个变迁最终发生。
3．2 “Transition”模块
变迁模块是一系列的判断逻辑电路，对库所模块输出信号进行判断，并根据随机选择的结果控制库所计数器的加减。以一个特定的变迁为例，这个变迁模块收集与之相关的库所模块的输出信号，包括up＿tr和down＿tr，在上级库所的down＿tr以及下级库所的up＿tr都是高电平时将active引脚置高电平，表示这个变迁发生的条件满足了。这样，当有多个变迁模块的active引脚为高时，说明有冲突发生。这些active信号进入随机选择模块（RandomChoice）处理，选中的一个从choice引脚返回，通过tr＿fire引脚控制相应的库所模块改变标识数。
3．3 “RandomChoice”模块
随机选择模块（RandomChoice）由2个部分组成，随机数发生器和多路复用器。他的作用是从众多满足发生条件的变迁中随机的选择一个发生。假设有4个变迁满足发生条件，相应的4个信号active1到active4进入复用器。这时候取随机数发生器输出值的最低两位控制多路复用器，实现四选一，从choice输出。由于随机数发生器产生的数是随机的，那么他的最低两位也是随机的，这样做出的选择就能满足系统要求的随机性了。任何时候，这些冲突的变迁只能有一个被挑选出来，如图4所示。
将这3个部分结合起来，具体的系统运行情况如下：首先，给表示库所的计数器赋初值，这个初值对应于库所的初始标识数，然后变迁模块根据各个计数值判断哪些变迁可能发生，将冲突的变迁通过随机选择返回来控制相应的库所改变标识数，接着又开始下一个循环，由变迁模块判断哪些变迁可能发生…。从赋予计数器初值以后，整个系统就处于完全自主的运行状态中，没有任何的外来干扰。可以事先给系统定义一个结束的时间，这样经过一段时间以后，系统自动停止运行，就可以看到系统运行过程的相关报告，比 如说某个变迁在这段时间里发生了多少次等。
4 应用举例
下面以著名的“哲学家晚餐”问题为例：5个哲学家围着一个圆桌晚餐，餐桌上每2人之间有一把餐叉，一共5把，一个哲学家必须同时拥有2把餐叉才能进餐，首先建立其Petri网模型如图5所示。
库所fork1到fork5表示餐叉的状态，空闲时标识为1，被使用时标识为0。库所eat1到eat5表示哲学家的状态，用餐时标识为1，空闲时标识为0。两种变迁分别是hun和fin，表示饥饿和用餐结束。每一个哲学家要用餐，必须同时拥有相邻的2个餐叉。在初始状态下，5把餐叉都是空闲的，哲学家都处于空闲状态，库所fork都有一个标识，库所eat都没有标识。很明显，哲学家进入用餐状态要面对一个餐叉数量不足的情况。也即变迁hun1～hun5是并发冲突的。根据上面叙述的基本并发Petri网的模块结构，可以将这个Petri网系统的各个变迁以及库所、随机选择器用VHDL语言描述出来。
部分VHDL源程序如下：
5 结 语
我们给出了一种基本并发Petri网的硬件实现方案，保证了变迁实施的并发性。该方案可以扩展应用 到许多实际问题的Petri网设计方案的硬件实现中去。这些系统常常会包含许多并发机制，用硬件实现将为Petri网的应用开拓更大的空间。本文通过著名的“哲学家晚餐”为例子，用Petri网来设计描述，并通过硬件描述语言VHDL仿真实现了这一功能。通过随机选择器的使用，以非人为干涉的方式解决了冲突问题。由于整个结构采用了VHDL语言分模块描述，使设计具有很强的可读性、可重用性以及可修改性。
［1］赵不贿，景亮，严仰光．Petri网的硬件实现［J］．软件学报，2002，13（8）．
［2］宋万杰，罗丰，吴顺君．CPLD技术及其应用［M］．西安：西安电子科技大学出版社，1999．
［3］袁崇义．Petri网原理［M］．北京：电子工业出版社，1998．
［4］Frank A．Scarpino，VHDLand AHDLdigitalsystem implementation pretice［M］．HallPTR．，1998．
［5］Kubatova H．Petri Nets in hardware design proceedings of the 32 international conference MOSIS98，1998．
