Model and Notations Normalization of a MTWEG

Alix Munier-Kordon, Pascal Urard, Mohamed Benazouz, Olivier Marchetti

Description

Model and Notations Normalization of a MTWEG Formulation using an Integer Linear Program Algorithms A new Approach for Minimizing Buffer Capacities with Throughput Constraint for Embedded System Design Mohamed Benazouz, Olivier Marchetti, Alix Munier-Kordon, Pascal Urard LIP6 Université P. et M. Curie Paris Montpellier, le 23 avril 2009

• minimizing buffer


• time ?


• formulation using


• ti tj


• mohamed benazouz


• lip6 université


• weighted event


• throughput constraint

Sujets

• Marchetti

Informations

• Publié par: pefav
• Publié le: 01 avril 2009
• Nombre de lectures: 48
• Langue: English

Extrait

Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
A new Approach for Minimizing Buffer
Capacities with Throughput Constraint for
Embedded System Design
Mohamed Benazouz, Olivier Marchetti, Alix Munier-Kordon,
Pascal Urard
LIP6
Université P. et M. Curie
Paris
Montpellier, le 23 avril 2009Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Outline
1 Model and Notations
2 Normalization of a MTWEG
3 Formulation using an Integer Linear Program
4 AlgorithmsModel and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Marked Timed Weighted Event Graph (MTWEG)
Definition
G =(T, P,ℓ, M ) is a Marked Timed Weighted Event Graph0
(MTWEG) where
1 T ={t ,··· , t } transitions;1 n
2 P ={p ,··· , p } places;1 m
3 ℓ: T → N duration function;
4 M : P → N initial marking;0Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Marked Timed Weighted Event Graph (MTWEG)
p
u(p) v(p)
M (p) tt 0 ji
Figure: A place p =(t , t) of a MTWEG.i j
1 Each place p∈ P is defined between two transitions t andi
t ;j
2 ∀p∈ P u(p) and v(p) are integers called the marking
functions.Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Firing of a transition
+P (t)={p =(t , t)∈ P, t ∈ T}i i j j
−P (t)={p =(t , t)∈ P, t ∈ T}i j i j
if t is fired at time τ:i
1 At time τ, v(p) tokens are removed from every place
−p∈P (t).i
2 At time τ +ℓ(t), u(p) tokens are added to every placei
+p∈P (t).i
M(τ, p)= The instantaneaous marking of a place p∈ P at time
τ ≥ 0Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Schedule and Periodic Schedule
Definition
⋆ +LetG be a MTWEG. A schedule is a function s : T × N → Q
⋆which associates, with any tuple(t , q)∈ T × N , the startingi
time of the qth firing of t .i
Definition
A schedule s is periodic if there exists a vector
n+w =(w ,..., w )∈ Q such that, for any couple1 n
⋆(t , q)∈ T × N , s(t , q)= s(t , 1)+(q− 1)w . w is then thei i i i i
1speriod of the transition t and λ (t)= its throughput.i i
wiModel and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
A car radio application (Wiggers et al.)
t t tMP3 Out To7 1 9
SpeakerReader
tCell 5
Phone
t3
tMicro- 10
phone
Signal to eliminate
Figure: Block diagram of a car-radio applicationModel and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Modelling using a MTWEG
1 Transitions corresponds to treatments;
2 Places corresponds to buffered transfers.
But...the size of the buffers should be limited !Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Bounded capacity
Definition
A place p =(t , t) has a bounded capacity F(p) > 0 if thei j
number of tokens stored in p can not exceed F(p):
∀τ ≥ 0, M(τ, p)≤ F(p)
Definition
A MTWEGG =(T, P, M ,ℓ, F) is said to be a bounded capacity0
graph if the capacity of every place p∈ P is bounded by F(p).Model and Notations
Normalization of a MTWEG
Formulation using an Integer Linear Program
Algorithms
Bounded capacity (Marchetti, Munier 2009)
M (p ) = M (p)0 1 0
p
pu(p) v(p) 1
u(p) v(p)
p2M (p)0t t t ti j i j
M(p,τ)≤ F(p)
M (p ) = F(p)− M (p)0 2 0
Figure: A place p with limited capacity F(p) and the couple of places
(p , p ) without capacities that models place p.1 2 c
Definition
G is a symmetric MTWEG if every place p =(t , t) is associatedi j
′with a backward place p =(t , t) modelling the limited capacity.j i