Analysis of storage system workloads is important for a number of reasons. The analysis might be performed to understand the usage patterns of existing storage systems. It is very important for the architects to understand the usage patterns when designing and developing a new, or improving upon the existing design of a storage system. It is also important for a system administrator to understand the usage patterns when configuring and tuning a storage system. The analysis might also be performed to determine the relationship between any two given workloads. Before a decision is taken to pool storage resources to increase the throughput, there is need to establish whether the different workloads involved are correlated or not. Furthermore, the analysis of storage system workloads can be done to monitor the usage and to understand the storage requirements and behavior of system and application software. Another very important reason for analyzing storage system workloads, is the need to come up with correct workload models for storage system evaluation. For the evaluation, based on simulations or otherwise, to be reliable, one has to analyze, understand and correctly model the workloads. In our work we have developed a general tool, called ESSWA (Enterprize Storage System Workload Analyzer) for analyzing storage system workloads, which has a number of advantages over other storage system workload analyzers described in literature. Given a storage system workload in the form of an I/O trace file containing data for the workload parameters, ESSWA gives statistics of the data. From the statistics one can derive mathematical models in the form of probability distribution functions for the workload parameters. The statistics and mathematical models describe only the particular workload for which they are produced. This is because storage system workload characteristics are sensitive to the file system and buffer pool design and implementation, so that the results of any analysis are less broadly applicable. We experimented with ESSWA by analyzing storage system workloads represented by three sets of I/O traces at our disposal. Our results, among other things show that: I/O request sizes are influenced by the operating system in use; the start addresses of I/O requests are somewhat influenced by the application; and the exponential probability density function, which is often used in simulation of storage systems to generate inter-arrival times of I/O requests, is not the best model for that purpose in the workloads that we analyzed. We found the Weibull, lognormal and beta probability density functions to be better models.

Dans la dernière décennie, les grilles de calcul ont permis de réunir des ressources de stockage et de calcul de multiples institutions pour pourvoir à des applications scientifiques de grande ampleur. Par analogie aux grilles électriques, l'idée d'origine est de fournir de manière transparente de la capacité de calcul selon les besoins. Cependant, alors que les applications se multiplient, l'efficacité des mécanismes sous-jacents d'allocation de ressources mérite l'attention. Cette thèse présente les contributions suivantes. - Identification des patterns d'allocation de ressource, et comment ils ont évolué depuis les clusters isolés jusqu'aux grilles qui s'étendent sur plusieurs institutions autonomes. - Identification d'un pattern commun (Late Binding) dans la façon dont plusieurs applications contournent depuis peu le méccanisme habituel (Meta-scheduling) dans le but d'obtenir une mainmise accrue sur l'allocation de ressources et de palier à certains manques d'efficacité. - Proposition d'un nouveau pattern (Symmetric Mapping) qui permet d'obtenir la séparation du contrôle entre les fournisseurs et utilisateurs de ressources. - Proposition d'un nouveau modèle pour spécifier des stratégies d'allocation de ressource. Ce modèle permet de représenter l'allocation dynamique, ainsi que de multiples contraintes et objectifs. - Transposition du problème des Domaines Administratifs Multiples (MADs) du domaine de la tolérance aux fautes à celui du calcul distribué. Identification du problème MAD comme problème distinctif des grilles parmi les systèmes de calcul distribué. Identification de Symmetric Mapping comme une solution. - Proposition d'une implémentation de Symmetric Mapping basée sur les machines virtuelles, et dont l'un des éléments déploie et contrôle des multiples machines virtuelles à partir de descriptions déclaratives. - Proposition d'un système qui détecte la terminaison d'un service et relance tout service interrompu sur un serveur nouvellement sélectionné, afin de maintenir une implémentation de Symmetric Mapping, ou tout système qui nécessite des services permanents sur des serveurs transitoires. - Proposition d'une nouvelle méthode pour l'analyse des tâches et la prédiction de performance afin d'associer de manière dynamique des tâches aux serveurs adéquats. La méthode s'appuie sur l'estimation de patterns d'accès mémoire par des distributions de probabilité connues. La signature des tâches est réduite à une taille constante et la prédiction est effectuée en temps constant. - Proposition de la première évaluation du cache thrashing, afin de permettre des prédictions de performance réalistes pour les CPUs partagés par plusieurs processus. L'analyse est basée sur un nouveau modèle de Markov des caches LRU. Elle donne une borne supérieure et une borne inférieure de la proportion de fautes de caches en présence de processus concurrents.

