Contribution à l'ordonnancement des instructions d'un graphe de flots de données contrôlées.

Abstract

L'évolution de l'informatique et de l'électronique dans les cinquante dernières années a été remarquable. Restreinte à ses débuts aux applications scientifiques ou militaires, elle fait aujourd'hui partie de la vie quotidienne. Une évolution si rapide que plusieurs ordinateurs qui appartenaient au domaine de la science fiction il y a vingt ans sont aujourd'hui disponibles pour le grand public. Ceci est dû au développement considérable de la technologie des semi-conducteurs et à des outils de CAO des circuits intégrés (CIs) de plus en plus performants. En effet, différents outils de synthèse, d'analyse et de vérification interviennent dans la CAO des Cls et ce, à différents niveaux d'abstraction. Parmi ces outils, on distingue celui de la synthèse de parties opératives (ensemble de registres et d'unités fonctionnelles interconnectés) qui consiste à ordonnancer les instructions d'un algorithme à implémenter sur un ASIC (circuit intégré à application spécifique) dans un souci d'obtenir un circuit autant performant que possible. Un flot de données contrôlé engendrant un nombre exponentiel de chemins de données, la méthode exacte pour un tel ordonnancement est à écarter (la complexité algorithmique ne serait pas polynomiale), et il s'agit alors d'opter pour une heuristique. Notre travail consiste, à partir de résultats partiels, à développer une technique d'ordonnancement efficace des instructions (pouvant être assujetties à des contraintes imposées par l'utilisateur) de flots de données contrôlés, visant un bon compromis entre la surface de la partie opérative et sa vitesse d'exécution en termes de nombre de cycles.