Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les systèmes distribués sont au coeur des technologies de l'information.Il est devenu classique de s'appuyer sur multiples unités distribuées pour améliorer la performance d'une application, la tolérance aux pannes, ou pour traiter problèmes dépassant les capacités d'une seule unité de traitement. La conception d'algorithmes adaptés au contexte distribué est particulièrement difficile en raison de l'asynchronisme et du non-déterminisme qui caractérisent ces systèmes. La simulation offre la possibilité d'étudier les performances des applications distribuées sans la complexité et le coût des plates-formes d'exécution réelles. Par ailleurs, le model checking permet d'évaluer la correction de ces systèmes de manière entièrement automatique. Dans cette thèse, nous explorons l'idée d'intégrer au sein d'un même outil un model checker et un simulateur de systèmes distribués. Nous souhaitons ainsi pouvoir évaluer la performance et la correction des applications distribuées. Pour faire face au problème de l'explosion combinatoire des états, nous présentons un algorithme de réduction dynamique par ordre partiel (DPOR), qui effectue une exploration basée sur un ensemble réduit de primitives de réseau. Cette approche permet de vérifier les programmes écrits avec n'importe laquelle des interfaces de communication proposées par le simulateur. Nous avons pour cela développé une spécification formelle complète de la sémantique de ces primitives réseau qui permet de raisonner sur l'indépendance des actions de communication nécessaire à la DPOR. Nous montrons au travers de résultats expérimentaux que notre approche est capable de traiter des programmes C non triviaux et non modifiés, écrits pour le simulateur SimGrid. Par ailleurs, nous proposons une solution au problème du passage à l'échelle des simulations limitées pour le CPU, ce qui permet d'envisager la simulation d'applications pair-à-pair comportant plusieurs millions de noeuds. Contrairement aux approches classiques de parallélisation, nous proposons une parallélisation des étapes internes de la simulation, tout en gardant l'ensemble du processus séquentiel. Nous présentons une analyse de la complexité de l'algorithme de simulation parallèle, et nous la comparons à l'algorithme classique séquentiel pour obtenir un critère qui caractérise les situations où un gain de performances peut être attendu avec notre approche. Un résultat important est l'observation de la relation entre la précision numérique des modèles utilisés pour simuler les ressources matérielles, avec le degré potentiel de parallélisation atteignables avec cette approche. Nous présentons plusieurs cas d'étude bénéficiant de la simulation parallèle, et nous détaillons les résultats d'une simulation à une échelle sans précédent du protocole pair-à-pair Chord avec deux millions de noeuds, exécutée sur une seule machine avec un modèle précis du réseau / Distributed systems are in the mainstream of information technology. It has become standard to rely on multiple distributed units to improve the performance of the application, help tolerate component failures, or handle problems too large to fit in a single processing unit. The design of algorithms adapted to the distributed context is particularly difficult due to the asynchrony and the nondeterminism that characterize distributed systems. Simulation offers the ability to study the performance of distributed applications without the complexity and cost of the real execution platforms. On the other hand, model checking allows to assess the correctness of such systems in a fully automatic manner. In this thesis, we explore the idea of integrating a model checker with a simulator for distributed systems in a single framework to gain performance and correctness assessment capabilities. To deal with the state explosion problem, we present a dynamic partial order reduction algorithm that performs the exploration based on a reduced set of networking primitives, that allows to verify programs written for any of the communication APIs offered by the simulator. This is only possible after the development of a full formal specification with the semantics of these networking primitives, that allows to reason about the independency of the communication actions as required by the DPOR algorithm. We show through experimental results that our approach is capable of dealing with non trivial unmodified C programs written for the SimGrid simulator. Moreover, we propose a solution to the problem of scalability for CPU bound simulations, envisioning the simulation of Peer-to-Peer applications with millions of participating nodes. Contrary to classical parallelization approaches, we propose parallelizing some internal steps of the simulation, while keeping the whole process sequential. We present a complexity analysis of the simulation algorithm, and we compare it to the classical sequential algorithm to obtain a criteria that describes in what situations a speed up can be expected. An important result is the observation of the relation between the precision of the models used to simulate the hardware resources, and the potential degree of parallelization attainable with this approach. We present several case studies that benefit from the parallel simulation, and we show the results of a simulation at unprecedented scale of the Chord Peer-to-Peer protocol with two millions nodes executed in a single machine

