[34] J. Rumbaugh. The Preacher at Arrakeen. In Gogolla and Kobryn [16].
[35] J. Rumbaugh, I. Jacobson, and G. Booch. The Unified Modeling Language Reference Manual. Addison Wesley, 1999.
[36] J. Saldhana and S.M. Shatz. UML Diagrams to Object Petri Net Models:
An Approach for Modeling and Analysis. In International Conference on Software Engineering and Knowledge Engineering, Chicago, Illinois, 2000.
[37] A.J.H. Simons and I. Graham. 30 Things That Go Wrong in Object Mod-elling with UML 1.3. In H. Kilov, B. Rumpe, and I. Simmonds, editors, Be-havioral Specifications of Businesses and Systems. Kluwer Academic Pub-lishers, 1999.
[38] J. Staunstrup. IAR visualSTATE Concept Guide, version 4. IAR Systems, 1999. www.iar.com.
[39] G. Wirtz. Application of Petri Nets in Modelling Distributed Software Sys-tems. In D. Moldt, editor, Workshop on Modelling of Objects, Components, and Agents, Aarhus, Denmark, 2001.
[40] J. Xu and J. Kuusela. Analyzing the Execution Architecture of Mobile Phone Software with Coloured Petri Nets. International Journal on Soft-ware Tools for Technology Transfer, 2(2), 1998.
[41] Aarhus Amt Electronic Patient Record. www.epj.aaa.dk.
[42] Centre for Pervasive Computing. www.pervasive.dk.
[43] Coloured Petri Nets at the University of Aarhus. www.daimi.au.dk/CPnets.
[44] Design/CPN. www.daimi.au.dk/designCPN.
[45] I-Logix. www.ilogix.com.
[46] Object Management Group. www.omg.org.
[47] Pervasive Healthcare. www.healthcare.pervasive.dk.
[48] Rational Software Corporation. www.rational.com.
[49] Systematic Software Engineering A/S. www.systematic.dk.
[50] Unified Modeling Language. www.uml.org.
State Spaces Using Colored Petri Nets
W.M. Zuberek
Department of Computer Science
Memorial University
St.John's, CanadaA1B 3X5
Abstract
The performance of many distributed applications depends upon the ratio of
computation to communicationtimes. In the case of distributedgeneration of
state spaces for timed Petri nets, this ratio is determined by the partitioning
functionwhich assignsgeneratedstates to classesassociated withprocessors; if
thepartitionclassescorrespondtoclustersofstateswithonlyafewconnections
between clusters, the required communication is minimized, and the
perfor-mance is maximized. The eects of state clustering areanalyzed bysimulating
a coloredtimedPetrinetmodelingthedistributedstate spacegeneration.
1. Introduction
Actualimplementationof complex, real-worldsystems is usuallypreceded bythorough
studies, performed on a formal model of the original system. For systems which exhibit
concurrentactivities,Petrinets areapopularchoiceof themodelingformalism, because of
theirabilitytoexpressconcurrency,synchronization,precedence constraintsand
nondeter-minism. Moreover, Petri nets \with time" (stochastic or timed) include the durations of
modeled activitiesand thisallows tostudytheperformanceaspectsof themodeledsystem
[1 , 14 ,21 ].
Thebasicanalysisofnetmodels,basedonexhaustivegenerationofallreachablestates,
is known asreachabilityanalysis. In reachabilityanalysis,the statesof themodeland the
transitions between states are organized in the so called reachability graph which is used
forverifying the requiredqualitative properties (such asabsenceof deadlocks orliveness).
FortimedandstochasticPetrinets(withdeterministicorexponentiallydistributedtimes),
this graph is a Markov chain, so its stationary probabilities of states can be determined
using known numerical methods [19 ]. These stationary probabilities are used to derive
performancemeasuresof themodel[1 , 6 ,21 ].
Forlargenetmodels,thestatespacecaneasilyexceedtheresourcesofasinglecomputer
system. Theavailabilityof clustersof (inexpensive)workstationsand portable librariesfor
distributed computing make distributed generation of the state space quite an attractive
alternative to thetraditionalsequentialapproach.
In distributed generation of the reachability graph, the (yet unknown) state space is
partitioned into n disjoint regions, R
1
;R
2
;:::;R
k
, and these regions are constructed
inde-pendentlybyk identicalprocessesrunningconcurrentlyon dierentmachines. Attheend,
theregions can be integrated inone state graphifneeded.
makessuchsystemssignicantlydierentfromclustersofworkstationsorPCs. Distributed
state space generation described in [12 ] is organized into a sequence of phases, and each
phasecontainsprocessing ofcurrentlyavailablestatesfollowed bycommunicationinwhich
non-local states are sent to their regions (i.e., processors). The next phase begins only
aftercompletionofalloperationsofthepreviousphase. Reasonablevaluesofspeedupwere
reported forsmallnumbersof processors (2 to 4) andforlarge state spaces.
The purposeofthispaperistopresent asimplecoloredPetrinetmodelofageneration
of the reachability graphs for timed Petri nets usinga cluster of processors connected by
a switch, and to illustrate the eects of state space partitioning on the performance of
distributed generation. In particular, it has been observed that for some types of timed
Petrinets,thestraightforwardpartitioningalgorithm[16 ,17 ]resultsinpoorspeedups,soa
more sophisticated partitioningalgorithm,taking into account structuralpropertiesof the
model,may be requiredto improvethe performanceof distributedstate space generation.
Section 2 provides a brief overview of basic concepts of timed Petri nets which are
relevant to thispaper. Section 3 outlinesthe distributedgeneration of the state space for
timedPetrinets. AsimplecoloredtimedPetrinetmodelofaclusterofprocessorsconnected
byaswitchispresentedinSection4,whileSection5discussestheresultsobtainedfromthe
presentedmodel. Asimpliedapproachto performanceevaluationisoutlined inSection6.
Section7 containsseveral concludingremarks.
2. Timed Petri Nets
A timed Petri net is a triple T = (M;c;f) where M is a marked (place/transition)
net, M = (P;T;A;m
0
), with P denoting the set of places, T { the set of transitions, A
{ the set of directed arcs, A P T [T P, and m
0
{ the initial marking function,
m
0
:P !f0;1;2;:::g. Mcan be extended in a numberof ways if needed;for example, it
canincludeasetofinhibitorarcsB PT,M=(P;T;A;B;m
0
),A\B =;,ormultiple
arcs described by a weight function w : A ! f1;2;:::g, M = (P;T;A;w;m
0
), and so
on. c is a conict-resolutionfunctionwhich assignsprobabilitiesto conicting transitions,
c : T ! [0;1], in such a way that for each free-choice class of transitions the sum of
assignedprobabilitiesisequalto1. Formore generalconicts,theprobabilitiesassignedto
transitions represent relative frequencies of transition rings,which are used to determine
theprobabilitiesofstatetransitions[10]. f istheringtimefunctionwhichassignsthering
times to transitions, f :T !R +
,where R +
denotesthe setof nonnegative real numbers;
ifringtimes areconstant, thenets arecalled D{timed; ifthey arerandomvariableswith
(negative)exponentialdistributions(describedbytheiraverage values), thenetsarecalled
M{timed(or Markovian); other distributionscan also be used.
In timed nets, it is assumed that each transition which can re, initiates its ring
in the same instant of time in which it becomes enabled, and the rings of transitions
occur in \real time", i.e., the tokens are removed from the input places at the beginning
of the ring interval, and they are deposited into the output places at the end of this
interval. Consequently, the behavioral description of a timed net must take into account
the places (i.e., the remaining tokens) as well as the ring transitions of a net [21 ]. For
D{timednets, astate ofa net, s, is a triple,s=(m;n;r), wherem is a markingfunction,
m :P ! f0;1;2;:::g, n is a ringfunction, n:T ! f0;1;2;:::g, which indicates, for each
transition, thenumberof its rings occurringin thisstate, and r is a (partial)
remaining-lastcomponent ofstate descriptions isnotused atall).
For example, let the ring times associated with the transitions of the D{timed net
shown inFig.2.1bef(t
FortheinitialmarkingshowninFig.2.1,thenethastwoinitialstates,onecorresponding
tot
1
'sringandthesecondcorrespondingtot
2
'sring;thesetwoinitialstatesareasfollows
(the m, n and r components of states are separated by semicolons; undened values of r
areindicatedby`{'):
s
The holding times (or durations) of s
1 and s
2
are equal to 1.0 and 0.9 (time units)
respectively; at the endof the ringtime, a token isdepositedin p
1 , sot
3
can initiate its
ring,whichis represented bys
3 :
s
3
=(0;0;0;1;0;0;0;0 ;1 ;0 ;0 ; ; ;0 :1; ; ):
The holding time of s
3
is 0.1, at the end of which tokes are deposited in p
2
,sothere aretwopossiblenextstates, s
4
Both these states have holding times equal to 0.1, at the endof which the ring of t
4
ends(whilet
1 ort
2
continuesits ring,withtheremainingringtimeequalto 0.9and 0.8,
respectively), and t
5
initiatesits ring,creating states s
6
The holdingtimesofs
6
continuesto re(with
theremaining ringtime equalto 0.1) creatingstate s
8
corresponds to theterminationof itsbothrings,tokens aredeposited
s2(0.9) s1(1.0)
s3(0.1)
s6(0.8) s4(0.1)
s8(0.1) s7(0.8) s5(0.1)
Fig.2.2. Stategraphforthenetshownin Fig.2.1.
It shouldbe noticed that fordierent valuesof ringtimes, thereachability graphfor
thenetshowninFig.2.1maybesignicantlydierent fromthe one showninFig.2.2.
TimedcoloredPetrinetsareextensionsofplace/transitionstimednets;atimedcolored
Petrinetis also atripleT =(M;c;f) where Mis a colored net, M=(P;T;C ;A;e;m
0 ),
with P, T and A as before, C denoting a set of attributes called \colors", e assigning
expressions(overcolorsandcolorvariables)toarcsofthesetA,theinitialmarkingfunction
extended to m
0
:P C ! f0;1;2;:::g, and the choice and ringtime functions extended
to: c : T B ! [0;1] and f : T B ! R +
, where B denotes the set of bindings, i.e.,
assignmentsofcolors from thesetC to variablesused inarcexpressions.
An outline of a\standard" approachto the(sequential) generationof state space (just
thestates, withoutarcs)can be asfollows:
1. Statespacegeneration:
2. var States:=;; (*set ofstates*)
3. unexplored:=;; (*queueofstates*)
4. begin
5. for eachsin IntitalStates(m
0 )do
6. States:=States[fsg;
7. insert(unexplored;s)
8. endfor;
9. whilenonempty(unexplored)do
10. state:=remove(unexplored);
11. for eachsinNextStates(state)do
12. ifs2=Statesthen
13. States:=States[fsg;
14. insert(unexplored;s)
15. endif
16. endfor
17. endwhile
18. end.
where function IntialStates(m) determines the set of initial states corresponding to the
markingfunctionm,andfunctionNextStates(s)determinesthesetofsuccessorstatesof s.
3. Distributed State Space Generation
Indistributedgenerationofthestate space,thepartitioningfunctionassignseachstate
to the region to which it belongs. The number of disjoint regions is usually equal to the
numberofavailableprocessors,k
p .
region(s)=[ X
i=0
i m(p
i )+
X
i=0
i n(t
i
)]mod (k
p )
where jPj is the cardinality of the set of places P, jTj is the cardinality of the set of
transitionsT,thecoeÆcients
i and
i
areintegernumbers,andm andnaremarkingand
ringcomponentsof astate s[21 ].
Three kinds of (logical) processes are used in distributedgenerationof thestate space
[16 ],asshowninFig.3.1: aprocessstartingthe distributedsystem andinitiatingthe
com-putations, called Spawner; several processes constructing the regions of the state space,
calledGenerators, and a process collectingand integratingthe results,called Collector.
Collector Spawner
Generator 1
Generator 4
Generator 2 Generator 3
Fig.3.1. Distributedstatespacegenerationsystem.
The execution begins with the Spawner which creates the Collector and spawns k
p
Generators onthehostsofthecluster;italsocollectstheidentiersof allcreatedprocesses
and broadcaststhem to all processes soeach process can send messages to any other one
[16 ]. In itsnal phase,theSpawnersendstheinitialstates to theappropriate Generators.
An outline ofthe Spawner process isasfollows [16 ]:
1. Spawner:
2. var m
0
; (*initialmarking*)
3. k; (*thenumberofhosts *)
4. proc table[]; (*processoridentiers*)
5. begin
6. inputvirtualmachineandmodeldescriptions;
7. spawnCollectoronthishost;
8. fori:=1to kdo
9. proc table[i]:=spawnGeneratoronhost[i]
10. endfor;
11. broadcast(proctable);
12. for eachsinInitialStates(m
0 )do
13. send(proctable[region(s)];s)
14. endfor
15. end.
For each state belonging to region R
i
, the Generator
i
determines all successor states.
A successorstate can be in the same region(in which case it is called a local state) orin
a dierent region (in which case it is called an external state). Each Generator
i
sends all
for receiving messages from other processes and for the termination detection. When the
Spawner creates the Generators, it actually creates Analyzer processes. As its rst step,
each Analyzercreatesits Receiverand Senderprocesses [16 ].
The Analyzer, Receiver, and Sender processes of each Generator reside on the same
processor. Their communicationisbased onsharedvariables, asshown nFig.3.2.