The growing amount and diversity of functions to be implemented by the current and future embedded applications (like, for example, in automotive electronics) have shown that, in many cases, time-triggered and event-triggered functions have to coexist on the computing nodes and to interact over the communication infrastructure. When time-triggered and event-triggered activities have to share the same processing node, a natural way for the execution support can be provided through a hierarchical scheduler. Similarly, when such heterogeneous applications are mapped over a distributed architecture, the communication infrastructure should allow for message exchange in both time-triggered and event-triggered manner in order to ensure a straightforward interconnection of heterogeneous components. This thesis studies aspects related to the analysis and design optimisation for safety-critical hard real-time applications running on hierarchically scheduled distributed embedded systems. It first provides the basis for the timing analysis of the activities in such a system, by carefully taking into consideration all the interferences that appear at run-time between the processes executed according to different scheduling policies. Moreover, due to the distributed nature of the architecture, message delays are also taken into consideration during the timing analysis. Once the schedulability analysis has been provided, the entire system can be optimised by adjusting its configuration parameters. In our work, the entire optimisation process is directed by the results from the timing analysis, with the goal that in the end the timing constraints of the application are satisfied. The analysis and design methodology proposed in the first part of the thesis is applied next on the particular category of distributed systems that use FlexRay as a communication protocol. We start by providing a schedulability analysis for messages transmitted over a FlexRay bus, and then by proposing a bus access optimisation algorithm that aims at improving the timing properties of the entire system. For all the problems that we investigated, we have carried out extensive experiments in order to measure the efficiency of the proposed solutions. The results have confirmed both the importance of the addressed aspects during system-level design, and the applicability of our techniques for analysing and optimising the studied systems.

Embedded systems are becoming increasingly common in our everyday lives. As technology progresses, these systems become more and more complex. Designers handle this increasing complexity by reusing existing components. At the same time, the systems must fulfill strict functional and non-functional requirements. This thesis presents novel and efficient techniques for the verification of component-based embedded system designs. As a common basis, these techniques have been developed using a Petri net based modelling approach, called PRES+. Two complementary problems are addressed: component verification and integration verification. With component verification the providers verify their components so that they function correctly if given inputs conforming to the assumptions imposed by the components on their environment. Two techniques for component verification are proposed in the thesis. The first technique enables formal verification of SystemC designs by translating them into the PRES+ representation. The second technique involves a simulation based approach into which formal methods are injected to boost verification efficiency. Provided that each individual component is verified and is guaranteed to function correctly, the components are interconnected to form a complete system. What remains to be verified is the interface logic, also called glue logic, and the interaction between components. Each glue logic and interface cannot be verified in isolation. It must be put into the context in which it is supposed to work. An appropriate environment must thus be derived from the components to which the glue logic is connected. This environment must capture the essential properties of the whole system with respect to the properties being verified. In this way, both the glue logic and the interaction of components through the glue logic are verified. The thesis presents algorithms for automatically creating such environments as well as the underlying theoretical framework and a step-by-step roadmap on how to apply these algorithms.