Le volume des données ne cesse de croître. À tel point qu'on parle aujourd'hui de "Big Data". La principale raison se trouve dans les progrès des outils informatique qui ont offert une grande flexibilité pour produire, mais aussi pour stocker des quantités toujours plus grandes. Les méthodes d'analyse de données ont toujours été confrontées à des quantités qui mettent en difficulté les capacités de traitement, ou qui les dépassent. Pour franchir les verrous technologiques associés à ces questions d'analyse, la communauté peut se tourner vers les techniques de calcul distribué. En particulier, l'extraction de motifs, qui est un des problèmes les plus abordés en fouille de données, présente encore souvent de grandes difficultés dans le contexte de la distribution massive et du parallélisme. Dans cette thèse, nous abordons deux sujets majeurs liés à l'extraction de motifs : les motifs fréquents, et les motifs informatifs (i.e., de forte entropie). / Le volume des données ne cesse de croître. À tel point qu'on parle aujourd'hui de "Big Data". La principale raison se trouve dans les progrès des outils informatique qui ont offert une grande flexibilité pour produire, mais aussi pour stocker des quantités toujours plus grandes.à l'extraction de motifs : les motifs fréquents, et les motifs informatifs (i.e., de forte entropie).

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques. / Comparative genomics is essentially a form of data mining in large collections of n-ary relations between genomic elements. Increases in the number of sequenced genomes create a stress on comparative genomics that grows, at worse geometrically, for every increase in sequence data. Even modestly-sized labs now routinely obtain several genomes at a time, and like large consortiums expect to be able to perform all-against-all analyses as part of these new multi-genome strategies. In order to address the needs at all levels it is necessary to rethink the algorithmic frameworks and data storage technologies used for comparative genomics.To meet these challenges of scale, in this thesis we develop novel methods based on NoSQL and MapReduce technologies. Using a characterization of the kinds of data used in comparative genomics, and a study of usage patterns for their analysis, we define a practical formalism for genomic Big Data, implement it using the Cassandra NoSQL platform, and evaluate its performance. Furthermore, using two quite different global analyses in comparative genomics, we define two strategies for adapting these applications to the MapReduce paradigm and derive new algorithms. For the first, identifying gene fusion and fission events in phylogenies, we reformulate the problem as a bounded parallel traversal that avoids high-latency graph-based algorithms. For the second, consensus clustering to identify protein families, we define an iterative sampling procedure that quickly converges to the desired global result. For both of these new algorithms, we implement each in the Hadoop MapReduce platform, and evaluate their performance. The performance is competitive and scales much better than existing solutions, but requires particular (and future) effort in devising specific algorithms.

