Limited Preemption of the 3-Phase Task Model using Preemption Thresholds

Phased execution models are employed to manage complexity in modern multi-core platforms, and this research introduces preemption thresholds as a method to limit preemptions in 3-phase task models to minimize local memory usage while maintaining schedulability.

The gist

Preemption thresholds can be used to reduce the number of preemptions that are unnecessary to maintain schedulability, which is shown to reduce the stack space.

System Model and Task Definition

The system under consideration is a multi-core system with a set of sporadic tasks, where each task is divided into three phases: read (R), execute (E), and write (W). Each task τi is represented by the tuple (Ti, Di, Mi, Pi, θi, Cri, Cei, Cwi), where Ti and Di represent the minimum inter-arrival time and relative deadline; Mi is the memory footprint; Pi is the fixed nominal priority; θi represents the preemption threshold where Pi ≤ θi; Cri and Cwi are worst-case execution times for read and write phases, respectively. The total worst-case execution time Ci is their sum, i.e., Ci = Cri + Cei + Cwi.

Execution Model under Preemption Thresholds

The paper focuses on partitioned fixed-priority scheduling where each task is statically assigned to a core (keep-in-core method). Read and write phases are non-preemptive, while execution phases can be preempted. A task’s priority is raised to its preemption threshold θi with the start of the read phase. Only tasks that have a nominal priority higher than the executing task’s preemption threshold θi are allowed to preempt τi’s execution phase. Preemption is realized using the keep-in-core method, where data of both tasks is stored in local memory during preemption, requiring both data sets to fit in local memory simultaneously.

Response Time Analysis

The response time analysis utilizes techniques from existing analyses for limited preemptive scheduling and fully preemptive E-phases. The analysis involves calculating the longest level-i active period Li,l using four delay factors: Intra-core interference (Ii), Intra-core blocking (Bi), Inter-core interference (Imemi), and Inter-core blocking (Bmemi). These factors are categorized into six groups based on nominal priorities and preemption thresholds. The maximum number of jobs released within the active period, Ki, is calculated using Equation 10: Ki = η+i(Li,l) = Li,l/Ti. The worst-case response time (WCRT) of task τi is then calculated by finding the maximum out of the response times of all jobs within the active period (Equation 13).

Memory Requirement Analysis

The analysis for local memory usage focuses on finding the preemption chain that results in the largest cumulative memory requirement. A preemption chain is a sequence where each task is preempted by the next task, defined by θP Ci(j) > PP Ci(j+1). The goal is to maximize X∀τj∈P Ci Mj. A task set is considered memory-feasible if the maximum preemption chain of each task on each core is not larger than S, meaning X∀τj∈P Ci Mj ≤ S. The paper proposes using the Maximal Preemption Threshold Assignment Algorithm (MPTAA) to assign maximum preemption thresholds, which aims to find the largest possible PT assignment while maintaining schedulability.

Evaluation Results

Evaluations demonstrate that preemption thresholds can significantly reduce memory usage by 2.5× compared to fully preemptive scheduling, while maintaining high schedulability ratios of 13× compared to non-preemptive scheduling for realistic memory sizes. Specifically, for realistic memory sizes, 13× more task sets are both schedulable and memory-feasible, while requiring 2.5× less local memory than fully-preemptive scheduling. The results show that PT scheduling achieves up to 40% more task sets than fully preemptive scheduling that are both schedulable and memory-feasible when the local memory size is less than 104KB. Furthermore, using PTs allows achieving 100% memory feasibility with only 40KB (2.5× improvement) compared to the 104KB required by FP scheduling. The number of cores can be reduced by half when utilizing PT scheduling to achieve both schedulability and memory feasibility for the same applications.

Conclusions

The paper concludes that using preemption thresholds can improve memory feasibility by 2.5× over fully preemptive scheduling while still maintaining the schedulability of fully preemptive scheduling, which is 13× more than non-preemptive scheduling. The proposed methods enable using a platform with a much smaller local memory for the same applications. Future work will explore preemption thresholds to improve schedulability.

