The development of controls for the execution of concurrent code is non-trivial. This work shows how existing discrete-event system (DES) theory can be successfully applied to this problem. From code without concurrency controls and a specification of desired behaviours, a DES representation of the problem is obtained, and then used to generate concurrency control code. By applying rigorously proven DES theory, the resulting code comes with guarantees not present in similar works. All control schemes generated in DES are nonblocking, yielding code that is free of both livelock and deadlock. Additionally, the generated control scheme is minimally restrictive, meaning only problematic behaviours are prevented. If the specifications cannot be enforced as presented, the largest controllable subset is instead enforced. The result, which requires no further interaction to generate, is the best possible control scheme given the interaction between the specifications and the original code. Existing methods encounter difficulties when faced with multiple specifications that interact to form deadlocks. Modular DES theory is successfully applied, allowing resolution of these conflicts without requiring the user to introduce new specifications. Moreover, the approach is independent of specific programming or specification languages. A Java implementation is given, along with two problems showing the process in action. / Thesis (Master, Computing) -- Queen's University, 2008-09-25 09:03:51.593

abstract: We are expecting hundreds of cores per chip in the near future. However, scaling the memory architecture in manycore architectures becomes a major challenge. Cache coherence provides a single image of memory at any time in execution to all the cores, yet coherent cache architectures are believed will not scale to hundreds and thousands of cores. In addition, caches and coherence logic already take 20-50% of the total power consumption of the processor and 30-60% of die area. Therefore, a more scalable architecture is needed for manycore architectures. Software Managed Manycore (SMM) architectures emerge as a solution. They have scalable memory design in which each core has direct access to only its local scratchpad memory, and any data transfers to/from other memories must be done explicitly in the application using Direct Memory Access (DMA) commands. Lack of automatic memory management in the hardware makes such architectures extremely power-efficient, but they also become difficult to program. If the code/data of the task mapped onto a core cannot fit in the local scratchpad memory, then DMA calls must be added to bring in the code/data before it is required, and it may need to be evicted after its use. However, doing this adds a lot of complexity to the programmer's job. Now programmers must worry about data management, on top of worrying about the functional correctness of the program - which is already quite complex. This dissertation presents a comprehensive compiler and runtime integration to automatically manage the code and data of each task in the limited local memory of the core. We firstly developed a Complete Circular Stack Management. It manages stack frames between the local memory and the main memory, and addresses the stack pointer problem as well. Though it works, we found we could further optimize the management for most cases. Thus a Smart Stack Data Management (SSDM) is provided. In this work, we formulate the stack data management problem and propose a greedy algorithm for the same. Later on, we propose a general cost estimation algorithm, based on which CMSM heuristic for code mapping problem is developed. Finally, heap data is dynamic in nature and therefore it is hard to manage it. We provide two schemes to manage unlimited amount of heap data in constant sized region in the local memory. In addition to those separate schemes for different kinds of data, we also provide a memory partition methodology. / Dissertation/Thesis / Ph.D. Computer Science 2014

This thesis project will attempt to answer the question if it is possible to gain performance by using SIMD instructions when generating code for scalar computation. The current trend in processor architecture is to equip the processors with multi-way SIMD units to form so-called throughput cores. This project uses the CELL SPE processor for a concrete implementation. To get good code quality the thesis project continues work on the code generator by Mattias Eriksson and Andrzej Bednarski based on integer linear programming. The code generator is extended to handle generation of SIMD code for 32bit operands. The result show for some basic blocks, positive impact in execution time of the generated schedule. However, further work has to be done to get a feasable run time of the code generator.

<div>The availability of modern hardware with large amounts of memory created a shift in the development of data-centric software; from optimizing I/O operations to optimizing computation. As a result, the main challenge has become using the memory hierarchy (cache, RAM, distributed, etc) efficiently. In order to overcome this difficulty, programmers of data-centric programs need to use low-level APIs such as Pthreads or MPI to manually optimize their software because of the intrinsic difficulties and the low productivity of these APIs. Data-centric systems such as Apache Spark are becoming more and more popular. These kinds of systems offer a much simpler interface and allow programmers and scientists to write in a few lines what would have been thousands of lines of low-level MPI code. The core benefit of these systems comes from the introduction of deferred APIs; the code written by the programmer is actually building a graph representation of the computation that has to be executed. This graph can then be optimized and compiled to achieve higher performance.</div><div><br></div><div>In this dissertation, we analyze the limitations of current data-centric systems such as Apache Spark, on relational and heterogeneous workloads interacting with machine learning frameworks. We show that the compilation of queries in multiples stages and the interfacing with external systems is a key impediment to performance because of their inability to optimize across code boundaries. We present Flare, an accelerator for data-centric software, which provides performance comparable to the state of the art relational systems while keeping the expressiveness of high-level deferred APIs. Flare displays order of magnitude speed up on programs combining relational processing and machine learning frameworks such as TensorFlow. We look at the impact of compilation on short-running jobs and propose an on-stack-replacement mechanism for generative programming to decrease the overhead introduced by the compilation step. We show that this mechanism can also be used in a more generic way within source-to-source compilers. We develop a new kind of static analysis that allows the reverse engineering of legacy codes in order to optimize them with Flare. The novelty of the analysis is also useful for more generic problems such as formal verification of programs using dynamic allocation. We have implemented a prototype that successfully verifies programs within the SV-COMP benchmark suite.</div>

