For hard-real time systems, cache memory increases execution time variability, increasing the complexity of timing analysis. As such, cache memory is often treated exclusively as a detractor to schedulability. Cache-aware co-located scheduling aims at improving schedulability by carefully scheduling threads to share cached values. Cache sharing between threads potentially reduces task execution times and increases schedulability with fewer resources. Antithetically, co-located scheduling may reduce parallelism, decreasing efficiency. Thus, identifying the optimal set of threads to co-locate that minimizes the resources required while ensuring timing constraints is a complex challenge. This work establishes optimal co-location as NP-Hard in the strong sense. It offers an approximation method for the co-located scheduling of Fork-Join tasks named 3-parm-hd . The approximation has a 3-factor guarantee and a resource augmentation bound of 3. The simulated evaluation shows 3-parm-hd increases schedulability compared to an optimal intractable algorithm (without co-location) scheduling 28% more tasks with 30% fewer cores. Simulated results show 3-parm-hd outperforms a 2-factor approximation for traditional makespan, scheduling 45 % more tasks with 41% fewer cores. An experimental RISC-V evaluation running on a QEMU platform confirms the benefits of 3-parm-hd , scheduling and executing tasks deemed unschedulable by a 2-factor makespan approximation without co-location.

Safety-critical systems depend on the temporal guarantees provided by schedulability analysis of hard real-time systems. Worst-case execution time analysis (WCET) is a necessary component in schedulability analysis of hard real-time systems. A central goal of WCET analysis is to produce a tight bound, since tighter bounds (generally) increase the schedulability of a system. Cache memory is an impediment to tight WCET analysis due to the variability it introduces into task systems. However, static modification of memory access patterns within mutable objects may increase cache-hits and reduce WCET. Herein, a mechanism for modifying and analyzing hard real-time tasks is proposed. The proposed mechanism leverages existing persistence analysis to identify sets of blocks to retain in cache during execution. Retention guarantees persistence, resulting in tighter WCET analysis.

For hard-real time systems, cache memory increases execution time variability, increasing the complexity of timing analysis. As such, cache memory is often treated exclusively as a detractor to schedulability. Cache-aware co-located scheduling aims to improve schedulability by carefully scheduling threads to share cached values. Cache sharing between threads potentially reduces task execution times and increases schedulability with fewer resources. Antithetically, co-located scheduling may reduce parallelism, decreasing efficiency. Thus, identifying the optimal set of threads to co-locate that minimizes the resources required while ensuring timing constraints is a complex challenge. This work establishes optimal co-location as NP-Hard in the strong sense. It offers an approximation method for the co-located scheduling of Fork-Join tasks named 3-PARM-HD. The approximation has a 3-factor guarantee and a resource augmentation bound of 3. The simulated evaluation shows 3-PARM-HD increases schedulability compared to an optimal intractable algorithm (without co-location) scheduling 28% more tasks with 30% fewer cores. Simulated results show 3-PARM-HD outperforms a 2-factor approximation for traditional makespan, scheduling 39% more tasks with 44% fewer cores. An experimental RISC-V evaluation running on a QEMU platform confirms the benefits of 3-PARM-HD, scheduling and executing tasks deemed unschedulable by a 2-factor makespan approximation without co-location.

Multiprocessor scheduling of hard real-time tasks modeled by directed acyclic graphs (DAGs) exploits the inherent parallelism presented by the model. For DAG tasks, a node represents a request to execute an object on one of the available processors. In one DAG task, there may be multiple execution requests for one object, each represented by a distinct node. These distinct execution requests offer an opportunity to reduce their combined cache overhead through coordinated scheduling of objects as threads within a parallel task. The goal of this work is to realize this opportunity by incorporating the cache-aware BUNDLE-scheduling algorithm into federated scheduling of sporadic DAG task sets.This is the first work to incorporate instruction cache sharing into federated scheduling. The result is a modification of the DAG model named the DAG with objects and threads (DAG-OT). Under the DAG-OT model, descriptions of nodes explicitly include their underlying executable object and number of threads. When possible, nodes assigned the same executable object are collapsed into a single node; joining their threads when BUNDLE-scheduled. Compared to the DAG model, the DAG-OT model with cache-aware scheduling reduces the number of cores allocated to individual tasks by approximately 20 percent in the synthetic evaluation and up to 50 percent on a novel parallel computing platform implementation. By reducing the number of allocated cores, the DAG-OT model is able to schedule a subset of previously infeasible task sets.

