Un système temps réel critique nécessite une validation temporelle utilisant un test d'ordonnançabilité avant sa mise en œuvre. Cette thèse traite le problème d'ordonnancement des taches à offset (transactions) sur une architecture monoprocesseur, en priorités fixes et en priorités dynamiques. Les méthodes existantes pour un test exact ont une complexité exponentielle et seules existent des méthodes approchées, donc pessimistes, qui sont pseudo-polynomiales. En priorités fixes nous proposons des méthodes pseudo-polynomiales, basées sur l'analyse de temps de réponse qui sont moins pessimistes que les méthodes existantes. Nous présentons quelques propriétés (accumulativité monotonique, dominance de tâches) rendant exacte les méthodes d'analyse approchées pour certains cas de systèmes, et optimisant le temps de calcul. En priorités dynamiques, nous proposons un test d'ordonnançabilité exact avec une complexité pseudo-polynomiale. Ce test est basé sur l'analyse de la demande processeur. Les qualités des résultats de nos méthodes sont confirmées par des évaluations expérimentales.

Cette thèse s'intéresse d'une part au problème de décomposition technologique orienté surface sur des réseaux programmables de type FPGAs (Field Programmable Gate Arrays) et d'autre part à la synthèse des macro-générateurs sur ASICs et plus précisément de la synthèse des additionneurs. La décomposition s'articule autour de deux axes essentiels: tout d'abord, il s'agit d'optimiser la taille de la représentation des fonctions booléennes. Les représentations de base choisies ici sont les ROBDDs (Reduced Ordered Binary Decision Diagrams) ainsi qu'une structure dérivée, les ITE (If Then Else). La deuxième étape concerne la décomposition proprement dite. Les technologies cibles sont ici des FPGAs à base de LUT-k (Look Up Table), en particulier les FPGAs XC5200 de Xilinx et Orca de AT&T. Les deux méthodes de décomposition technologique orienté surface proposées permettent une décomposition hétérogène en prenant en compte non pas une seule configuration mais un ensemble de configurations possibles de la cellule cible. La première méthode est fondée sur un parcours descendant et optimisé du ROBDD. La seconde méthode s'appuie sur une modélisation en recouvrement d'hypergraphe du problème de décomposition technologique. Dans les deux méthodes, le coût exact en terme de surface finale du circuit est pris en compte à chaque étape de la décomposition. L'étude menée dans la deuxième partie de la thèse sur la macro-génération conduit dans un premier temps à l'exploration de l'espace des solutions possibles puis à l'optimisation d'une solution sélectionnée par un algorithme de dérivation discrète. L'utilisation d'un filtre permet la restriction de l'espace des solutions à explorer et d'autre part guide le processus de dérivation en éliminant les solutions trivialement médiocres. La combinaison des processus d'exploration et de dérivations permet la génération de macros dont les caractéristiques physiques sont les plus proches possibles de celles fixées par un utilisateur potentiel. Ces méthodes ont été intégrées au sein d'un outil universitaire ASYL+ développé au laboratoire CSI

La première partie de la thèse est consacrée au problème de la gestion des feux tricolore d'un carrefour, et la deuxième partie s'inscrit dans le cadre plus général de la modélisation des déplacements urbains