Ce travail se place dans le contexte de la conception, la modélisation et la simulation de systèmes hétérogènes contenant a la fois des capteurs, des composants analogiques, des composants numériques et des circuits RF.La seule manière de simuler un système avec une telle complexité avec un temps de simulation raisonnable est de faire une modélisation haut niveau.Cependant, pour que ce modèle haut niveau soit fiable, les modèles des blocs analogiques et RF doivent contenir une description précise des leurs imperfections.Dans ce travail nous proposons une méthode systématique pour la caractérisation et le raffinement des modèles des blocs analogiques et RF.Cette méthode est réalisée dans un environnement C++ base sur: - l'outil de simulation haut niveau SystemC-AMS- l'outil de résolution d'expression symbolique GiNaC- l'outil de synthèse de circuits intégrés analogique CAIRO+/CHAMSPour illustrer la validité de la méthode proposée, nous présenterons le modèle d'un nœud d'un réseau de capteurs sans fil avec une caractérisation automatique de certains blocs analogiques et RF.Les points suivant résument les contributions apportées pour ce travail.- La première implémentation d'un modèle analogique numérique mixte complexe avec le langage SystemC AMS: un nœud de réseau de capteurs sans fil.- L'introduction du raffinement pour une approche générique des modèles au niveau système.- Un outil d'évaluation précise des performances linéaires et non-linéaires des circuit analogiques pour le raffinement des modèles niveau système et l'optimisation de la conception niveau circuit.- Une méthodologie de conception niveau circuit basée sur des outils de dimensionnement et d'évaluation des performances avec précision.- Un environnement de conception multi-niveaux unifiée appliqué aux systèmes mixtes avec une très forte interaction entre la simulation niveau système et la conception optimisée niveau circuit.

Cette thèse vise à la conception d'un environnement pour le calcul haute performance dans un cadre d'optimisation numérique. Les outils de conception et d'optimisation sont répartis dans plusieurs équipes distantes, académiques et industrielles, qui collaborent au sein des memes projets. Les outils doivent etre fédérésau sein d'un environnement commun afin d'en faciliter l'accès aux chercheurs et ingénieurs. L'environnement que nous proposons, pour répondre aux conditions précédentes, se compose d'un système de workflow et d'un système de calcul distribué. Le premier a pour objctif de faciliter la tache de conception tandis que le second se charge de l'exécution sur des ressources de calcul distribuées. Bien sur, des suystèmes de communication entre les deux systèmes doivent etre développés. Les calculs doivent etre réalisés de manière efficace, en prenant en compte le parallélisme interne de certains codes, l'exécution synchrone ou asynchrone des taches, le transfert des données et les ressources matérielles et logicielles disponibles. De plus, l'environnement doit assurer un bon niveau de tolérance aux pannes et aux défaillances logicielles, afin de minimiser leur influence sur le résultat final ou sur le temps de calcul. Une condition importante est de pouvoir implanter un dispositif de reprise sur erreur, de telle sorte que le temps supplémentaire de traitement des erreurs soit très inférieur au temps de ré-exécution total.Dans le cadre de ce travail, notyre choix s'est porté sur le moteur de workflow Yawl, qui présente de bonnes caractéristiques en termes i) d'indépendancze vis à vis du matériel et du logiciel et ii) de mécanisme de reprise sdur erreur. Pour la partie calcul distribué, nos expériences ont été réalisées sur la plateforme Grid5000, en utilisant 64 machines différentes réparties sur cinq sites géographiques. Ce document d&taille les choix de conception de cet environnement ainsi que les ajouts et modifications que nous avons apportées à Yawl pour lui permettre de fonctionner sur une plateforme distribuée.

