Search

Modern safety-critical embedded applications like autonomous driving need to be fail-operational. At the same time, high performance and low power consumption are demanded. A common way to achieve this is the use of heterogeneous multi-cores. When applied to such systems, prevalent fault tolerance mechanisms suffer from some disadvantages: Some (e.g. triple modular redundancy) require a substantial amount of duplication, resulting in high hardware costs and power consumption. Others (e.g. lockstep) require supplementary checkpointing mechanisms to recover from errors. Further approaches (e.g. software-based process-level redundancy) cannot handle the indeterminism introduced by multithreaded execution. This paper presents a novel approach for fail-operational systems using hardware transactional memory, which can also be used for embedded systems running heterogeneous multi-cores. Each thread is automatically split into transactions, which then execute redundantly. The hardware transactional memory is extended to support multiple versions, which allows the reproduction of atomic operations and recovery in case of an error. In our FPGA-based evaluation, we executed the PARSEC benchmark suite with fault tolerance on 12 cores.

In this paper, we present a functional programming model and a dataflow execution model similar to distributed computing frameworks, like Apache Spark and Flink. Our programming and execution model is suitable for any platform, although its main target are safety-critical embedded systems. Therefore, we emphasize on low overhead, timing analyzability, and potential support for fault tolerance. We implemented our design for the x86 shared memory platform and showed that the performance is comparable to the performance of OpenMP.

Worst-case execution time (WCET) analysis is crucial for designing real-time systems. While the WCET of tasks in a single core system can be upper bounded in isolation, the tasks in a manycore system are subject to shared memory interferences which impose high overestimation of the WCET bounds. However, manycore-based massively parallel applications will enter the area of real-time systems in the years ahead. Explicit message-passing and a clear separation of computation and communication facilitates WCET analysis for those programs. Thereby, the separation is especially ensured if applying collective communication.We propose a process of analysing state-of-the-art communication patterns with respect to worst case timing. As MPI is the standard for performing collective communication, we use it to show how to evaluate the timing behaviour in detail. We compare different communication patterns and show the tremendous impact of choosing an appropriate one.

Parallelization of AUTOSAR legacy software is a fundamental step to exploit the performance of multi-core electronic control units (ECUs). However, communication between runnables causes serialization and intra-task parallelization can therefore introduce large idle intervals, if a task contains a long critical path. Distributing the instructions of a runnable over cores (fine-grained parallelism) can reduce the serialization to a shorter time, but this requires an efficient and timing analyzable implementation. This paper investigates the efficiency of fine-grained parallelism for reducing the worst-case execution time in automotive applications. A pattern-supported parallelization approach is applied to extract parallelism of runnables in a structured way. Algorithmic skeletons are used to implement fine-grained parallelism in a dynamic (assignment at runtime) and in a static (a priori assignment) way. The performance evaluation showed that the static assignment is as efficient as a state-of-the-art barrier. Thereby, parallelism is explicitly expressed in a model and implemented in a timing analyzable way.

Critical Real-Time Embedded Systems require functional and timing validation to prove that they will perform their functionalities correctly and in time. For timing validation, a bound to the Worst-Case Execution Time (WCET) for each task is derived and passed as an input to the scheduling algorithm to ensure that tasks execute timely. Bounds to WCET can be derived with deterministic timing analysis (DTA) and probabilistic timing analysis (PTA), each of which relies upon certain predictability properties coming from the hardware/software platform beneath. In particular, specific hardware designs are needed for both DTA and PTA, which challenges their adoption by hardware vendors. This paper makes a step towards reconciling the hardware needs of DTA and PTA timing analyses to increase the likelihood of those hardware designs to be adopted by hardware vendors. In particular, we show how Time Division Multiple Access (TDMA), which has been regarded as one of the main DTA-compliant arbitration policies, can be used in the context of PTA and, in particular, of the industrially-friendly Measurement-Based PTA (MBPTA). We show how the execution time measurements taken as input for MBPTA need to be padded to obtain reliable and tight WCET estimates on top of TDMA-arbitrated hardware resources with no further hardware support. Our results show that TDMA delivers tighter WCET estimates than MBPTA-friendly arbitration policies, whereas MBPTA-friendly policies provide higher average performance. Thus, the best policy to choose depends on the particular needs of the end user. The research leading to these results has been funded by the EU FP7 under grant agreement no. 611085 (PROXIMA) and 287519 (parMERASA). This work has also been partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P and the HiPEAC Network of Excellence. Miloˇs Pani´c is funded by the Spanish Ministry of Education under the FPU grant FPU12/05966. Jaume Abella has been partially supported by the MINECO under Ramon y Cajal postdoctoral fellowship number RYC-2013-14717.