En informatique ubiquitaire, l'observation du monde physique et de son "contexte" (une représentation haut niveau de la situation physique) est essentielle. Il existe de nombreux moyens pour observer le contexte. Typiquement, cela consiste en un traitement en plusieurs étapes commençant par la récupération de données brutes issues de capteurs. Diverses technologies de capteurs sont utilisées pour la récupération d'informations de bas niveau sur les activités physiques en cours. Ces données sont ensuite rassemblées, analysées et traitées ailleurs dans les systèmes d'information afin d'offrir une reconnaissance de contexte. Les applications déployées réagissent alors en fonction du contexte/de la situation détecté(e). Parmis les capteurs utilisés, les tags RFID, une technologie émergente, permettent de créer un lien virtuel direct entre les objets physiques et les systèmes d'information. En plus de stocker des identifiants, ils offrent un espace mémoire générique aux objets auxquels ils sont attachés, offrant de nouvelles possibilités d'architectures en informatique omniprésente. Dans cette thèse, nous proposons une approche originale tirant parti de l'espace mémoire offerts aux objets réels par les tags RFID. Dans notre approche, les objets supportent directement le système d'information. Ce type d'intégration permet de réduire les communications requises par le traitement à distance. Pour ce faire, des données sémantiques sont tout d'abord attachées aux objets afin de les rendre auto-descriptifs. Ainsi, les données pertinentes concernant une entité physique sont directement disponibles pour un traitement local. Les objets peuvent ensuite être liés virtuellement grâce à des structures de données dédiées ou ad hoc et distribuées sur les objets eux-mêmes. Ce faisant, le traitement des données peut se faire de façon directe. Par exemple, certaines propriétés peuvent être vérifiées localement sur un ensemble d'objets. Une relation physique peut être déduite directement de la structure de données, d'où le nom de "structures de données tangibles". Vis-à-vis des approches conventionnelles tirant parti des identifiants, notre approche offrent des avantages en termes de vie privée, de mise à l'échelle, d'autonomie et d'indépendance vis-à-vis des infrastructures. Le défi se situe au niveau de son expressivité limitée à cause du faible espace mémoire disponible sur les tags RFID. Les principes sont validés dans deux prototypes aux applications différentes. Le premier prototype est développé dans le domaine de la gestion de déchets afin d'aider le tri et d'améliorer le recyclage. Le deuxième offre des services supplémentaires, tels qu'une assistance lors du montage et de la vérification d'objets composés de plusieurs parties, grâce aux structures de données distribuées sur les différentes parties. / Pervasive computing or ambient computing aims to integrate information systems into the environment, in a manner as transparent as possible to the users. It allows the information systems to be tightly coupled with the physical activities within the environment. Everyday used objects, along with their environment, are made smarter with the use of embedded computing, sensors etc. and also have the ability to communicate among themselves. In pervasive computing, it is necessary to sense the real physical world and to perceive its “context” ; a high level representation of the physical situation. There are various ways to derive the context. Typically, the approach is a multi-step process which begins with sensing. Various sensing technologies are used to capture low level information of the physical activities, which are then aggregated, analyzed and computed elsewhere in the information systems, to become aware of the context. Deployed applications then react, depending on the context situation. Among sensors, RFID is an important emerging technology which allows a direct digital link between information systems and physical objects. Besides storing identification data, RFID also provides a general purpose storage space on objects, enabling new architectures for pervasive computing. In this thesis, we defend an original approach adopting the later use of RFID i.e. a digital memory integrated to real objects. The approach uses the principle where the objects self-support information systems. This way of integration reduces the need of communication for remote processing. The principle is realized in two ways. First, objects are piggybacked with semantic information, related to itself ; as self-describing objects. Hence, relevant information associated with the physical entities are readily available locally for processing. Second, group of related objects are digitally linked using dedicated or ad-hoc data structure, distributed over the objects. Hence, it would allow direct data processing - like validating some property involving the objects in proximity. This property of physical relation among objects can be interpreted digitally from the data structure ; this justifies the appellation “Tangible Data Structures”. Unlike the conventional method of using identifiers, our approach has arguments on its benefits in terms of privacy, scalability, autonomy and reduced dependency with respect to infrastructure. But its challenge lies in the expressivity due to limited memory space available in the tags. The principles are validated by prototyping in two different application domains. The first application is developed for waste management domain that helps in efficient sorting and better recycling. And the second, provides added services like assistance while assembling and verification for composite objects, using the distributed data structure across the individual pieces.

Offrir un accès transparent et sécurisé à un ensemble de ressources passe par la définition de logiciels de médiation qui rendent la complexité de l'architecture sous-jacente transparente à l'utilisateur en offrant des facilités de conception, d'intégration, d'interrogation et d'administration permettant le partage de données et de programmes d'une manière fiable et efficace. Un très gros effort a été mené ces vingt dernières années pour aider à la mise en œuvre de ces logiciels de médiation, que cela soit par la communauté bases de données ou par la communauté systèmes distribués. Ces deux communautés adressent différemment le problème de l'accès transparent et sécurisé à des ressources largement distribuées, il est donc important aujourd'hui de comprendre la variabilité des solutions en termes de fonctionnalités, de design, d'algorithmes et d'architectures afin d'identifier les différentes dimensions du problème. <br />Ce mémoire retrace l'ensemble de mes activés de recherche réalisées à partir de 1992 au sein du thème SBD (Systèmes et Bases de Données) du laboratoire PRISM de l'Université de Versailles-St-Quentin, et depuis 2002, dans le cadre du projet SMIS (Secure & Mobile Information System) à l'INRIA. Il détaille les aspects pluridisciplinaires de l'accès transparent aux données comme la conception et le développement de systèmes de médiation de données pour l'interopérabilité de bases de données relationnelles, objets et XML, et la problématique d'accès aux données dans les systèmes à objets distribués à l'aide d'annuaires. Il aborde également la problématique d'accès sécurisé aux données, notamment dans un contexte XML. <br />Ce mémoire détaille l'ensemble de mes contributions scientifiques autour de ces trois thèmes, indique pour chacun d'eux le contexte historique de l'époque et le replace vis-à-vis de l'existant. Pour conclure, il liste un ensemble de perspectives et directions de recherche à la lueur de mon expérience pluridisciplinaire et du constat de l'adoption croissante de XML comme fondation technologique pour l'accès transparent et sécurisé aux données largement distribuées.

