Conditionally Optimal Parallelization of Real-Time Tasks for Global EDF Scheduling

Abstract

Real-time applications are rapidly growing in their size and complexity. This trend is apparent even in extreme deadline-critical sectors such as autonomous driving and artificial intelligence. Such complex program models are described by a directed-acyclic-graph (DAG), where each node of the graph represents a task, and the connected edges portray the precedence relation between the tasks. With this intricate structure and intensive computation requirements, extensive system-wide optimization is required to ensure a stable real-time execution.

On the other hand, recent advances in parallel computing frameworks, such as OpenCL and OpenMP, allow us to parallelize a real-time task into many different versions, which is called ``parallelization freedom.'' Depending on the degree of parallelization, the thread execution times can vary significantly, that is, more parallelization tends to reduce each thread execution time but increase the total execution time due to parallelization overhead.

By carefully selecting a ``parallelization option'' for each task, i.e., the chosen number of threads each task is parallelized into, we can maximize the system schedulability while satisfying real-time constraints. Because of this benefit, parallelization freedom has drawn recent attention. However, for global EDF scheduling, G-EDF for short, the concept of parallelization freedom still has not brought much attention. To this extent, this dissertation proposes a way of optimally assigning parallelization options to real-time tasks for G-EDF on a multi-core system. Moreover, we aim to propose a polynomial-time algorithm that can be used for online situations where tasks dynamically join and leave.

We formalize a monotonic increasing property of both tolerance and interference to the parallelization option to achieve this. Using such properties, we develop a uni-directional search algorithm that can assign parallelization options in polynomial time, which we formally prove the optimality.

With the optimal parallelization, we observe significant improvement of schedulability through simulation experiment, and then in the following implementation experiment, we demonstrate that the algorithm is practically applicable for real-world use-cases.

This dissertation first focuses on the traditional task model, i.e., multi-thread task model, then extends also to target the multi-segment (MS) task model and finally discusses the more general directed-acyclic-graph (DAG) task model to accommodate a wide range of real-world computing models.

이 논문은 Global EDF 스케줄러에서의 실시간 태스크의 최적 병렬화 기법에 대해 기술한다. 이를 위해 병렬화 옵션 증가에 대해 tolerance와 interference가 단조 증가함을 수학적으로 밝힌다. 이러한 특성을 이용하여, 다항식 시간안에 수행될 수 있는 실시간 태스크의 병렬화 기법을 제안하고, 수학적으로 최적의 방법임을 증명한다. 시뮬레이션 실험을 통해, 실시간 태스크의 스케줄링 성능의 비약적인 상승을 관찰하고, 이어지는 실제 세계 워크로드를 이용한 구현 실험에서 실제 세계 적용 가능성을 점검한다. 이 논문은 먼저 전통적인 멀티쓰레드 태스크 모델을 대상으로 최적 병렬화 방법을 논하며, 이후 멀티 세그먼트, DAG 태스크 모델까지 확장하는 방법을 기술한다.