Bufferless deflection routing is a serious alternative to wormhole flow control and packet switching. It is based on the principle of deflecting a flit to a non-optimal route instead of buffering it, when two flits compete for the same link. The major weakness of deflection is the exploding number of misrouted flits at high network load, which increases the duration of flits within the network and requires to reassemble the flits at the receiver. These deflections can be reduced significantly by adding a small side buffer instead of always deflecting flits. In the presented approach, the side buffer is complemented by a restricted deflection policy that preserves the flit order: x-y-routing in an unidirectional 2D-torus ensures that collisions are impossible, as long as a flit is transported in the same direction. Only at the transition from x- to y-direction, collisions may happen and are avoided by controlled in-order deflection in x-direction. In-order delivery not only simplifies the arbitration logic, but avoids costly mechanisms for livelock-prevention and reassembly of flits at the receiver.

Software-based fault-tolerance mechanisms can increase the reliability of multi-core CPUs while being cheaper and more flexible than hardware solutions like lockstep architectures. However, checkpoint creation, error detection and correction entail high performance overhead if implemented in software. We propose a software/hardware hybrid approach, which leverages Intel's hardware transactional memory (TSX) to support implicit checkpoint creation and fast rollback. Hardware enhancements are proposed and evaluated, leading to a resulting performance overhead of 19% on average.

Open self-x systems of a very large scale – interconnecting several thousand of autonomous and heterogeneous entities – become increasingly complex in their organisational structures. This is due to the fact that such systems are typically restricted to a local view in the sense that they have no global instance, which can be responsible for controlling or managing the whole system. Therefore, new ways have to be found to develop and manage them. An essential aspect that has recently gained much attention in this kind of systems is the social concept of trust. Using appropriate trust mechanisms, entities in the system can have a clue about which entities to cooperate with. This is very important to improve the robustness of self-x systems, which depends on a cooperation of autonomous entities. The contributions of this chapter are trustworthy concepts and generic self-x algorithms with the ability to self-configure, self-optimise, and self-heal that work in a distributed manner and with no central control to ensure robustness. Some experimental results of our algorithms are reported to show the improvement that can be obtained compared with the baseline measurements.

The high parallelism of future Teradevices, which are going to contain more than 1,000 complex cores on a single die, requests new execution paradigms. Coarse-grained dataflow execution models are able to exploit such parallelism, since they combine side-effect free execution and reduced synchronization overhead. However, the terascale transistor integration of such future chips make them orders of magnitude more vulnerable to voltage fluctuation, radiation, and process variations. This means dynamic fault-tolerance mechanisms have to be an essential part of such future system. In this paper, we present a fault tolerant architecture for a coarse-grained dataflow system, leveraging the inherent features of the dataflow execution model. In detail, we provide methods to dynamically detect and manage permanent, intermittent, and transient faults during runtime. Furthermore, we exploit the dataflow execution model for a thread-level recovery scheme. Our results showed that redundant execution of dataflow threads can efficiently make use of underutilized resources in a multi-core, while the overhead in a fully utilized system stays reasonable. Moreover, thread-level recovery suffered from moderate overhead, even in the case of high fault rates.