The BUNDLE and BUNDLEP scheduling algorithms are cache-cognizant thread-level scheduling algorithms and associated worst case execution time and cache overhead (WCETO) techniques for hard real-time multi-threaded tasks. The BUNDLE-based approaches utilize the inter-thread cache benefit to reduce WCETO values for jobs. Currently, the BUNDLE-based approaches are limited to scheduling a single task. This work aims to expand the applicability of BUNDLE-based scheduling to multiple task multi-threaded task sets. BUNDLE-based scheduling leverages knowledge of potential cache conflicts to selectively preempt one thread in favor of another from the same job. This thread-level preemption is a requirement for the run-time behavior and WCETO calculation to receive the benefit of BUNDLE-based approaches. This work proposes scheduling BUNDLE-based jobs non-preemptively according to the earliest deadline first (EDF) policy. Jobs are forbidden from preempting one another, while threads within a job are allowed to preempt other threads. An accompanying schedulability test is provided, named Threads Per Job (TPJ). TPJ is a novel schedulability test, input is a task set specification which may be transformed (under certain restrictions); dividing threads among tasks in an effort to find a feasible task set. Enhanced by the flexibility to transform task sets and taking advantage of the inter-thread cache benefit, the evaluation shows TPJ scheduling task sets fully preemptive EDF cannot.

In "BUNDLE: Real-Time Multi-Threaded Scheduling to Reduce Cache Contention", Tessler and Fisher propose a scheduling mechanism and combined worst-case execution time calculation method that treats the instruction cache as a beneficial resource shared between threads. Object analysis produces a worst-case execution time bound and separates code segments into regions. Threads are dynamically placed in bundles associated with regions at run time by the BUNDLE scheduling algorithm where they benefit from shared cache values. In the evaluation of the previous work, tasks were created with a predetermined worst-case execution time path through the control flow graph. Apriori knowledge of the worst-case path is an impractical restriction on any analysis. At the time, the only other solution available was an all-paths search of the graph, which is an equally impractical approach due to its complexity. The primary focus of this work is to build upon BUNDLE, expanding its applicability beyond a proof of concept. We present a complete worst-case execution time calculation method that includes thread level context switch costs, operating on real programs, with representative architecture parameters, and compare our results to those produced by Heptane's state of the art method. To these ends, we propose a modification to the BUNDLE scheduling algorithm called BUNDLEP. Bundles are assigned priorities that enforce an ordered flow of threads through the control flow graph - avoiding the need for multiple all-paths searches through the graph. In many cases, our evaluation shows a run-time and analytical benefit for BUNLDEP compared to serialized thread execution and state of the art WCET analysis.

In "BUNDLE: Real-Time Multi-Threaded Scheduling to Reduce Cache Contention" Tessler and Fisher present a positive perspective of instruction caches for hard real-time multithreaded tasks. The thread-aware scheduling algorithm limits the execution of threads to sets of instructions that cannot result in cache conflicts. Identification of these sets result in conflict free regions which are used to identify scheduling groups called bundles in the BUNDLE scheduling algorithm. Placement of a thread in a particular bundle depends on, what the authors call, "anticipating execution". However, they do not define a complete mechanism to anticipate execution. In this work, we propose a method to anticipate execution that modifies cache hardware and introduces a new interrupt raised prior to a cache conflict. This new interrupt is combined with (a slightly modified version of) the BUNDLE scheduling algorithm. The intent is to implement these hardware modifications for ARM on the gem5 simulator with the scheduling algorithm integrated into the RTEMS operating system. The hope is this work serves as further motivation to bring the positive perspective of caches to physical processors and operating systems.

