Nowadays the ever increasing algorithmic complexity of embedded applications requires the designers to turn towards heterogeneous and highly integrated systems denoted as SoC (System-on-a-Chip). These architectures may embed CPU-based processors, dedicated datapaths as well as recon gurable units. However, embedded SoCs are submitted to stringent requirements in terms of speed, size, cost, power consumption, throughput, etc. Therefore, new computing paradigms are required to ful l the constraints of the applications and the requirements of the architecture. Recon gurable Computing is a promising paradigm that provides probably the best trade-o between these requirements and constraints. Dynamically recon gurable architectures are their key enabling technology. They enable the hardware to adapt to the application at runtime. However, these architectures raise new challenges in SoC design. For example, on one hand, designing a system that takes advantage of dynamic recon guration is still very time consuming because of the lack of design methodologies and tools. On the other hand, scheduling hardware tasks di ers from classical software tasks scheduling on microprocessor or multiprocessors systems, as it bears a further complicated placement problem. This thesis deals with the problem of scheduling online real-time hardware tasks on Dynamically Recon gurable Hardware Devices (DRHWs). The problem is addressed from two angles : (i) Investigating novel algorithms for online real-time scheduling/placement on DRHWs. (ii) Scheduling/Placement algorithms library for RTOS-driven Design Space Exploration (DSE). Regarding the first point, the thesis proposes two main runtime-aware scheduling and placement techniques and assesses their suitability for online real-time scenarios. The first technique discusses the impact of synthesizing, at design time, several shapes and/or sizes per hardware task (denoted as multi-shape task), in order to ease the online scheduling process. The second technique combines a looking-ahead scheduling approach with a slots-based recon gurable areas management that relies on a 1D placement. The results show that in both techniques, the scheduling and placement quality is improved without signi cantly increasing the algorithm time complexity. Regarding the second point, in the process of designing SoCs embedding recon gurable parts, new design paradigms tend to explore and validate as early as possible, at system level, the architectural design space. Therefore, the RTOS (Real-Time Operating System) services that manage the recon gurable parts of the SoC can be re fined. In such a context, gathering numerous hardware tasks scheduling and placement algorithms of various complexity vs performance trade-o s in a kind of library is required. In this thesis, proposed algorithms in addition to some existing ones are purposely implemented in C++ language, in order to insure the compatibility with any C++/SystemC based SoC design methodology.

<p>This thesis describes a further development of a building block for programmable devices in embedded systems handling real-time functionality.</p><p>Embedded systems are included in a variety of products within different technical areas such as industrial automation, consumer electronics, automotive industry, and communication-, and multimedia systems. Products ranging from trains and airplanes to microwave ovens and washing machines are controlled by embedded systems.</p><p>Programmable devices constitute a part of these embedded systems. Today, a programmable device can include a complete system containing building blocks connected with each other via programs written using a hardware description language. The programmable devices can be programmed and changed over and over again and this flexibility makes it possible to explore how these building blocks can best be designed in relation to system requirements, before final implementation.</p><p>This thesis describes a further development of a building block for programmable devices implemented in a non-traditional way, i.e., the implementation is written using both hardware description language and traditional software languages. This new building block handles real-time functionality in a non-traditional way that enables certain benefits, such as increased performance, predictability and less memory consumption. Using a non-traditional implementation also has its drawbacks, and e.g., extensions and adjustments can be hard to handle since modifications are required in both hardware and software programming languages.</p><p>The new building block was investigated in order to see how it could be facilitated when used for real-time functionality. The configurability of the block was extended which enables further customization of the building block. This leads to the possibility to use the block within a wider spectrumof applications. It is also possible to reduce the size and cost of the final product since resource usage can be optimized.</p><p>Furthermore, a mathematicalmodel estimating resource usage for real-time functionality has been developed. The model enables distinctive trade-offs comparisons, and guidance for system designers, when considering what type of real-time operating system to use in a certain design.</p>

