Safety-critical systems are systems in which failure may lead to serious harm for humans or the environment. Due to the nature of these systems, there exist regulatory standards that recommend a set of safety mechanisms that should be included in these systems, e.g., IEC 61508. However, these standards offer little to no implementation assistance for these mechanisms. This thesis provides such development assistance, by proposing an approach for the automatic generation of safety mechanisms via Model-Driven Development (MDD). Such an automation of previously manual activities has been known to increase developer productivity and to reduce the number of bugs in the implementation. In the context of safety-critical systems, the latter also means an improvement in safety. The approach introduces a novel way to define safety requirements as structured sentences. This structure allows for the automatic parsing of these requirements in order to subsequently generate software-implemented safety mechanisms, as well as to initially configure hardware-implemented safety mechanisms. The generation approach for software-implemented safety mechanisms uses Unified Modeling Language (UML) stereotypes to represent these mechanisms in the application model. Automated model-to-model transformations parse this model representation and realize the safety mechanisms within an intermediate model. From this intermediate model, code may be generated with simple 1:1 mappings. For the generation of hardware-implemented safety mechanisms, this thesis introduces a novel Graphical User Interface (GUI) tool for representing the configuration of hardware interfaces. A template-based code snippet repository is used for generating the code responsible for the configuration of the hardware-implemented safety mechanisms. The presented approach is validated by applying it to the development of a safety-critical fire detection application example. Furthermore, the runtime overhead of the respective transformation steps of the code generation process is measured. The results indicate a linear scalability and a runtime that is no impediment to the workflow of the developer. Furthermore, the memory and runtime overhead of the generated code is evaluated. The results show that the inclusion of a single safety mechanism for a single system element has a negligible overhead. However, the relative overhead indicates that the application of safety mechanisms should be limited to those system elements that are strictly safety-critical, as their arbitrary application to all system elements would have large effects on the runtime and memory usage of the application.

Due to their highly parallel architecture, Graphics Processing Units (GPUs) offer increased performance for programs benefiting from parallel execution. A range of technologies exist which allow GPUs to be used for general-purpose programming, NVIDIA’s CUDA platform is one example. CUDA makes it possible to combine source code written for GPUs and Central Processing Units (CPUs) in the same program. Those sections that benefit from parallel execution can be written as CUDA kernels and will be executed on the GPU. With CUDA it is common to have tens, or even hundreds, of thousands of threads running in parallel. While the high level of parallelism can offer significant performance increases for executed programs, it can also make CUDA programs hard to debug. Although debuggers for CUDA exist, they can not be used in the same way as standard debuggers, and they do not reduce the difficulties of reasoning about parallel execution. As a result, developers may feel compelled to fall back to inefficient debugging methods, such as relying on print statements. This project examines two possible approaches for creating a tool which simplifies the process of debugging CUDA programs, by transforming a parallel CUDA program to a sequential program in another high level language: one method centered around the Clang Abstract Syntax Tree (AST), and the other method centered around LLVM Intermediate Representation (IR) code. The method using Clang was found to be the most suitable for the purpose of translating CUDA, as it enables modifying only select parts, such as kernels, of the input program. Thus, the tool Cumulus was developed as a Clang plugin. Cumulus translates parallel CUDA code into sequential C++ code, allowing developers to use any method available for C++ debugging to debug their CUDA program. Cumulus is indicated to be a potential aid in debugging CUDA programs, by providing developers with increased flexibility. / Tack vare sin högst parallella arkitektur kan grafikprocessorer erbjuda ökad prestanda för program som gagnas av parallel exekvering. En mängd teknologier finns, vilka möjliggör att grafikprocessorer kan användas inte bara till grafikberäkningar, utan även till allmäna beräkningar. NVIDIA’s plattform CUDA är en sådan teknik. CUDA gör det möjligt att i samma program kombinera källkod skriven för att exekveras på en centralprocessor, med källkod skriven för att exekveras på en grafikprocessor. Kodsektioner i ett program som gagnas av att köras parallellt kan skrivas som en CUDA kernel, vilket är en funktion som exekveras på grafikprocessorn. Med CUDA är det är inte ovanligt att ha tiotusentals, eller till och med hundratusentals, trådar som körs parallellt. Den mycket höga nivån av parallellism kan erbjuda markant ökad prestanda för exekverade program, men kan samtidigt göra det svårt att felsöka CUDA-program. Särskilda avlusare för CUDA existerar, men de kan inte användas på samma sätt som standardavlusare, och de minskar inte svårigheterna med att resonera kring parallella beräkningar. På grund av detta kan utvecklare känna sig nödgade att använda ineffektiva felsökningsmetoder, såsom att förlita sig på printsatser. Det här projektet undersöker två möjliga metoder för att skapa ett verktyg som förenklar felsökandet i CUDAprogram, genom att översätta ett parallellt CUDA-program till ett sekventiellt program i ett klassiskt högnivå-programmeringsspråk. Den ena möjliga metoden är centrerad kring Clangs AST, den andra möjliga metoden är centrerad kring LLVM IR-kod. Metoden som använder Clang fanns vara den mest lämpliga metoden för syftet att översätta CUDA-kod, eftersom den möjliggör översättning av endast utvalda delar av originalprogrammet, exempelvis kernels. Således utvecklades verktyget Cumulus som en Clangplugin. Cumulus översätter parallell CUDA-kod till serialiserad C++-kod, vilket låter utvecklare använda alla de metoder som finns tillgängliga för att felsöka C++-program, för att felsöka sina CUDA-program. Evalueringen av Cumulus indikerar att verktyget kan fungera som en möjlig hjälp vid felsökande av CUDA-program, genom att erbjuda utvecklare ökad flexibilitet.

