Invited Talks
-
Architectural Influence on the Timing Predictability
Reinhard Wilhelm (Universität des Saarlandes, Saarbrücken)
Abstract: Hard real-time systems need safe methods to determine the upper bound on their execution times. These bounds are obtained by a multi-phase approach, whose core is the static analysis of the hardware platform's behavior for the program under analysis.
The problem of determining upper bounds on execution times for single tasks and for quite complex processor architectures has been solved. Several commercial WCET tools are available and have experienced very positive feedback from extensive industrial use. This feedback concerned speed, precision of the results, and usability. The aiT timing-analysis tool has been used in the certification of several time-critical applications in the Airbus A380 and thereby has been accepted as a validated tool for these applications by the European Airworthiness Authorities.
The task to be analyzed attains its WCET on one (or sometimes several) of its possible execution paths. If the input and the initial state leading to the execution of this worst-case path were known, the problem would be easy to solve. The task would then be started in this initial state with this input, and the execution time would be measured. In general, however, this worst-case input and initial state are not known and hard or impossible to determine.
Processor-Behavior Analysis gathers information on the processor behavior for the given task, in particular the behavior of the components that influence the execution times, such as memory, caches, pipelines, and branch prediction. It determines upper bounds on the execution times of instructions or basic blocks.
The complexity of the processor-behavior analysis subtask and the set of applicable methods critically depend on the complexity of the processor architecture. We describe methods that are being used to solve the above mentioned subtasks of timing analysis.
The precision of the results of timing analyses strongly depend on the architecture of the used hardware platform. A large variance in the execution time of instructions is introduced by the processor's caches. A precise analysis of the cache behavior is mandatory for a precise overall timing analysis. The cache replacement strategy influences the results of cache behaviour prediction. We present results about the predictability properties of several cache architectures.
The instruction pipeline of modern high-performance processors has to be modeled in a conservative way with respect to the timing behavior. Out-of-order execution and control speculation increase the search space of potential execution orders whose upper bound has to be considered. This potentially extends the gap between the computed upper bound and the really occurring worst-case execution time. -
Understanding Gossiping in Distributed Systems
Maarten van Steen (Vrije Universiteit Amsterdam)
Abstract: Gossiping in distributed systems is receiving increasing attention for its excellent scalability properties. The phenomenon refers to the repeated probabilistic exchange of information between two nodes. Repetition and probailistic choice are two key elements: in principle, gossiping is the endless process of randomly choosing two members and subsequently letting these two exchange information. The effect is that information can spread within a group just as it would in real life.
Gossip-based solutions show a great deal of emergent behavior, and it is often unclear what the relationship is between a specific configuration of a gossiping protocol and its behavior. Likewise, we often see a difference between what theory would predict about a protocol and what happens in practice, notably when concentrating on extra-functional behavior such as reliability, robustness, and reactions to changes in node membership.
In this talk, I will highlight some of the recent results in this field of research, with an emphasis on the experimental evaluation of gossip-based systems. The intention is to make clear that we are dealing with a promising approach towards designing large-scale systems, yet that there is still much to do to increase our understanding of the observed emergent behavior.