Abstract FR:

Le cur d'un outil de synthese d'architecture est sans conteste la partie algorithmique qui effectue l'ordonnancement et l'allocation des ressources. Cette partie doit permettre de trouver la meilleure solution d'ordonnancement et d'allocation des ressources, par rapport a des contraintes de temps, de types et de nombre de ressources que le concepteur peut vouloir imposer. Dans le cadre du projet osys (outil de synthese et de specification), un couple d'algorithmes, le mls (minimum list scheduling) et le cvfp (clique valued fast partitioning), a ete mis au point permettant en grande partie de repondre aux exigences citees plus haut, tout en conservant une grande rapidite d'execution. Le minimum list scheduling est un algorithme d'ordonnancement (de type list scheduling) qui permet d'ordonnancer a l'aide d'un minimum de ressources un processus se deroulant dans un temps donne. Dans osys ce temps a ete pris comme le minimum. De plus, il repartit au mieux (equipartition) ces ressources sur les differents pas de controles possibles. Les resultats obtenus sont, sur les exemples classiques, comparables aux meilleurs produits actuellement, pour une complexite inferieure. A l'issue du deroulement du mls, des ressources en general en nombre minimum et reparties au mieux, ont ete ordonnancees sur des pas de controles permettant de decrire un processus donne. Il est important que la phase suivante d'allocation des ressources conserve ces proprietes. Le cvfp, algorithme de type partitionnement en clique, permet cette conservation. Cet algorithme, base sur la theorie des graphes, applique sur les arcs du graphe de depart representant les compatibilites temporelles entre les differents nuds, une fonction de valuation qui donne aux arcs, un poids d'autant plus grand que l'interet a regrouper ces nuds est eleve. Il applique ensuite une heuristique qui accelere considerablement la recherche de la, ou des solutions, en partitionnant en un nombre minimum de cliques, de poids total maximum, le graphe ainsi value. Les resultats obtenus montrent en general une meilleure repartition et utilisation des ressources. Le temps d'execution, pour un meme jeu de ressources alloue, est de plusieurs ordres de grandeur inferieur aux meilleurs publies a ce jour. Ce couple d'algorithmes permet d'accelerer la chaine de traitement ordonnancement-allocation des ressources dans un outil de synthese d'architecture. Il montre egalement la possibilite de creer grace a osys, un outil modulaire ou le concepteur peut integrer des algorithmes adaptes a ses besoins