Nous nous sommes intéressés aux systèmes embarqués temps-réel critiques (SETRC) qui soulèvent des problématiques de criticité, de respect de contraintes temporelles et de disponibilité des ressources telles que la mémoire. Pour maîtriser la complexité de conception de ces systèmes, l’Ingénierie Dirigée par les Modèles (IDM) propose de les modéliser pour les analyser au regard de leurs exigences et pour générer en partie leur code d’exécution. Cependant ces deux phases doivent s’articuler correctement de sorte que le système généré respecte toujours les propriétés du modèle initialement analysé. Par ailleurs, le générateur de code doit s’adapter à de multiples critères : notamment pour assurer le respect des performances ou bien pour cibler différentes plates-formes d’exécution qui ont leurs propres contraintes et sémantiques d’exécution. Pour réaliser cette adaptation, le processus de développement requiert de faire évoluer les règles de transformation selon ces critères. Son architecture doit également de permettre de sélectionner les composants logiciels répondant à ces critères. Nous répondons à cette problématique en proposant un processus de génération s’appuyant sur l’IDM. Lorsque l’utilisateur a spécifié et validé un modèle de haut niveau, une transformation traduit automatiquement ce modèle en un second modèle détaillé proche du code généré. Pour assurer la conservation des exigences, le modèle détaillé est exprimé dans le même formalisme que le modèle initial de sorte qu’il reste analysable. Cette démarche détermine l’impact de la stratégie du générateur sur les performances du système final et permet au générateur de changer de stratégie, à une étape donnée, pour assurer le respect des contraintes du système. Pour faciliter le développement et la sélection de stratégies alternatives, nous proposons une méthodologie qui s’articule autour d’un formalisme pour l’orchestration des transformations, un ensemble de patrons de transformation (qui factorisent et généralisent les règles de transformation) et une adaptation de composants logiciels selon leur impact sur les performances. Nous avons mis en place ce processus au sein de l’environnement OSATE, pour lequel nous avons développé le framework RAMSES (Refinment of AADL Models for Synthesis of Embedded Systems). Nous l’avons expérimenté sur la génération des communications entre tâches pour lesquelles plusieurs stratégies d’implémentation ont été définies / We focused on real-time embedded critical systems (RTECS) which present different problems: criticality, respect of time constraints and resources availability such as memory. In order to master design complexity of such systems, Model Driven Engineering (MDE) proposes to model it for analysis purposes and to generate, partially or totally, its execution code. However, these two phases must be correctly connected to ensure the generated code is always enforcing all the properties of the model initially analysed. In addition, the code generator must be adapted to several criteria: in particular to ensure respect of performances or to target different execution platforms which have their own execution constraints and semantics. To realize such an adaptation, the development process requires to evolve transformation rules according to these criteria. Its architecture needs also to allow the selection of the generated software components respecting these criteria.We answer such a problem by proposing a generation process based on the MDE. When the user specifies and validates a high-level model, a model transformation translates automatically this model into a detailed model close to the generated code. To ensure the conservation of the requirements, the detailed model is expressed in the same formalism as the initial model so that it remains analysable (by the same tools initially used). This approach determines the impact of the code generation strategy on the performances of the final system and allows the generator to adapt its strategy, in a given stage, to insure the respect of the system constraints. To facilitate the development and the selection of alternative strategies, we propose a methodology which articulates around a formalism for the orchestration of the transformations, a set of transformation patterns (which factorize and generalize the transformation rules) and an adaptation of software components according to their impact on the performances. We set up this process within the environment OSATE, for which we have developed the framework RAMSES (Refinement of AADL Models for Synthesis of Embedded Systems). We have experimented it on the code generation of the communications between tasks for which several strategies of implementation were defined.