Ce manuscrit présente certains de mes travaux de recherche en matière de gestion de données, réalisés au sein de l'équipe bases de données STORM du laboratoire Logiciels, Systèmes, Réseaux de l'IMAG. Ils ont été effectués depuis 1995 (et jusqu'à 2003), année de ma prise de fonctions en tant que Maître de Conférences à l'Institut National Polytechnique (INP) de Grenoble, en poste à l'Ecole Nationale Supérieure d'Informatique et de Mathématiques Appliquées de Grenoble(ENSIMAG). Mes travaux concernent des aspects système --- gestion de cache et duplication de données, support transactionnels, parmi d'autres. Ils contribuent d'une part à l'extension des fonctions des SGBD et d'autre part à la conception de services séparés utilisables indépendamment d'un SGBD. Mon point de vue porte sur la diversification du panorama des architectures des systèmes de gestion de données. J'ai d'abord travaillé dans l'introduction de fonctions déductives et actives dans les SGBD pour ensuite m'orienter vers des solutions plus ouvertes, des intergiciels de gestion de données distribuées sur des unités fixes et mobiles.

Dans les environnements d'exécution parallèle, la régulation de charge (ou l'ordonnancement applicatif) est le module responsable du contrôle de l'exécution d'un programme sur les ressources de l'architecture distribuée (processeurs et modules mémoire). En pratique, le choix de la stratégie de régulation la plus performante dépend non seulement de l'application mais doit aussi être adapté en fonction de l'architecture cible. Dès lors, la portabilité d'un code ne peut être assurée que si l'on peut modifier cette stratégie. Dans cette thèse, nous proposons l'utilisation de la description dynamique du flot de données comme l'élément central permettant de séparer le code applicatif de la régulation de charge. Sur cette proposition est basée la construction d'un environnement logiciel, modulaire et générique, qui rend possible la modification ou l'ajustement de la stratégie de régulation de charge. La spécification de cet environnement repose sur l'identification des interfaces de la régulation avec d'une part l'application et d'autre part l'architecture. Cette identification, centrée sur l'exploration macroscopique du flot de données, est originale: nous montrons qu'elle étend d'autres systèmes classiques de régulation de charge. Enfin, la validation expérimentale de cet environnement est réalisée grâce à son intégration dans l'interface de programmation Athapascan-1 de l'environnement Athapascan, du projet APACHE. Différentes stratégies d'ordonnancement, statiques, dynamiques et hybrides, ont ainsi été implantés. Nous présentons les performances de quelques unes de ces stratégies appliquées à des programmes Athapascan-1 sur différentes architectures.

Les travaux de cette thèse s'intéressent aux problèmes de performance et de coût des architectures MPSoC à base de NoC, en tirant parti des possibilités offertes par les technologies d'intégration 3D. Plusieurs contributions originales sont proposées. Tout d'abord, une étude approfondie à propos des différentes granularités de partitionnement au sein des circuits 3D est réalisée. En se basant sur cette analyse, ce travail de thèse est orienté aux architectures 3D partitionnées au niveau des blocs macroscopiques. Ainsi, la contribution de l'intégration 3D est limitée aux interconnexions verticales inter-blocs. Afin d'améliorer les performances de ces interconnexions, une topologie hiérarchique de NoC est proposée pour diminuer la latence et augmenter le débit des communications au sein des architectures 3D partitionnées au niveau des macro-blocs. D'autre part, un modèle au niveau du système est présenté pour évaluer et comparer les coûts des différentes options technologiques de l'intégration 3D. Partant de cette évaluation, nous proposons une architecture multiprocesseur reconfigurable empilable pour les applications de télécommunication 4G, en tenant compte des problèmes de coût.