This thesis addresses several issues related to the design and optimization of embedded systems. In particular, in the context of time-constrained embedded systems, the thesis investigates two problems: the minimization of the energy consumption and the implementation of predictable applications on multiprocessor system-on-chip platforms. Power consumption is one of the most limiting factors in electronic systems today. Two techniques that have been shown to reduce the power consumption effectively are dynamic voltage selection and adaptive body biasing. The reduction is achieved by dynamically adjusting the voltage and performance settings according to the application needs. Energy minimization is addressed using both offline and online optimization approaches. Offline, we solve optimally the combined supply voltage and body bias selection problem for multiprocessor systems with imposed time constraints, explicitly taking into account the transition overheads implied by changing voltage levels. The voltage selection technique is applied not only to processors, but also to buses with repeaters and fat wires. We investigate the continuous voltage selection as well as its discrete counterpart. While the above mentioned methods minimize the active energy, we propose an approach that combines voltage selection and processor shutdown in order to optimize the total energy. In order to take full advantage of slack that arises from variations in the execution time, it is important to recalculate the voltage and performance settings during run-time, i.e., online. However, voltage scaling is computationally expensive, and, thus, performed at runtime, significantly hampers the possible energy savings. To overcome the online complexity, we propose a quasi-static voltage scaling scheme, with a constant online time complexity O(1). This allows to increase the exploitable slack as well as to avoid the energy dissipated due to online recalculation of the voltage settings. Worst-case execution time (WCET) analysis and, in general, the predictability of real-time applications implemented on multiprocessor systems has been addressed only in very restrictive and particular contexts. One important aspect that makes the analysis difficult is the estimation of the system’s communication behavior. The traffic on the bus does not solely originate from data transfers due to data dependencies between tasks, but is also affected by memory transfers as result of cache misses. As opposed to the analysis performed for a single processor system, where the cache miss penalty is constant, in a multiprocessor system each cache miss has a variable penalty, depending on the bus contention. This affects the tasks’ WCET which, however, is needed in order to perform system scheduling. At the same time, the WCET depends on the system schedule due to the bus interference. In this context, we propose, an approach to worst-case execution time analysis and system scheduling for real-time applications implemented on multiprocessor SoC architectures.

Les Syst emes sur puce (soc) sont de plus en plus complexes. Leur concep- tion repose largement sur la r eutilisation des blocs, appel es ip (Intellectual Pro- perty). Ces ip sont construites par des concepteurs di erents travaillant avec des outils di erents. Aussi existe-t-il une demande pressante concernant l'in- terop erabilit e des ip, c'est- a-dire d'assurer la compatibilit e des formats et l'uni- cit e d'interpr etation de leurs descriptions. ip-xact constitue un standard de facto d e ni dans le cadre de la conception de syst emes electroniques pour fournir des repr esentations portables de composants ( electroniques) et d'ip. ip-xact a r eussi a assurer la compatibilit e syntaxique, mais il a n eglig e les aspects comportemen- taux. uml est un langage de mod elisation classique pour le g enie logiciel. Il four- nit des el ements de mod ele propres a couvrir tous les aspects structurels et com- portementaux d'une conception. Nous pr^onons une utilisation conjointe d'uml et d'ip-xact pour r ealiser la n ecessaire interop erabilit e. Plus pr ecis ement, nous r eutilisons le pro l uml pour marte pour etendre uml avec des caract eristiques temps r eel embarqu ees. Le paquetage Mod elisation G en erique de Ressources de marte est etendu pour prendre en compte des sp eci cit es structurelles d'ip- xact. Le Mod ele de temps de marte etend le mod ele atemporel d'uml avec le concept de temps logique bien adapt e a la mod elisation au niveau syst eme electronique. La premi ere contribution de cette th ese est la d e nition d'un mod ele de do- maine pour ip-xact. Ce mod ele de domaine est utilis e pour construire un pro l uml pour ip-xact qui r eutilise autant que possible les st er eotypes de marte et en d e nit de nouveaux uniquement en cas de besoin. Une transformation de mod ele a et e mise en uvre dans ATL permettant d'utiliser des editeurs graphiques uml comme front-end pour la sp eci cation d'ip et la g en eration des sp eci cations ip- xact correspondantes. Inversement, des chiers ip-xact peuvent ^etre import es dans un outil uml par une autre transformation de mod eles. La deuxi eme contribution porte sur la mod elisation de propri et es et de con- traintes temporelles portant sur des ip. Les diagrammes comportementaux d'uml sont enrichis avec des horloges logiques et des contraintes d'horloge exprim ees dans le langage de speci cation de contraintes d'horloge (ccsl) de marte. La sp eci cation ccsl peut alors servir de mod ele de r ef erence pour le com- portement temporel attendu et la v eri cation des impl ementations a di erents niveaux d'abstraction (rtl ou tlm). Les propri et es temporelles sont v eri ees en utilisant une biblioth eque sp ecialis ee d'observateurs.

