Schedulability Analysis of Non-preemptive Sporadic Gang Tasks on Hardware Accelerators

Binqi Sun, Tomasz Kloda, Jiyang Chen, Cen Lu, Marco CaccamoRTAS 2023 · DOI

Abstract

Hardware accelerators like Google's Edge TPU are increasingly vital for Edge AI, but their non-preemptive nature and the requirement for parallel "gang" task execution pose significant scheduling challenges. This paper presents a novel schedulability analysis for non-preemptive sporadic gang tasks. By formulating the "carry-in limitation" as a knapsack problem, the proposed method significantly reduces pessimism in interference estimation. Evaluation on synthetic task sets and real-world Edge TPU benchmarks demonstrates that the new analysis identifies up to 85.7% more schedulable task sets compared to existing state-of-the-art techniques.

Introduction

In the domain of Edge AI, hardware accelerators such as the Edge TPU are essential for executing deep neural networks (DNNs) with low latency. However, these devices present two major constraints for real-time systems. First, they have high preemption costs due to limited on-chip SRAM; switching between models requires slow reloads from main memory, making non-preemptive execution preferable. Second, large models often require intra-task parallelism, where a single task must occupy multiple processors simultaneously—a paradigm known as gang scheduling.

The Gang Task Scheduling Problem

Existing mathematical tests for verifying real-time deadlines (schedulability analysis) are often too pessimistic for gang tasks. Unlike traditional sequential tasks, a gang task is represented as a "rectangle" in the time and processor domain. Interference is not merely a matter of when a task runs, but how many processors it occupies.

Figure 6: Gang task scheduling model where tasks occupy multiple CPUs simultaneously over time.

This "rectangle problem" means that the worst-case interference assumed by prior models is often physically impossible given the fixed number of available processors. To address this, the authors introduce a "carry-in limitation" technique, which identifies jobs released before a specific time window that are still running and delaying new tasks.

Methodology

The core innovation of this paper is the formulation of the interference selection problem as a generalized knapsack problem. In this model, interfering tasks are treated as "items" and the available processor count as the "capacity."

Two new schedulability tests were developed:

  1. Fixed Test: A computationally efficient test using Linear Programming (LP) relaxation to solve the knapsack problem in quadratic time.
  2. Response Time Analysis (RTA): A more precise test using Dynamic Programming (DP). Although it has pseudo-polynomial complexity, it provides much tighter bounds on task response times.

Evaluation and Benchmarks

The researchers evaluated their analysis using 10,000 synthetic task sets and a real-world case study involving eight representative convolutional neural networks (CNNs) benchmarked on ASUS AI Accelerator cards.

Figure 4: WCET of various CNN models relative to the number of Edge TPUs, illustrating diminishing returns for smaller models.

As shown in the benchmarks, increasing the number of TPUs does not always result in lower latency. For smaller models like Inception-v1, the I/O overhead between chips can actually increase the Worst-Case Execution Time (WCET). This highlights the necessity of a "rigid" gang model where the processor count is fixed based on model size and system constraints.

Key Results

The proposed RTA test outperformed the previous state-of-the-art (Kim2016) by 85.7% in identifying schedulable task sets in the Edge TPU benchmarks. In synthetic tests, the analysis found up to 46.5% more schedulable sets. The "Fixed" test also proved to be a practical middle ground, offering significant accuracy improvements while remaining computationally fast.

Conclusion

By treating gang task interference as a resource allocation problem, this research provides a much-needed tool for engineers to maximize the utilization of multi-accelerator systems. Future work will look into "malleable" tasks, where processor allocation can change dynamically, and more detailed modeling of memory bus contention.

Summary updated

BibTeX
@inproceedings{sun2023schedulability,
  author = {Binqi Sun and Tomasz Kloda and Jiyang Chen and Cen Lu and Marco Caccamo},
  title = {{Schedulability Analysis of Non-preemptive Sporadic Gang Tasks on Hardware Accelerators}},
  booktitle = {RTAS},
  year = {2023},
  doi = {10.1109/rtas58335.2023.00019},
}
Figure