As a fastidious researcher, I have analyzed the provided scientific paper, Limited Preemption of the 3-Phase Task Model using Preemption Thresholds by Thilanka and Becker. This paper focuses on improving the resource utilization and feasibility of real-time systems (specifically 3-phase task models) running on multi-core platforms by introducing a limited preemption strategy via preemption thresholds (PT).

Based strictly on the technical contributions of this paper, here are the specific improvements that can be made to AI systems—assuming these AI tasks can be modeled using the described 3-phase execution model (Read/Execute/Write) and fixed-priority scheduling:

) Improved AI System Capabilities:

The paper directly addresses challenges in complex, multi-core COTS platforms (like those used for modern large language models or real-time control systems). The improvements focus on optimizing resource management to reduce memory footprint without sacrificing schedulability.

1. Reduced Local Memory Footprint for Inference/Execution:

Improve the system's ability to run complex AI models (especially those involving large weights or intermediate activations) on hardware with limited onboard memory (like embedded accelerators or edge devices). By applying the proposed preemption thresholds, the system can achieve a local memory reduction of up to 2.5× compared to fully preemptive scheduling while maintaining high schedulability ratios (13× better than non-preemptive). This means AI models can be deployed on smaller, more cost-effective hardware with less required scratchpad/local memory.

2. Enhanced Schedulability for Time-Critical AI Tasks:

Improve the system's reliability in meeting strict deadlines for critical operations (e.g., autonomous vehicle control loops or real-time decision-making). The analysis provides a worst-case response time (WCRT) calculation that accounts for intra-core interference, inter-core blocking, and memory contention under the limited preemption scheme. This allows AI algorithms to be scheduled such that critical tasks are guaranteed to meet their deadlines even when other high-priority tasks are preempted strategically.

3. Optimized Preemption Strategy for Model Execution:

Implement a dynamic scheduling policy based on the MPTAA (Maximal Preemption Threshold Assignment Algorithm) adapted for 3-phase models. This algorithm ensures that preemption thresholds are set to maximize stack utilization (memory efficiency) while ensuring the task set remains schedulable under fixed-priority constraints. For AI inference, this means intelligently deciding when a lower-priority background task should be allowed to preempt a high-priority inference task based on its assigned threshold, minimizing unnecessary context switching overhead while preventing catastrophic deadline misses.

4. Feasibility in Multi-Core Heterogeneous Environments:

Improve the ability of the system to operate effectively across multiple cores with varying resource constraints (SPM size). The paper demonstrates that for a given utilization and core count, the limited preemption approach can achieve both schedulability and memory feasibility where fully preemptive methods fail (e.g., achieving 100% memory feasibility at 40KB instead of 104KB). This capability is crucial for scaling AI workloads across heterogeneous multi-core systems where resources are shared dynamically.

Phased execution models are a well-known solution to tackle the unpredictability of today's complex COTS multi-core platforms. The semantics of these models dedicate phases for a task's execution and shared memory accesses. Memory phases are solely dedicated to load all necessary instructions and data to private local memory, and to write back the results of the computation. During execution phases, only the private local memory is accessed. While non-preemptive execution phases utilize the local memory well, schedulability is reduced due to blocking. On the other hand, fully preemptive execution phases allow for better schedulability, but require local memory to be large enough to hold all tasks involved in preemption simultaneously. Limited preemption is a promising approach that provides moderation between non-preemptive and fully preemptive scheduling. In this paper, we propose using preemption thresholds to limit the number of preemptions to minimize local memory usage while maintaining schedulability. We propose worst-case response-time and worst-case memory-requirement analyses for sporadic 3-phase tasks under partitioned fixed-priority scheduling with preemption thresholds. We consider two distinct arbitration schemes for memory-phase scheduling between cores: task-priority-based and core-priority-based. We further show how the state-of-the-art algorithm to assign preemption thresholds can be applied to the considered task model. Evaluations demonstrate that preemption thresholds can significantly reduce the memory usage compared to fully preemptive scheduling, while maintaining high schedulability ratios compared to non-preemptive scheduling.