In 2011 a new functional safety standard for electronic and electrical systems in vehicles waspublished, called ISO 26262. This standard concerns the whole lifecycle of the safety criticalelements used in cars, including the development process of such elements. As the correctnessof the tools used when developing such an element is critical to the safety of the element,the standard includes requirements concerning the software tools used in the development,including verification tools. These requirements mainly specify that a developer of a safetycritical element should provide proof of their confidence in the software tools they are using.One recommended way to gain this confidence is to use tools developed in accordance to a“relevant subset of [ISO 26262]”.This project aims to develop a verification system in accordance to ISO 26262, exploringhow and what specifications should be included in this “relevant subset” of ISO 26262 andto which extent these can be included in their current form. The work concludes with thedevelopment of a single safety element of the verification system, to give an demonstrationof the viability of such a system.

La dernière génération de cartes à puce permet le téléchargement d'applications après leur mise en circulation. Outre les problèmes que cela implique, cette capacité d'extension applicative reste encore aujourd'hui bridée par un espace de stockage adressable restreint. La thèse défendue dans ce mémoire est qu'il est possible d'exécuter efficacement des applications stockées dans la mémoire non-adressable des cartes à puce, disponible en plus grande quantité, et ce, malgré ses temps de latences très longs, donc peu favorables a priori à l'exécution de code. Notre travail consiste d'abord à étudier les forces et faiblesse de la principale réponse proposée par l'état de l'art qu'est un cache. Cependant, dans notre contexte, il ne peut être implémenté qu'en logiciel, avec alors une latence supplémentaire. De plus, ce cache doit respecter les contraintes mémoires des cartes à puce et doit donc avoir une empreinte mémoire faible. Nous montrons comment et pourquoi ces deux contraintes réduisent fortement les performances d'un cache, qui devient alors une réponse insuffisante pour la résolution de notre challenge. Nous appliquons notre démonstration aux caches de code natif, puis de code et méta-données Java et JavaCard2. Forts de ces constats, nous proposons puis validons une solution reposant sur une pré-interprétation de code, dont le but est à la fois de détecter précocement les données manquantes en cache pour les charger à l'avance et en parallèle, mais aussi grouper des accès au cache et réduire ainsi l'impact de son temps de latence logiciel, démontré comme son principal coût. Le tout produit alors une solution efficace, passant l'échelle des cartes à puce.

The task has been to develop a network media renderer on an embedded linux system running on a Spartan 6 FPGA. One of the challenges have been to make the best use of the limited FPGA area. MP3 have been the prioritised format. To achieve fast MP3 decoding a MicroBlaze soft processor have been configured for speed with concern to the small area availabe. Also the software MP3 decoding process have been accelerated with hardware. MP3 files with full quality (320 kbit/s) can be decoded with real time requirements. A sound interface hardware have been designed to handle the decoded sound samples and convert them to the S/PDIF standard interface. Also UPnP commands have been implemented with the MP3 player software to complete the renderer’s network functionality.

