Model and Notations Normalization of a MTWEG

pages

English

Documents

2009

Écrit par
Mohamed Benazouz , Olivier Marchetti , Pascal Urard , Alix Munier-Kordon

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

2009

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Publié le

01 avril 2009

Nombre de lectures

Langue

English

minimizing buffer

time ?

formulation using

ti tj

mohamed benazouz

lip6 université

weighted event

throughput constraint

Voir

Publié par

pefav

Publié le

01 avril 2009

Nombre de lectures

Langue

English

Marchetti

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)
Deﬁnition
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 deﬁned 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 ﬁred 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
Deﬁnition
⋆ +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 ﬁring of t .i
Deﬁnition
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
Deﬁnition
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)
Deﬁnition
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
Deﬁnition
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