Nombre d'applications ont pour comportement principal l'attente d'un événement venant d'un environnement extérieur, la préparation d'un résultat et l'exécution d'actions sur cet environnement. Les interfaces graphiques et les systèmes avioniques en sont des exemples. Le paradigme SCC, pour Sense--Compute--Control, est particulièrement adapté à la description de ces applications. Le développement d'applications suivant ce paradigme est cependant rendu difficile par le manque de cadre conceptuel et d'outils de support. Cette thèse propose un cadre conceptuel dédié au paradigme SCC et se concrétise par un langage de description d'architectures nommé DiaSpec. Ce langage fournit un cadre de travail pour guider le développement d'une application SCC en assignant des rôles aux membres du projet et en proposant une séparation des préoccupations. En plus de fournir un cadre de conception, cette thèse fournit un support de programmation. En effet, à partir de descriptions écrites en DiaSpec, un framework de programmation dédié est généré dans un langage cible. Ce framework de programmation guide l'implémentation d'une application SCC en exposant les mêmes abstractions que le langage DiaSpec. Ce framework de programmation est conçu de façon à assurer que l'implémentation d'une application est conforme à l'architecture décrite en DiaSpec, en s'appuyant sur le système de types du langage cible. Les contributions de cette thèse sont évaluées suivant des critères d'expressivité, d'utilisabilité et de productivité.

Pruesse et Ruskey ont présenté un algorithme pour la génération de leur code Gray pour les idéaux d'un poset (ensemble partiellement ordonné) où deux idéaux adjacents diffèrent par un ou deux éléments. Leur algorithme fonctionne en temps amorti de O(n) par idéal. Squire a présenté une récurrence pour les idéaux d'un poset qui lui a permis de trouver un algorithme pour générer ces idéaux en temps amorti de O(log n) par idéal, mais pas en code Gray. Nous utilisons la récurrence de Squire pour trouver un code Gray pour les idéaux d'un poset, où deux idéaux adjacents diffèrent par un ou deux éléments. Dans le pire des cas, notre algorithme a la même complexité que celle de l'algorithme de Pruesse et Ruskey et dans les autres cas, sa complexité est meilleure que celle de leur algorithme et se rapproche de celle de l'algorithme de Squire. Squire a donné une condition pour obtenir cette complexité. Nous avons trouvé une condition moins restrictive que la sienne. Cette condition nous a permis d'améliorer la complexité de notre algorithme. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poset, Extension linéaire, Cycle hamiltonien, Code Gray, Algorithme, Complexité.

Dans cette thèse, nous présentons des développements de l'approche utilisée dans l'équipe « ParSys » du LRI pour traduire automatiquement des codes scientifiques écrits dans un langage dédié inspiré de Matlab en codes de production haute performance. Pour garantir cette performance, nous mettons à profit d'une part la méta-programmation par templates C++ afin d'analyser chaque expression pour détecter les opportunités de parallélisme, et d'autre part la programmation parallèle asynchrone pour utiliser au mieux les ressources disponibles des machines multi-cœurs. Pour faire le lien entre ces deux étapes du processus de génération de code, des squelettes algorithmiques multi-niveaux sont implémentés. Nos outils ont été implantés dans la bibliothèque NT2 et évalués sur des applications scientifiques du monde réel. / In this thesis, we present developments to the approach used by the LRI Parsys team to automatically translate MATLAB-like scientific codes into high performance production codes. To reach a high level of performance, we have combined C++ template meta-programming and asynchronous parallel programming to analyze each expression and detect parallelism opportunities first, and then to ensure near-optimal use of the available resources of multi-core machines. To link these two stages of the code generation process, we have implemented a solution based on multi-level algorithmic skeletons. We have implemented our tools in the NT2 library and evaluated them with several significant scientific benchmarks.