>Magister Scientiae - MSc / This thesis validates that packet aggregation is a viable technique to increase call ca-pacity for Voice over Internet Protocol over wireless mesh networks. Wireless mesh networks are attractive ways to provide voice services to rural communities. Due to the ad-hoc routing nature of mesh networks, packet loss and delay can reduce voice quality.Even on non-mesh networks, voice quality is reduced by high overhead, associated with the transmission of multiple small packets. Packet aggregation techniques are proven to increase VoIP performance and thus can be deployed in wireless mesh networks. Kernel level packet aggregation was initially implemented and tested on a small mesh network of PCs running Linux, and standard baseline vs. aggregation tests were conducted with a realistic voice tra c pro le in hop-to-hop mode. Modi cations of the kernel were then transferred to either end of a nine node 'mesh potato' network and those tests were conducted with only the end nodes modi ed to perform aggregation duties. Packet ag- gregation increased call capacity expectedly, while quality of service was maintained in both instances, and hop-to-hop aggregation outperformed the end-to-end con guration. However, implementing hop-to-hop in a scalable fashion is prohibitive, due to the extensive kernel level debugging that must be done to achieve the call capacity increase.Therefore, end-to-end call capacity increase is an acceptable compromise for eventual scalable deployment of voice over wireless mesh networks.

Depuis l'A380 et avec l'introduction du standard ARINC 661, les systèmes d'affichage et de contrôle des cockpits sont passés d'un rôle de simple afficheur, à celui d'un système interactif permettant à l'équipage d'interagir sur les écrans grâce à l'utilisation d'un ensemble clavier/dispositif de pointage appelé KCCU. L'utilisation de cette nouvelle capacité d'interaction est à ce jour limitée à des interactions avec des systèmes avions non critiques. Pour envisager son extension à des systèmes critiques il faut se poser la question du respect d'exigences de sureté de fonctionnement imposées à de tels systèmes sans pour autant diminuer son niveau d'utilisabilité. Dans cette optique, nous proposons dans le cadre de nos travaux de recherche, différentes approches pour contribuer au développement d'un tel système interactif critique. La première approche est de tendre vers une conception zéro défaut, en réalisant une description précise et non ambigüe des composants logiciels du système interactif en utilisant une technique de description formelle. La seconde approche est l'utilisation de techniques de tolérance aux fautes car il existe toujours des fautes résiduelles de conception, des fautes matérielles ou venant de l'environnement. Dans ce cas, l'utilisation de technique de tolérance aux fautes permet au système de continuer à remplir ses fonctions en dépit de l'occurrence de fautes. La troisième approche est l'explicitation de l'impact des différentes approches de tolérance aux fautes sur l'utilisabilité du système interactif. Cette explicitation est faite au travers de la réalisation et de l'analyse des modèles de tâche, décrivant l'activité de l'utilisateur du système.

Les assistants de preuve basés sur des théories des types dépendants sont de plus en plus utilisé comme un outil pour développer programmes certifiés. Un exemple réussi est l'assistant de preuves Coq, fondé sur le Calcul des Constructions Inductives (CCI). Coq est un langage de programmation fonctionnel dont un expressif système de type qui permet de préciser et de démontrer des propriétés des programmes dans une logique d'ordre supérieur. Motivé par le succès de Coq et le désir d'améliorer sa facilité d'utilisation, dans cette thèse nous étudions certaines limitations des implémentations actuelles de Coq et sa théorie sous-jacente, CCI. Nous proposons deux extension de CCI que partiellement resourdre ces limitations et que on peut utiliser pour des futures implémentations de Coq. Nous étudions le problème de la terminaison des fonctions récursives. En Coq, la terminaison des fonctions récursives assure la cohérence de la logique sous-jacente. Les techniques actuelles assurant la terminaison de fonctions récursives sont fondées sur des critères syntaxiques et leurs limitations apparaissent souvent dans la pratique. Nous proposons une extension de CCI en utilisant un mécanisme basé sur les type pour assurer la terminaison des fonctions récursives. Notre principale contribution est une preuve de la normalisation forte et la cohérence logique de cette extension. Nous étudions les définitions par filtrage dans le CCI. Avec des types dépendants, il est possible d'écrire des définitions par filtrage plus précises, par rapport à des langages de programmation fonctionnels Haskell et ML. Basé sur le succès des langages de programmation avec types dépendants, comme Epigram et Agda, nous développons une extension du CCI avec des fonctions similaires.

