Traffic shaping is a well-known technique in the area of networking and is proven to reduce global buffer requirements and end-to-end delays in networked systems. Due to these properties, shapers also play an increasingly important role in the design of multiprocessor embedded systems that exhibit a considerable amount of on-chip traffic. Despite the growing importance of traffic shapping in this area, no methods exist for analyzing shapers in distributed embedded systems and for incorporating them into a system-level performance analysis. Until now it was not possible to determine the effect of shapers on end-to-end delay guarantees or buffer requirements in such systems. In this work, we present a method for analyzing greedy shapers, and we embed this analysis method into a well-established modular performance analysis framework for real-time embedded systems. The presented approach enables system-level performance analysis of complete systems with greedy shapers, and we prove its applicability by analyzing three case study systems.

System level performance analysis plays a fundamental role in the design process of real-time embedded systems. Several different approaches have been presented so far to address the problem of accurate performance analysis of distributed embedded systems in early design stages. The existing formal analysis methods are based on essentially different concepts of abstraction. However, the influence of these different models on the accuracy of the system analysis is widely unknown, as a direct comparison of performance analysis methods has not been considered so far. We define a set of benchmarks aimed at the evaluation of performance analysis techniques for distributed systems. We apply different analysis methods to the benchmarks and compare the results obtained in terms of accuracy and analysis times, highlighting the specific effects of the various abstractions. We also point out several pitfalls for the analysis accuracy of single approaches and investigate the reasons for pessimistic performance predictions.

We present an analytic method to determine the provably smallest possible slot length that must be allocated in a TDMA resource, to serve an event-triggered hard real-time load with arbitrary deterministic timing behavior. Based on this method, we then present constructive methods to find all feasible as well as the optimal cycle length in a TDMA resource, and we show how to determine the minimum required bandwidth of a TDMA resource. We demonstrate the applicability and computational efficiency of the presented methods in a case study of a large distributed embedded system with a TDMA bus, where we find the optimal parameter set for the TDMA bus

Traffic shaping is a well-known technique in the area of networking and is proven to reduce global buffer requirements and end-to-end delays in networked systems. Due to these properties, shapers also play an increasingly important role in the design of multi-processor embedded systems that exhibit a considerable amount of on-chip traffic. Despite their growing importance in this area, no methods exist to analyze shapers in distributed embedded systems, and to incorporate them into a system-level performance analysis. Hence it is until now not possible to determine the effect of shapers to end-to-end delay guarantees or buffer requirements in these systems. In this work, we present a method to analyze greedy shapers, and we embed this analysis method into a well-established modular performance analysis framework. The presented approach enables system-level performance analysis of complete systems with greedy shapers, and we prove its applicability by analyzing two case study systems

Recently, a number of frameworks were proposed to extend interface theory to the domains of single-processor and distributed real-time systems. This paper unifies some of these approaches and proves properties like refinement and independent implementability. We also explicitly state the requirements to a framework for these properties to be fulfilled. Further, a new notion of adaptive interfaces is introduced that supports the design by providing mechanisms for propagating system constraints, such as (end-to-end) delays, available computing and communication resources, buffer spaces, and energy. Guarantees and assumptions on interfaces are not any longer static but adapt according to the system environment. This can be used to answer synthesis questions at design time or to adapt system parameters to changing environment requirements at run-time. The applicability of the presented framework is proven by adapting it to a number of different real-time analysis models.

Interface-based design is now considered to be one of the keys to tackling the increasing complexity of modern embedded systems. The central idea is that different components comprising such systems can be developed independently and a system designer can connect them together only if their interfaces match, without knowing the details of their internals. We use the concept of rate interfaces for compositional (correct-by-construction) design of embedded systems whose components communicate through data streams. Using the associated rate interface algebra, two components can be connected together if the output rate of one component is "compatible" with the input rate of the other component. We formalize this notion of compatibility and show that such an algebra is non-trivial because it has to accurately model the burstiness in the arrival rates of such data streams and the variability in their processing requirements. We discuss how rate interfaces simplify compositional design and at the same time help in functional and performance verification which would be difficult to address otherwise. Finally, we illustrate these advantages through a realistic case study involving a component-based design of a multiprocessor architecture running a picture-in-picture application