Le 3GPP (3rd Generation Partnership Project) a choisi, dans sa Release 99, le protocole AAL2/ATM pour le transport des données sur les interfaces Iub et Iur du réseau d'accès de l'UMTS, nommé UTRAN (UMTS Terrestrial Radio Access Network). L'AAL-2 (ATM Adaptation Layer - Type 2) est une couche d'adaptation au-dessus de la couche ATM. L'AAL2 consiste à agréger plusieurs paquets de différents flux dans une même cellule ATM pour réduire le temps de remplissage surtout pour les applications temps-réel à bas débit. Les études menées sur l'AAL2 pour évaluer ses performances ne sont pas nombreuses, surtout dans le contexte de l'UTRAN où les contraintes temporelles sont strictes à cause des mécanismes de synchronisation des canaux de transport radio. Le lien entre le Node B et le RNC, où le protocole AAL2 est déployé, ne doit pas constituer le goulot d'étranglement (Bottleneck) pour les flux transportés. Le protocole AAL2 doit être bien étudié pour évaluer ses performances et ses capacités pour le transport des canaux radio. <br />L'AAL2 constitue un véritable protocole de transport qui se superpose au protocole de transport ATM. Or, dans les normes de l'AAL2, aucune notion de qualité de service (QoS) n'était définie pendant notre étude. En plus, les études faites étaient insuffisantes pour définir un modèle complet de la QoS dans l'AAL2. Nous avons alors contribué pour définir des classes de QoS au niveau AAL2, des paramètres de QoS, des capacités de transfert (AAL2-TC) ainsi que des critères de performance. Ensuite, nous proposons des schémas d'association (mapping) entre les différentes classes de service de l'UMTS et les classes de l'AAL2 d'une part et entre les classes de l'AAL2 et les classes de l'ATM d'autre part. Un schéma de partage de la bande passante entre les différentes classes est proposé ainsi qu'un schéma de contrôle d'admission des connexions AAL2. Dans le cas où plusieurs types de trafic seraient agrégés dans le même VC ATM, un mécanisme d'ordonnancement au niveau AAL2 est nécessaire pour pouvoir différencier entre les classes de services. Plusieurs algorithmes d'ordonnancement sont proposés au niveau de l'AAL2 et une comparaison entre ces mécanismes est réalisée dans plusieurs contextes pour évaluer les avantages et les inconvénients de chaque algorithme. Nous proposons un nouvel algorithme dynamique appelé DyWRR qui s'adapte avec le changement du trafic. Nous étudions aussi un paramètre important relatif au protocole AAL2 qui est le Timer-CU (Timer - Combined Use). Ce paramètre de temporisation a une influence sur le délai des paquets et sur le taux d'utilisation de la bande passante. Une étude fine et détaillée de ce paramètre est réalisée pour obtenir des résultats sur sa valeur optimale. Le choix de l'ATC (ATM Transfer Capability) pour le transport des connexions AAL2 fait une partie de notre étude. Le DBR et le SBR sont deux ATC proposées et une comparaison entre ces deux solutions est analysée. Quand on parle de l'AAL2 comme un protocole de transport, l'idée de la commutation AAL2 ne sera plus exclue. Au lieu de commuter les cellules ATM, on peut commuter les paquets AAL2 pour qu'on puisse séparer les connexions AAL2 dans un nud donné du réseau. La commutation AAL2 présente des avantages mais également des inconvénients que nous traitons dans cette thèse.<br />Les résultats de létude sur lAAL2 faite dans le cadre de cette thèse ont été utilisés pour une contribution à la normalisation au sein de lITU-T (International Telecommunication Union -Telecommunication standardization sector). Ces travaux de normalisation ont abouti à une nouvelle norme appelée ITU-T I.378 qui traite la problématique de la qualité de service et du contrôle de trafic au niveau de lAAL2.<br />Dans la Release 5 du 3GPP, l'IP est introduit comme protocole de transport sur les interfaces Iub et Iur dans une optique de réaliser des réseaux "tout-IP". Ce protocole, dans sa version simple, ne peut pas garantir une qualité de service parce qu'il ne fournit qu'une seule classe de service pour tous les flux, la classe du meilleur effort (Best Effort). Des mécanismes de différenciation des services sont alors nécessaires comme DiffServ ou IntServ dans le contexte de l'UTRAN. Plusieurs architectures pour le transport en IP sur l'interface Iub sont présentées. D'ailleurs, ces solutions en IP introduisent une charge supplémentaire à cause de la longueur des en-têtes. Sachant que les opérateurs des télécommunications s'intéressent à l'optimisation de la bande passante sur les liens appelés Last Mile Link, une étude est alors réalisée dans cette thèse pour évaluer les performances des solutions en IP dans l'UTRAN.

