Les récentes avancées dans le domaine du traitement d'antennes et dans la microélectronique ont fait naître la technologie des antennes intelligentes connue sous le nom de "smart antennas". Considérée comme rupture technologique pour les réseaux sans fil, les systèmes d'antennes intelligentes pourraient répondre aux exigences de plus en plus fortes des applications et services en termes de débit, de capacité et de connectivité. Aujourd'hui, les smart antennas sont exploitées pour développer plusieurs technologies incluant les systèmes de commutation de faisceaux, les antennes adaptatives et les systèmes MIMO (Multiple Input Multiple Output). L'utilisation des antennes MIMO a été reconnue comme une technologie-clé, capable d'accroître considérablement la capacité des réseaux sans fil en exploitant différemment et mieux le spectre radio. Elle fait partie des récents et futurs standards tels que le 3GPP-LTE et le IEEE-802.11n. Dans cette thèse, nous nous sommes intéressés à l'exploitation des techniques multi-antennes dans le contexte des réseaux mobiles. Nous nous sommes focalisés principalement sur deux axes de recherche : la formation de faisceaux et le multiplexage spatial. Dans une première étude, nous avons proposé un schéma de formation de faisceaux, basé sur la technique LCMV (Linearly Constrained Minimum Variance) et permettant de former des faisceaux plus adaptés en cas de mobilité. Dans cette solution, l'incertitude sur la localisation des nœuds est compensée par des faisceaux de largeurs adaptées. De plus, dans le cas où les paramètres (vitesse et direction) de mouvement des nœuds sont connus, nous avons proposé d'exploiter des techniques simples d'extrapolation afin de limiter les calculs complexes des méthodes de poursuite continue (tracking), très consommatrices en ressources. Dans une seconde étude, nous avons proposé une solution d'ordonnancement basée sur la technique du multiplexage spatial qui est une caractéristique fondamentale des systèmes MIMO. L'algorithme proposé (SCLS : Stream-Controlled Multiple Access) exploite les informations inter-couches (cross-layer) : environnement radio de la couche PHY et charge de trafic de la couche LIEN. Il permet de choisir l'ensemble des liens à activer simultanément et détermine sur chacun de ces liens, le nombre d'antennes à utiliser pour transmettre des flux parallèles. SCLS permet ainsi de minimiser le temps nécessaire pour satisfaire les demandes de trafic et de maximiser le débit global utilisé à chaque instant. Dans la troisième étude, nous avons considéré la problématique d'estimation des directions d'arrivée et de départ. Nous avons proposé un algorithme (E-Capon) d'estimation conjointe de ces directions ainsi que du retard de propagation des trajets multiples dans un canal MIMO. Nous nous sommes basés sur la méthode de Capon qui permet de réduire la complexité de traitement pour offrir une estimation rapide et robuste des informations relatives à la localisation des nœuds. Notre objectif est de concevoir une technique mieux adaptée aux changements dynamiques de topologie que l'on peut observer dans les réseaux sans fil.

Les travaux présentés dans cette thèse portent sur diverses techniques d'ordonnance- ment de tâches indépendantes pour des plates-formes de type maître-esclaves dis- tribuées à grande échelle, lorsque les temps de communications des tâches sont pris en compte par des modèles réalistes. Les contributions de cette thèse se situent à trois niveaux : 1) Algorithmique Parallèle : nous avons montré la complexité d'ordonnancer des tâches indépendantes sur une plate-forme hétérogène en modélisant les communications avec un modèle un-port, en regardant plusieurs sources d'hétérogénéité et plusieurs fonctions objectives; 2) Produit de matrices : nous avons calculé la borne théorique du volume de communication minimal nécessaire pour effectuer un produit de matrices dont les données sont centralisées, et où la mémoire des esclaves est limitée, et nous avons défini un algorithme efficace de partage de la mémoire, impliquant un volume de communication proche de la borne théorique. Nous avons ensuite étendu cet algorithme à des plate-formes hétérogènes ; 3) Ordonnancement : dans le cadre d'ordonnancement d'applications constituées d'un très grand nombre de tâches indépendantes et de caractéristiques identiques, nous avons étudié en régime permanent comment minimiser le retard de chaque application lorsqu'elles sont plusieurs à entrer en compétition pour les ressources de calcul, et comment minimiser la consommation de la plate-forme lorsqu'une seule application est déployée.

Thesis (doctoral) - Universität, Darmstadt. / Includes bibliographical references.

Thesis (doctoral) - Universität, Darmstadt. / Includes bibliographical references.