Nombre d'applications ont pour comportement principal l'attente d'un événement venant d'un environnement extérieur, la préparation d'un résultat et l'exécution d'actions sur cet environnement. Les interfaces graphiques et les systèmes avioniques en sont des exemples. Le paradigme SCC, pour sense-compute-control, est particulièrement adapté à la description de ces applications. Le développement d'applications suivant ce paradigme est complexe à cause du manque de cadre conceptuel et d'outils de support.Cette thèse propose un cadre conceptuel dédié au paradigme SCC et se concrétise par un langage de description d'architectures. À partir d'une description dans ce langage, un framework de programmation peut être généré. Il guide l'implémentation d'une application grâce à un support dédié et vérifie que cette implémentation est conforme à l'architecture décrite. Les contributions de cette thèse sont évaluées suivant des critères d'expressivité, d'utilisabilité et de productivité. / Numerous applications have, as their main behavior, to wait for information coming from a foreign environment, to prepare a result, and to execute actions on this environment. Graphical user interfaces and avionic systems are two examples. The SCC paradigm, for Sense–Compute–Control, is dedicated to the description of such applications. Developing applications with this paradigm is made difficult by the lack of conceptual framework and tool support.This thesis proposes a conceptual framework dedicated to the SCC paradigm which is materialized by an architecture description language named DiaSpec. This language provides a framework to support the development of an SCC application, assigning roles to the stakeholders and providing separation of concerns. This thesis also proposes dedicated programming support. Indeed, from DiaSpec descriptions a dedicated programming framework is generated in a target language. This programming framework guides the implementation of an SCC application and raises the level of abstraction of this implementation with both high-level and dedicated mechanisms. This programming framework is designed to ensure conformance of the implementation to its architecture described in DiaSpec by leveraging the target language type system. Contributions of this thesis are evaluated through three criteria: expressiveness, usability and productivity.

Malgré des progrès récents, développer une application d'informatique ubiquitaire reste un défi à cause d'un manque de canevas conceptuels et d'outils aidant au développement. Ce défi implique de prendre en charge des objets communicants hétérogènes, de surmonter la complexité des technologies de systèmes distribués, de définir l'architecture d'une application, et d'encoder cela dans un programme. De plus, tester des applications d'informatique ubiquitaire est problématique car cela implique d'acquérir, de tester et d'interfacer une variété d'entités logicielles et matérielles. Ce procédé peut rapidement devenir coûteux en argent et en temps lorsque l'environment ciblé implique de nombreuses entités.Cette thèse propose une méthodologie outillée pour développer et tester des applications d'informatique ubiquitaire. Notre méthodologie fournit tout d'abord le langage de conception DiaSpec. Ce langage permet de définir une taxonomie d'entités spécifiques à un domaine applicatif, s'abstrayant ainsi de leur hétérogénéité. Ce langage inclut également une couche permettant de définir l'architecture d'une application. Notre suite outillée fournit un compilateur qui, à partir de descriptions DiaSpec, génère un canevas de programmation guidant les phases d'implémentation et de test. Afin d'aider à la phase de test, nous proposons une approche de simulation et un outil intégré dans notre méthodologie outillée : l'outil DiaSim. Notre approche utilise le support de test généré par DiaSpec pour tester les applications de manière transparente dans un environnement physique simulé. La simulation d'une application est rendue graphiquement dans un outil de visualisation 2D.Nous avons combiné DiaSim avec un langage dédié permettant de décrire les phénomènes physiques en tant qu'équations différentielles. Cette combinaison nous permet une simulation réaliste des applications d'informatique ubiquitaire. DiaSim a été utilisé pour simuler des applications dans des domaines applicatifs variés. Notre approche de simulation a également été appliquée à un système avionique, démontrant la généralité de notre approche de simulation. / Despite much progress, developing a pervasive computing application remains a challenge because of a lack of conceptual frameworks and supporting tools. This challenge involves coping with heterogeneous devices, overcoming the intricacies of distributed systems technologies, working out an architecture for the application, and encoding it into a program. Moreover, testing pervasive computing applications is problematic because it requires acquiring, testing and interfacing a variety of software and hardware entities. This process can rapidly become costly and time-consuming when the target environment involves many entities.This thesis proposes a tool-based methodology for developing and testing pervasive computing applications. Our methodology first provides the DiaSpec design language that allows to define a taxonomy of area-specific building-blocks, abstracting over their heterogeneity. This language also includes a layer to define the architecture of an application. Our tool suite includes a compiler that takes DiaSpec design artifacts as input and generates a programming framework that supports the implementation and testing stages.To address the testing phase, we propose an approach and a tool integrated in our tool-based methodology, namely DiaSim. Our approach uses the testing support generated by DiaSpec to transparently test applications in a simulated physical environment. The simulation of an application is rendered graphically in a 2D visualization tool.We combined DiaSim with a domain-specific language for describing physical environment phenomena as differential equations, allowing a physically-accurate testing. DiaSim has been used to simulate various pervasive computing systems in different application areas. Our simulation approach has also been applied to an avionics system, which demonstrates the generality of our parameterized simulation approach.

