基于P-不变量的Petri网并行化方法的研究
37582009,30(16)计算机工程与设计ComputerEngineeringandDesign 网络与通信技术?
基于P一不变量的Petri网并行化方法的研究
李文敬，王汝凉，廖伟志
(广西师范学院信息技术系，广西南宁530001)
摘要：为使Petri网系统能够并行执行或模拟运行，提出了基于P-不变量的Petri网并行化方法根据Petri网系统具有同步
与并发的特点，给出基于P.不变量的Petri网模型分割，进程创建条件与并行化分析.在此基础上，提出并行进程创建条件拓
展定理并给予证明和实例验证.给出实现并行化所需要解决的Petri 网模型行为规范的形式化,P.不变量求解与基于P-不变
量的Petri网并行化方法.实验结果表明，基于P一不变量的Petri网系统的并行化方法是可行和有效的.
关键词:P.不变量;Petri网；分割；并行进程；并行化方法
中图法分类号:TP301.6文献标识码:A文章编号:1000.7024(2009)16.3758-04 RearchonPetrinetsparallelizationmethodbadonP—invariants LIWen-jing,WANGRu-liang,LIAOWei?zhi (DepartmentofInformationTechnology,GuangxiTeachersEducationUniv
ersity,Nanning530001,China)
Abstract:ToachievetheparallelprocessorsimulationruninPetrinetssystem, aparallelizationmethodofPetrinetsiSputforward. BadonthecharacteristicsofsynchronizationandconcurrenceofPetrinetss ystem,partitionandconditionsofcreatingparallelprocess iIlPetrinetmodelsbadontheP.invariantsaregivenanditsparallelizationiSa nalyzed.Badonthe,theexpansiontheoremfor parallelprocessandthecreationoftheconditionsiSputforwardandprovedwit hexamplesofverification.Theformalcodeofconduct ofPetrinetmodelsintherealizationofparallelization.P—invariantsolutiona ndparallelizationmethodbadontheP—invariantsarepro-
vided.TheexperimentalresultsshowthattheparallelizationmethodofPetrin etsystembadontheP-invari
antsiSfeasibleandeffective.
Keywords:P.invariants;Petrinets:partition;parallelprocess;parallelization me也Od
0引言
Petri网是一种系统的数学，图形建模和分析工具.它特
别适用于具有同步，并发，冲突的离散事件系统的建模，并被
广泛应用于分布式并行处理，离散事件，柔性制造等复杂系统
的设计和分析.目前，所建立的原型Petri网，着色Pctri网，时
always be my baby间Petri网等各种系统模型，都着重于对其结构，行为，功能的
静态分析与研究；而系统的行为和功能等动态的性能需要通
过系统的模拟，动画演示或运行来体现.Petri网是复杂系统
运行过程中并发，互斥，同步最直接，自然和精确的表示.所
以，对Pe网系统并行化方法进行研究，为实际的Petri网系
统的并行实现和运行提供有效的并行化方法，具有非常重要的意义.1986年，希尔瓦和威利拉，豪斯尔德特分别提出了Petri网的集中化和分散化并行方法.但当Petri网模型变得非常庞大，复杂时，集中化和分散化的并行化方法，实现的性能
都会很差”.文献[1]提出了库所不变量的并行分割技术，但
该技术只适用于正库所的情况.在此基础上，我们对库所是
manage是什么意思
空的情况进行拓展，提出Petri网系统中非负库所的并行化条件，实现并行化所需要解决的Petri网模型行为规范的形式化, P.不变量求解过程和基于P一不变量的Petri网并行化方法.实验结果表明，基于P.不变量的Petri网并行化方法是可行和
有效的.
1Petri网基本概念与术语
Petri网是用于描述分布式系统的一种模型，它既能描述
系统的结构，又能模拟系统的运行.以下引入Petri网与本
英语幼儿故事
文相关的概念和术语.
定义1满足下列条件的三元组Ⅳ=(尸，称作一个网
ill的反义词(net):
(1)PxT:~
(2)PM=
元旦用英语怎么说(3)F_C(ex乃U(P)
小林浩平(4)dom㈣Ucod㈣=户u
其中:dom(=EPU1]3yEPUT:(x,y)eF);cod(=
{∈PulqyEPUT:，曲∈.
P和腥两个不相交的集合，称为网Ⅳ的基本元素,P的元
口才班
收稿日期:2009—02—25；修订日期:2009.04—07.
纹绣培训
基金项目：国家自然科学基金项目(60864001)；广西自然科学基金项目(0731028).
作者简介：李文敬(1964一)，男(壮族)，广西南宁人，副教授，研究方向为并行计算,Petri网；王汝凉(1963一)，男，广西北海人，博士，教
授，研究方向为神经网络；廖伟志(1974--)，男(壮族)，广西风山人，博士，副教授，研究方向为Petri网.E—mail:*************.6n
李文敬，王汝凉，廖伟志：基于P一不变量的Petri网并行化方法的研究2009,30(16)3759
素称为库所(place),T中的元素称为变迁.F是网中的流关系.
一
个网可以用一个二分图来表示：用一个小圆圈表示P中的元
素，用一个小矩形或短划线表示中的元素，用有向弧表示流
关系.若,EF，则从x~:lJy画一条有向弧.
氨基酸缩写定义2设Ⅳ=(P,T；为一个网.对于xEPUT，记
云的英文
=
l3yEPUTA,x)EF}
x’=l3yEPUTA,EF}
称为的前集或输人集,X’为X的后集或输出集;Ux’为
元素的外延.
定义3设Ⅳ=(尸,；是一个网，映射P一Ⅳ(自然数集)
称为网Ⅳ的一个标识,E=(Ⅳ，称为标识网.若P=,p:,…,
p)，通常将标识慷示为一个列向量M={坳)，脚z),…,
m(p)}.用图形表示标识网时，枷∈P，若脚)=|j}，则在库所p
中加人k个小黑点矩阵,D和D一分别称为输出
矩阵和输入矩阵.
2Petri网并行化分析
Petri静态网模型是不能执行的，要对网模型进行模拟和
运行，需要生成并行代码或串行代码.基于Petri网系统具有
自然的并行性，以下主要对P/T网系统的并行化进行分析
和研究.
2.1网分割与并行进程的创建
Petri网的并行性分析首先要提取网结构模型，将网分割
成若干子网，然后将所有子网组成一组进程，这些进程分别
被创建为并行进程.
提取结构模型m.若网N是P/T网时，则不用转换；若Ⅳ不
是P/T网模型，则将其转换成结构上与Ⅳ等价的P/T网模型. 在转换过程中:①lⅣ中的每个库所都转换成P/T网的库所，库所中的初始标志不变;②Ⅳ中的每个变迁都转换成P/T网的变