Thèse (Ph. D.)--Université Laval, 2001. / Bibliogr.: f. [204]-226. Publié aussi en version électronique.

Les systèmes temps réel sont des systèmes informatiques composés de tâches auxquelles sont associées des contraintes temporelles, appelées échéances. Dans notre étude, nous distinguons deux familles de tâches : les tâches temps réel dur et les tâches temps réel souple. Les premières possèdent une échéance stricte, qu'elles doivent impérativement respecter. Elles sont de nature périodique, ou sporadique, et l'étude analytique de leur comportement fait l'objet d'un état de l'art conséquent. Les secondes sont de nature apériodique. Aucune hypothèse sur leur modèle d'arrivéée ni sur leur nombre n'est possible. Aucune garantie ne saurait être donnée sur leur comportement dès lors que l'on ne peut écarter les situations de surcharge, où la demande de calcul peut dépasser les capacités du système. La problématique devient alors l'étude des solutions d'ordonnancement mixte de tâches périodiques et apériodiques qui minimisent les temps de réponse des tâches apériodiques tout en garantissant les échéances des tâches périodiques. De nombreuses solutions ont été proposées ces vingt dernières années. On distingue les solutions basées sur la réservation de ressources, les serveurs de tâches, des solutions exploitant les instants d'inactivité du système, comme les algorithmes de vol de temps creux. La spécification Java pour le temps réel (RTSJ) voit le jour dans les années 2000. Si cette norme répond à de nombreux problèmes liés à la gestion de la mémoire ou à l'ordonnancement des tâches périodiques, celui de l'ordonnancement mixte de tâches périodiques et apériodiques n'est pas abordé. Nous proposons dans cette thèse d'apporter les modifications nécessaires aux algorithmes principaux d'ordonnancement mixte, le Polling Server (PS), le Deferrable Server (DS) et le Dynamic Approximate Slack Stealer (DASS) en vue de leur implantation avec RTSJ. Ces algorithmes ne peuvent en effet être implantés directement tels qu'ils sont décrits, car ils sont trop liés à l'ordonnanceur du système. Nous proposons des extensions aux APIs RTSJ existantes pour faciliter l'implantation de ces mécanismes modifiés, et nous fournissons les interfaces utiles à l'ajout d'autres solutions algorithmiques. Nous proposons également des modifications sur les APIs existantes de RTSJ afin de répondre aux problèmes d'intégration et d'implantation d'algorithmes d'analyse de faisabilité. Nous proposons enfin un algorithme d'estimation des temps creux, le Minimal Approximate Slack Stealer (MASS), dont l'implantation au niveau utilisateur, permet son intégration dans RTSJ

L'utilisation de TCP sur des liens asymétriques entraîne fréquemment des débits plus faibles qu'attendus au point de nuire sensiblement à la qualité de service ressentie par l'utilisateur. Ces baisses de performances peuvent prendre diverses formes parmi lesquelles une forte latence en début de connexion, une sous utilisation de la capacité du lien ou encore des latences excessivement hautes pour l'ensemble de la connexion. Afin de contrer ces effets, plusieurs approches sont possibles, que ce soit de bout-en-bout par des modifications de la pile TCP/IP ou en cœur de réseau avec divers mécanismes d'ordonnancement. L'objectif de cette thèse est d'explorer comment un résultat similaire à celui obtenu par des méthodes d'ordonnancement au goulot d'étranglement peut être obtenu en travaillant de bout-en-bout, c'est à dire là où les ressources de calcul et de mémoire sont les plus abondantes. Ce questionnement est accompagné par une analyse en profondeur des phénomènes causant une dégradation des performances, ainsi que l'évaluation des solutions existantes. Finalement, des solutions nouvelles, en cœur de réseau ainsi que de bout en bout, ont été apportées et testées sur banc d'essai. / Using TCP on asymmetric links may lead to unexpected and significant performance drops, severely degrading user experience. Those performance drops can come in various forms, among which a huge latency at the beginning of a connection, under-utilization of link capacities, or even excessive delays for the whole connection.In order to prevent those effects to happen, various approaches exist, either end-to-end through changes in the TCP/IP stack, or in the network core with a collection of scheduling algorithms.The first goal of this thesis is to explore if and how an end-to-end policy (i.e where CPU and memory resources are the most abundant) can achieve similar results as buffering policies in the core of the network. Secondly, we provide an in-depth analysis of the root cause of the performance drops, and evaluate existing algorithms. Finally, new solutions, both end-to-end and in the core of the network, are brought and tested in real life networks.