System level performance analysis techniques play an important role in the design process of complex embedded systems. They allow to analyze essential characteristics of a system design in an early design stage and support therewith the choice of important design decisions. While analytical methods for system level performance analysis lead to hard bounded analysis results, the obtained results are often overly pessimistic due to a lack of details such analytical methods can incorporate in their system analysis. To overcome this problem, we present new abstract models for event streams and system components of embedded systems, and show how these models can be combined to modules for modular performance analysis. With the presented models, we can capture complex functional properties of systems, as for example caches, variable resource demand of events in an event stream, or arbitrary up- and down-sampling of event streams in a system component. The applicability of our models and their advantages over traditional models for performance analysis are shown in a case study of a system component with LRU (Least Recently Used) cache.

The central idea behind interface-based design is to describe components by a component interface. In contrast to a component description that describes what a component does, a component interface describes how a component can be used. A well designed component interface provides enough information to decide whether two or more components can work together properly in a system. In this work, we expand the idea of interface-based design to the area of real-time system design. Here, the term of 'working together properly' refers to questions like: Does the composed system satisfy all requested real-time properties such as delay and throughput constraints? For this, we introduce Real-Time Interfaces, that connect the principles of Real-Time Calculus with Interface-based Design. In contrast to traditional real-time system design, in interface-based real-time system design the compliance to real-time constraints is checked at composition time. This leads to faster design processes and partly removes the need for the classical binary search approach to find an economically dimensioned system. Further, interface-based real-time system design also benefits from the properties of incremental design and independent implementability.

Modern embedded systems are typically integrated as multiprocessor system on chips, and are often characterized by the complex behaviors and dependencies that system components exhibit. Different events that trigger such systems normally cause different execution demands, depending on their event type as well as on the task they are processed by, leading to complex workload correlations. For example in data processing systems, the size of an events payload data will typically determine its execution demand on most or all system components, leading to highly correlated workloads. Performance analysis of such complex system is often very difficult, and conventional analysis methods have no means to capture the possible existence of workload correlations. This leads to overly pessimistic analysis results, and thus to too expensive system designs with considerable performance reserves. We propose an abstract model to characterize and capture workload correlations present in a system architecture, and we show how the captured additional system information can be incorporated into an existing framework for modular performance analysis of embedded systems. We also present a method to analytically obtain the proposed abstract workload correlation model from a typical system specification. The applicability of our approach and its advantages over conventional performance analysis methods is shown in a detailed case study of a multiprocessor system on chip, where the analysis results obtained with our approach are considerably improved compared to the results obtained with conventional analysis methods.

We present an interface theory based approach to static analysis of actor models. We first introduce a new interface theory, which is based on interface automata, and which is capable of counting with numbers. Using this new interface theory, we can capture temporal and quantitative aspects of an actor interface as well as an actor's token exchange rate. We will show, how to extract this information from actors written in the cal actor language (CAL), and we also present a method to capture the interface information as well as the structure of dataflow models into an interface automaton. This automaton acts as glue between the automata of all actors in the model, and by successfully composing all actor automata with it, we can prove interface compatibility of all actors with the composition framework. After successful composition, the resulting automaton will contain information that can be used for further static analysis of the composite actor model.

Many real-time embedded systems process event streams which are composed of a finite number of different event types. Each different event type on the stream would typically impose a different workload to the system, and thus the knowledge of possible correlations and dependencies between the different event types could be exploited to get tighter analytic performance estimations of the complete system. We propose an abstract stream model to characterize such an event stream. The model captures the needed information of all possible traces of a class of event streams and can hence be used to obtain hard bounded worst-case and best-case estimations of a system. We show how the proposed abstract stream model can be obtained from a concrete stream specification, and how it can be used for performance analysis. The applicability of our approach and its advantages over traditional worst-case performance analysis are shown in a case study of a multimedia application.