Dans les domaines critiques tels que l’avionique, le ferroviaire ou encore l’automobile, il faut, afin de pouvoir certifier un système, démontrer qu’il réalise la fonction pour laquelle il a été conçu, selon des exigences temporelles spécifiées. En effet, un rendu temporel trop long peut rendre des données erronées, et ainsi mettre en danger la sûreté des personnes. Aujourd’hui, la plupart des approches proposent d’assurer ces exigences de Qualité de service au niveau des couches basses, e.g., au travers d’une bande passante déterministe, d’allocation statique d’intervalles de temps, et d’un ordonnancement prédéfini. Ces contraintes assurent que les applications ne peuvent dépasser le temps d’exécution alloué ; les applications récupèrent de ce fait des exigences qui sont découplées de leur fonctionnalité. En revanche, il faut aussi pouvoir certifier des exigences temporelles spécifiques à une application. De là, les garanties au niveau des couches basses ne sont plus suffisantes. Il faudrait pouvoir prendre en compte ces exigences dès la phase de conception des applications. Aujourd’hui, la plupart des approches existant dans ce domaine se concentrent sur le support de QoS à des phases isolées du processus de développement logiciel, empêchant la traçabilité des exigences. Cette thèse propose une approche dirigée par la conception pour supporter les exigences de QoS tout au long du processus de développement logiciel, intégrée dans une méthodologie outillée, appelée DiaSuite. L’extension de QoS enrichit le langage de conception DiaSpec avec la capacité d’instancier les exigences de QoS sur les composants logiciels. Un support de surveillance à l’exécution de ces exigences temporelles est ensuite généré, directement à partir de la spécification. Cette thèse intègre uniformément les concepts temporels avec les concepts de gestion d’erreurs, au travers de la méthodologie DiaSuite, afin de proposer une couche de supervision qui puisse effectuer une reconfiguration applicative, dans le cas de violation de contrat de QoS. Les contributions de cette thèse sont évaluées au regard du respect des critères de cohérence et de conformité, illustrés au travers d’une étude de cas dans le domaine avionique. / In critical domains such as avionics, railways or automotive, to certify a system, it is required to demonstrate that it achieves its function, with respect to specified timing requirements. Indeed, longer-than-predicted function computing can make data erroneous, leading potentially to endanger people lives. Today, most approaches propose to ensure these Quality of Service requirements at platform level, e.g., through deterministic bandwidth, static time slots allocation and predefined scheduling. These constraints ensure applications can’t overpass allocated time slots; applications are then fed with requirements decoupled to their functionality. However, it shall be possible to certify timing requirements, dedicated to an application. Hence, guarantees at platform-level are not sufficient anymore. It should be possible to take into account these requirements from the stage of application design. Today, most of existing approaches in this domain, focus on supporting QoS at individual stages of the software development process, preventing requirements traceability. This thesis proposes a design-driven approach to supporting QoS throughout software development process, integrated in a tool-based methodology, namely DiaSuite. The QoS extension enriches the DiaSpec design language, with the capability to instantiate QoS requirements onto software components. A runtime execution support to monitoring these timing requirements, is then generated, directly from the specification. This thesis uniformly integrates timing concepts with error ones, around DiaSuite methodology, to propose a supervision layer that could lead to application reconfiguration in case of QoS contract violation. Contributions of this thesis are evaluated through respect of coherence and conformance critera, illustrated through a case study in avionics.