Uppdragsgivaren Saab Electronic Defence Systems i Jönköping erbjuder ett flertal produkter främst inom avioniksystem. För att kunna utvärdera och kontrollera produktens design i ett tidigt skede så kan en simulering av systemets beteende och att felsöka så tidigt som möjligt vara ett möjligt alternativ. En systemsimulering kan innebära att mjukvaruutveckling och felsökning kan påbörjas långt innan hårdvaruprototypen är tillgänglig, med samma storlek och komplexitet som systemet. Andra fördelar med simulering är att det går enklare att fastställa orsaken till systemkrasch, hitta de längsta exekveringstiderna och göra felinjiceringar. Syftet med detta examensarbete är att testa och utvärdera hur simulatorer och emulatorer är som utvecklings- och testverktyg. Rapporten innehåller en marknadsundersökning där tio stycken emulatorer och simulatorer hittades. Av dessa valdes två stycken ut, Wind River Simics och Imperas OVPSim. Tester utfördes för användarvänlighet, debugging, samt jämförande tester mellan riktig hårdvara och simulerad miljö. Resultatet visar att simulatorer kan hjälpa till vid produktutveckling, men att de ännu inte är så optimala för att utvärdera hårdvara i. Detta för att avvikelser kan förekomma i exekveringstider mellan riktig och simulerad hårdvaruarkitektur. / This thesis has been carried out in cooperation with Saab Electronic Defence Systems in Jönköping which has a wide range of products, mainly for Avionic applications. In order to evaluate and verify their design it is often required to simulate behaviour and debug as early as possible. System simulation can enable software development and debug to commence long before a hardware prototype is available and also scale with the size and complexity of the system. Another benefit of simulation is to more easily determine root causes to system crashes, establish worst case execution time cases and making fault injection. Therefore this thesis will focus on evaluating simulators and emulators, as development- and testing tools. This report contains a marketing research, where ten emulators and simulators were found. Of these, two simulators were chosen for further investigation; WindRiver Simics and Imperas OVPSim. The evaluations considered both usability and debugging features as well as comparative tests between real hardware and the simulated environment. The results show that simulators can help in product development, but they are not yet optimal for evaluating hardware. This is because deviations may occur in execution times between real and simulated hardware architectures.

In a system like a Scania heavy duty truck, faultcodes (DTCs) are generated and stored locally in the ECUs when components, e.g. sensors or actuators, malfunction. Tests are run periodically to detect failure in the system. The test results are processed by the diagnostic system that tries to isolate the faulty components and set local faultcodes. Currently, in a Scania truck, local diagnoses are only based on local diagnostic information, which the DTCs are based upon. The diagnosis statement can, however, be more complete if diagnoses from other ECUs are considered. Thus a system that extends the local diagnoses by exchanging diagnostic information between the ECUs is desired. The diagnostic information to share and how it should be done is elaborated in this thesis. Further, a model of distributed diagnosis is given and a few distributed diagnostic algorithms for transmitting and receiving diagnostic information are presented. A basic idea that has influenced the project is to make the diagnostic system scalable with respect to hardware and thereby making it easy to add and remove ECUs. When implementing a distributed diagnostic system in networked real-time embedded systems, technical problems arise such as memory handling, process synchronization and transmission of diagnostic data and these will be discussed in detail. Implementation of a distributed diagnostic system is further complicated due to the fact that the isolation process is a non deterministic job and requires a non deterministic amount of memory.

Debugging is an important phase in the embedded software development cycle because of its high proportion in the overall cost in the product development. Debugging is difficult for real-time applications as such programs are time-sensitive and must meet deadlines in often a resource constrained environment. A common approach for real-time systems is to monitor the execution instead of stepping through the program, because stepping will usually violate all deadline constraints. We consider a time-triggered approach for program monitoring at runtime, resulting in bounded and predictable overhead. In time-triggered execution monitoring, a monitor runs as a separate process in parallel with an application program and samples the program's state periodically to evaluate a set of properties. Applying this technique in computing systems, results in bounded and predictable overhead. However, the time-triggered approach can have high overhead depending on the granularity of the monitoring effort. To reduce this overhead, we instrument the program with markers that will require to sample less frequently and thus reduce the overhead. This leads to interesting problems of (a) where to place the markers in the code and (b) how to manipulate the markers. While related work investigates the first part, in this work, we investigate the second part. We investigate different instrumentation schemes and propose two new schemes based on bitvectors that significantly reduce the overhead for time-triggered execution monitoring. Time-triggered execution monitoring suffers from several drawbacks such as; the time-triggered monitor requires certain synchronization features at the operating system level and may suffer from various concurrency and synchronization dependencies in a real-time setting. Furthermore, the time-triggered execution monitoring scheme requires the embedded environment to provide multi-tasking features. To address the aforementioned problems, we propose a new method called time-triggered self-monitoring, where the program under inspection is instrumented, so that it self-samples its state in a periodic fashion without requiring assistance from an external monitor or an internal timer. The experimental results show that a time-triggered self-monitored program performs significantly better in terms of execution time, binary code size, and context switches when compared to the same program monitored by an external time-triggered monitor.