With the increasing need for larger and morepowerful distributed embedded systems comes the need formore tools to manage them. One area where such a tool isneeded is the internal communication for a distributed embeddedsystem. This project focuses on the development of such atool, namely the development of a communication middlewarewhose network configuration is automatically generated by apredefined network model. The middleware is responsible forrouting information on the network and relieves the applicationdeveloper of this responsibility. By using a multi-layer approach,additional functions can be easily implemented.The middleware demonstrated reasonable results for simplenetworks. However, it does not take into account the timingcharacteristics of the platform. A fact that currently preventsits use in most large networks. / I takt med att behovet av större och kraftfullaredistribuerade inbyggda system ökar, ökar även behovetav verktyg för att hantera dessa system. Ett område där ettsådant verktyg behövs är den interna kommunikationen i ettdistribuerade inbyggt system. Det här projektet fokuserar på att utveckla ett sådant verktyg, genom att utveckla en modellbaseratprogramvara som automatiskt konfigureras med kodgenereringutifrån en fördefinierad modell över nätverket. Eftersom programvaranhanterar datatransmissionen i nätverket, avlastasdetta ansvar från applikationens utvecklare. Genom att användaen modellbaserat metod kan framtida funktioner enkelt implementeras.Programvaran visade ett rimligt resultat för enklare nätverk.Men programvaran tar inte hänsyn till plattformens egenskaper.Något som förhindrar programvaran från att tillämpas på storskaliga nätverk. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

<p>In this thesis we consider the need to generate efficient solvers for inverse imaging problems in a way that supports both quality and performance in software, as well as flexibility in the underlying mathematical models. Many problem domains involve large data sizes and rates, and changes in mathematical modelling are limited only by researcher ingenuity and driven by the value of the application. We use a problem in Magnetic Resonance Imaging to illustrate this situation, motivate the need for better software tools and test the tools we develop. The problem is the determination of velocity profiles, think blood-flow patterns, using Phase Contrast Angiography. Despite the name, this method is completely noninvasive, not requiring the injection of contrast agents, but it is too time-consuming with present imaging and computing technology.</p> <p>Our approach is to separate the specification, the mathematical model, from the implementation details required for performance, using a custom language. The Domain Specific Language (DSL) provided to scientists allows for a complete abstraction from the highly optimized generated code. The mathematical DSL is converted to an internal representation we refer to as the Coconut Expression Library. Our expression library uses the directed acyclic graphs as an underlying data structure, which lends itself nicely to our automatic simplifications, differentiation and subexpression elimination. We show how parallelization and other optimizations are encoded as rules which are applied automatically rather than schemes that need to be implemented by the programmer in the low-level implementation. Finally, we present results, both in terms of numerical results and computational performance.</p> / Master of Science (MSc)