Applications in industry often have grown and improved over many years. Since their performance demands increase, they also need to benefit from the availability of multi-core processors. However, a reimplementation from scratch and even a restructuring of these industrial applications is very expensive, often due to high certification efforts. Therefore, a strategy for a systematic parallelization of legacy code is needed. We present a parallelization approach for hard real-time systems, which ensures a high reusage of legacy code and preserves timing analysability. To show its applicability, we apply it on the core algorithm of an avionics application as well as on the control program of a large construction machine. We create models of the legacy programs showing the potential of parallelism, optimize them and change the source codes accordingly. The parallelized applications are placed on a predictable multi-core processor with up to 18 cores. For evaluation, we compare the worst case execution times and their speedups. Furthermore, we analyse limitations coming up at the parallelization process.

The participants in open self-organising systems, including users and autonomous agents, operate in a highly uncertain environment in which the agents’ benevolence cannot be assumed. One way to address this challenge is to use computational trust. By extending the notion of trust as a qualifier of relationships between agents and incorporating trust into the agents’ decisions, they can cope with uncertainties stemming from unintentional as well as intentional misbehaviour. As a consequence, the system’s robustness and efficiency increases. In this context, we show how an extended notion of trust can be used in the formation of system structures, algorithmically to mitigate uncertainties in task and resource allocation, and as a sanctioning and incentive mechanism. Beyond that, we outline how the users’ trust in a self-organising system can be increased, which is decisive for the acceptance of these systems.

International audience; The EC project parMERASA (Multicore Execution of Parallelized Hard Real-Time Applications Supporting Analyzability) investigated timing-analyzable parallel hard real-time applications running on a predictable multicore processor. A pattern-supported parallelization approach was developed to ease sequential to parallel program transformation based on parallel design patterns that are timing analyzable. The parallelization approach was applied to parallelize the following industrial hard real-time programs: 3D path planning and stereo navigation algorithms (Honeywell International s.r.o.), control algorithm for a dynamic compaction machine (BAUER Maschinen GmbH), and a diesel engine management system (DENSO AUTOMOTIVE Deutschland GmbH). This article focuses on the parallelization approach, experiences during parallelization with the applications, and quantitative results reached by simulation, by static WCET analysis with the OTAWA tool, and by measurement-based WCET analysis with the RapiTime tool.

This book treats the computational use of social concepts as the focal point for the realisation of a novel class of socio-technical systems, comprising smart grids, public display environments, and grid computing. These systems are composed of technical and human constituents that interact with each other in an open environment. Heterogeneity, large scale, and uncertainty in the behaviour of the constituents and the environment are the rule rather than the exception. Ensuring the trustworthiness of such systems allows their technical constituents to interact with each other in a reliable, secure, and predictable way while their human users are able to understand and control them. "Trustworthy Open Self-Organising Systems" contains a wealth of knowledge, from trustworthy self-organisation mechanisms, to trust models, methods to measure a user's trust in a system, a discussion of social concepts beyond trust, and insights into the impact open self-organising systems will have on society.

Current timing analysis techniques can be broadly classified into two families: deterministic timing analysis (DTA) and probabilistic timing analysis (PTA). Each family defines a set of properties to be provided (enforced) by the hardware and software platform so that valid Worst-Case Execution Time (WCET) estimates can be derived for programs running on that platform. However, the fact that each family relies on each own set of hardware designs limits their applicability and reduces the chances of those designs being adopted by hardware vendors. In this paper we show that Time Division Multiple Access (TDMA), one of the main DTA-compliant arbitration policies, can be made PTA-compliant. To that end, we analyze TDMA in the context of measurement-based PTA (MBPTA) and show that padding execution time observations conveniently leads to trustworthy and tight WCET estimates with MBPTA without introducing any hardware change. In fact, TDMA outperforms round-robin and time-randomized policies in terms of WCET in the context of MBPTA.

Safety-critical systems demand increasing computational power, which requests high-performance embedded systems. While commercial-of-the-shelf (COTS) processors offer high computational performance for a low price, they do not provide hardware support for fault-tolerant execution. However, pure software-based fault-tolerance methods entail high design complexity and runtime overhead. In this paper, we present an efficient software/hardware-based redundant execution scheme for a COTS ×86 processor, which exploits the Transactional Synchronization Extensions (TSX) introduced with the Intel Haswell microarchitecture. Our approach extends a static binary instrumentation tool to insert fault-tolerant transactions and fault-detection instructions at function granularity. TSX hardware support is used for error containment and recovery. The average runtime overhead for selected SPEC2006 benchmarks was only 49% compared to a non-fault-tolerant execution.