Le besoin constant de puissance de calcul a poussé les développeurs à concevoir de nouvelles architectures: les architectures parallèles. Le calcul scientifique dépend fortement des performances de ces dernières afin de fournir des résultats dans un temps optimal. Les applications scientifiques exécutées sur de tels systèmes doivent alors tirer partie des spécificités de ces nouvelles architectures pour être efficaces.Cette thèse présente une nouvelle approche pour la conception de logiciels embarquant des optimisations relatives aux architectures : l'approche AADEMRAL (Architecture Aware DEMRAL). Cette méthodologie a pour but de simplifier le développement de bibliothèques de calcul parallèle avec un support multi-Architectural grâce à une approche générique et générative.Cette nouvelle méthodologie est ensuite intégrée dans trois bibliothèques. La première d'entre elles, Boost.Dispatch, permet de concevoir des logiciels basés sur l'approche AADEMRAL. Boost.Dispatch est une bibliothèque C++fournissant une interface générique pour réaliser de la surcharge de fonction avisée de l'architecture sous-Jacente. Ensuite nous présentons deux bibliothèques C++ implémentées en tant que langages orientés domaine : Boost.SIMD et NT2. Leurs conceptions mettent en œuvre la méthodologie AADEMRAL et leurs implémentations sont basées sur Boost.Dispatch. Boost.SIMD propose une interface de haut niveau pour la programmation des unités vectorielles.NT2 se base sur une interface similaire à celle de Matlab et fournie un support pour les systèmes multi-Cœurs et les unités vectorielles. Enfin, nous validons les performances de ces deux outils ainsi que la robustesse de notre nouvelle approche en présentant une série de résultats obtenus sur des applications de référence. / The constant increasing need for computing power has pushed the development of parallel architectures. Scientific computing relies on the performance of such architectures to produce scientific results. Programming efficient applications that takes advantage of these computing systems remains a non trivial task. In this thesis, we present a new methodology to design architecture aware software: the AA-DEMRAL methodology. This methodology aims at simplifying the development of parallel programming tools with multi-Architectural support through a generic and generative approach. We then present three high level programming tools that rely on this approach. First, we introduce the Boost.Dispatch library that provides a way to develop software based on the AA-DEMRAL methodology. The Boost.Dispatch library is a C++ generic framework for architecture aware function dispatching. Then, we present two C++ template libraries implemented as Architecture Aware DSELs which assess the AA-DEMRAL methodology through the use of Boost.Dispatch: Boost.SIMD, that provides a high level API for SIMD extensions and NT2 , which propose a Matlab like interface with support for multi-Core and SIMD based systems. We assess the performance of these libraries and the validity of our new methodology through benchmarks.

