研究Petri网的并行化功能分区策略

研究Petri网的并行化功能分区策略摘要：为了解决佩特里网系统的并行算法和并行功能，实现佩特里网的并行控制和执行，基于P-invariant和T-graph的两个不同的功能分区策略被提出来解决佩特里网系统的并行算法。首先，在分析佩特里网模型和并发功能后，P/T网的并行系统功能的基本思想被提出来。其次，代数方法，P-invariants的代数解法和齐次线性方程用来描述P/T网并行数学模型和它的正式流程；佩特里网的并行分区策略基于P-invariants，模型分割、创建过程的条件，通过给出理论证明和实例验证得出了并行分析。T-graph被定义的概念从过度的角度；通过理论证明和实例验证Petri网模型的子网划分原则，子网划分条件和并行化分析。最后，这两种佩特里网功能分区策略的性质：P-invariant和T-graph的对比，他们的优点和缺点进行了评估。因此，有效的分区策略是为佩特里网的并行化。关键词：并行；库所；变迁；分区策略一引言Petri网是一种数学模型和系统分析工具的图形化建模工具。它特别适合于具有同步，并发，冲突的离散事件系统建模，并且被广泛应用于复杂的系统的设计与分析，如分布式并行处理，离散事件，柔性制造。目前，原型Petri网，有色Petri网，时间Petri网和其他系统模型建立，专注于静态分析和研究其结构，行为，功能的；系统的动态性能行为和功能是反映系统仿真，动画或操作。Petri网是并发运行的进程的同步和互斥的复杂系统中最直接的、自然的和精确的表示工具。所以，研究的Petri网系统并行的方法以便提供有效的并行化方法在实际Petri网系统的实施和运行是非常重要的。在Petri网系统并行化的研究中，文献[1]提供了在P/T网中集中式方法；该方法可以扫描每个变迁模型，检查转换的触发器，但它不能保持并行模式；文献[2]提出在有色Petri网分散式方法。该方法完全专注于分布式执行，通过程序来实现每个过程和变化，它保持并行的模型，但是当网络规模变大并且有大量的元素的颜色集的元素时，其效率是很低的。文献[3]提供了划分条件的不变量，适用于探讨在大型网络中，但缺乏Petri网络的并行分区策略的研究和分析，缺乏完整性划分条件，以及对Petri网并行算法的设计和实现。因此，我们希望提供有效的划分策略并行算法的设计和实现，研究的Petri网功能划分策略是P-不变和T-图。二P/T网模型和功能分析有两种关于Petri网的模式表示方法：一个是图形表示，另一种是代数的表示。在大多数情况下，代数表示和图形表示是等价的。因此，我们结合了两种方法来分析Petri网模型的结构和并行功能模型，来揭示该Petri网可以并行的内部机制。A：P/T网和原型的Petri网为了深入分析P/T网模型和它的功能，我们给出的P/T网络的代数定义1。1，Petri的其它相关基本概念在文献[4-5]中。定义一：六元组N=（P，T；F，K，W，M）称为一个库所变迁网系统，其中W：F→{1，2，3…}称为权函数。（1）K：P→{1，2，3…}，称为容量函数；M：P→{1，2，3…}是N的一个标示，满足条件∀p∈P：M（p）≤K（p）；（2）对于变迁t∈T，t是可行的，记作M[t＞的条件为：∀p∈·t：M(p)≥W(p，t)∀p∈t·-·t：M(p)+W(t，p)≤K(p)∀p∈t·∩·t：M(p)+W(t，p)-W(p，t)≤K(p)；（3）若从M发生t得到的新标识为M′，则∀p∈P：M（p）－W（p，t），若p∈·t－t·；M′（p）＝M（p）＋W（t，p），若p∈t·－·t；M（p）＋W（t，p）－W（p，t），若p∈t·∩·t；M（p），其他。记作M[t＞M。从定义1，我们可以知道P/T网络是基于原型Petri网，并增加了容量函数和权重函数的功能集合。Petri网图等价表示为：P是一组在所有的库所顶点组成部分；T是包含所有变迁的图表。它们构成了两种不同类型的Petri网的顶点；F是一个有向边（弧）组，位于不同类型的顶点之间。W是在设定权重的映射边缘，对每一个库所包含非负整数标记；任何变迁被启用，那么Petri网就是活的。P/T网和Petri网之间有三个不同的要点：（1）增加容量的功能和权重函数；（2）变迁在M状态下能否发生和前后库所位都有关系，而在原型网络仅具有与前者位关系；（3）变迁发生之后，令牌改变量超过1，而原型网络的量只有1。B：P/T网功能分析在P/T网模型地点被视为系统的条件，位置，资源等其他被动状态，但变化是系统执行积极的行为，事件的执行，操作，发送，接收等。P/T网络系统包括并发，冲突，混乱等。在函数的执行密切相关的情况下，P/T网络功能如下分析。（1）：独立的P/T网的变迁。如果网中任何变迁满足前后权值为1时，即当变迁仅具有一个输入和一个输出的库所，变迁是一个本地行为或局部作用。它可以独立地发生。（2）并发的P/T网变迁。如果任意两个变迁t1和t2，有一个标记M使得M[t1M1→M1[t2和M[t2M2→M2[t1两个流程，则两个变迁t1和t2是并发的且它们不相互影响。（3）P/T网的冲突库所。如果网中的库所|p•|≥2，即两个以上的输出转换，所以，那个库所是有冲突的库所。冲突的库所是输出变迁的共享资源。（4）P/T网的冲突变迁。如果任意两个变迁t1和t2，有一个标记M使得M[t1M1→M1[t2和M[t2M2→M2[t1两个流程，则两个变迁t1和t2是在M的冲突，当一个发生时，另一个变迁将失去发生权。反过来也是如此。我们可以通过施加外部控制解决冲突问题，增加了库所Pa和Pb，让Pa和Pb形成一个控制回路。t1和t2的冲突就解决了。（5）P/T网混乱的变迁。如果在网络上有一个变迁发生，它会让其他两个变迁冲突。这就是所谓的P/T网混乱的并发性和冲突互动。Petri网的网络功能，同时必须考虑这些变迁在不同的情况。（1）如果情况是第一种情况，变迁行为是本地的行为；它的动作只有与输入，输出位置有关。（2）如果情况是第二种情况下，这些转换可以同时执行；它们可以并行执行；（3）如果情况是在第三情况下，处理不能正常工作。添加两个库，使它们形成一个控制回路，T1和T2之间的冲突消失，形成两个并行的转换。在这个时候，它可以被分入所述第二种情况。P/T网系统在整体上可分为上几个功能模块，某些功能模块可被同时执行，并且一些组件可以是顺序执行的，相同的功能模块可以同时并行执行或顺序执行。现在的问题是如何划分的P/T网的功能模块，接下来我们给出的P/T并行和其功能的策略的基本思想。三并行Petri网系统的基本概念Petri网运行仿真、动画演示，最直接的方法是使用并发和同步的特点去并行Petri网。但并行Petri网的基本思路包括：一是提取的P/T网模型和正规化；二是要解决的P/T网模型的转换子集或子集的库所，根据库所分区策略或变迁分区策略；三是分裂的P/T网的一些子网的模型；四是子网和子网之间的并行度的分析；五是制定和实施并行算法的Petri网。从P/T网结构模型的提取是不同的Petri网模型到P/T模型。由于在不同的领域和不同的实际问题的解决方案的应用，人们使用不同的Petri网模型来描述系统的结构和行为。有许多种Petri网模型，包括有色Petri网，时间Petri网，混杂Petri网，模糊Petri网和其他高级Petri网系统。虽然各种类型的模型在实际系统运算能力的模拟，而且可以相互转换，但必须考虑哪一种Petri网模型是最方便，最理想的有关系统或部门并行的一个问题功能。文献[6]进行了研究这个问题，他说，在P/T网模型的并行和功能划分的理想模式。从文献[6]我们可以看到Petri网的方法转化为P/T网，本文介绍了Petri网的并行功能分区策略。以下是库所不变量和T图两种不同功能的分区策略。四基于P库所的功能分区策略P/T网的P-不变式功能划分策略主要包括：求出的P-不变量和不变集；设置子网条件；确定P/T的网络（子网）的并行处理。A：求出P库所据P不变量的定义解决齐次线性方程，我们得到的不变解。定义3设N=(P，T；F)是一个网，|P|=m，|T|=n，D是网N的关联矩阵。如果存在非平凡的m维非负整数向量X满足DX=0，则称X为网N的一个P-不变量。定义4设X是网N=(P，T；F)的一个P-不变量，则称‖X‖={pi∈P|X(i)0}为P-不变量X的支集。如果Petri网模型比较复杂、包含的库所和变迁数量较大，用手工计算和验证显得困难且容易出错。根据定义3、定义4和解齐次线性方程组的方法求解库所不变量的步骤如下：(1)求出关联矩阵D及秩r。当r=m时，齐次线性方程组DX=0只有零解，Petri网不能进行功能划分，结束；当rm时，转下一步。(2)解齐次线性方程组DX=0，求Petri网的库所不变量。(3)根据定义3，从库所不变量集合中求出库所不变量支集集合。例1：如图1所示的Petri网模型，分别求出它的库所不变量和库所不变量支集的集合。图一：包含2个库所不变量的Petri网根据定义3，Petri网的关联矩阵是：10−100−111000−101−1000−11求出的库所不变量分别为：X1=[1，0，1，0，o]T，X2=[o，0，0，1，1]T。由定义3得库所不变量支集集合Γp={X1，X2}。B：基于进程的分区条件从上述求解库所不变量可以看出，网N的库所不变量x可能有多个。但是，不是每个库所不变量(子网)都能构成具有独立功能的Petri网进程。如何进行子网的分割？下面定理三将会给出条件。定理3设Γp是P／T网（P，T；F，K，W，M）的库所不变量支集集合，Γp中的元素所对应的子网都满足以下条件:证明1假如网N的P-不变量支集只有1个元素，且满足(1)~(4)的条件，则该元素对应的子网可以创建一个进程；2假设网N的P-不变量支集集合Γp有n(有限)个元素，已知有n-1元素对应的子网是网N的进程，这n-1个元素满足式(1)~(3)的条件；第n个元素也满足式(1)~(3)的条件，由条件(4)可知，n-1个元素与第n个元素构成的网N的P-不变量支集集合Γp，满足式(4)的条件。证毕。C：确定P/T网的并行过程（子网）P-不变量支集集合Γp的元素具有子网中至少有一个库所的初始标识为正数；每一个库所的输入弧W(t’,p)与输出弧W(p,t)的值都是1；两个子网之间没有共享库所；每种可能的分割，其进程的变迁刚好与N网的变迁集T相同；例2图2给出P/T网，请划分子网并作并行处理。图二：Petri网∑含有三个P-不变量易求，X1=[1,1,0,0,0,0,0]T，X2=[0,0,1,1,0,0,0]T，X3=[0,0,0,0,0,1,1]T根据定理3验证，‖X1‖={p1,p2},‖X2‖={p3,p4},‖X3‖={p6,p7}.都是网的P-不变量支集。五基于T图的功能分区策略基于变迁的Petri网并行划分的思想是：将网中任意两个同属于某个库所的前集或后集且不同的变迁划分到不同的等价类中。A：T-图的定义和基本原则其形式化定义如下：定义5定义6定义7定义8由以上4个定义就可以得到基于T-图的子网划分的基本原理。首先，由定义8求取各变迁的标记Φ（ti）t∈T；其次，分析得到标记Φ（ti），把Φ（ti）=1的标记放入新集合A中，并标记Φ（ti）、Φ（tj）∈T-A，直到所有标记Φ（ti）=0为止；最后通过定义6和定义7构建划分子网。B：T-图划分网条件下面给出Petri网模型基于T-图的子网划的条件定理。定理4设Σ=（P，T；F，M0）为Petri网，若该网可划分，当且仅当存在t∈T且Φ（t）=1。定理5设Σi=（P，T；F，M0）为Petri网Σ的一个划分子网，则Σi是个T-图。C：确定T-图的过程遍历Petri网的变迁集，根据定义5和6的定义来确定每个变迁phi（T）的值是1，根据T-图划分的分支网的基本原理一步步划分子网。下面是Petri网的并行划分子网的例子。例3：如图1所示的Petri网模型，给出基于T-图的划分子网。由定理1可知，开始时，