Ce manuscrit synthétise plus d'une décade de notre recherche académique sur le sujet d'optimisation de codes bas niveau, dont le but est une intégration dans un compilateur optimisant ou dans un outil d'optimisation semi-automatique. Dans les programmes bas niveau, les caractéristiques du processeur sont connues et peuvent être utilisées pour générer des codes plus en harmonie avec le matériel. Nous commençons notre document par une vue générale sur le problème d'ordonnancement des phases de compilation. Actuellement, des centaines d'étapes de compilation et d'optimisation de codes existent; un problème fondamental et ouvert reste de savoir comment les combiner et les ordonner efficacement. Pour pallier rapidement cette difficulté, une stratégie du moindre effort consiste à appliquer une compilation itérative en exécutant successivement le programme avant de décider de la technique d'optimisation de code à employer et avec quels paramètres. Nous prouvons que l'approche de compilation itérative ne simpli fie pas fondamentalement le problème, et l'utilisation de modèles statiques de performances reste un choix raisonnable. Un problème classique de con it entre deux étapes de compilation est celui qui lie l'allocation de registres et l'ordonnancement d'instructions. Nous montrons comment gérer efficacement cet antagonisme en séparant les contraintes de registres des contraintes d'ordonnancement d'instructions. Cela est possible grâce à la notion de saturation en registres (RS), qui est le besoin maximal en registres pour tous les ordonnancements possibles d'un graphe. Nous apportons une contribution formelle et une heuristique efficace, qui permettent la détection de contraintes de registres toujours véri fiées; ils peuvent par conséquent être négligées. Nous introduisons la plate-forme SIRA, qui permet de garantir l'absence de code de vidage avant l'ordonnancement d'instructions. SIRA est un modèle basé sur la théorie des graphes permettant de borner le besoin maximal en registres pour tout pipeline logiciel, sans altérer, si possible, le parallélisme d'instructions. SIRA modélise les contraintes cycliques des registres dans différentes architectures possibles : avec plusieurs types de registres, avec tampons ou les d'attente, et avec des bancs de registres rotatifs. Nous apportons une heuristique efficace qui montre des résultats satisfaisants, que ce soit comme outil indépendant, ou comme passe intégrée dans un vrai compilateur. Dans le contexte des processeurs exhibant des retards d'accès aux registres (VLIW, EPIC, DSP), nous attirons l'attention sur le problème qui peut survenir lorsque les contraintes de registres sont traitées avant l'ordonnancement d'instructions. Ce problème est la création de circuits négatifs ou nuls dans le graphe de dépendances de données. Nous montrons comment éliminer ces circuits indésirables dans le contexte de SIRA. SIRA définit une relation formelle entre le nombre de registres alloués, le parallélisme d'instructions et le facteur de déroulage d'une boucle. Nous nous basons sur cette relation pour écrire un algorithme optimal qui minimise le facteur de déroulage tout en sauvegardant le parallélisme d'instructions et en garantissant l'absence de code de vidage. D'après nos connaissances, ceci est le premier résultat qui démontre que le compactage de la taille de code n'est pas un objectif antagoniste à l'optimisation des performances de code. L'interaction entre la hiérarchie mémoire et le parallélisme d'instructions est un point central si l'on souhaite réduire le coût des latences d'opérations de chargement. Premièrement, notre étude pratique avec des micro-benchmarks montre que les processeurs superscalaires ayant une exécution dans le désordre ont un bug de performances dans leur mécanisme de désambiguation mémoire. Nous montrons ensuite qu'une vectorisation des opérations mémoire résoud ce problème pour des codes réguliers. Deuxièmement, nous étudions l'optimisation de préchargement de données pour des codes VLIW embarqués irréguliers. Finalement, avec l'arrivée des processeurs multicoeurs, nous observons que les temps d'exécution des programmes deviennent très variables. A fin d'améliorer la reproductibilité des résultats expérimentaux, nous avons conçu le Speedup-Test, un protocole statistique rigoureux. Nous nous basons sur des tests statistiques connus (tests de Shapiro-Wilk, F de Fisher, de Student, de Kolmogorov-Smirnov, de Wilcoxon- Mann-Whitney) a n d'évaluer si une accélération observée du temps d'exécution médian ou moyen est signi cative.