Summary form only given. Research on hard real-time systems and their models has predominately focused upon single-threaded tasks. When multithreaded tasks are introduced to the classical real-time model the individual threads are treated as distinct tasks, one for each thread. These artificial tasks share the deadline, period, and worst case execution time of their parent task. In the presence of instruction and data caches this model is overly pessimistic, failing to account for the execution time benefit of cache hits when multiple threads of execution share a memory address space. This work takes a new perspective on instruction caches. Treating the cache as a benefit to schedulability for a single task with m threads. To realize the “inter-thread cache benefit” a new scheduling algorithm and accompanying worst-case execution time (WCET) calculation method are proposed. The scheduling algorithm permits threads to execute across conflict free regions, and blocks those threads that would create an unnecessary cache conflict. The WCET bound is determined for the entire set of m threads, rather than treating each thread as a distinct task. Both the scheduler and WCET method rely on the calculation of conflict free regions which are found by a static analysis method that relies on no external information from the system designer. By virtue of this perspective the system's total execution execution time is reduced and is reflected in a tighter WCET bound compared to the techniques applied to the classical model. Obtaining this tighter bound requires the integration of three typically independent areas: WCET, schedulability, and cache-related preemption delay analysis.

Research on hard real-time systems and their models has predominately focused upon single-threaded tasks. When multi-threaded tasks are introduced to the classical real-time model the individual threads are treated as distinct tasks, one for each thread. These artificial tasks often share the deadline, period, and worst case execution time of their parent task. In the presence of instruction and data caches this view is overly pessimistic, failing to account for the execution time benefit of cache hits when multiple threads of execution share a memory address space.This work takes a new perspective on instruction caches. Treating the cache as a benefit to schedulability for a single task with m threads. To realize the "inter-thread cache benefit" a new scheduling algorithm, BUNDLE, and accompanying method for calculating the worst-case execution time (WCET) including cache overhead (WCET+O) method are proposed. BUNDLE permits threads to execute across conflict free regions, and blocks those threads that would create an unnecessary cache conflict. The WCET bound is determined for the entire set of m threads, rather than treating each thread as a distinct task. Both the scheduler and WCET+O method rely on the calculation of conflict free regions which are found by a static analysis method of the task object. By virtue of this perspective the system's total execution execution time is reduced and is reflected in a tighter WCET+O bound compared to the techniques applied to the classical model. Obtaining this tighter bound requires the integration of three typically independent areas: WCET, schedulability, and cache-related preemption delay analysis.

Schedulability analysis for real-time systems has been the subject of prominent research over the past several decades. One of the key foundations of schedulability analysis is an accurate worst case execution time (WCET) measurement for each task. In real-time systems that support preemption, the cache related preemption delay (CRPD) can represent a significant component (up to 44% as documented in research literature) [1] -- [3] of variability to overall task WCET. Several methods have been employed to calculate CRPD with significant levels of pessimism that may result in a task set erroneously declared as non-schedulable. Furthermore, they do not take into account that CRPD cost is inherently a function of where preemptions actually occur. Our approach for computing CRPD via loaded cache blocks (LCBs) is more accurate in the sense that cache state reflects which cache blocks and the specific program locations where they are reloaded. Limited preemption models attempt to minimize preemption overhead (CRPD) by reducing the number of allowed preemptions and/or allowing preemption at program locations where the CRPD effect is minimized. These algorithms rely heavily on accurate CRPD measurements or estimation models in order to identify an optimal set of preemption points. Our approach improves the effectiveness of limited optimal preemption point placement algorithms by calculating the LCBs for each pair of adjacent preemptions to more accurately model task WCET and maximize schedulability as compared to existing preemption point placement approaches. We propose an optimal preemption point placement algorithm using dynamic programming. Lastly, we will demonstrate, using a case study, improved task set schedulability and optimal preemption point placement via our new LCB characterization.