<p>The Integrated Modular Avionics architecture , IMA, provides means for runningmultiple safety-critical applications on the same hardware. ARINC 653 is aspecification for this kind of architecture. It is a specification for space and timepartition in safety-critical real-time operating systems to ensure each application’sintegrity. This Master thesis describes how databases can be implementedand used in an ARINC 653 system. The addressed issues are interpartitioncommunication, deadlocks and database storage. Two alternative embeddeddatabases are integrated in an IMA system to be accessed from multiple clientsfrom different partitions. Performance benchmarking was used to study the differencesin terms of throughput, number of simultaneous clients, and scheduling.Databases implemented and benchmarked are SQLite and Raima. The studiesindicated a clear speed advantage in favor of SQLite, when Raima was integratedusing the ODBC interface. Both databases perform quite well and seem to begood enough for usage in embedded systems. However, since neither SQLiteor Raima have any real-time support, their usage in safety-critical systems arelimited. The testing was performed in a simulated environment which makesthe results somewhat unreliable. To validate the benchmark results, furtherstudies must be performed, preferably in a real target environment.The Integrated Modular Avionics architecture , IMA, provides means for runningmultiple safety-critical applications on the same hardware. ARINC 653 is aspecification for this kind of architecture. It is a specification for space and timepartition in safety-critical real-time operating systems to ensure each application’sintegrity. This Master thesis describes how databases can be implementedand used in an ARINC 653 system. The addressed issues are interpartitioncommunication, deadlocks and database storage. Two alternative embeddeddatabases are integrated in an IMA system to be accessed from multiple clientsfrom different partitions. Performance benchmarking was used to study the differencesin terms of throughput, number of simultaneous clients, and scheduling.Databases implemented and benchmarked are SQLite and Raima. The studiesindicated a clear speed advantage in favor of SQLite, when Raima was integratedusing the ODBC interface. Both databases perform quite well and seem to begood enough for usage in embedded systems. However, since neither SQLiteor Raima have any real-time support, their usage in safety-critical systems arelimited. The testing was performed in a simulated environment which makesthe results somewhat unreliable. To validate the benchmark results, furtherstudies must be performed, preferably in a real target environment.</p>

Today&rsquo / s reconfigurable devices successfully combine &lsquo / reconfigurable computing machine&rsquo / paradigm and &lsquo / high degree of parallelism&rsquo / and hence reconfigurable computing emerged as a promising alternative for computing-intensive applications. Despite its superior performance and lower power consumption compared to general purpose computing using microprocessors, reconfigurable computing comes with a cost of design complexity. This thesis aims to reduce this complexity by providing a flexible and user friendly development environment to application programmers in the form of a complete reconfigurable computing platform. The proposed computing platform is specially designed for real time embedded applications and supports true multitasking by using available run time partially reconfigurable architectures. For this computing platform, we propose a novel hardware task model aiming to minimize logic resource requirement and the overhead due to the reconfiguration of the device. Based on this task model an optimal 2D surface partitioning strategy for managing the hardware resource is presented. A mesh network-on-chip is designed to be used as the communication environment for the hardware tasks and a runtime mapping technique is employed to lower the communication overhead. As the requirements of embedded systems are known prior to field operation, an oine design flow is proposed for generating the associated bit-stream for the hardware tasks. Finally, an online real time operating system scheduler is given to complete the necessary building blocks of a reconfigurable computing platform suitable for real time computing-intensive embedded applications. In addition to providing a flexible development environment, the proposed computing platform is shown to have better device utilization and reconfiguration time overhead compared to existing studies.

The Integrated Modular Avionics architecture , IMA, provides means for runningmultiple safety-critical applications on the same hardware. ARINC 653 is aspecification for this kind of architecture. It is a specification for space and timepartition in safety-critical real-time operating systems to ensure each application’sintegrity. This Master thesis describes how databases can be implementedand used in an ARINC 653 system. The addressed issues are interpartitioncommunication, deadlocks and database storage. Two alternative embeddeddatabases are integrated in an IMA system to be accessed from multiple clientsfrom different partitions. Performance benchmarking was used to study the differencesin terms of throughput, number of simultaneous clients, and scheduling.Databases implemented and benchmarked are SQLite and Raima. The studiesindicated a clear speed advantage in favor of SQLite, when Raima was integratedusing the ODBC interface. Both databases perform quite well and seem to begood enough for usage in embedded systems. However, since neither SQLiteor Raima have any real-time support, their usage in safety-critical systems arelimited. The testing was performed in a simulated environment which makesthe results somewhat unreliable. To validate the benchmark results, furtherstudies must be performed, preferably in a real target environment.The Integrated Modular Avionics architecture , IMA, provides means for runningmultiple safety-critical applications on the same hardware. ARINC 653 is aspecification for this kind of architecture. It is a specification for space and timepartition in safety-critical real-time operating systems to ensure each application’sintegrity. This Master thesis describes how databases can be implementedand used in an ARINC 653 system. The addressed issues are interpartitioncommunication, deadlocks and database storage. Two alternative embeddeddatabases are integrated in an IMA system to be accessed from multiple clientsfrom different partitions. Performance benchmarking was used to study the differencesin terms of throughput, number of simultaneous clients, and scheduling.Databases implemented and benchmarked are SQLite and Raima. The studiesindicated a clear speed advantage in favor of SQLite, when Raima was integratedusing the ODBC interface. Both databases perform quite well and seem to begood enough for usage in embedded systems. However, since neither SQLiteor Raima have any real-time support, their usage in safety-critical systems arelimited. The testing was performed in a simulated environment which makesthe results somewhat unreliable. To validate the benchmark results, furtherstudies must be performed, preferably in a real target environment.