The rise of multicore processors for industrial embedded control applications forces companies to face the challenge of replacing legacy single-core applications by multithreaded programs. We present a systematic and tool-supported approach starting with existing single-core code and transforming it into multi-threaded code such that timing analysis is preserved and eased. The approach is based on (a) scheduling periodic tasks onto multiple dedicated cores as well as (b) executing other code parts after a model-based parallelization, which introduces structured parallelism only, on the remaining cores. The main advantage of our approach compared to a re-implementation is a strongly reduced effort for implementation and testing because of the reuse of existing code. The approach is demonstrated and evaluated for the control code of a foundation crane; slack time is introduced as measurement for the effectiveness.

Bootstrapping of embedded computers is often neglected in real-time research. Nevertheless certain real-time applications even require predictable startup times, e.g. in the case of system restarts during operation due to some fault conditions. The complexity of bootstrapping will increase in upcoming manycore processors that utilise distributed memories and networks-on-chip (NoCs), as all cores must be provided with their code and data. We propose a new approach for bootstrapping a real-time manycore processor and compare it with two state-of-the-art approaches. Moreover, we present the mwsim tool that finds an upper timing bound through an abstract simulation of the boot process and apply it for the analysis of the worst-case duration of the three approaches. The results show an advantage of up to 23% of our newly proposed approach. They show also that the performance of a real-time NoC poses a central bottleneck to the overall performance of the boot process. We discuss these results and point out possible solutions to circumvent the bottleneck.

The enormous growth in integration density enables to build processors with more and more cores on a single die, but also makes them orders of magnitude more vulnerable to faults due to voltage fluctuation, radiation, and process variations [4] etc. Since this trend will continue in the future, fault-tolerance mechanisms must be an essential part of such future systems if the computations are to be carried out on a reliable basis. Already, chip manufacturers have taken measures to handle faults in current multi-core processors such as error correcting codes for busses, caches etc. With a huge number of cores, common strategies like dual modular and triple modular redundant processing [5] along with massive parallel computing are possible. Threaded dataflow execution models are one way to exploit the parallelism of future 1000 core systems. Current GPU architectures reflect that [3]. The side-effect free execution of threads within the dataflow execution model can not only be used to provide massive parallel computational capacity, but also enables simple and efficient rollback mechanisms [16]. In this paper, we describe fault detection and tolerance mechanisms investigated within the TERAFLUX EC project [17], which offers a solution to exploit the massive parallelism offered by dataflow architectures at all abstraction levels.

This paper presents a novel fault localization approach for NoCs by leveraging so called timed heartbeat messages. While these messages are periodically sent to report health states of processor cores to a fault detection unit, information about the network health state (topology) can be extracted from their timing behavior. We show how this health state information can be easily extracted from the message arrival times and give an estimation of the expected costs for this technique.

The EC project parMERASA investigates techniques for the parallelization of industrial real-time applications from automotive, avionic, and construction machinery domains. The aim is to execute such applications on many-core processors with up to 64 cores. The system software plays a key role in the deployment of applications. However, requirements of application domains differ widely, and thus no general solution can be implemented. In this paper we present the cross-domain system architecture utilized in the parMERASA project to provide Runtime Environments (RTEs) for the three different domains. The approach eases the implementation of domain-specific RTEs through a generic kernel library that provides basic hardware abstractions and timing-analyzable synchronization mechanisms.

In this paper, we utilise transactional memory (TM) to limit interferences of concurrent hard real-time (HRT) and best-effort (BE) tasks in a shared memory multi-core. We first propose a way to calculate the worst-case execution time (WCET) bound of HRT transactions when the set of concurrent transactions is known. In the next step we enhance our TM contention manager to prioritise transactions depending on their real-time requirements. With our approach it is possible to bound the interferences of any BE transaction and thus ensure a predictable execution of concurrently running HRT transactions. Our evaluation shows that the impact of BE tasks on the WCET bound of HRT tasks is minimal, while allowing them to share data.

