Thesis (M.Sc.) - Carleton University, 2002. / Includes bibliographical references (p. 92-94). Also available in electronic format on the Internet.

<div>To leverage modern hardware platforms to their fullest, more and more database systems embrace compilation of query plans to native code. In the research community, there is an ongoing debate about the best way to architect such query compilers. This is perceived to be a difficult task, requiring techniques fundamentally different from traditional interpreted query execution. In this dissertation, we contribute to this discussion by drawing attention to an old but underappreciated idea known as Futamura projections, which fundamentally link interpreters and compilers. Guided by this idea, we demonstrate that efficient query compilation can actually be very simple, using techniques that are no more difficult than writing a query interpreter in a high-level language. We first develop LB2: a high-level query compiler implemented in this style that is competitive with the best compiled query engines both in sequential and parallel execution on the standard TPC-H benchmark. </div><div><br></div><div>Query engines process a variety of data types and structures including text, spatial, graphs, etc. Several spatial and graph engines are implemented as extensions to relational query engines to leverage optimized memory, storage, and evaluation. Still, the performance of these extensions is often stymied by the interpretive nature of the underlying data management, generic data structures, and the need to execute domain-specific external libraries. On that basis, compiling spatial and graph queries to native code is a desirable avenue to mitigate existing limitations and improve performance. To support compiling spatial queries, we extend the LB2 main-memory query compiler with spatial predicates, indexing structures, and spatial operators. To support compiling graph queries, we extend LB2 with graph data structures and operators. The spatial extension matches the performance of hand-written code and outperforms relational query engines and map-reduce extensions. Similarly, the graph extension matches, and sometimes outperforms, low-level graph engines.</div>

Frames sind parametrisierte Elemente zur Erzeugung von Programmen in einer beliebigen Zielprogrammiersprache. Ihre Handhabung ist einfach und schnell zu erlernen. Allerdings findet bei Verwendung von Frames eine “Verunreinigung” des Programmcodes, der als Basis für die Generatorentwicklung dient, mit Befehlen der Generatorsprache statt. Dies erschwert die Weiterverwendung der gewohnten Entwicklungsumgebung für die Zielprogrammiersprache. Eine eventuelle Weiterentwicklung der Programmbasis muss anschließend in Form von Frames erfolgen. Im Rahmen dieser Arbeit erfolgt die Beschreibung noninvasiver Frames, bei denen Informationen zur Position der Frames getrennt vom Programmcode aufbewahrt werden. Ihre Vermischung erfolgt in einem separaten Schritt zur Darstellung oder zur eigentlichen Codeerzeugung. Der Prozess der Generatorentwicklung auf der Basis noninvasiver Frames passt sich gut in die Prozesse von Merkmal-orientierter (FOSD) und Generativer Softwareentwicklung (GSE) ein, weil noninvasive Frames die automatisierte Prüfung aller mit dem Generator erzeugbaren Programme hinsichtlich Syntax und bestimmter semantischer Eigenschaften unterstützen und die Generierung durch Auswahl der gewünschten Programmeigenschaften ermöglichen. Die Machbarkeit der Entwicklung von Softwaregeneratoren mit noninvasiven Frames wird anhand zweier Fallstudien demonstriert.

Thesis (Ph. D.)--University of Alabama at Birmingham, 2006. / Description based on contents viewed Jan. 26, 2007; title from title screen. Includes bibliographical references (p. 200-214).

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.

Modern distributed object systems pass remote parameters based on their runtime type. This design choice limits the expressiveness, readability, and maintainability of distributed applications. While a rich body of research is concerned with middleware extensibility, modern distributed object systems do not offer programming facilities to extend their remote parameter passing semantics. Thus, extending these semantics requires understanding and modifying the underlying middleware implementation. This thesis addresses these design shortcomings by presenting (i) a declarative and extensible approach to remote parameter passing that decouples parameter passing from parameter types, and (ii) a plugin-based framework, DeXteR, that enables the programmer to extend the native set of remote parameter passing semantics, without having to understand or modify the underlying middleware implementation. DeXteR treats remote parameter passing as a distributed cross-cutting concern. It uses generative and aspect-oriented techniques, enabling the implementation of different parameter passing semantics as reusable application-level plugins that work with application, system, and third-party library classes. The flexibility and expressiveness of the framework is validated by implementing several non-trivial parameter passing semantics as DeXteR plugins. The material presented in this thesis has been accepted for publication at the ACM/USENIX Middleware 2008 conference. / Master of Science

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.

Lors du développement des applications ubiquitaires, il est essentiel de définir des politiques de sécurité et de développerdes mécanismes de sécurité pour assurer la confidentialité et l’intégrité des applications. De nombreux langages de spécification de politiques se concentrent uniquement sur leur puissance d’expression. Les défis émergents dans les systèmes ubiquitaires ne peuvent pas être résolus par ces approches. Par exemple, la sensibilité au contexte est un élément central des systèmes ubiquitaires. Les approches existantes tiennent rarement compte des informations contextuelles dans leurs langages. Cette thèse propose une approche générative pour spécifier et implanter les politiques de sécurité dans les applications ubiquitaires. Pour définir une politique de sécurité, nous proposons un langage de spécification qui tient compte des informations contextuelles. Il permet aux développeurs de spécifier les règles de la politique et les entités requises (e.g. la description spatiale, les rôles, le contexte). Les politiques sont implémentés par des systèmes de réécriture, ce qui offre une grande puissance de vérification. Pour appliquer une politique, nous proposons une architecture qui intègre les concepts importants des politiques de sécurité (sujet, contexte, objet) dans des applications ubiquitaires. Pour mettre en oeuvre notre approche, nous avons enrichi une approche existante pour le développement des applications ubiquitaires. La spécification de la politique de sécurité et la description de l’application ubiquitaire enrichie sont utilisées pour générer un canevas de programmation qui facilite l’implémentation des mécanismes de sécurité, tout en séparant les aspects sécurités de la logique applicative. / When developing pervasive computing applications, it is critical to specify security policies and develop security mechanisms to ensure the confidentiality and integrity of the applications. Numerous policy specification languages only focus on their expressive power. The emerging challenges in pervasive computing systems can not be fulfilled by these approaches. For instance, context awareness is a central aspect of pervasive computing systems. Existing approaches rarely consider context information in their language.This thesis proposes a generative approach dedicated to specifying and enforcing security policies in pervasive computingapplications. To specify a policy, we propose a context-aware policy specification language which helps developers to specify policy rules and required entities (e.g. spatial description, roles, context information). Policies are implemented by term rewriting systems which offers great verification power. To enforce a policy, we propose an architecture that embeds important concepts of security policies (subject, object, security related context) into pervasive computing applications. To apply our approach, we enriched an existing approach which is dedicated to develop pervasive computing applications. Based on the policy specification and the enriched pervasive computing application descriptions, a dedicated programming framework is generated. This framework guides the implementation and raises the level of abstraction which can reduce the workloads of developers.

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.

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'environnement ciblé implique de nombreuses entités. Cette thèse propose une méthodologie outillée pour dévelop- per 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é permet- tant de décrire les phénomènes physiques en tant qu'équations différentielles, permettant des simulations réalistes. 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.