TY - CHAP

T1 - A Practical Survey on Static Task Scheduling Optimization Approaches for Heterogeneous Architectures

AU - Hollmann, Jonas

AU - Lüders, Matthias

AU - Arndt, Jakob

AU - Kyriakopoulos, Ioannis

AU - Blume, Holger

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025/6/11

Y1 - 2025/6/11

N2 - The complexity of software increases constantly, even in embedded real-time and safety-critical systems. This ever-increasing computational demand causes more complex application-specific accelerators to get integrated into modern computational systems, causing a shift towards heterogeneous architectures. In many safety-critical real-time applications, the workload to be executed is known beforehand, allowing the developer to determine a static scheduling of the workload upfront. This allows the developer to validate safety constraints fully, a task that is often not feasible using dynamic scheduling. Generally, programming heterogeneous processors quickly becomes an almost impossible challenge for software developers. As such, numerous approaches for automatically generating static schedules have been proposed over the years. These heuristic approaches use simplified models of the target platform by ignoring concepts like memory locality or processor core clustering, as well as a simplified graph representation of the software in exchange for lower computational complexity. However, we have yet to see a practical survey of existing approaches, especially in the context of embedded real-time and safety-critical systems. Thus, we map existing heuristic approaches for the automatic generation of an approximate optimal static task scheduling to real hardware using a generic approach. In doing so the effects of the simplification during the modeling process, as well as the efficiency of the underlying heuristic are assessed by benchmarking the results of such scheduling optimization algorithms applied to algorithms of various complexity such as the Fast Fourier Transform and sparse matrix multiplication on several heterogeneous target architectures. Finally, we discuss the capabilities of existing approaches and their applicability for modern real-time critical embedded systems.

AB - The complexity of software increases constantly, even in embedded real-time and safety-critical systems. This ever-increasing computational demand causes more complex application-specific accelerators to get integrated into modern computational systems, causing a shift towards heterogeneous architectures. In many safety-critical real-time applications, the workload to be executed is known beforehand, allowing the developer to determine a static scheduling of the workload upfront. This allows the developer to validate safety constraints fully, a task that is often not feasible using dynamic scheduling. Generally, programming heterogeneous processors quickly becomes an almost impossible challenge for software developers. As such, numerous approaches for automatically generating static schedules have been proposed over the years. These heuristic approaches use simplified models of the target platform by ignoring concepts like memory locality or processor core clustering, as well as a simplified graph representation of the software in exchange for lower computational complexity. However, we have yet to see a practical survey of existing approaches, especially in the context of embedded real-time and safety-critical systems. Thus, we map existing heuristic approaches for the automatic generation of an approximate optimal static task scheduling to real hardware using a generic approach. In doing so the effects of the simplification during the modeling process, as well as the efficiency of the underlying heuristic are assessed by benchmarking the results of such scheduling optimization algorithms applied to algorithms of various complexity such as the Fast Fourier Transform and sparse matrix multiplication on several heterogeneous target architectures. Finally, we discuss the capabilities of existing approaches and their applicability for modern real-time critical embedded systems.

KW - Heterogeneous safety-critical embedded systems

KW - List scheduling

KW - Multicore

KW - Task scheduling

UR - http://www.scopus.com/inward/record.url?scp=105009247154&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-90200-0_34

DO - 10.1007/978-3-031-90200-0_34

M3 - Contribution to book/anthology

SN - 978-3-031-90199-7

VL - Conference proceedings

T3 - Lecture Notes in Computer Science

SP - 425

EP - 437

BT - Euro-Par 2024

A2 - Caino-Lores, Silvina

A2 - Zeinalipour, Demetris

A2 - Doudali, Thaleia Dimitra

A2 - Singh, David E.

A2 - Garzón, Gracia Ester Martín

A2 - Sousa, Leonel

A2 - Andrade, Diego

A2 - Cucinotta, Tommaso

A2 - D'Ambrosio, Donato

A2 - Diehl, Patrick

A2 - Dolz, Manuel F.

A2 - Jukan, Admela

A2 - Montella, Raffaele

A2 - Nardelli, Matteo

A2 - Garcia-Gasulla, Marta

A2 - Neuwirth, Sarah

ER -