Le domaine du calcul haute performance (i.e. la science des super-calculateurs)est caractérisé par l’évolution continuelle des architectures de calcul, la proliférationdes ressources de calcul et la complexité croissante des problèmes que les utilisateursveulent résoudre. Un des logiciels les plus importants de la pile logicielle dessupercalculateurs est le Système de Gestion des Ressources et des Tâches. Il est lelien entre la charge de travail donnée par les utilisateurs et la plateforme de calcul. Cetype de logiciels spécialisés fournit des fonctions pour construire, soumettre, planifieret surveiller les tâches dans un environnent de calcul complexe et dynamique.Pour pouvoir atteindre des supercalculateurs exaflopiques, de nouvelles con-traintes et objectifs ont été inventés. Cette thèse développe et teste l’idée que lesutilisateurs de ces systèmes peuvent aider à atteindre l’échelle exaflopique. Spé-cifiquement, nous montrons des techniques qui utilisent les comportements desutilisateurs pour améliorer la consommation énergétique et les performances glob-ales des supercalculateurs.Pour tester ces nouvelles techniques, nous avons besoin de nouveaux outils etméthodes qui sont capables d’aller jusqu’à l’échelle exaflopique. Nous proposonsdonc des outils qui permettent de tester de nouveaux algorithmes capables des’exécuter sur ces systèmes. Ces outils sont capables de fonctionner sur de petitssupercalculateurs en émulant ou simulant des systèmes plus puissants. Après avoirévalué différentes techniques pour mesurer l’énergie dans les supercalculateurs, nousproposons une nouvelle heuristique, basée sur un algorithme répandu (Easy Backfill-ing), pour pouvoir contrôler la puissance électrique de ces énormes systèmes. Nousmontrons aussi comment, en utilisant la même méthode, contrôler la consommationénergétique pendant une période de temps. Le mécanisme proposé peut limiterla consommation énergétique tout en gardant des performances satisfaisantes. Sil’énergie est une ressource limitée, il faut la partager équitablement. Nous présen-tons de plus un mécanisme permettant de partager la consommation énergétiqueentre les utilisateurs. Nous soutenons que cette méthode va motiver les utilisateursà réduire la consommation énergétique de leurs calculs. Finalement, nous analysonsle comportement actuel et passé des utilisateurs pour améliorer les performancesdes supercalculateurs. Cette approche non seulement surpasse les performances destravaux existants, mais aussi ouvre la voie à l’utilisation de méthodes semblablesdans d’autres aspects des Systèmes de Gestion des Ressources et des Tâches. / The field of High Performance Computing (HPC) is characterized by the contin-uous evolution of computing architectures, the proliferation of computing resourcesand the increasing complexity of applications users wish to solve. One of the mostimportant software of the HPC stack is the Resource and Job Management System(RJMS) which stands between the user workloads and the platform, the applica-tions and the resources. This specialized software provides functions for building,submitting, scheduling and monitoring jobs in a dynamic and complex computingenvironment.In order to reach exaflops HPC systems, new constraints and objectives havebeen introduced. This thesis develops and tests the idea that the users of suchsystems can help reaching the exaflopic scale. Specifically, we show and introducenew techniques that employ users behaviors to improve energy consumption andoverall cluster performances.To test the proposed techniques, we need to develop new tools and method-ologies that scale up to large HPC clusters. Thus, we designed adequate tools thatassess new RJMS scheduling algorithms of such large systems. These tools areable to run on small clusters by emulating or simulating bigger platforms. Afterevaluating different techniques to measure the energy consumption of HPC clusters,we propose a new heuristic, based on the popular Easy Backfilling algorithm, inorder to control the power consumption of such huge systems. We also demonstrate,using the same idea, how to control the energy consumption during a time period.The proposed mechanism is able to limit the energy consumption while keepingsatisfying performances. If energy is a limited resource, it has to be shared fairly.We also present a mechanism which shares energy consumption among users. Weargue that sharing fairly the energy among users should motivate them to reducethe energy consumption of their applications. Finally, we analyze past and presentbehaviors of users using learning algorithms in order to improve the performancesof the parallel platforms. This approach does not only outperform state of the artmethods, it also shows promising insight on how such method can improve otheraspects of RJMS.