This thesis describes a further development of a building block for programmable devices in embedded systems handling real-time functionality. Embedded systems are included in a variety of products within different technical areas such as industrial automation, consumer electronics, automotive industry, and communication-, and multimedia systems. Products ranging from trains and airplanes to microwave ovens and washing machines are controlled by embedded systems. Programmable devices constitute a part of these embedded systems. Today, a programmable device can include a complete system containing building blocks connected with each other via programs written using a hardware description language. The programmable devices can be programmed and changed over and over again and this flexibility makes it possible to explore how these building blocks can best be designed in relation to system requirements, before final implementation. This thesis describes a further development of a building block for programmable devices implemented in a non-traditional way, i.e., the implementation is written using both hardware description language and traditional software languages. This new building block handles real-time functionality in a non-traditional way that enables certain benefits, such as increased performance, predictability and less memory consumption. Using a non-traditional implementation also has its drawbacks, and e.g., extensions and adjustments can be hard to handle since modifications are required in both hardware and software programming languages. The new building block was investigated in order to see how it could be facilitated when used for real-time functionality. The configurability of the block was extended which enables further customization of the building block. This leads to the possibility to use the block within a wider spectrumof applications. It is also possible to reduce the size and cost of the final product since resource usage can be optimized. Furthermore, a mathematicalmodel estimating resource usage for real-time functionality has been developed. The model enables distinctive trade-offs comparisons, and guidance for system designers, when considering what type of real-time operating system to use in a certain design.

Tato práce se zabývá návrhem a implementací dvou konkrétních softwarových modulů, které jsou částí distribuovaného řídícího systému CoSMic. Tento systém je určen pro řízení speciálního zařízení pro charakterizaci papírových vláken. Prvním vyvinutým modulem je HapticFiber, ten má poskytovat rozhraní mezi řídícím systémem a speciálním vstupním zařízením - haptic device. Druhým modulem je ViCo, jehož účelem je poskytnout softwarovou obálku pro uživatelem definovaný algoritmus zpracovaní obrazu. Tento modul musí být připraven splnit určitá časová omezení, proto je nutné, aby běžel v rámci operačním systému reálného času.

Nowadays, multi-core processors are widely used in embedded applications due to the advantages of higher performance and lower power consumption. However, the complexity of multi-core architectures makes it a considerably challenging task to extend a single-core version of a real-time operating system to support multi-core platform. This thesis documents the process of design and implementation of a multi-core version of RODOS - an embedded real-time operating system developed by German Aerospace Center and the University of Würzburg - on a dual-core platform. Two possible models are proposed: Symmetric Multiprocessing and Asymmetric Multiprocessing. In order to prevent the collision of the global components initialization, a new multi-core boot loader is created to allow that each core boots up in a proper manner. A working version of multi-core RODOS is implemented that has an ability to run tasks on a multi-core platform. Several test cases are applied and verified that the performance on the multi-core version of RODOS achieves around 180% improved than the same tasks running on the original RODOS. Deadlock free communication and synchronization APIs are provided to let parallel applications share data and messages in a safe manner.

