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

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.