In the billion transistor era only a few architectural approaches propose new paths to improve the execution of conventional sequential instruction streams. Many legacy applications could profit from processors that are able to speed-up the execution of sequential applications beyond the performance of current superscalar processors. The Grid arithmetic logic unit (ALU) Processor (GAP) accelerates conventional sequential instruction streams without the need for recompilation. The GAP comprises a processor front-end similar to that of a superscalar processor extended by a configuration unit and a two-dimensional array of functional units that forms the execution unit. Instruction sequences are mapped dynamically into the array by the configuration unit so that they form the dataflow graph of the sequence. This study shows a performance evaluation of the GAP architecture with different array dimensions as well as its performance using a simplified interconnection network. GAP outperforms an out-of-order superscalar processor by a maximum of factor 2 with a complete crossbar interconnect between two array rows. Reducing the interconnection network to the minimum shows a maximum performance drawback of 10% for only a particular configuration and a single benchmark. In general, the slowdown is less than 2% for the minimum interconnect (two buses) and about 0.02% if three interconnection buses are used.

Open, heterogeneous multi-agent systems (MAS) have to cope with a variety of uncertainties introduced by the systems' participants and their environment. In such systems, agents can use trust values that characterize the behavior of their interaction partners as a measure of uncertainty, allowing agents to make more appropriate decisions. However, because of the systems' dynamics and the agents' limited knowledge, the accuracy of these trust values is often limited as well, introducing another form of uncertainty. In this paper, we present confidence as a general concept to indicate the degree of certainty that a trust value describes the actual observable behavior of an agent. On the basis of three open MAS, we identify different criteria the confidence depends on by revealing situations in which trust values can be inaccurate and therefore impair an agent's decision. By means of scenarios, we show that a trust-aware agent can increase its own utility when its decisions are based on the confidence in trust values.

The multicore era in automotive computing is just starting. Meanwhile, processor technology in high-performance domains is advancing from shared memory to message-passing multicore processors. In this paper we present an approach on implementing AUTOSAR OS on such a message-passing multicore processor. We show where AUTOSAR semantic can be preserved, and if not, point out solutions.

Instruction memories have a large influence on the timing behavior of hard real-time systems. Thus, to obtain safe and tight WCET estimates the instruction memory has to be predictable. Instruction memories in embedded real-time systems range from scratchpads with fixed content to dynamically managed fine-grained caches. In this paper we focus on a function-based dynamic instruction memory (D-ISP) and examine different replacement policies. We show their influence on the timing behavior of a hard real-time system and the complexity of a hardware implementation. A timing analysis unveils that a stack-based replacement policy reaches similar WCET estimates as LRU, especially for small scratchpad sizes. But in contrast to the stack-based replacement policy, LRU cannot be implemented with a reasonable amount of resources. Whereas, an experimental implementation of the proposed stack-based replacement policy needs only up to 23% more resources than a FIFO implementation.

State-of-the-art Network on Chips (NoCs) provide a high throughput and low latency by sending packets of data through a mesh topology, using virtual channels and wormhole flow control. The downside of this technology is a high area and energy consumption due to many buffers, large crossbars and a complex arbitration logic within the routers.In our approach, we avoid flow control and complex analysis of the head flit by sending single standalone flits instead of large packets of flits. As the order of flits is preserved between sending and receiving node, large data blocks can be sent anyway. The complexity of the router is further reduced by using an unidirectional 2D torus instead of a mesh, which reduces the number of router ports from 5 to 3. The flits are X-Y-routed and transported bufferless, as long as they stay within one dimension. Consequently there is only one FIFO per router, which buffers flits when they turn from X to Y direction. In terms of throughput and latency the so-called paternoster router is comparable with a conventional router with two virtual channels, but it consumes 50% less energy and 60% less area.

Organic Computing Systems feature self-organizing techniques to manage the rising complexity of distributed systems. This paper introduces an implementation of self-configuration, self-healing and self-optimization by means of an Organic Manager. The Organic Manager is based on an automated planner and integrated in a middleware. The Organic Manager unites formerly distributed self-x features to use synergetic effects. An evaluation with four scenarios compares the behavior of the system under two different planning models. We show that an automated planner can lead to an optimized system quickly and reliably.