Automatically generating a program from its specification eliminates a large source of errors that is often unavoidable in a manual approach. While a general purpose code generator is impossible to build, it is possible to build a practical code generator for a specific domain. This thesis investigates the theory behind Booster — a domain specific, object based specification language and automatic code generator. The domain of Booster is information systems — systems that consist of a rich object model in which the objects refer to each other to form a complicated network of associations. The operations of such systems are conceptually simple (changing the attributes of objects, adding or removing new objects and creating or destroying associations) but they are tricky to implement correctly. The thesis focuses on the theoretical foundation of the Booster approach, in particular on three contributions: semantics, model completion, and code generation. The semantics of a Booster model is a single abstract data type (ADT) where the invariants and the methods of all the classes in the model are promoted to the level of the ADT. This is different from the traditional view that considers each class as a separate ADT. The thesis argues that the Booster semantics is a better model of object oriented systems. The second important contribution is the idea of model completion — a process that augments the postconditions of methods with additional predicates that follow from the system’s invariant and the method’s original intention. The third contribution describes a simple but effective code generation technique that is based on interpreting postconditions as executable statements and uses weakest preconditions to ensure that the generated code refines its specification.

Cette thèse, à caractère industriel, vise à répondre à une problématique de production de l’entreprise ITK. Par la mise en oeuvre des techniques de l’ingénierie dirigée par les modèles, nous proposons un environnement de modélisation et de simulation pour la croissance des plantes. Outre sa facilité d’utilisation pour les agronomes, le prototype obtenu permet la génération automatique de code Java des modèles à intégrer dans des outils d’aide à la décision exécutés sur une plateforme Java Enterprise Edition. / This PhD thesis has an industrial purpose. It is motivated by a software production issue met within the ITK company. Using the techniques provided by model-driven engineering, we propose a modeling and simulation environment dedicated to plant growth. The prototype achieved proves to be easy to use for crop modelers. It is also enhanced with a Java code generation feature. The models obtained from this code generation are designed to be integrated into decision support systems running on a Java Entreprise Edition platform.

Especificações formais são úteis para descrever o que um sistema deve fazer sem definir como, e, em virtude da sua natureza formal e da possibilidade de abstração, é possível analisá-las sistematicamente. No entanto, o uso de especificações formais como parte do desenvolvimento de software não constitui prática comum. Isso se dá, em parte, pelo fato de existirem apenas um pequeno número de metodologias e ferramentas adequadas que dêem suporte a esse desenvolvimento. O primeiro objetivo deste trabalho é propor uma metodologia de desenvolvimento que possibilite, a partir de uma especificação formal em notação Z, produzir uma implementação dessa especificação em Java. Essa metodologia centra-se na geração do esqueleto da aplicação Java e na instrumentação desse esqueleto com mecanismos de verificação de condições (invariantes, pré e pós-condições) e rastreamento de violações dessas condições. Através desses mecanismos, possibilita-se intercalar desenvolvimento formal e informal no processo global de desenvolvimento de software. O segundo objetivo é desenvolver uma ferramenta que implemente parte dessa metodologia, produzindo uma implementação parcial que deverá ser complementada pelo usuário. / Formal specifications are useful for describing what a system should do, without defining how, and, owing to its formal nature, it is possible to analyse them systematically. However useful formal specifications are, their usage as part of the software development process is rather rare. This is, in part, due to the scarcity of both methodologies and tools that support this development. The first goal of this work is to define a software development methodology that enables the developer to produce a Java application from a formal specification written in Z. This methodology will rely strongly on the generation of Java application skeletons and instrumentation of the generated code with means of verifying conditions (invariants, pre and post-conditions) e tracing violations of these conditions. Through this mechanisms, it is possible to mix formal and informal development in the global software development process. The second goal of this work is to develop a tool that will implement part of this methodology, producing a partial implementation that must be complemented by the developer.

Title: Pattern matching in compilers Author: Ondřej Bílka Department: Department of Applied Mathematics Supervisor: Jan Hubička, Department of Applied Mathematics Abstract: In this thesis we develop tools for effective and flexible pattern matching. We introduce a new pattern matching system called amethyst. Amethyst is not only a generator of parsers of programming languages, but can also serve as an alternative to tools for matching regular expressions. Our framework also produces dynamic parsers. Its intended use is in the context of IDE (accurate syntax highlighting and error detection on the fly). Amethyst offers pattern matching of general data structures. This makes it a useful tool for implement- ing compiler optimizations such as constant folding, instruction scheduling, and dataflow analysis in general. The parsers produced are essentially top-down parsers. Linear time complexity is obtained by introducing the novel notion of structured grammars and reg- ularized regular expressions. Amethyst uses techniques known from compiler optimizations to produce effective parsers. Keywords: Packrat parsing, dynamic parsing, structured grammars, functional programming 1

