Loading...
Please wait, while we are loading the content...
Similar Documents
Ordonnancement temps réel multiprocesseur de tâches non-préemptives avec contraintes de précédence, de périodicité stricte et de latence
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kermia, O. |
| Copyright Year | 2009 |
| Abstract | La realisation de systemes temps reel embarques complexes que l'on trouve dans les domaines de l'avionique, de l'automobile, de la robotique, etc. Conduisent a resoudre des problemes d'ordonnancement temps reel non preemptif pour des architectures multiprocesseurs en respectant des contraintes multiples de precedence, de periodicite stricte et de latence. Dans la litterature les problemes de ce type sont resolus avec des methodes approchees (heuristiques) donnant des resultats dans un temps raisonnable comparees a des methodes exactes. Par ailleurs le probleme tel que nous le posons a ete peu etudie. Ce dernier etant complexe nous avons choisi d'etudier separement la periodicite d'une part et la latence d'autre part, avec aussi dans les deux cas des contraintes de precedence. L'ensemble des resultats obtenus est utilise pour traiter l'ordonnancement avec les trois contraintes. Afin de resoudre le probleme d'ordonnancement avec precedence et periodicite stricte nous avons propose une heuristique composee de trois etapes. La premiere etape appelee "assignation" est la plus importante car elle permet de decider si un systeme est ordonnancable ou pas sans etre oblige d'attendre l'execution des deux autres etapes de l'heuristique. Comme nous avons choisi d'utiliser la methode du partitionnement - partitionner le probleme multiprocesseur en plusieurs problemes monoprocesseur - plutot que la methode globale pour faire l'ordonnancement multiprocesseur, nous avons pu donner une condition pour qu'une tâche, eventuellement plusieurs, soient ordonnancables sur un processeur auquel d'autres tâches ont deja ete assignees. Nous avons propose deux versions d'algorithme d'assignation, une version gloutonne tres rapide et une version. Recherche locale. Fondee sur le retour arriere (backtracking) qui revient a tester localement plusieurs assignations pour trouver celle qui satisfait les contraintes de periodicite stricte. Nous avons montre que la version "recherche locale", bien que moins rapide que la version gloutonne, donne des resultats tres proches de ceux d'un algorithme exact de type "Branch & Cut". La seconde etape appelee "deroulement". Consiste simplement a repeter chaque tâche et les arcs de precedence qui la concernent suivant le rapport entre l'hyper-periode (PPCM des periodes de toutes les tâches) et sa periode. La troisieme etape consiste a ordonnancer les tâches sur les processeurs auxquels elles ont ete assignees tout en minimisant le temps d'execution de toutes les tâches (makespan), en prenant en compte le cout des communications interprocesseurs dues au fait que deux tâches liees par une precedence ont ete assignees a deux processeurs differents. Par ailleurs comme nous considerons des systemes embarques pour lesquels les ressources sont limitees nous avons ajoute une quatrieme etape, specifique a l'embarque, qui effectue de maniere gloutonne de la repartition de charge et de memoire. L'heuristique d'ordonnancement avec precedence et periodicite stricte a ete programmee en OCAML dans le logiciel SynDEx diffuse par l'equipe projet AOSTE. Pour tester ces resultats theoriques ainsi que leur implantation dans le logiciel SynDEx on a effectue une experimentation sur une application de suivi en train virtuel de CyCabs (vehicule electrique automatique concu par l'equipe projet IMARA) avec contraintes de precedence et de periodicite. Afin de resoudre le probleme d'ordonnancement multiprocesseur avec precedence et latence nous avons effectue une etude d'ordonnancabilite qui a montre que sa resolution est tres liee aux chemins de tâches reliant la paire de tâches sur laquelle la contrainte de latence est imposee. Nous avons propose une heuristique dans le cas d'une seule latence se composant d'une premiere etape appelee "clusterisation" et une deuxieme etape appelee "union". La clusterisation consiste a regrouper les tâches faisant partie du meme chemin dans le graphe et l'union cherche a adapter le nombre de ces clusters au nombre de processeurs en procedant a des unions entre clusters. Le cas de plusieurs latences demande de prendre en compte les differentes possibilites de chemins entre plusieurs paires de tâches soumises a differentes latences. Pour le cas le plus complexe correspondant a des chemins, entre paires de tâches soumises a differentes latences, croises on a propose une heuristique qui minimise la duree de l'ordonnancement entre chacune de ces paires de tâches. Les resultats obtenus precedemment ont ete utilises pour proposer une heuristique d'ordonnancement avec contraintes de precedence, de periodicite et de latence. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.syndex.org/publications/pubs/theses/THOK.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
