Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach.
AbstractStochastic timed Petri nets are a useful tool in performance analysis of concurrent systems such as parallel computers, communication networks, and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for practical problems due to their sizes. In this paper, we provide a method to compute efficiently upper and lower bounds for the throughputs and mean token numbers for a large class of stochastic timed Petri nets. Our approach is based on uniformization technique and linear programming.
Introduction
Stochastic Timed Petri Nets (STPN) are Petri nets where transitions have -ring delays.
Since the last decade, they have been receiving increasing interest in the modeling and
performance analysis of discrete event systems. Such a tool is particularly useful for modeling
systems which exhibit concurrent, asynchronous or nondeterministic behaviors, such
as parallel and distributed systems, communication networks and AEexible manufacturing
systems. The reader is referred to the extensive survey of [36] on theoretical analyses
and applications of Petri nets. Applications to the performance evaluation of parallel and
distributed machines (hardware components) and parallel and distributed computations
(software components) can also be found in [3] and the special issue of J. of Parallel and
Distributed Computing (Vol. 15, No. 3, July 1992).
Most literature of STPN is on Stochastic Petri Nets (SPN) [29, 35], where transition
-ring times are mutually independent exponentially distributed random variables, and
their extensions: Generalized Stochastic Petri Nets (GSPN) [2] where immediate transitions
(i.e. those without -ring delay) are allowed, and Extended Stochastic Petri Nets
(ESPN) [28] where transitions are allowed to generate random numbers of tokens upon
-rings. Numerical analysis of such nets is based on the analysis of the embedded Markov
chains. Decomposition techniques are proposed, see e.g. [19, 34] and references therein.
Analytical solutions exist in product-form for equilibrium distributions for special cases of
SPN, see [15] and references their in.
There also exist analyses of stochastic timed Petri nets without Markovian assump-
tions. Most of them provide performance bounds, see [10, 11, 17, 18, 25]. Others analyze
stability conditions [4, 9]. The reader is referred to [5] for a survey on recent results on
quantitative analysis of STPN, including approximations and simulations.
Although there exist various quantitative analysis techniques and some software tools
(e.g. GreatSPN [23] and SPNP [27]) for STPN, the applications of STPN are most often
limited to small size problems. This is mostly due to the time and space complexity of
numerical analysis algorithms and of simulations.
In this paper, we provide a new method to compute eOEciently upper and lower bounds
for linear functions of the throughputs and mean token numbers in general Markovian
Petri nets. Our approach is based on uniformization technique and linear programming.
The STPN models under consideration are closely related to GSPN models de-ned in [24],
with in addition the possibility of randomly generating tokens upon transition -rings.
Uniformization technique is one of the most useful techniques for analyzing continuous
time Markov chains [31]. In [32], such a technique was used to establish linear equality
constraints among the expectation of state variables in queueing networks. This allowed
RR n\Sigma2642
4 Z. Liu
the authors to bound the performance measures, both above and below, by solving a linear
program. Similar approaches were taken to determine lower bounds on achievable performance
of control policies in multiclass queueing networks [13], optimal control policies for
Klimov's problem [14], and stability regions of queueing networks and scheduling policies
[33]. In these studies, linear or nonlinear programming were used to obtain bounds.
The method of linear programming has already been used in operational analysis for
deriving bounds in non-Markovian STPN [17, 18, 25]. Since no statistical assumptions are
made on the distributions of -ring times, such bounds are usually loose. Several techniques
were proposed for the improvement of such bounds in special cases of Petri nets [20, 21].
In our work, we consider Markovian STPN. We show that, like in [32, 13], the Markovian
assumption allows us to establish a set of linear equality constraints among the
expectation of state variables in the Petri nets, such as token numbers in the places and
indicator functions of whether transitions are enabled. More precisely, we analyze the
evolution of state variables in steady state and write out evolution equations using the
uniformization technique. Taking the quadratic forms of these equations allows us to establish
the linear constraints. Exploiting further structural and probabilistic properties of
the Petri nets, we obtain an augmenting set of linear equalities and inequalities, some of
which are similar to those in [25]. Upper and lower bounds of performance measures are
then obtained by solving the linear program.
The paper is organized as follows. In Section 2, we de-ne the STPN models under
consideration as well as the notation. In Section 3, we derive the linear equalities based on
the uniformization technique. In Section 4, we establish other linear constraints based on
the behavioral properties and probabilistic laws. In Section 5, we provide the summary of
the linear programming formulation. In Section 6, we present applications of our technique.
Finally, in Section 7, we conclude with remarks on the extensions of our results.
Notation
A Petri Net can be viewed as a directed graph
E), where the set of vertices is
the union of the set of places P and the set of transitions T . The set of arcs E is composed
of two subsets E 0 and E 00 . The arcs of E 0 are either of the form (p; t) or of the form (t; p)
with We shall denote by
the set of transitions that precede place p in P: ffl
the set of transitions that follow place p in P:
the set of places that precede transition t in T
INRIA
Performance Analysis of Stochastic Timed Petri Nets 5
the set of places that follow transition t in g.
The arcs of E 00 are inhibitor arcs connecting places to transitions. For any t 2 T , let ffi t be
the set of places from which there is an inhibitor arc, and for any p 2 P, let p ffi be the set
of transitions to which there is an inhibitor arc. Denote by j p;t the weight of the inhibitor
arc from place p to transition t, t.
The net N is strongly connected if there is a path from any place/transition to any
place/transition.
For all p 2 P, de-ne the following set of transitions:
Tokens circulate in the Petri Net. This circulation takes place when transitions are
-red. When transition t 2 T is -red, - p;t tokens are consumed at each place p 2 ffl t, and
oe t;p tokens are created at each place p 2 t ffl . Variables - p;t and oe t;p are considered as the
weights of the arcs of E 0 .
An example of the Petri net is illustrated in Figure 1. It contains 7 places
g. Transitions t are immediate
transitions. Places p 1 and p 6 have initial marking 1, whereas the others have initial
marking 0. There are two inhibitor arcs (p represented by arcs ended
with a circle.
When the weights of the arcs are upper bounded by 1, N is called an ordinary net, as
opposed to weighted net.
In this paper, we will consider a more general case where the numbers of tokens created
by -ring completions are random variables. When transition t 2 T is -red for the n-th
time, oe t;p (n) tokens are created at each place p 2 t ffl . For all
is assumed to be a sequence of independent and identically distributed (i.i.d.) random
variables. The sequences of random variables foe t 1 ;p (n);
are, however, in general dependent for t 1 6= t 2 . Let oe t;p be the expectation of
oe t;p (n).
For all
(n) and oe t;p 2
(n) can be dependent if p 1 . For example, when
creates one token in one of its output places after each
RR n\Sigma2642
6 Z. Liu

Figure

1: An example of Petri net.
-ring. Two cases will be considered: independent token generation and selective token
generation. In the case of independent token generation, we assume that for any t 2 T ,
the sequences of random variables foe t;p (n)g n , are assumed to be (statistically)
independent. In the case of selective token generation, however, the sequences of random
variables foe t;p (n)g n , are dependent in such a way that for all n, at most one of
the output places has tokens created:
so that oe t;p 1
for any p 1 special case of selective token generation is the routing mechanism
where a token is generated at one and only one of the output places after each -ring:
below discussions on immediate transitions).
There are two special classes of ordinary Petri nets, referred to as state machines and
marked graphs. A state machine is an ordinary Petri net without inhibitor arcs such that
for each transition t, ffl t is a singleton and
marked graph
is an ordinary Petri net without inhibitor arcs such that for each place p, both ffl p and p ffl
are singleton.
Firings of transitions are timed, i.e., each -ring takes a certain amount of time before
completion. The token consumptions in places of ffl t and token creations in places of t ffl
occur simultaneously at the end of a -ring of transition t. Throughout the paper we will
assume that all the -ring times are independent random variables. The -ring times of
transition are i.i.d. random variables of exponential distribution with parameter - t .
In GSPN framework, Petri nets can have immediate transitions, i.e. transitions whose
-ring times are zero. In this case, immediate transitions have higher -ring priorities, see
[24]. Using algorithms of [26], these immediate transitions can be eliminated without
changing performance behavior of the net.
INRIA
Performance Analysis of Stochastic Timed Petri Nets 7
Of particular interests are immediate transitions which play roles of synchronization
and/or routing. More precisely, in this case, we assume that for any immediate transition
t, t is the only output transition of all its input places, i.e. t. Further,
we assume that for any immediate transition t, t, and
ffl either oe t;p 0
ffl or oe t;p
with a harmless abuse of notation, the index ffl p denotes the
unique transition preceding place p.
In the Appendix, we present a direct transformation technique which removes this kind of
immediate transitions without changing the -ring behavior of the other transitions.
Thus, we will assume throughout this paper that the Petri net N has no immediate
transition, so that all parameters - t are -nite.
A transition t is enabled to -re when there are at least - p;t tokens at each place p 2 ffl t
and there are at most j tokens at each place t. We adopt the single-server
semantics for the transitions. A -ring can start only if the transition is enabled and the
previous -ring has completed. It is assumed that -rings are started as soon as possible.
The case of in-nite-server semantics will be discussed in Section 7.
A -ring of transition t is preempted when the transition is disabled (i.e. at least one
place strictly less than - p;t tokens, or at least one place has more than
or equal to j p;t tokens) before the -ring time expires. The -ring is resumed as soon as
the transition becomes enabled. The disabling of a transition is due both to competitions
with other transitions having common input places (some tokens in these places can be
consumed by other transitions during the -ring of the transition), and to token arrivals in
input places of inhibitor arcs. The -ring mechanism described here is called (cf. [1]) race
policy with age memory. Note that for the case of exponential distributions of -ring times,
the race policies with or without age memory have stochastically the same performance
behavior due to the memorylessness property of exponential distributions. However, in
Section 7, when we consider the case where -ring times have general distributions, the
race policy under consideration will be that with age memory.
The state of the system is characterized by the marking
is the number of tokens in place p at time - . The process X(-) is assumed to be
left-continuous so that X p (-) is the number of tokens in place just before time - . The
initial marking is the marking at time 0.
RR n\Sigma2642
8 Z. Liu
The Markovian Petri net described above will be denoted by
Throughout this paper we will assume that the Petri net is live. Moreover, we assume
that the net is stable in the sense that X(-) converges to a stationary variable X (of
dimension jPj) when - goes to in-nity. Moreover, we assume that the -rst and second
moments of X are -nite, i.e. E[X p
assumptions it is easy to see (using H#lder's inequality) that for all
1.
Let e t (-) be the indicator function of whether transition t is enabled at time - (or
more precisely, just before time -
Let e t be the stationary version of e t (-), and q
Denote by x the mean number of tokens in place p 2 P, and y
. The corresponding vectors are denoted by
the (asymptotic) throughput of transition t 2 T , i.e. the
number of completed -rings of transition t per unit of time, and
In the sequel, we provide a method of computing upper and lower bounds of L(x;
for any arbitrarily -xed linear function L. Our approach is based on linear programming.
The upper (resp. lower) bound is obtained by maximizing (resp. minimizing) the objective
function L under linear constraints.
3 Uniformization and Linear Equalities
We will use the uniformization technique to derive linear equalities between variables x,
y, q and '. We will consider the Petri net N where each transition t 2 T is continuously
-ring with i.i.d. exponentially distributed -ring times of parameter - t . When a -ring is
completed at transition t 2 T , there are two possibilities. If t is enabled, then tokens are
consumed in places ffl t and are created in places t ffl . Otherwise, if t is disabled when the
-ring is completed, nothing happens, and this -ring completion corresponds to a -ctive
-ring completion.
INRIA
Performance Analysis of Stochastic Timed Petri Nets 9
Let f- n g be the sequence of time epochs of, real or -ctive, -ring completions in N . It is
clear that f- n g is distributed according to a Poisson process with parameter
Let F -n denote the oe-eld generated by the events up to time - n .
Let A t (n) be the indicator function such that A t only if the n-th, real or
-ctive, -ring completion occurs at transition t 2 T . Clearly,
for any t 2 T , fA t (n)g is a sequence of i.i.d. random variables, independent of e t (- n ), such
that P
Since for any -xed t 2 T , the random variables (oe t;p (n); are i.i.d. in n, we can
assume with no loss of generality that the numbers of tokens created in places t ffl at time
- n are oe t;p (n), is enabled at time - n .
We assume without loss of generality that the system is in steady state so that, owing
to process see time average) property (cf. e.g. [6]), (X(- n ); e(- n )) has
the same law as (X; e).
The throughput of transition t 2 T can be computed as follows. In the system,
transitions are -red, either really or -ctively, at the rate of -. At each -ring completion
epoch - n , the -ring occurs at transition t 2 T with probability - t =-. Therefore, (real
or -ctive) -ring completions occur at transition t at the rate of - t . Since these -ring
completions are independent of e t , we have
The following evolution equation is essential. For all
(2)
Taking the conditional expectation yields
RR n\Sigma2642
Z. Liu
Thus,
In the steady state, E[X p (- n+1 so that
by taking expectation in (3), we obtain the following AEow balance equalities:
Calculating the second moments from (2) yields
Thus,
In the steady state, E[X 2
and E[e t (- n Hence, by taking expectation in (5), we obtain the following second
moment condition:X
INRIA
Performance Analysis of Stochastic Timed Petri Nets 11
More generally, for any p 1 we compute the expectation of the product of
numbers of tokens from (2). Assume -rst that token generations of all transitions t 2 T
are statistically independent i.e., random variables oe t;p (n), are independent. Then:
RR n\Sigma2642
Z. Liu
After some simple algebra, we obtain
In the steady state,
Thus, by taking expectation in (7) we obtain the following population covariance condition:
INRIA
Performance Analysis of Stochastic Timed Petri Nets 13
Note that when relations (6) and (8) are identical.
Assume now that token generations of some transitions are selective, i.e. for some t 2
be the subset of transitions which
have selective token generations. Then, for any t 2 T 0 and any p 1
Therefore, by a similar computation we obtain:
Observe that equality (8) can be considered as a special case of (9). Indeed, if T
then both equalities coincide.
4 Other Constraints
In this section, we derive other linear constraints of variables x, y and q. Except for (24),
the linear constraints established in this section requires no Markovian assumption and
holds for general stochastic Petri nets.
4.1 Behavioral Properties
Liveness. Since we assume that the net is live, we have that for any - , at least one
transition is enabled, so that
RR n\Sigma2642
14 Z. Liu
As a consequence,
so that
ConAEicting transitions. For all
where, by convention, - t, and j t. For any pair of transitions
enabled
only if t 1 is enabled, so that e t 1
(-) for all - . Hence,
If transitions are in equal conAEict, i.e. -(t 1 then the
above relation implies that q t 1
Boundedness. For all be the minimum and maximum
numbers, respectively, of tokens in place p. Then, trivially,
As a consequence, for any place p 2 P such that
The bounds (13) can be extended to a set of places S ' P. Let b S - 0 and
be the minimum and maximum of total numbers of tokens in places of S. Then, trivially,
Cycle population conservation. A special case of (15) is when the subset
of places consists of a cycle, i.e., there is a set of transitions
INRIA
Performance Analysis of Stochastic Timed Petri Nets 15
such that ffl
g.
Since the net is live and stable, the sum of tokens in these places is constant:
Denote by C any cycle in N , and C C the population in C. It then follows
Reachable markings. Let be the incidence matrix such that C
E). It is well-known
(see e.g. [36]) that any reachable marking X from the initial marking M can be written
as
where the superscript T denotes the transpose operator, and the (column) vector H corresponds
to the -ring sequence to reach X (or more precisely, the vector of numbers of
-rings of each transition in order to reach X). Let X in (19) be the random variable of
the marking in the stationary regime. Then, by taking expectation in (19) we obtain
where are newly introduced unknown variables.
Rewriting (20) in scalar form yields
oe t;p u
4.2 Constraints Derived from Probability Theory
path comparisons. Since for any t 2 T , e t - 1 almost surely (a.s.), the
enabling rate is bounded by one:
For the same reason, we have X p e t - X p a.s., so that
RR n\Sigma2642
Z. Liu
Another consequence is
A t
so that
According to the relation
so that, by taking the expectation, we obtain
Probabilistic inequalities. According to Chernooe's inequality, we get for all n - 1,
where
V is the iminj operation.
For bounded places
INRIA
Performance Analysis of Stochastic Timed Petri Nets 17
Therefore,
or, equivalently,
Consider any transition t 2 T such that all incoming places are bounded, i.e., for all
1. Using the fact that
we obtain that
where the last inequality comes from relations (27,29). Hence, we obtain an enabling lower
Applying again Chernooe's inequality to (30) yields
where the last inequality comes from relations (27,29). Thus, we obtain an enabling upper
RR n\Sigma2642
Z. Liu
Note that in (32), the iminj operator i
is nonlinear. However, linear inequalities
can be generated by taking either operand of any of the iminj operators.
Consider now an arbitrary bounded place p with bound B p . Then for any t 2 T ,
Thus,
Similarly,
where the last inequality comes from (28). Thus,
Single entry transitions. For all
INRIA
Performance Analysis of Stochastic Timed Petri Nets 19
so that
Little's Law. According to Little's law (see e.g. [40]), for all
is the input rate tokens at place p, and R p is the mean token sojourn time at
place p. Since R p is lower bounded by the minimum -ring times of output transitions of
p, we obtain
or, equivalently,
4.3 Subnet Throughputs
Like in [21], we derive bounds on throughputs of transitions by comparing throughputs
of N with those in the subnets (when they are considered in isolation) of N . We will
consider in particular two special classes of subnets: strongly connected state machines
(SCSM) and strongly connected marked graphs (SCMG).
E) be an arbitrary Petri net, and N subnet of N ,
is a restriction of E on fP 0 S T 0 g \Theta fP 0 S T 0 g. Assume that
the transitions of T 0 (resp. arcs of E 0 , places of P 0 ) have the same sequences of -ring times
(resp. weights, initial markings) in both nets. Assume further that none of the places of
connected with transitions of in the original net N by non-inhibitor arcs, i.e.
in N , there is no (t; p) 2
t denote the throughput of transition t 2 T 0 when the subnet N 0 is considered in
isolation. The following theorems show that under some conditions, the throughputs of
these transitions of the N 0 are upper bounds of the throughputs of the same transitions
in the original net.
Theorem 1 If N 0 is a strongly connected marked graph, then for any transition t in N 0 ,
t .
Proof. Due to the fact that in the original net N , none of the places of P 0 is connected
with transitions of non-inhibitor arcs, the subnet is connected with the rest of
RR n\Sigma2642
Z. Liu
the system only through transitions of T 0 . As N 0 is a strongly connected marked graph,
no transitions in N 0 are in conAEict. Moreover, in N , the -ring mechanism is race policy
with age memory. Thus, for any transition t 2 T 0 , the only eoeect that tokens in places
of have is delaying the -rings of t of T 0 . Thus, by the monotonicity property of
marked graphs [11], we conclude that ' t - ' 0
t for all t 2 T 0 .
Theorem 2 Assume that N 0 is a strongly connected state machine such that for any two
transitions t 1 and t 2 of N 0 , t 1 and t 2 are in conAEict in N 0 implies that t 1 and t 2 are in
equal conAEict in N , i.e. ffl t . Then for any transition t in N 0 , ' t - ' 0
t .
Proof. The proof is similar to that of Theorem 1. Note -rst that the subnet N 0 is connected
with the rest of the system only through transitions of T 0 or inhibitor arcs. Under the
assumption of the theorem, any two transitions which are in (equal) conAEict in N 0 are in
equal conAEict in N . Moreover, in N , the -ring mechanism is race policy with age memory.
Thus, in N , tokens in the places of [ t2T 0
not change the winners of -ring races
among transitions of T 0 . In other words, the only eoeect that tokens in places of ffl
have is delaying the -rings of transitions of T 0 . Thus, by the monotonicity property of
state machines [8], we conclude that ' t - ' 0
t for all t 2 T 0 .
Note that the above two theorems hold for any arbitrarily -xed sequences of -ring
times. No Markovian assumption is needed.
EOEcient computational algorithms for computing the throughput of state machines
have been proposed in the queueing literature, see e.g. [16, 22, 38, 39].
The computation of throughput of SCMGs has been investigated in [11], where various
computable upper bounds were proposed. Exact value of the throughput can be obtained
by simulation using matrix multiplications in the (max; +) algebra, see [7].
5 Summary of the Linear Programming Formulation
Theorem 3 Let be an arbitrary Markovian timed Petri net, and
an arbitrary linear function de-ned on the nonnegative state variables x;
of the net. Let ff and fi be the solutions of the linear programming problems
INRIA
Performance Analysis of Stochastic Timed Petri Nets 21
such that the linear constraints of Table (1) are satis-ed, where u
Recall that in Table 1, inequalities containing the operator i
inequalities
generated by taking either operand of any of the iminj operators.
6 Applications
In this section we illustrate applications of the above techniques to the performance ana-
lyses. We shall consider two applications, one in manufacturing system, another in parallel
computing. Unless otherwise stated, the numerical results are obtained without linear inequalities
pertaining to boundedness of subsets of places and subnet throughputs.
6.1 Production Line
The -rst example is concerned with a production line with in-nite supply, see Figure 2-
(a). In the example, there are four servers, represented by circles. The -rst server has an
in-nite-capacity buoeer with an in-nite number of production requirements, represented
by small dashed circles. The other three servers have -nite-capacity buoeers: 3, 2 and 4.
For starts a service only when the downstream buoeer 1 has at least
one empty room. This corresponds to the so-called blocking before service.
The corresponding Petri net model is depicted in Figure 2-(b), where transitions re-present
the servers and the initial markings of the places on the bottom represent the
buoeer capacities.
We assume that the service times at server i are i.i.d. exponentially distributed with
parameter 4. The objective function in this problem is the total throughput
. The numerical results are presented and compared with the exact values.
In the experimentation, we have carried out computations for -ve sets of parameters
of - i 's. The lower and upper bounds are given in the columns il.b.j, iu.b.1j and iu.b.2j,
whereas the exact values are provided in the column iexactj. The upper bounds in column
iu.b.1j are obtained by further using subnet throughput constraints. In columns io.l.b.j
and io.u.b.j, we also present the bounds computed by linear programming approch based
on the linear constraints of Section 4 without Markovian assumption (which implies in
particular that the linear equalities of Section 3 are not used).
RR n\Sigma2642
22 Z. Liu

Table

1: Summary of Linear Constraints
AEow balance
second moment 2
population
covariance
liveness
conAEicting
transitions
boundedness
cycle population
reachable marking x
sample path
comparisons y p;t - x p 8p 2
enabling bound q t
Bp \Gamma- p;t +1
xp
Bp \Gammaj p;t +1
INRIA
Performance Analysis of Stochastic Timed Petri Nets 23
(a)
(b)
server 3 server 4
server 2
server 1

Figure

2: (a): Example of production line. (b): The corresponding Petri net model.

Table

2: Bounds on the throughput of the production line
Case exact u.b.1 u.b.2 o.l.b. o.u.b.
5 1.111 1.111 1.111 1.111 1.350 2.667 2.963 2.963 1.111 4.444
RR n\Sigma2642
Z. Liu
Recall that the Petri net is a marked graph so that according to [11] the throughput
is increasing in the -ring rates of transitions. Such a fact is clearly shown in the column
iexactj for cases 1, 2, 3 and 4. It is worthwhile noticing that the lower and upper bounds
in the columns il.b.j, iu.b.1j and iu.b.2j also reAEect such monotonicity.
6.2 Cyclic Execution
Consider now performance analysis of a parallel computing system. Parallel programs are
represented by directed acyclic graphs, referred to as task graphs, where vertices correspond
to tasks of a parallel program, and directed edges correspond to precedence relations
between tasks: a task can start execution only when all its predecessors have completed
execution. The tasks are assigned to the parallel processors for execution according to
some prede-ned rules.
In our example, parallel programs have the same structure, given by the task graph
in

Figure

3-(a). These programs dioeer only in the running times of tasks which are independently
and exponentially distributed random variables, with parameters
for tasks There are three identical processors. Tasks 1 and 2 are assigned to
processor 1, tasks 3 and 4 to processor 2, and tasks 5 and 6 to processor 3.
(a) (b)

Figure

3: (a) Task graph of parallel programs. (b) Cyclic execution of the parallel program.
On each processor, dioeerent instantiations of the same task are executed according to
the rule -rst come -rst serve (FCFS). i.e., task i of the n-th arrived program can start
execution only after task i of program completes. Dioeerent tasks assigned to the
same processor are, however, executed according to the processor sharing (PS) discipline.
In our example, since only two dioeerent tasks are assigned to each processor, the processor
INRIA
Performance Analysis of Stochastic Timed Petri Nets 25
is shared by at most two tasks. A parallel program is considered completed if all its tasks
-nish their execution.
We consider cyclic execution of the task graph, cf. Figure 3-(b). The cyclic execution
is de-ned in such a way that task t1 (resp. task t2) of program n + h can start execution
only after task t5 (resp. t6) of program n completes execution, The number
h is referred to as the height of the cyclic execution in the literature [30].
The representation of this parallel computing system by STPN is illustrated in Figure 4.
The initial marking of place p1 (the same for place p2) corresponds to the height h.
p3
p6 p7 p8

Figure

4: Petri net representation of the cyclic execution
Inhibitor arcs are used to model the PS mechanism. Transitions t11 and t12 (resp. t21
and t22, t31 and t32 and t33, t41 and t42, t51 and t52, t61 and t62 and t63) represent
tasks 1 (resp. 2, 3, 4, 5, 6). Firing times of transitions t11 and t12 (resp. t21 and t22,
RR n\Sigma2642
26 Z. Liu
t31 and t32 and t33, t41 and t42, t51 and t52, t61 and t62 and t63, are exponentially
distributed with parameter Two or three
transitions are used for each task in order to represent situations whether the execution
of a task is shared with others. Note that transitions t32 and t33 (resp. t62 and t63)
are never enabled simultaneously. The use of two additional transitions for task 3 (resp.
task is due to the fact that in each program, task 4 (resp. task 5) is allowed to start
execution only when both tasks 1 and 2 (resp. tasks 3 and 4) have completed execution.
Thus, the execution of task 3 (resp. task 6) is not shared with task 4 (resp. task 5) if only
task 1 or only task 2 (resp. only task 3 or only task
The objective function in this problem is still the total throughput, i.e. the sum of
transition throughputs. It is easy to see that this total throughput is equal to six times
the throughput of the parallel system in terms of the number of programs completed per
unit of time.
In

Table

3, we provide numerical results for -ve dioeerent sets of parameters with -xed
height 4. The lower and upper bounds are given in the columns il.b.j and iu.b.j,
whereas in columns io.l.b.j and io.u.b.j, we also present the bounds computed by linear
programming approch based on the linear constraints of Section 4 without Markovian
assumption (which implies in particular that the linear equalities of Section 3 are not
used).

Table

3: Bounds on the throughput of the cyclic execution
Case
In

Figures

5 and 6, we provide the curves of the bounds as functions of the the height
of the cyclic execution in Cases 1 and 2.
7 Conclusions and Extensions
In this paper, we have established performance bounds for Markovian STPN by taking a
linear programming approach. We -rst provided a set of linear equality constraints among
the expectation of state variables in the Petri nets, such as token numbers in the places
and indicator functions of transition enabling. We further obtained an augmenting set of
INRIA
Performance Analysis of Stochastic Timed Petri Nets 27
O.L.B.
L.B.
U.B.
O.U.B.
height (h)
Figure

5: Bounds as functions of height of the cyclic execution for Case 1
O.L.B.
L.B.
U.B.
O.U.B.
height (h)

Figure

Bounds as functions of height of the cyclic execution for Case 2
RR n\Sigma2642
28 Z. Liu
linear equalities and inequalities by exploiting structural and probabilistic properties of
the Petri nets. These linear constraints allowed us to compute upper and lower bounds
of performance measures by solving the linear program. We have applied this method to
performance analyses of a manufacturing system and a parallel system.
The constraints derived in Section 4 are not restricted to exponentially distributed
-ring times. These inequalities can also be used in operational analysis of timed Petri
nets.
In Theorems 1 and 2, we compared throughputs of transitions in a net and those in a
SCMG or a SCSM subnet (when it is considered in isolation). Similar inequalities can be
obtained using monotonicity results [11, 8, 12] for other subnets.
Throughout this paper, the transitions have single-server semantics. Our analysis can
be extended immediately to STPN with bounded marking and in-nite-server transitions.
Indeed, in such a case, each in-nite-server transition can be replaced by K single-server
transitions, where K is the upper bound of the token numbers in the places. More precisely,
we replace each in-nite-server transition t by K single-server transitions
such a way that - p;t k
An example of such a
transformation is illustrated in Figure 7, where
(a) (b)312

Figure

7: Transformation from in-nite-server transition to single-server transitions. (a)
an in-nite-server transition. (b) equivalent single-server transitions.
In our analysis, we assumed that the -ring times of each transition are i.i.d. exponential
random variables with a -xed parameter. It is simple to extend the results to the case of
marking dependent -ring rates, i.e., the -ring rate of a transition depends on the marking
of input places, provided the number of dioeerent -ring rates is bounded. As an example,
consider a transition t with a single input place. Let - 1
t and - 3
t be the -ring rates of
INRIA
Performance Analysis of Stochastic Timed Petri Nets 29
transition t when there are one token, two tokens, and more than 3 tokens in the input
place. We replace the transition by three transitions t 1 , t 2 and t 3 with -ring rates - 1
t and - 3
respectively, in such a way that at any time at most one of the transitions is
enabled, see Figure 8. The set of outgoing places are the same as that of t: oe t k
3.
(a) (b)3123

Figure

8: Transformation from marking-dependent -ring rate to marking-independent
-ring rates. (a) transition with 3 -ring rates. (b) equivalent transitions with -xed -ring
rates.
Our approach can be extended to the case that -ring times have phase-type distributions
[37]. A phase-type distribution can be considered as the distribution of the time
that a token passes through an ordinary Markovian state machine with a single source
and a single sink transitions. The -ring times have exponential distributions for all transitions
except the source and the sink which are immediate transitions. The sink transition
represents the absorbing state. Let transition t have a phase-type distribution which is
represented by a Markovian state machine N 0 with source transition t 0 and sink transition
t s . We replace transition t in the original net by the subnet N 0 as follows. For any p 2 P
and any transition t 0 6= t s of N 0 (including t 0 and excluding t s
and oe t 0 . For any p 2
is a new place with initial marking 1. An example of the construction is illustrated in

Figure

9 for an Erlang distribution with 3 stages. Recall that the -ring mechanism under
consideration is race policy with age memory. The reader can therefore easily check
that when transitions whose -ring times have phase-type distributions are thus replaced
by corresponding Markovian state machines, we obtain a stochastically equivalent STPN
with exponential -ring times.
The performance measures considered in the paper are mostly the throughputs of
transitions and the expectations of X p and X p e t . The same approach can be used to
RR n\Sigma2642
Z. Liu
(a)122224(b)

Figure

9: Transformation from phase-type -ring times to exponential -ring times. (a)
transition with 3-stages-Erlang-distribution -ring times. (b) transitions with exponential
-ring times.
INRIA
Performance Analysis of Stochastic Timed Petri Nets 31
obtain linear equalities among higher moments of the token numbers. More precisely, for
any m - 1, linear equalities can be established for variables E[X k
ii
. Similarly, for
any m - 1, linear equalities can be established for variables E[X k 1
p2 (- n+1 )jF -n
ii
Finally, we remark that when the weights of the STPN are real numbers, all our
analyses go through straightforwardly and the same results hold.

Appendix

Elimination of Immediate Transitions
We present here a direct transformation technique which removes immediate transitions
playing roles of synchronization and/or routing. We assume that for any such immediate
transition t, t is the only output transition of all its input places, i.e.
t. Further, we assume that for any immediate transition t,
and
ffl either oe t;p 0
ffl or oe t;p
with a harmless abuse of notation, the index ffl p denotes the
unique transition preceding place p.
We show below that this kind of immediate transitions can be removed from the
net without changing the -ring behavior of the other transitions. Consider a net
E) with initial marking M and weights -; oe. Let t 0 be an immediate transition,
g. Without loss of generality, we assume
that min p2 ffl t 0
We construct a new net f
E) with initial marking f
M and weights ~
oe.
The key idea is to create a place p i
for each pair of input place p i and output place p j
of transition t 0 . The set of input transitions of p i
j is the union of ffl p i and ffl p j . The set
of output transitions of p i
. Such a transformation is illustrated in Figure 10, where
transition t 0 is an immediate transition.
The mathematical de-nition of f
N is as follows.
e
RR n\Sigma2642
Z. Liu
(a) (b)

Figure

10: Removal of Immediate Transitions. (a): A subnet containing an immediate
transition. (b): The subnet without immediate transition.
e
e
where E is de-ned by
The initial marking f
M and weights ~
oe are de-ned accordingly:
f
~
~ oe t;p
It is easily seen that if the sequences of the -rings times are the same for the same
transitions in N and f
-ring commencement and completion times are identical.
The detailed proof can be done by induction and is left to the interested reader.
INRIA
Performance Analysis of Stochastic Timed Petri Nets 33

Acknowledgements

: The author is very grateful to Dr Alain JEAN-MARIE for constructive
comments and for eOEcient help in the computation of numerical results.



--R

iThe Eoeect of Execution Policies on the Semantics and Analysis of Stochastic Petri Netsj
iA Class of Generalized Stochastic Petri Nets for the Performance Analysis of Multiprocessor Systemsj
Performance Models of Multiprocessor Systems
iErgodic Theory of Stochastic Petri Netsj
iAnnotated Bibliography on Stochastic Petri Netsj
Elements of Queueing Theory
iParallel Simulation of Stochastic Petri Nets Using Recursive Equationsj
iRecursive Equations and Basic properties of Timed Petri Netsj
iStationary regime and stability of free-choice Petri netsj
iEstimates of Cycle Times in Stochastic Petri Netsj
iComparison Properties of Stochastic Decision Free Petri Netsj
iGlobal and Local Monotonicities of Stochastic Petri Netsj
iOptimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterizations of Achievable Performancej
Achievable Region and Side Constraintsj
iA Characterisation of Independence for Competing Markov Chains with Applications to Stochastic Petri Netsj
iA computational Algorithm for Closed Queueing Networks with Exponential Servers.
iErgodicity and Throughput Bounds of Petri Nets with Unique Consistent Firing Count Vectorj
iProperties and performance bounds for closed free choice synchronized monoclass queueing networksj
iA General Iterative Technique for Approximate Throughput Computation of Stochastique Marked Graphsj

iEmbedded Product-form Queueing Networks and the Improvement of Performance Bounds for Petri Net Systemsj
iComputational Algorithms for Product Form Queueing Networks.
iGeneralized Stochastic Petri Nets: A De-nition at the Net Level and Its Implicationsj
iOperational Analysis of Timed Petri Nets and Application to the Computation of Performance Boundsj
SPN: What is the Actual Role of Immediate Transitions?
iSPNP: Stochastic Petri net packagej
iExtended Stochastic Petri Nets: Applications and Analysisj

iCyclic scheduling on parallel processors: an overviewj
Markov Chain Models - Rarity and Exponentiality
iPerformance Bounds for Queueing Networks and Scheduling Policiesj
iStability of Queueing Networks and Scheduling Policiesj
iComplete Decomposition of Stochastic Petri Nets Representing Generalized Service Networksj
iPerformance Analysis using Stochastic Petri Netsj


iQueueing Networks with Multiple Closed Chains: Theory and Computational Algorithms.

iA Last Word on L
--TR

--CTR
Jinjun Chen , Yun Yang, Adaptive selection of necessary and sufficient checkpoints for dynamic verification of temporal constraints in grid workflow systems, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.2 n.2, p.6-es, June 2007
mean token number;linear programming;throughput;stochastic timed petri net;uniformization;performance bound