Este trabalho propõe uma nova abordagem para o desenvolvimento de sistemas embarcados, através da combinação da abstração e propriedades de verificação de modelos da linguagem declarativa Alloy com a ampla aceitação de Java na indústria. A abordagem surge no contexto de que a automação de software no domínio embarcado tornou-se extremamente necessária, uma vez que atualmente a maior parte do tempo de desenvolvimento é gasta no projeto de software de produtos tão restritos em termos de recursos. As ferramentas de automação de software embarcado devem atender a demanda por produtividade e manutenibilidade, mas respeitar restrições naturais deste tipo de sistema, tais como espaço de memória, potência e desempenho. As ferramentas de automação de projeto lidam com produtividade e manutenibilidade ao permitir especificações de alto nível, tarefa difícil de atender no domínio embarcado devido ao comportamento misto de muitas aplicações embarcadas. Abordagens que promovem meios para verificação formal também são atrativas, embora geralmente sejam difíceis de usar, e por este motivo não são de grande auxílio na tarefa de reduzir o tempo de chegada ao mercado do produto. Através do uso de Alloy, baseada em lógica de primeira-ordem, é possível obter especificações em altonível e verificação formal de modelos com uma única linguagem. Este trabalho apresenta a poderosa abstração proporcionada pela linguagem Alloy em aplicações embarcadas, assim como regras para obter automaticamente código Java a partir de modelos Alloy. A geração de código Java a partir de modelos Alloy, combinada a uma ferramenta de estimativa, provê exploração de espaço de projeto, atendendo assim as fortes restrições do projeto de software embarcado, o que normalmente não é contemplado pela engenharia de software tradicional. / This work proposes a new approach for embedded software development, by combining the abstraction and model verification properties of the Alloy declarative language with the broad acceptance in industry of Java. The approach comes into play since software automation in the embedded domain has become a major need, as currently most of the development time is spent designing software for such hardconstrained resources products. Design automation tools for embedded systems must meet the demand for productivity and maintainability, but constraints such as memory, power and performance must still be considered. Design automation tools deal with productivity and maintainability by allowing high-level specifications, which is hard to accomplish on the embedded domain due to the mixed behavior nature of many embedded applications. Approaches that provide means for formal verification are also attractive, but their usage is usually not straightforward, and for this reason they are not that helpful in dealing with time-tomarket constraints. By using Alloy, based in first-order logic, it is possible to obtain high-level specifications and formal model verification with a single language. This work shows the powerful abstraction provided by the Alloy language for embedded applications, as well as rules for obtaining automatically Java code from Alloy models. The Java source code generation from Alloy models, combined with an estimation tool, provides design space exploration to match tight embedded software design constraints, what is usually not taken into account by standard software engineering techniques.

<p>In this thesis we address the problem of optimal code generation for irregular architectures such as Digital Signal Processors (DSPs).</p><p>Code generation consists mainly of three interrelated optimization tasks: instruction selection (with resource allocation), instruction scheduling and register allocation. These tasks have been discovered to be NP-hard for most architectures and most situations. A common approach to code generation consists in solving each task separately, i.e. in a decoupled manner, which is easier from a software engineering point of view. Phase-decoupled compilers produce good code quality for regular architectures, but if applied to DSPs the resulting code is of significantly lower performance due to strong interdependences between the different tasks.</p><p>We developed a novel method for fully integrated code generation at the basic block level, based on dynamic programming. It handles the most important tasks of code generation in a single optimization step and produces an optimal code sequence. Our dynamic programming algorithm is applicable to small, yet not trivial problem instances with up to 50 instructions per basic block if data locality is not an issue, and up to 20 instructions if we take data locality with optimal scheduling of data transfers on irregular processor architectures into account. For larger problem instances we have developed heuristic relaxations.</p><p>In order to obtain a retargetable framework we developed a structured architecture specification language, xADML, which is based on XML. We implemented such a framework, called OPTIMIST that is parameterized by an xADML architecture specification.</p><p>The thesis further provides an Integer Linear Programming formulation of fully integrated optimal code generation for VLIW architectures with a homogeneous register file. Where it terminates successfully, the ILP-based optimizer mostly works faster than the dynamic programming approach; on the other hand, it fails for several larger examples where dynamic programming still provides a solution. Hence, the two approaches complement each other. In particular, we show how the dynamic programming approach can be used to precondition the ILP formulation.</p><p>As far as we know from the literature, this is for the first time that the main tasks of code generation are solved optimally in a single and fully integrated optimization step that additionally considers data placement in register sets and optimal scheduling of data transfers between different registers sets.</p>