Nos últimos anos os sistemas embarcados tem-se tornado notório nos mercados de eletroeletrônicos de consumo, automação industrial e comercial e em veículos em geral. Grande parte destas aplicações possui restrições temporais, sendo assim caracterizadas como sistemas de tempo real embarcado. Atualmente, a computação distribuída tem alcançado este tipo de sistema e por razão principal em custos desses sistemas, alguns barramentos ou redes de comunicação vêm sendo empregados como plataforma de conexão entre módulos eletrônicos. Um exemplo de aplicação de sistemas embarcados distribuídos e de tempo real é a eletrônica embarcada em veículos automotores, onde se encontram várias unidades de controle eletrônico espalhadas interior desses veículos com diferentes funções e se comunicando via rede de comunicação. Algumas pesquisas importantes nesta área já apresentaram diferentes abordagens em sistemas distribuídos de tempo real (SDTR) objetivando cobrir a crescente demanda de desempenho, previsibilidade e confiabilidade dessas aplicações emergentes. Tais requisitos envolvem baixa latência de transmissão, baixa variabilidade no tempo (jitter), tolerância a falhas e suporte para atualizações futuras - flexibilidade. Particularmente na área automotiva, onde é considerada a possibilidade de substituição de dispositivosmecânicos/hidráulicos por sistemas eletrônicos, conhecidos como "by-wire" systems. Assegurar um comportamento previsível e confiável desses sistemas assim como agregar um nível de flexibilidade são características necessárias em grande parte de aplicações de SDTR. O modelo de comunicação FTT (Flexible Time-Triggered) apresentado nesta dissertação, apresenta um alto grau de flexibilidade em relação a outros protocolos, tais como TTCAN, TTP e FlexRay. Um sistema distribuído de tempo real baseado no modelo FTT se adapta às mudanças de requisitos da aplicação em tempo de execução, sendo possível adicionar novas unidades de controle eletrônico sobre a rede após a fase de projeto. Esta característica advém do escalonador dinâmico deste modelo de comunicação. Este trabalho apresenta algumas propostas de melhoria de desempenho de tempo de resposta do protocolo FTT-CAN, descrevendo alguns pontos negligenciados na atual especificação do protocolo. As propostas têm como foco a estratégia de disparo de mensagens e tarefas, sendo a primeira relacionada à transmissão de mensagens síncrona (ou time-triggered), onde existem dois inconvenientes que geram jitter neste segmento de transmissão; a segunda é relacionado ao disparo de tarefas, onde existem algumas deficiências na liberação de tarefas síncronas na atual especificação do protocolo FTT-CAN. / Embedded computing systems have become widely used in many areas. The greater part of those systems has time constraints and therefore they can be characterized as real time embedded systems. Nowadays, distributed computing has reached the embedded application, where some fieldbuses are already being used as communication platforms. Some important researches has presented different approaches in the real time distributed embedded system domain aiming to cover the growing demands of performance, predictability and reliability of emerging applications. Such requirements involve low latency, reduced jitter, time composability, fault-tolerance and support for future extensions – flexibility. Particularly in the automotive area, on which several mechanical and/or hydraulic systems are being replaced by electronic "by-wire"systems, the importance of ensuring predictable behavior while also presenting some degree of flexibility plays a key role. Regarding to the flexibility, the Flexible Time Triggered communication model stands out against the others ones due to its high degree of flexibility. In this context, the FTT communication model appears as an interesting approach due to its high degree of flexibility while still ensuring a deterministic timing behavior. A distributed system based on a FTT communication infrastructure can adapts to changing application requirements, making possible the addition of new messages and nodes during operation. In this way, the communication infrastructure needs to schedule newest messages on-line. This master’s work presents some proposals to improve the FTT-CAN response-time and indicating some drawbacks in already presented approaches. The improvements are concerning messages and tasks scheduling. Despite of its interesting characteristics, FTT CAN present some negative aspects regarding its timing behavior: the issue is on the synchronous message transmission, where there are two neglected points that generate jitter in this traffic; the other one is tasks dispatching, where there are some deficiencies concerning synchronous tasks execution. These disadvantages were not discussed in literature yet. This work presents new proposals to task and message scheduling of FFT-CAN based applications, therefore overcoming some of the main drawbacks of the protocol.

Concurrent programs are pervasive owing to the increasing adoption of multi-core systems across the entire computing spectrum. However, the large set of possible program behaviors make it difficult to write correct and efficient con-current programs. This also makes the formal and automated analysis of such programs a hard problem. Thus, concurrent programs provide fertile grounds for a large class of insidious defects. Static analysis techniques infer semantic properties of programs without executing them. They are attractive because they are sound (they can guarantee the absence of bugs), can execute with a fair degree of automation, and do not depend on test cases. However, current static analyses techniques for concurrent programs are either precise and prohibitively slow, or fast but imprecise. In this thesis, we partially address this problem by designing efficient static analyses for concurrent programs. In the first part of the thesis, we provide a framework for designing and proving the correctness of data flow analysis for race free multi-threaded programs. The resulting analyses are in the same spirit as the \sync-CFG" analysis, originally proposed in De et al, 2011. Using novel thread-local semantics as starting points, we devise abstract analyses which treat a concurrent program as if it were sequential. We instantiate these abstractions to devise efficient relational analyses for race free programs, which we have implemented in a prototype tool called RATCOP. On the benchmarks, RATCOP was fairly precise and fast. In a comparative study with a recent concurrent static analyzer, RATCOP was up to 5 orders of magnitude faster. In the second part of the thesis, we propose a technique for detecting all high-level data races in a system library, like the kernel API of a real-time operating system (RTOS) that relies on ag-based scheduling and synchronization. Such races are good indicators of atomicity violations. Using our technique, a user is able to soundly disregard 99:8% of an estimated 41; 000 potential high-level races. Our tool detected 38 high-level data races in FreeRTOS (a popular OS in the embedded systems domain), out of which 16 were harmful.