The expectations on embedded systems have grown incredibly in recent years. Not only are there more applications for them than ever, the applications are increasingly complex, and their security is essential. To meet such demanding goals, designers and programmers are always looking for more efficient methods of computation. One technique that has gained attention over the past couple of decades is bitsliced software. In addition to high efficiency in certain situations, including block ciphers computation, it has been used in designs to resist hardware attacks. However, this technique requires both program and data to be in a specific format. This requirement makes writing bitsliced software by hand laborious and adds computational overhead to transpose the data before and after computation. This work describes a code generation tool that produces it from a higher-level description in Verilog. By supporting the synthesis of sequential circuits, this tool extends bitsliced software to parallel synchronous software. This tool is then used to implement a method for accelerating software neural network processing with reduced-precision computation on highly constrained devices. To address the data transposition overhead and to support a hardware attack-resistant architecture, a custom DMA controller is introduced that efficiently transposes the data as it transfers along with dedicated hardware for masking and redundancy generation. In combination, these tools make bitsliced software and its benefits more accessible to system designers and programmers. / Master of Science / Small computers embedded in devices, such as cars, smart devices, and other electronics, face many challenges. Often, they are pushed to their limits by designers and programmers to reach acceptable levels of performance. The increasing complexity of the applications they run compounds with the need for these applications to be secure. The programmers are always looking for better, more efficient methods of doing computations. Over the past two decades bitsliced software has gained attention as a technique that can, in certain situations, be more efficient than standard software. It also has properties that make it useful for designs implementing secure software. However, writing bitsliced software by hand is a laborious task, and the data input to the software needs to be in a specific format. To make writing the software easier, a tool that generates it from the well-known Verilog hardware description language is discussed in this work. This tool is then used to implement a method to accelerate artificial intelligence calculations on highly constrained computers. A custom hardware module is also introduced to speed up the formatting of data for bitsliced processing. In combination, these tools make bitsliced software and its benefits more accessible.

No description available.

No description available.

LibX is a browser plugin that allows users to access library resources directly from their browser. Many libraries that wished to adopt LibX needed to customize a version of LibX for their own institution. Most librarians did not possess the necessary knowledge of XML, running scripts and the underlying implementation of LibX required to create customized, functional LibX versions for their own institutions. Therefore, we have developed a web-based tool called the LibX Edition Builder that empowers librarians to create their own customized LibX version (editions), effortlessly. The Edition Builder provides rich interactivity to its users by exploiting the ZK AJAX framework whose components we adapted. The Edition Builder provides automatic detection of relevant library resources based on several heuristics which we have developed, which reduces the time and effort required to configure these resources. We have used sound software engineering techniques such as agile development principles, code generation techniques, and the model-view-controller design paradigm to maximize maintainability of the Edition Builder, which enables us to easily incorporate changing functional requirements in the Edition Builder. The LibX Edition Builder is currently used by over 800 registered users who have created over 400 editions. We have carried out a custom log-based usability evaluation that examined the interactions of our users over a 5 month period. This evaluation has shown that the Edition Builder can dramatically reduce the time needed to customize LibX editions and is being increasingly adopted by the library community. / Master of Science

With the enormous amount of information being created digitally or converted to digital formats and made available through Digital Libraries (DLs), there is a strong demand for building tailored DL services to attend the preferences and needs of diverse targeted communities. However,construction and adaptation of such services takes significant effort when not assisted by methodologies, tools, and environments that support the complete life cycle of DL development,including requirements gathering, conceptual modeling, rapid prototyping, and code generation/reuse. With current systems, these activities are only partially supported, generally in an uncorrelated way that may lead to inconsistencies and incompleteness. Moreover, such existing approaches are not buttressed by comprehensive and formal foundations and theories. To address these issues we describe the development, implementation, and deployment of a new generic digital library generator yielding implementations of digital library services from models of DL "societies" and "scenarios". The distinct aspects of our solution are: 1) an approach based on a formal, theoretical framework; 2) use of state-of-the-art database and software engineering techniques such as domain-specific declarative languages, scenario-synthesis, and componentized and model-driven architectures; 3) analysis centered on scenario-based design and DL societal relationships; 4) automatic transformations and mappings from scenarios to workflow designs and from these to Java implementations; and 5) special attention paid to issues of simplicity of implementation, modularity, reusability, and extensibility. We demonstrate the feasibility of the approach through a number of examples. / Master of Science