Future computing systems (Teradevices) will probably contain more than 1000 cores on a single die. To exploit this parallelism, threaded dataflow execution models are promising, since they provide side-effect free execution and reduced synchronization overhead. But the terascale transistor integration of such chips make them orders of magnitude more vulnerable to voltage fluctuation, radiation, and process variations. This means reliability techniques have to be an essential part of such future systems, too.In this paper, we conceptualize a fault tolerant architecture for a scalable threadeddataflow system. We provide methods to detect permanent, intermittent, and transientfaults during the execution. Furthermore, we propose a recovery technique for dataflow threads.

Recent computer architectures can be configured in lots of different ways. To explore this huge design space, system simulators are typically used. As performance is no longer the only decisive factor but also e.g. power usage or the resource usage of the system it became very hard for designers to select optimal configurations. In this article we use a multi-objective design space exploration tool called FADSE to explore the vast design space of the Grid Alu Processor (GAP) and its post-link optimizer called GAPtimize. We improved FADSE with techniques to make it more robust against failures and to speed up evaluations through parallel processing. For the GAP, we present an approximation of the hardware complexity as second objective besides execution time. Inlining of functions applied as a whole program optimization with GAPtimize is used as example for a code optimization. We show that FADSE is able to thoroughly explore the design space for both GAP and GAPtimize and it can find an approximation of the Pareto frontier consisting of near-optimal individuals in moderate time.

Multicore processors can deliver higher performance than single-core processors by exploiting thread level parallelism (TLP): applications are split into independent threads, each of which is mapped into a different core, reducing the execution time and potentially its worst-case execution time (WCET). Unfortunately, inter-thread interferences generated by simultaneous accesses to shared resources from different threads may completely destroy the performance benefits brought by TLP. This paper proposes a software/hardware cache partitioning approach that reduces the inter-thread memory interferences generated in hard real-time software-pipelined parallel applications. Our results show that our approach effectively reduces memory interferences, while still guaranteeing a predictable timing behaviour, achieving a WCET estimation reduction of 28% for a software pipelined version of the LU decomposition application with respect to the single-threaded version.

Reputation is an important aspect of trust. If no direct trust experiences are available, one needs to rely on reputation data from other sources. In this paper we present the Neighbor-Trust metric that exploits these communication capabilities of a network by directly asking all neighbors of a target communication partner for reputation trust data. This results in a reputation path of length one, but also in a vulnerability to attacks by unknown, lying entities that try to promote not trustworthy entities. However, by adding weights for reputation data given by entities and a learning mechanism the Neighbor-Trust metric is able to identify and adapt to lying participants in the network by reducing the weight their reputation data has in future reputation calculations. We present an evaluation for the metric and show how to exclude lying participants from the network.

Multi-cores are the contemporary solution to satisfy high performance and low energy demands in general and embedded computing domains. However, currently available multi-cores are not feasible to be used in safety-critical environments with hard real-time constraints. Hard real-time tasks running on different cores must be executed in isolation or their interferences must be time-bounded. Thus, new requirements also arise for a real-time operating system (RTOS), in particular if the parallel execution of hard real-time applications should be supported. In this paper we focus on the MERASA system software as an RTOS developed on top of the MERASA multi-core processor. The MERASA system software fulfils the requirements for time-bounded execution of parallel hard real-time tasks. In particular we focus on thread control with synchronisation mechanisms, memory management and resource management requirements. Our evaluations show that all system software functions are time-bounded by a worst-case execution time (WCET) analysis.

This paper proposes a new algorithm called SDS for solving distributed constraint satisfaction problems in wireless sensor networks. It introduces minimal overhead by using piggybacking for information dissemination and is naturally insusceptible against message loss. Partitioning into coordinating cliques has been used to demonstrate the feasibility of our approach.