Les travaux présentés dans cette thèse portent sur l'ordonnancement d'applications sur des plate- formes hétérogènes à grande échelle. Dans la mesure où le problème général est trop complexe pour être résolu de façon exacte, nous considérons deux relaxations. Tâches divisibles : La première partie est consacrée aux tâches divisibles, qui sont des appli- cations parfaitement parallèles et pouvant être arbitrairement subdivisées pour être réparties sur de nombreux processeurs. Nous cherchons à minimiser le temps de travail total lors de l'exécution de plusieurs applications aux caractéristiques différentes sur un réseau linéaire de processeurs, sachant que les données peuvent être distribuées en plusieurs tournées. Le nombre de ces tour- nées étant fixé, nous décrivons un algorithme optimal pour déterminer précisément ces tournées, et nous montrons que toute solution optimale requiert un nombre infini de tournées, résultat restant vrai sur des plate-formes non plus linéaires mais en étoile. Nous comparons également notre méthode à des méthodes déjà existantes. Ordonnancement en régime permanent : La seconde partie s'attache à l'ordonnancement de nombreuses copies du même graphe de tâches représentant une application donnée. Au lieu de chercher à minimiser le temps de travail total, nous optimisons uniquement le cœur de l'or- donnancement. Tout d'abord, nous étudions des ordonnancements cycliques de ces applications sur des plate-formes hétérogènes, basés sur une seule allocation pour faciliter leur utilisation. Ce problème étant NP-complet, nous donnons non seulement un algorithme optimal, mais éga- lement différentes heuristiques permettant d'obtenir rapidement des ordonnancements efficaces. Nous les comparons à ces méthodes classiques d'ordonnancement, telles que HEFT. Dans un second temps, nous étudions des applications plus simples, faites de nombreuses tâches indépendantes, que l'on veut exécuter sur une plate-forme en étoile. Les caractéristiques de ces tâches variant, nous supposons qu'elles peuvent être modélisées par des variables aléatoires. Cela nous permet de proposer une ε-approximation dans un cadre clairvoyant, alors que l'ordonnan- ceur dispose de toutes les informations nécessaires. Nous exposons également des heuristiques dans un cadre non-clairvoyant. Ces différentes méthodes montrent que malgré la dynamicité des tâches, il reste intéressant d'utiliser un ordonnancement statique et non des stratégies plus dynamiques comme On-Demand. Nous nous intéressons ensuite à des applications, dont plusieurs tâches sont répliquées sur plu- sieurs processeurs de la plate-forme de calcul afin d'améliorer le débit total. Dans ce cas, même si les différentes instances sont distribuées aux processeurs tour à tour, le calcul du débit est difficile. Modélisant le problème par des réseaux de Petri temporisés, nous montrons comment le calculer, prouvant également que ce calcul peut être fait en temps polynomial avec le modèle Strict One-Port. Enfin, le dernier chapitre est consacré à l'application de ces techniques à un processeur multi- cœur hétérogène, le Cell d'IBM. Nous présentons donc un modèle théorique de ce processeur ainsi qu'un algorithme d'ordonnancement adapté. Une implémentation réelle de cet ordonnanceur a été effectuée, permettant d'obtenir des débits intéressants tout en simplifiant l'utilisation de ce processeur et validant notre modèle théorique.

Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille sur des machines parallèles. Dans ce contexte, la mémoire est un facteur qui limite voire empêche souvent l'utilisation de solveurs directs, notamment ceux basés sur la méthode multifrontale. Cette étude se concentre sur les problèmes de mémoire et de performance des deux phases des méthodes directes les plus coûteuses en mémoire et en temps : la factorisation numérique et la résolution triangulaire. Dans une première partie nous nous intéressons à la phase de résolution à seconds membres creux, puis, dans une seconde partie, nous nous intéressons à la scalabilité mémoire de la factorisation multifrontale. La première partie de cette étude se concentre sur la résolution triangulaire à seconds membres creux, qui apparaissent dans de nombreuses applications. En particulier, nous nous intéressons au calcul d'entrées de l'inverse d'une matrice creuse, où les seconds membres et les vecteurs solutions sont tous deux creux. Nous présentons d'abord plusieurs schémas de stockage qui permettent de réduire significativement l'espace mémoire utilisé lors de la résolution, dans le cadre d'exécutions séquentielles et parallèles. Nous montrons ensuite que la façon dont les seconds membres sont regroupés peut fortement influencer la performance et nous considérons deux cadres différents : le cas "hors-mémoire" (out-of-core) où le but est de réduire le nombre d'accès aux facteurs stockés sur disque, et le cas "en mémoire" (in-core) où le but est de réduire le nombre d'opérations. Finalement, nous montrons comment améliorer le parallélisme. Dans la seconde partie, nous nous intéressons à la factorisation multifrontale parallèle. Nous montrons tout d'abord que contrôler la mémoire active spécifique à la méthode multifrontale est crucial, et que les techniques de "répartition" (mapping) classiques ne peuvent fournir une bonne scalabilité mémoire : le coût mémoire de la factorisation augmente fortement avec le nombre de processeurs. Nous proposons une classe d'algorithmes de répartition et d'ordonnancement "conscients de la mémoire" (memory-aware) qui cherchent à maximiser la performance tout en respectant une contrainte mémoire fournie par l'utilisateur. Ces techniques ont révélé des problèmes de performances dans certains des noyaux parallèles denses utilisés à chaque étape de la factorisation, et nous avons proposé plusieurs améliorations algorithmiques. Les idées présentées tout au long de cette étude ont été implantées dans le solveur MUMPS (Solveur MUltifrontal Massivement Parallèle) et expérimentées sur des matrices de grande taille (plusieurs dizaines de millions d'inconnues) et sur des machines massivement parallèles (jusqu'à quelques milliers de coeurs). Elles ont permis d'améliorer les performances et la robustesse du code et seront disponibles dans une prochaine version. Certaines des idées présentées dans la première partie ont également été implantées dans le solveur PDSLin (solveur linéaire hybride basé sur une méthode de complément de Schur).

Je présente dans ce document mes résultats de recherche sur la conception sûre de systèmes embarqués sûrs. La première partie concerne la répartition automatique de programmes synchrones. Le caractère automatique de la répartition apporte un réel degré de sûreté dans la conception de systèmes répartis car c'est la partie la plus délicate de la spécification qui est automatisée. Grâce à cela, l'absence d'inter-blocage et l'équivalence fonctionnelle entre le programme source centralisé et le programme final réparti peuvent être formellement démontrées. La deuxième partie traite le sujet de l'ordonnancement et de la répartition de graphes de tâches flots-de-données sur des architectures à mémoire répartie, avec contraintes de tolérance aux fautes et de fiabilité. Je présente principalement des heuristiques d'ordonnancement statique multiprocesseur avec pour but la tolérance aux fautes et la fiabilité des systèmes, mais également l'utilisation de méthodes formelles telles que la synthèse de contrôleurs discrets ou les transformations automatiques de programmes. Enfin, la troisième partie concerne les autoroutes automatisées, avec deux volets : la commande longitudinale de véhicules autonomes et les stratégies d'insertion dans les autoroutes automatisées.

Les défis actuels du développement des systèmes embarqués<br />complexes tels que les systèmes intégrés de traitement d'image,<br />consistent à réaliser avec succès des produits fiables,<br />performants, efficaces quelles que soient les conditions d'utilisation et peu<br />coûteux. Relever ces défis passe par un bon choix d'architecture, de méthodes<br />et outils adaptés aux applications visées et aux technologies cibles. Pour de<br />nombreuses applications, en particulier en télécommunication et multimédia,<br />des réalisations temps réel souple sont souvent suffisantes, c'est-à-dire des<br />implémentations visant à obtenir une qualité de service adaptée aux besoins.<br />Au lieu de s'appuyer sur des temps d'exécutions pire cas ou des séquences de<br />test souvent peu représentatives pour concevoir ces systèmes, notre approche<br />vise une plate-forme auto-adaptative capable de s'auto-configurer au cours de<br />l'exécution de l'application (donc en ligne). On peut citer comme exemples<br />d'applications le cas d'une caméra fixe de télésurveillance qui adapte ses<br />traitements en fonction de la nature des images acquises ou un terminal mobile<br />multimodal qui change de norme de transmission si la qualité du canal de<br />communication l'exige.<br />Les composants reconfigurables ont des niveaux de performances et une<br />flexibilité qui les rendent très attractifs dans un nombre croissant de<br />développements. La reconfiguration dynamique (partielle ou complète) offre la<br />possibilité de réutiliser les mêmes ressources matérielles pour une succession<br />de traitements, et ce de façon analogue à une réalisation logicielle. Nous<br />proposons une approche permettant d'allouer et d'ordonnancer dynamiquement<br />les tâches d'une application flot de données en fonction d'une estimation de<br />leurs temps d'exécution afin de respecter au mieux les contraintes de temps.<br />Cette reconfiguration en ligne nécessite des recherches de compromis<br />complexité/efficacité de l'allocation et de l'ordonnancement afin d'optimiser la<br />qualité de service et de réduire leurs coûts de réalisation.

La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d'origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d'ordonnancement cumulatif. Un problème d'ordonnancement consiste à déterminer les dates de débuts et de fins d'un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l'on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l'on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l'aide d'algorithmes dédiés et de métaheuristiques. Par exemple, l'utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d'ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l'idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d'accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appe- lées à chaque noeud de l'arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d'un million de tâches et 64 resources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes de placement et d'ordonnancement.