Logo: to the web site of Uppsala University

Real-time Calculus (RTC) is a non-stochastic queuing theory to the worst-case performance analysis of distributed real-time systems. Workload as well as resources are modelled as piece-wise linear, pseudo-periodic curves and the system under investigation is modelled as a sequence of algebraic operations over these curves. The memory footprint of computed curves increases exponentially with the sequence of operations and RTC may become computationally infeasible fast. Recently, Finitary RTC has been proposed to counteract this problem. Finitary RTC restricts curves to finite input domains and thereby counteracts the memory demand explosion seen with pseudo periodic curves of common RTC implementations. However, the proof to the correctness of Finitary RTC specifically exploits the operational semantic of the greed processing component (GPC) model and is tied to the maximum busy window size. This is an inherent limitation, which prevents a straight-forward generalization. In this paper, we provide a generalized Finitary RTC that abstracts from the operational semantic of a specific component model and reduces the finite input domains of curves even further. The novel approach allows for faster computations and the extension of the Finitary RTC idea to a much wider range of RTC models.

Messages traversing a network commonly experience waiting times due to sharing the forwarding resources. During those times, the crossed systems must provide sufficient buffer space for queueing messages. Network Calculus (NC) is a mathematical methodology for bounding flow delays and system buffer requirements. The accuracy of these performance bounds depends mainly on two factors: the principles manifesting in the NC flow equation and the functions describing the system. We focus on the latter aspect. Common implementations of NC overapproximate these functions in order to keep the analysis computationally feasible. However, overapproximation often results in a loss of accuracy of the performance bounds. In this paper, we make such compromising tradeoffs between model accuracy and computational effort obsolete. We limit the accurate system description to functions of a compact domain, such that the accuracy of the NC analysis is preserved. Tying the domain bound to the algebraic operators of NC instead of the operational semantics of components, allows us to directly apply our solution to algebraic NC analyses that implement principles such as pay burst only once and pay multiplexing only once.

This paper proposes a scheme which drives a processor beyond its rated operation frequency, e.g., by exploiting Intel's boost technology, to digest the peak workload of the system in time. In the setting of deadline constrained workloads, this is far from trivial: the boost mode can only be used during short time spans, therefore it can only help to digest the peak workload, rather than serving the normal case. A lowered processor frequency, used outside the peak workload time, yields a backlog of not completed jobs. This backlog may result in deadline violations or buffer overflows, if the next burst of job arrivals appears too early. To overcome the above problem, we propose a peak workload aware speed assignment strategy, which only allows the system to build up computation backlog if the absence of high computation demands is assured. Contrasting the existing body of work, we take advantage of bursty arrival patterns of compute jobs, thereby progressing over the standard (non-bursty sporadic) job release model. Together with our scheme, we also present a tool chain and simulations of synthetic workloads for investigating the thermal effects of different speed assignment strategies.

The Dynamic Power and Thermal Management (DPTM) system of Dynamic Voltage Frequency Scaling (DVFS) enabled processors compensates peak temperatures by slowing or even powering parts of the system down. While ensuring the integrity of computations, this comes with the drawback of losing performance. In the context of hard real-time systems, such unpredictable losses in performance are unacceptable, as they may lead to deadline misses which may yet compromise the integrity of the system. To safely execute hard real-time workloads on such systems, this article presents an online scheme for assigning speeds in such a way that (a) the system executes at low clock speed as often as possible, while (b) deadline violations are strictly ruled out. The proposed scheme is compared with an offline scheme which has complete knowledge about arrival times and execution demands of the workload. The benchmarking shows that for a workload which is always very close to the modelled maximum, our approach performs on-par with the offline scheme. In case of a workload which diverges from the modelled maximum more often, the speed assignments produced by our scheme become more pessimistic, as to ensure that all deadlines are met.

To handle hot spots or power shortages, modern multicore processors are equipped with a supervisory dynamic thermal and power management (DTPM) system. When necessary, the DTPM system autonomously adapts the capacity of the cooling system or throttles the speed of core-local clocks via dynamic voltage and frequency scaling (DVFS) techniques. Opposed to best-effort scenarios, online DVFS with real-time workloads also needs to consider completion times of computations. Whereas execution times can be bounded adequately with worst-case estimates, arrival times of computation requests are potentially unknown. A deadline for completing a computation can easily be missed, if workloads suddenly peak and past clock speed assignments have built-up a non-negligible backlog of computations. To overcome this problem, we introduce an online DVFS management scheme which is history-aware. It operates a core at higher speed levels only if the future workload has the potential to result in timing violations, if not anticipated by rising clock speed assignments. We present an implementation of the scheme running on the GemS hardware simulator.

In modern multi-core systems with multiple real-time (RT) applications, memory traffic accessing the shared SDRAM is increasingly diverse, e.g., transactions have variable sizes. RT memory controllers with dynamic command scheduling can efficiently address the diversity by issuing appropriate commands subject to the SDRAM timing constraints. However, the scheduling dependencies between commands make it challenging to derive tight bounds for the worst-case response time (WCRT) and the worst-case bandwidth (WCBW) of a memory controller. Existing modeling and analysis techniques either do not provide tight WCRT and WCBW bounds for diverse memory traffic with variable transaction sizes or are difficult to adapt to different RT memory controllers. This paper models a memory controller using Timed Automata (TA), where model checking is applied for analysis. Our TA model is modular and accurately captures the behavior of a RT memory controller with dynamic command scheduling. We obtain WCRT and WCBW bounds, which are validated by simulating the worst-case transaction traces obtained by model checking with a cycle-accurate model of the memory controller. Our method outperforms three state-of-the-art analysis techniques. We reduce WCRT bound by up to 20%, while the average improvement is 7.7%, and increase the WCBW bound by up to 25% with an average improvement of 13.6%. In addition, our modeling is generic enough to extend to memory controllers with different mechanisms.

Multicore technology has the potential for drastically increasing productivity of embedded real-time computing. However, joint use of hardware, e.g., caches, memory banks and on-chip buses makes the integration of multiple real-time applications into a single system difficult: resource accesses are exclusive and need to be sequenced. Moreover, resource access schemes of modern off-the-shelf multicore chips are commonly optimized for the average-case, rather than being timing predictable. Real-time analysis for such architectures is complex, as execution times depend on the deployed hardware, as well as on the software executing on other cores. This will ask for significant abstractions in the timing analysis, where the resulting pessimism will lead to over-provisioned system designs and a lowered productivity as the number of applications to be put together into a single architecture needs to be decreased. In response to this, (a) we present a formal approach for bounding the worst-case response time of concurrently executing real-time tasks under resource contention and almost arbitrarily complex resource arbitration policies, with a focus on main memory as shared resource, (b) we present a simulation framework which allows for detailed modeling and empirical evaluation of modern multicore platforms and applications running on top of them, and (c) we present experiments to demonstrate the advantages and disadvantages of the presented methodologies and compare their accuracy. For limiting non-determinism inherent to the occurrence of cache misses, we particularly take advantage from the predictable execution model as discussed in recent works.