Theoretical real-time research generally neglects context switch times. But in recent embedded applications which consist of dozens of threads with very short execution times, their impact is too serious to be ignored. We present a hard real-time scheduling algorithm that perfectly hides the context switch times of an arbitrary number of threads. It requires a Simultaneous Multithreaded (SMT) processor with at least two hardware thread slots and achieves a utilisation of 100%. The schedulability test is the same as for Earliest Deadline First (EDF) with a context switch time of zero. The hard real-time threads are executed alternately in the two slots of the processor. The inactive slot is used to unload the preceding thread context to memory and to load the subsequent thread context from memory. By hardware the active slot is completely isolated, in order to avoid any influence of the context switch on the execution of the active thread. This isolation is extensive, hence if further SMT thread slots are available, they can be used to execute threads with lower real-time demands. Even the context switch hardware can be re-used for them, enabling a very high throughput of mixed real-time task sets.

Currently few architectural approaches propose new paths to raise the performance of conventional sequential instruction streams in the time of the billions transistor era. Many application programs could profit from processors that are able to speed up the execution of sequential applications beyond the performance of current super scalar processors. The Grid Alu Processor (GAP) is a runtime reconfigurable processor designed for the acceleration of a conventional sequential instruction stream without the need of recompilation. It comprises a super scalar processor front-end, a configuration unit, and an array of reconfigurable functional units (FUs), which is fully integrated into the pipeline. The configuration unit maps data dependent and independent instructions simultaneously at runtime into the array of FUs. This paper evaluates the GAP architecture and optimizes the architecture, the number of FUs, and the configuration layers implemented in the array. The simulations show a significant speed-up for sequential applications on GAP in comparison to an out-of-order super scalar simulator (Simple Scalar). The GAP simulator outperforms Simple Scalar on average by about 50% on the basic architecture and about 100% with an extended version including configuration layers.

Organic Computing (OC) systems differ from classical software systems as the topology and the participating components of the system are not predefined and therefore are subject to unforeseeable change during the systems' runtime. Thus, completely new challenges to the verification and validation of such systems as well as for interactions between system components and, of course, between the system and the user arise. These challenges can be subsumed by the terms trustworthiness or trust. This paper proposes - after exploring the notions and principles of trust in the literature - a definition of trust which encompasses all aspects that define the trustworthiness of an Organic Computing system. It then outlines the different research challenges that have to be tackled in order to provide an understanding of trust in OC-systems and gives perspectives on how this endeavour can be taken on. Current research initiatives in the area of trust in computing systems are reviewed and discussed.

Ubiquitous and pervasive computing envisions context-aware systems that gather real-world information from many fixed and mobile microchips and sensors integrated in everyday objects. To provide valuable services, it is necessary to estimate the location of users or objects. Outdoor location tracking is achieved by Global Positioning System (GPS), but due to its poor indoor coverage, there is a need for alternative technologies in buildings. Since multiple wireless sensors may be situated in the environment, they can be used for location estimation and tracking. This paper presents LocSens, a cost-effective location tracking system based on sensor nodes with wireless connectivity. LocSens works with a minimum number of sensor nodes. It is established and tested in a real indoor scenario over multiple rooms. LocSens could be improved by optimising algorithms and using more precise sensor boards. Results confirm gained accuracy in location estimation and tracking of moving objects.

The increasing complexity of computer-based technical systems requires new ways to control them. The initiatives Organic Computing and Autonomic Computing address exactly this issue. They demand future computer systems to adapt dynamically and autonomously to their environment and postulate so-called self-* properties. These are typically based on decentralized autonomous cooperation of the system's entities. Trust can be used as a means to enhance cooperation schemes taking into account trust facets such as reliability. The contributions of this paper are algorithms to manage and query trust information. It is shown how such information can be used to improve self-* algorithms. To quantify our approach evaluations have been conducted.