Le contenu de cette thèse est divisé en deux parties. La première partie de cette thèse porte sur l'étude d'approches heuristiques pour approximer des fronts de Pareto. Nous proposons un nouvel algorithme de recherche locale pour résoudre des problèmes d'optimisation combinatoire. Cette technique est intégrée dans un modèle opérationnel générique où l'algorithme évolue vers de nouvelles solutions formées en combinant des solutions trouvées dans les étapes précédentes. Cette méthode améliore les algorithmes de recherche locale existants pour résoudre le problème d'assignation quadratique bi- et tri-objectifs.La seconde partie se focalise sur les algorithmes d'ordonnancement dans un contexte non-préemptif. Plus précisément, nous étudions le problème de la minimisation du stretch maximum sur une seule machine pour une exécution online. Nous présentons des résultats positifs et négatifs, puis nous donnons une solution optimale semi-online. Nous étudions ensuite le problème de minimisation du stretch sur une seule machinedans le modèle récent de la réjection. Nous montrons qu'il existe un rapport d'approximation en O(1) pour minimiser le stretch moyen. Nous montrons également qu'il existe un résultat identique pour la minimisation du flot moyen sur une machine. Enfin, nous étudions le problème de la minimisation du somme des flots pondérés dans un contexte online. / The content of this thesis is divided into two parts. The first part of the thesis deals with the study of heuristic based approaches for the approximation Pareto fronts. We propose a new Double Archive Pareto local search algorithm for solving multi-objective combinatorial optimization problems. We embed our technique into a genetic framework where our algorithm restarts with the set of new solutions formed by recombination and mutation of solutions found in the previous run. This method improves upon the existing Pareto local search algorithm for bi-objective and tri-objective quadratic assignment problem.In the second part of the thesis, we focus on non-preemptive scheduling algorithms. Here, we study the online problem of minimizing maximum stretch on a single machine. We present both positive and negative theoretical results. Then, we provide an optimally competitive semi-online algorithm. Furthermore, we study the problem of minimizing stretch on a single machine in a recently proposed rejection model. We show that there exists an O(1)-approximation ratio for minimizing average stretch. We also show that there exists an O(1)-approximation ratio for minimizing average flow time on a single machine. Lastly, we study the weighted average flow time minimization problem in online settings. We present a mathematical programming based framework that unifies multiple resource augmentation. Using the concept of duality, we show that there exists an O(1)-competitive algorithm for solving the weighted average flow time problem on unrelated machines. Furthermore, we proposed that this idea can be extended to minimizing l_k norms of weighted flow problem on unrelated machines.

Dans cette thèse, nous nous intéressons aux problèmes d'ordonnancement simultané de tâches et de périodes d'indisponibilité. Dans un premier temps, nous réalisons une revue de littérature sur la prise en compte des indisponibilités dans les problèmes d'ordonnancement.Ensuite, nous définissons un modèle général qui englobe des modèles existants de la littérature pour des ateliers à une machine et à machines parallèles. Une approche globale de résolution basée sur les problèmes d'affectation linéaire a été développée. Cette approche permet de résoudre le modèle général comme un simple problème d'affectation. Un grand nombre de critères d'optimisation et de modèles de maintenance peuvent être traités en utilisant cette approche, fournissant ainsi l'accès à tous les modèles qui ont souvent été étudiés séparément dans la littérature. Les résultats élaborés avec cette approche ont permis de résoudre des problèmes d'ordonnancement non traités avant et aussi de généraliser et améliorer des résultats antérieurs.Nous proposons, en dernier lieu, une étude d'un problème flow shop à deux machines en présence d'une période d'indisponibilité sur la deuxième machine. Une étude de complexité est menée sur le problème. Ensuite, nous définissons des propriétés d'optimalité. En se basant sur ces propriétés, trois méthodes de résolution exacte sont proposées; une méthode énumérative, un programme linéaire et une méthode basée sur l'approche de séparation et évaluation B&B. Une analyse expérimentale est présentée afin d'évaluer les performances de ces méthodes. / In classical scheduling problems, machines are assumed to be continuously available. However, in a real manufacturing system, machine may become unavailable during the scheduling period due to preventive maintenance. In this dissertation, we are interested in the problems of jointly scheduling jobs and unavailability periods.We start our study by introducing a general framework for scheduling problems and we present a review of the scheduling problems with unavailability periods.Then, we consider a general model for scheduling jobs on single-machine and unrelated parallel-machines with maintenance interventions. A unified approach is presented to solve this model as an assignment problem. A large number of performance criteria and maintenance models can be treated in this way, thus providing access to models that have often been studied separately in the published literature.Finally, we focus on the problem of a two-machine flow-shop makespan scheduling with the deteriorating maintenance period on the second machine. Then, we establish some conditions of the optimal schedule. In order to solve the problem, we proposed different exact methods: enumerative method, mixed-integer programming (MIP) model and a branch & bound algorithm. Numerical experiments are reported for all the proposed methods.