Dans le domaine des plates-formes ouvertes, l’utilisation des cadriciels (frameworks) enrichis par des déclarations pour exprimer les permissions de l’application est de plus en plus répandue. Ceci est une réaction logique au fait qu’il y a une explosion d’adoption des appareils embarqués et mobiles. Leur omniprésence dans notre vie quotidienne engendre des craintes liées à la sécurité et à la vie privée, car l’usager partage de plus en plus ses données et ressources privées avec des tiers qui développent des applications auxquelles on n’a pas de raison de faire confiance. Malheureusement, la manière dont ces langages de spécification ainsi que ces cadres d’applications sont développés est généralement assez ad hoc et repose sur un domaine d’application et un langage de programmation fixes. De plus, ces cadriciels ne sont pas assez restrictifs pour régler le problème de la fuite de données privées et ne donnent souvent pas non plus assez d’informations à l’usager sur le comportement attendu de l’application. Cette thèse présente une méthodologie généraliste pour développer des cadriciels dirigés par des déclarations, qui cible un spectre large de langages de programmation. Nous montrons comment des langages de déclaration expressifs permettent de spécifier avec modularité les droits d’accès aux ressources ainsi que le flux de contrôle d’une telle application. Ces langages peuvent ensuite être compilés en un cadriciel garantissant à l’usager final le respect de ces permissions. Par rapport aux cadriciels existants, notre méthodologie permet de guider la personne qui développe des applications à partir des spécifications ainsi que d’informer l’usager final sur l’usage des ressources sensibles. Contrairement aux travaux existants, la méthodologie présentée dans cette thèse ne repose par sur un langage de programmation particulier. Nous montrons comment mettre en oeuvre de tels cadriciels dans un spectre de langages : des langages avec typage statique ou dynamique, et suivant le paradigme objet ou fonctionnel. L’efficacité de l’approche est montrée à travers des prototypes dans le domaine des applications mobiles dans deux langages très différents, à savoir Java et Racket, ce qui montre la généralité de notre approche. / In the domain of open platforms, it has become common to use application programming frameworks extended with declarations that express permissions of applications. This is a natural reaction to ever more widespread adoption of mobile and pervasive computing devices. Their wide adoption raises privacy and safety concerns for users, as a result of the increasing number of sensitive resources a user is sharing with non-certified third-party application developers. However, the approach to designing these declaration languages and the frameworks that enforce their requirements is often ad hoc, and limited to a specific combination of application domain and programming language. Moreover, most widely used frameworks fail to address serious privacy leaks, and, crucially, do not provide the user with insight into application behaviour. This dissertation presents a generalised methodology for developing declaration-driven frameworks in a wide spectrum of host programming languages. We show that rich declaration languages, which express modularity, resource permissions and application control flow, can be compiled into frameworks that provide strong guarantees to end users. Compared to other declaration-driven frameworks, our methodology provides guidance to the application developer based on the specifications, and clear insight to the end user regarding the use of their private resources. Contrary to previous work, the methodology we propose does not depend on a specific host language, or even on a specific programming paradigm. We demonstrate how to implement declaration-driven frameworks in languages with static type systems, completely dynamic languages, object-oriented languages, or functional languages. The efficacy of our approach is shown through prototypes in the domain of mobile computing, implemented in two widely differing host programming languages, demonstrating the generality of our approach.