Ubiquitous and pervasive computing envisions context-aware systems that gather real world information from many fixed and mobile microchips and sensors integrated in everyday objects. To provide valuable services, it is necessary to estimate the location of users or objects. Outdoor location tracking is achieved by Global Positioning System (GPS), but due to its poor indoor coverage, there is a need for alternative technologies in buildings. Since multiple wireless sensors may be situated in the environment, they can be used for location estimation and tracking. This paper presents LocSens, a cost-effective location tracking system based on sensor nodes with wireless connectivity. LocSens works with a minimum number of sensor nodes. It is established and tested in a real indoor scenario over multiple rooms. This paper describes results of several location estimation algorithms and experiences with tracking of moving objects.

The increasing complexity of computer-based technical systems require new ways to control them. The initiatives Organic Computingand Autonomic Computingaddress exactly this issue. They demand future computer systems to adapt dynamically and autonomously to their environment. In this paper we propose a new approach based on automated planning to realise self-organising capabilities for complex distributed computing systems. The user/administrator only defines objectives describing the conditions which should hold in the system, whereas the system itself is responsible for meeting them using a planning engine. As many planning algorithms are known to be sound and complete, formal guarantees can be given. Thus we aim at building trusted self-organising distributed computer system which are suitable to control real technical systems. Our approach is demonstrated and evaluated on the basis of a simulated production cell with robots and carts. We propose and evaluate two optimisations.

Failure detectors are a fundamental part of safe fault-tolerant distributed systems. Many failure detectors use heartbeats to draw conclusions about the state of nodes within a distributed environment. The contribution of this paper is an approach whose benefits are twofold. On the one hand it reduces the network overhead produced by heartbeat-style failure detectors. On the other hand it improves the quality of these failure detectors by providing them with richer information about the current network condition. We call this approach lazy monitoring since the active sending of heartbeats is avoided if possible. As it is independent of the actual failure detection algorithm it can be used in many domains. For evaluation purposes we applied our approach to the Smart Doorplate Project. In this testbed the proposed technique reduced the traffic to 1.2% while providing much more information about the environment to the failure detectors.

We developed an SMT processor that allows a static WCET analysis of several hard real-time threads and uses the remaining resources for soft or non real-time threads. The analysis is possible, because one Dominant Meta Thread (DMT) is executed as if it were the unique thread on the processor and thus single-threaded WCET techniques can be applied. To provide more than one hard real-time thread the execution time of the Dominant Meta Thread is distributed by time sharing whereby the length of the time slices and periods can be adjusted at runtime. Our technique, called Dominant Time Sharing (DTS), can be used to minimize the number of control units in embedded hard real-time systems and hence reduces the overall energy consumption and material demand. In contrast to many other studies we are able to handle multicycle memory latencies while preserving analyzability. The proposed technique can easily be extended to access other external resources like coprocessors or reconfigurable arrays.

The concepts of Autonomic and Organic Computing (AC/OC) promise to make modern computer systems more secure and easier to manage. In this paper, we extend the observer/controller architecture typically used in AC/OC systems towards a new target area --- embedded real-time systems. As a result we present a two-layered management architecture. We discuss aspects of internal communication and design a communication model. Finally, we present a generic classification system for the upper layer of the management architecture.

Grid and ubiquitous computing systems generally consist of a large number of networked nodes with applications implemented as distributed services or processes, respectively. A crucial point is the distribution of the services to balance the load within the system during runtime. In a former work we developed a self-optimization mechanism which shows outstanding performance in static environments where the services do not change their resource consumptions (e.g. CPU, memory, communication bandwidth). In this paper we present simulation results for the self-optimization within dynamic environments where the services change their load during runtime.

This paper proposes a processor core that allows to support the autonomic computing principles in embedded hard-real-time systems. The simultaneous multithreaded CAR-core processor features hardware-integrated scheduling schemes that isolate the hard-real-time thread from non-real-time threads. It is binary compatible with Infineon's TriCore processor and designed as IP core for a system-on-chip. The challenge for the processor design is to implement simultaneous multithreading such that a thread cannot influence the timing behavior of another thread in order to allow predictable thread execution times. Therefore new instruction issue and data memory access techniques are proposed. The autonomic computing requirements shall be implemented by autonomic managers running as helper threads in own thread slots concurrent to the real-time application. The autonomic manager threads monitor the application and decide if self-configuration, self-healing, self-optimization, or self-protection must be triggered