Les machines multicœurs équipées d'accélérateurs deviennent de plus en plus populaires dans le domaine du Calcul Haute Performance. Les architectures hybrides réduisent la consommation énergétique de manière significative et sont donc amenées à se généraliser dans l'ère du manycœur. Cependant, la complexité induite par ces architectures a un impact direct sur leur programmabilité. Il est donc indispensable de fournir des abstractions portables afin de tirer pleinement parti de ces machines. Les approches qui consistent à exécuter une application sur des processeurs généralistes et à ne déporter que certaines parties prédéterminées du calcul sur des accélérateurs ne sont pas suffisantes. Le véritable défi consiste donc à concevoir des environnements où les applications sont réparties sur l'intégralité de la machine, c'est-à-dire où les différents calculs sont ordonnancés dynamiquement sur la totalité des unités de calcul disponibles. Dans cette thèse, nous proposons donc un nouveau modèle de support exécutif fondé sur une abstraction de tâche et spécifiquement conçu pour répondre aux nombreux défis en termes d'ordonnancement de tâches et de gestion de données. La plate-forme StarPU a été conçue lors de cette thèse afin de démontrer la pertinence de ce modèle. StarPU propose une interface expressive permettant d'accéder à un ordonnancement flexible, fortement couplé à une gestion de données efficace. À l'aide de cet environnement et en associant les différentes tâches avec des modèles de performance auto-calibrés, il devient par exemple très simple de concevoir des stratégies d'ordonnancement prenant en compte les temps de calcul et les surcoûts liés aux mouvements de données. Nous montrons que notre modèle fondé sur un paradigme de tâche est suffisamment puissant pour exploiter les grappes de calcul d'une part, et les architectures manycœurs hybrides d'autre part. Nous analysons les performances obtenues non seulement grâce à des tests synthétiques, mais aussi à l'aide d'applications réelles. Nous obtenons ainsi des accélérations substantielles, ainsi qu'une très bonne efficacité parallèle sur différents types de plates-formes multicœurs, dotées d'accélérateurs.

Depuis plusieurs années, le nombre de cœurs de calcul dans les processeurs ne cesse d'augmenter à chaque nouvelle génération. Les processeurs multi-cœurs sont maintenant très fréquents mais le développement de logiciels séquentiels reste une pratique très courante. Pour palier à ce problème, des outils de parallélisation automatique ont été proposés mais ils ne sont pas encore prêts pour une utilisation à grande échelle. Nous proposons d'étendre les outils existants dans trois directions différentes. Premièrement, on peut remarquer que le code source de certains programmes n'est pas disponible. Nous proposons donc un système de parallélisation statique de code binaire qui permet de paralléliser un application séquentielle déjà compilée. Ensuite, on peut s'apercevoir que la performance d'un programme dépend du contexte d'exécution dans lequel il s'exécute. Nous présentons donc un système qui permet de sélectionner une version d'un programme parmi plusieurs afin d'exploiter au mieux les particularités du contexte d'exécution courant. Enfin, étant donné que certains programmes sont difficiles à analyser statiquement, nous proposons un système de parallélisation spéculative permettant d'appliquer dynamiquement des transformations de code complexes sur ces programmes. Ces trois systèmes utilisent le modèles polyédrique comme une boîte à outil permettant d'analyser, de transformer ou de paralléliser les programmes. En travaillant à différentes phases de la vie des programmes, ils forment une approche globale qui étend les techniques de parallélisation existantes.

Cette thèse explore les possibilités algorithmiques offertes par la synthèse de haut niveau de circuits dans le cadre de la logique synchrone et à destination d'une Mémoire Active Programmable. Une chaîne de compilation expérimentale permettant de générer automatiquement un circuit reconfigurable à partir d'une spécification de haut niveau y est présentée. Le langage de haut niveau est DSL (Design Source Language). DSL est basé sur le langage fonctionnel Jazz. DSL permet de décrire tout type de circuit dans le modèle de la logique synchrone, d'en faire la simulation et la synthèse, puis de l'exécuter sur une Mémoire Active Programmable. Le compilateur procède par étapes successives pour synthétiser un circuit à partir de son code-source de haut niveau. Chacune des étapes de la compilation génère des annotations qui précisent les propriétés du circuit jusqu'à une forme synthétisable. Les annotations sont pour la plupart ajoutées automatiquement par le compilateur mais sont partie intégrante de la syntaxe de DSL et peuvent ainsi être précisées par le concepteur. DSL prend en charge la génération automatique de l'ensemble des routines systèmes qui permettent au circuit de communiquer avec son hôte. Ce système de prototypage et d'accélération matérielle automatique sur PAM est testé sur des circuits variés, comme des algorithmes de tramage, d'estimation de mouvement et de détection des points de Harris.