Notre environnement est de plus en plus peuplé de grandes quantités d’objets intelligents. Certains surveillent des places de stationnement disponibles, d’autres analysent les conditions matérielles dans les bâtiments ou détectent des niveaux de pollution dangereux dans les villes. Les quantités massives de capteurs et d’actionneurs constituent des infrastructures de grande envergure qui s’étendent sur des terrains de stationnement entiers, des campus comprenant plusieurs bâtiments ou des champs agricoles. Le développement d’applications pour de telles infrastructures reste difficile, malgré des déploiement réussis dans un certain nombre de domaines. Une connaissance considérable des spécificités matériel / réseau de l’infrastructure de capteurs est requise de la part du développeur. Pour remédier à ce problème, des méthodologies et des outils de développement logiciel permettant de relever le niveau d’abstraction doivent être introduits pour que des développeurs non spécialisés puissent programmer les applications. Cette thèse présente une méthodologie dirigée par la conception pour le développement d’applications orchestrant des quantités massives d’objets communicants. La méthodologie est basée sur un langage de conception dédié, nommé DiaSwarm qui fournit des constructions déclaratives de haut niveau permettant aux développeurs de traiter des masses d’objets en phase de conception, avant de programmer l’application. La programmation générative est utilisée pour produire des cadres de programmation spécifiques à la conception pour guider et soutenir le développement d’applications dans ce domaine. La méthodologie intègre le traitement parallèle de grandes quantités de données collectées à partir de masses de capteurs. Nous introduisons un langage de déclarations permettant de générer des cadres de programmation basés sur le modèle de programmation MapReduce. En outre, nous étudions comment la conception peut être utilisée pour rendre explicites les ressources requises par les applications ainsi que leur utilisation. Pour faire correspondre les exigences de l’application à une infrastructure de capteurs cible, nous considérons les déclarations de conception à différents stades du cycle de vie des applications. Le passage à l’échelle de cette approche est évaluée dans une expérience qui montre comment les cadres de programmation générés s’appuyant sur le modèle de programmation MapReduce sont utilisés pour le traitement efficace de grands ensembles de données de relevés des capteurs. Nous examinons l’efficacité de l’approche proposée pour relever les principaux défis du génie logiciel dans ce domaine en mettant en oeuvre des scénarios d’application qui nous sont fournis par des partenaires industriels. Nous avons sollicité des programmeurs professionnels pour évaluer l’utilisabilité de notre approche et présenter des données quantitatives et qualitatives de l’expérience. / Our environment is increasingly populated with large amounts of smart objects. Some monitor free parking spaces, others analyze material conditions in buildings or detect unsafe pollution levels in cities. The massive amounts of sensing and actuation devices constitute large-scale infrastructures that span over entire parking lots, campuses of buildings or agricultural fields. Despite being successfully deployed in a number of domains, the development of applications for such infrastructures remains challenging. Considerable knowledge about the hardware/network specificities of the sensor infrastructure is required on the part of the developer. To address this problem, software development methodologies and tools raising the level of abstraction need to be introduced to allow non-expert developers program applications. This dissertation presents a design-driven methodology for the development of applications orchestrating massive amounts of networked objects. The methodology is based on a domain-specific design language, named DiaSwarm that provides high-level, declarative constructs allowing developers to deal with masses of objects at design time, prior to programming the application. Generative programming is used to produce design-specific programming frameworks to guide and support the development of applications in this domain. The methodology integrates the parallel processing of large-amounts of data collected from masses of sensors. We introduce specific language declarations resulting in the generation of programming frameworks based on the MapReduce programming model. We furthermore investigate how design can be used to make explicit the resources required by applications as well as their usage. To match the application requirements to a target sensor infrastructure, we consider design declarations at different stages of the application lifecycle. The scalability of this approach is evaluated in an experiment, which shows how the generated programming frameworks relying on the MapReduce programming model are used for the efficient processing of large datasets of sensor readings. We examine the effectiveness of the proposed approach in dealing with key software engineering challenges in this domain by implementing application scenarios provided to us by industrial partners. We solicited professional programmers to evaluate the usability of our approach and present quantitative and qualitative data from the experiment.

Avec l'émergence d'Internet et la prolifération de nouvelles technologies, la conception et le développement d'applications complexes doivent impérativement prendre en compte les standards et les aspects de répartition, déploiement et réutilisation de code. C'est la source d'une nouvelle problématique liée à la programmation. Un changement radical des méthodologies est nécessaire pour aisément prendre en compte ces différentes facettes. Cette thèse jette les bases d'une nouvelle manière de programmer où ces facettes ou intentions sont automatiquement intégrées aux spécifications ou modèles abstraits de l'application lors de phases de génération de code source. Cette nouvelle programmation est dit générative. Cette idée a été appliquée, à différents niveaux, lors de la réalisation d'une application, aussi bien pour la représentation de données ou d'environnements interactifs que pour les traitements sémantiques ou l'architecture. Ainsi le code final obtenu après génération s'appuie sur les technologies XML pour la représentation des données, les technologies objets et beans pour les vues et l'interface utilisateur, la programmation par aspect et le patron de conception visiteur pour les traitements sémantiques et la programmation par composants pour une architecture ouverte et une application répartie et déployable. Les principaux gains d'une telle programmation sont une meilleure qualité du logiciel due à la séparation de la logique métier et des spécificités technologiques, une simplification du code métier à écrire, l'ajout rapide de nouvelles facettes et un portage vers d'autres plates-formes ou technologies facilité.