Algorithme de prédictions

statistiques du temps d’exécution

basé sur la méthode de KPPV

Pour contact :{Email: ghaffari@i3s.unice.fr}

SCS 2004, Monastir 19 Mars 2004

Présenté par: Fakhreddine GHAFFARI

Plan de l’exposé

Introduction

Approche de partitionnement en ligne

Estimation du temps d’exécution

Schéma d’exécution de l’approche

Résultats et interprétations

Conclusion

2

Applications à contraintes temps réel strict :

chaque tâche doit être exécutée avec le temps d’exécution du pire de cas

(WCET)

Applications à contraintes temps réel mou:

WCET = pessimisme excessif = Sur-dimensionner les architectures

Mauvaise gestion des ressources de calcul

La probabilité du cas de WCET

est très faible !!

Introduction

Densité de probabilité en fonction du

temps d’exécution 3

Introduction Le temps d’exécution d’une tâche peut dépendre de:

•Type de l’application : quantité de données à traiter, type de

données

•Type de l’unité de traitement : logiciel/matériel

•Facteur d’environnement : le temps de communication avec

l’environnement est variable

Travailler avec un temps d’exécution variable est plus réaliste

qu’avec le WCET

Exemples d’applications :

Détection de mouvement sur plusieurs images

Traitement matriciel pour différent tailles de matrice,

différents degrés de précision

Estimation de mouvement pour différents représentations

de l’image 4

Multiplication membre à membre

de deux matrices en fonction de

leur taille

Multiplication de deux matrices en fonction de leur taille

Exemple d’application : calcul matriciel

5

Approche de partitionnement en ligne

Outil de

Partitionnement

dynamique

Exécution de

l’application

Données

non

traitées

Prédictions

Statistiques

Texe\tâche

Texe\tâche

Données traitées 6

Évaluation

Estimateur

Tmes – T esti

Estimateur

Hors ligne

Estim 1

Estim 2

Estim 3

Ensemble

Des

observations

Ti- Tref > s ?

Oui

Non

Résumé de l’approche

T1

T2 T3

Texe

Nb Res

Estimation Partitionn Exécution Mesures

Texe

Nb Res

Texe

Nb Res

WCET

WCET

WCET

Partitionn Estimation Exécution Mesures

7

Algorithme d’estimation (1)

Méthode de KPPV

8

Compromis complexité/efficacité : précision, rapidité et simplicité de

réalisation

t1 ti-1 ti

t0 . . . ti+1= ?

di ti+1 = f (ti , ti-1, ti-2…, di, di -1…)

Algorithme d’estimation (2)

min

1

1

)

)(1*)(

1( t

jdistidist

tk

Estimk

ik

j

i

• Quelles valeurs des poids à affecter aux anciennes mesures?

9

• Quelle fonction permettant d’estimer mieux le temps d’exécution?

2

1

2 ))()((1

)( xmtxWn

e i

n

i

i

i

n

i

i txWn

xm )(1

)(1

t = m(x) + e

Quelle valeur du paramètre de corrélation ?

Texe – Tréf > s ?

Garder la dernière

valeur du Pc

Télécharger la donnée

et calculer Pc

Estimer Texe pour

les restes des

implémentations

Nouvelle valeur Texe

‡

Dernière valeur Texe

Nouvelle valeur Texe

=

Dernière valeur Texe

Estimer Texe pour

toutes les

implémentations

Non Oui

10

Schéma d’exécution de l’approche

Exemple d’ordonnancement

HW

Estim

SW

In-1 In+1 In

Partitio

T1

T2

T3

En-1

Pn-1

T1

T2

T3

T1 T2

T3

En

Pn

En-2

Pn-2

11

Comparaison entre estimateur 1 et estimateur 2

Estimations en fonction de K avec le point (3,3.26)

0

1

2

3

4

5

6

1 3 5 7 9 11 13 15 17 19 K

Estimateur 1 Estimateur 2

min

1

))(

11(1 tt

idistkEstim i

k

i

min

1

1

)

)(

1*)(

1(2 t

jdistidist

t

kEstim

k

ik

j

i

Résultats et Interprétations

12

Comparaison entre deux fonctions d’estimations :

Estimations pour K = 20

0

5

10

15

20

25

30

35

2 3 5 10 12 15 20 22 25 26 30 33 35 37 Pc

Te

xe

----- Estimées ___ Mesurées

Comparaison entre mesures et estimations

Évaluation de l’estimateur (1)

13

Évaluation de l’estimateur (2)

K évolue avec la taille de Database

0

5

10

15

20

25

30

35

40

45

2 5 12 20 25 25 25 26 33 37 43 47 50

Pc

Tex

e

Mesurées Estimées

• résultat : construction de l’enveloppe englobante en fonction du nombre des objets

14

Travaux en cours

Amélioration de la méthode de Kppv :

choix de la distance (Euclidienne, ou autre…)

Choix des poids : Epanechnikov Kernel

1²),1(4/3)( uuuK

)()(

)(xfxxK

xWr

ii

)(/1)(

1

i

k

i

rr XXKkxf

15

Avec

Conclusion et perspectives

Nous avons présenté une approche d’estimation du temps d’exécution :

+ KPPV , efficace mais il faut bien choisir :

K : le nombre des voisins

F (x): la fonction d’estimation

Wi : les poids affectées aux voisins

perspectives

+ réaliser la méthode du partitionnement en l’implantant sur l’architecture cible

+ expérimenter l’estimateur Kppv en ligne avec toute la chaîne du partitionnement pour plusieurs applications…

16