Experiment Source Code and Raw Data
This page gives the source code and raw data used to produce various publications. All of these papers were produced using the resources of the RTS Lab. They are organised by order of publication, most recent first. For each paper, we give the title, authors, abstract, and links to download source code and a PDF where possible.
Unless stated otherwise, the required software platform is a recent Linux system (i386 or x86_64). Some experiments require FPGA hardware and tools from Xilinx, but it is usually possible to reproduce the results with only the MicroBlaze GCC compiler.
Evaluating Mixed Criticality Scheduling Algorithms with Realistic Workloads
David Griffin, Iain Bate, Benjamin Lesage, Frank Soboczenski
WMC 2015
Software package (v1.0)
Software package (old version)
This software package contains mc_taskset_simulator, an efficient multi-threaded simulator for evaluating mixed criticality scheduling policies. It can generate task utilisations through a variety of means, including the DepET-RND algorithm.
Modelling Fault Dependencies when Execution Time Budgets are Exceeded
David Griffin, Benjamin Lesage, Frank Soboczenski, Iain Bate
RTNS 2015
This software package contains fm2, a forecast-based exceedance model generator, and DepET, a task execution time generator utilising fm2 models.
Reducing the Implementation Overheads of IPCP and DFP
Hesham Almatary, Neil Audsley, Alan Burns
RTSS 2015
effecient-ipcp-linux4-glibc2.21.zip
Explicit Reservation of Cache Memory in a Predictable, Preemptive Multitasking Real-time System
Jack Whitham, Neil Audsley, Rob Davis
ACM TECS
We describe and evaluate explicit reservation of cache memory as a way of reducing the cache-related preemption delay (CRPD) which is observed when tasks share a cache in a preemptive multitasking hard real-time system. We present exact and sufficient schedulability analyses for systems that share a cache by explicit reservation, and use these analyses as the basis for a series of experiments to evaluate the approach. We find that explicit reservation is most useful for large task sets with high utilization. Some task sets cannot be safely scheduled with a conventional cache, but are schedulable with explicit reservation.
Investigation of Scratchpad Memory for Preemptive Multitasking
Jack Whitham, Sebastian Altmeyer, Rob Davis, Neil Audsley, Claire Maiza
RTSS 2012
paper.pdf
msrs-dist-3.tar.bz2
qemu-patch (used for measurements)
We present a multitasking scratchpad memory reuse scheme (MSRS) for the dynamic partitioning of scratchpad memory between tasks in a preemptive multitasking system. We specify a means to compute the worst-case response time (WCRT) and schedulability of task sets executed using MSRS. Our scratchpad-related preemption delay (SRPD) is an analog of cache-related preemption delay (CRPD), proposed in previous work as a way to compute the worst-case cost imposed upon a preempted task by preemption in a multitasking system. Unlike CRPD, however, SRPD is independent of the number of tasks and the local memory size.
We compare SRPD with CRPD by experiment and determine that neither dominates the other, i.e. either may be better for certain task sets. However, MSRS leads to improved schedulability versus cache when contention for local memory space is high, either because the local memory size is small, or because the task set is large, provided that the cost of loading blocks from external memory to scratchpad is similar to the cost of loading blocks into cache.
Lossy Compression for Must/May Analysis of Tree Based Caches
David Griffin, Alan Burns
Journal of Real Time Systems
PLRUFullTreeSourceCode.tar.bz2
A PLRU cache is considered to be harder to analyse than an LRU cache from a traditional point of view, because the physical representation of such a cache is more complex than an LRU cache. This paper explores a non-traditional approach for deriving simplifications of cache states based on information theory and lossy compression. By arguing about the value of each bit of information within a PLRU cache, and choosing to loose only that which is least useful to the analysis, this paper demonstrates a full Must/May analysis for the PLRU cache. Further, the same technique is applied to generalise the method to the case of the HNMRU cache.
Optimal Program Partitioning for Predictable Performance
Jack Whitham, Neil Audsley
ECRTS 2012
Scratchpad memory (SPM) provides a predictable and energy efficient way to store program instructions and data. It would be ideal for embedded real-time systems if not for the practical difficulty that most programs have to be modified in source or binary form in order to use it effectively. This modification process is called partitioning, and it splits a large program into sub-units called regions that are small enough to be stored in SPM.
Earlier papers on this subject have only considered regions formed around program structures, such as loops, methods and even entire tasks. Region formation and SPM allocation are performed in two separate steps. This is an approximation that does not make best use of SPM.
In this paper, we propose a k-partitioning algorithm as a new way to solve the problem. These allow us to carry out region formation and SPM allocation simultaneously. We can generate optimal partitions for programs expressed either as call trees or by a restricted form of control-flow graph (CFG). We show
Explicit Reservation of Local Memory in a Predictable, Preemptive Multitasking Real-time System
Jack Whitham, Neil Audsley
RTAS 2012
carousel.pdf
carousel-software-1.tar.bz2
This paper proposes Carousel, a mechanism to manage local memory space, i.e. cache or scratchpad memory (SPM), such that inter-task interference is completely eliminated. The cost of saving and restoring the local memory state across context switches is explicitly handled by the preempting task, rather than being imposed implicitly on preempted tasks. Unlike earlier attempts to eliminate inter-task interference, Carousel allows each task to use as much local memory space as it requires, permitting the approach to scale to large numbers of tasks.
Carousel is experimentally evaluated using a simulator. We demonstrate that preemption has no effect on task execution times, and that the Carousel technique compares well to the conventional approach to handling interference, where worst-case interference costs are simply added to the worst-case execution times (WCETs) of lower-priority tasks.
Time-Predictable Out-of-Order Execution for Hard Real-Time Systems
Jack Whitham, Neil Audsley
IEEE Transactions on Computers, volume 59, number 9, pages 1210-1223, 2010, 10.1109/TC.2010.109
Download paper from IEEE (paywall)
Download software and additional information.
Superscalar out-of-order CPU designs can achieve higher performance than simpler in-order designs through exploitation of instruction-level parallelism in software. However, these CPU designs are often considered to be unsuitable for hard real-time systems because of the difficulty of guaranteeing the worst-case execution time (WCET) of software. This paper proposes and evaluates modifications for a superscalar out-of-order CPU core to allow instruction-level parallelism to be exploited without sacrificing time predictability and support for WCET analysis. Experiments using the M5 O3 CPU simulator show that WCETs can be two-four times smaller than those obtained using an idealized in-order CPU design, as instruction-level parallelism is exploited without compromising timing safety.
Investigating average versus worst-case timing behavior of data caches and data scratchpads
Jack Whitham, Neil Audsley
ECRTS 2010
Software downloads and additional information.
This paper shows that a program using a time predictable memory system for data storage can achieve a similar worst-case execution time (WCET) to the average-case execution time (ACET) using a conventional heuristic-based memory system including a data cache. This result is useful within any embedded system where time-predictability and performance are both important, particularly hard real-time systems carrying out intensive data processing activities. It is a counter-example to the conventional wisdom that time-predictable means “slow” in comparison to ACET-focused heuristics. To carry out the investigation, 36 “memory access models” are derived from benchmark programs and assumed to be representative of typical code. The models generate LOAD/STORE instructions to exercise a data cache or scratchpad memory management unit (SMMU). The ACET is determined for the data cache and the WCET is determined for the SMMU. After improvements are applied, results show that the SMMU WCET is within 5% of the data cache ACET for 34 models. In 16 of 36 cases, the SMMU WCET is better than the data cache ACET.