Scheduling and analysis of parallel software in multiprocessor real-time systems

With the emergence of multiprocessor systems as the standard enabling platform for high-performance real-time embedded computing systems, computational workloads have evolved towards highly parallel structures to match the enhanced processing capabilities offered by the underlying hardware. Furthermore, in the case of heterogeneous platforms, general-purpose multiprocessors are combined with specialized computing devices such as field-programmable gate arrays (FPGAs) and graphics processing units (GPUs). Therefore, parallel embedded software is often designed to leverage the availability of both multiprocessors and hardware accelerators in order to reduce the expected computation time and improve the resulting power efficiency. Designing, scheduling and analyzing parallel real-time systems of this kind requires to carefully account for the timing constraints of each task in addition to the precedence constraints in place between computational activities executing on different processing devices. This thesis proposes theoretical advancements in real-time scheduling of parallel software on multiprocessor systems supporting hardware acceleration, by investigating techniques to schedule, model, and analyze parallel systems and to guide resource allocation in the system design phase. First, the thesis presents the event-driven delay-induced (EDD) task model, a specialized graph-based model that is suitable for capturing the behavior of complex computing workloads, including parallel computation on multiprocessor systems and both synchronous and asynchronous hardware acceleration. Response-time analysis techniques for EDD tasks under fixed-priority and Earliest Deadline First (EDF) scheduling are also presented. Subsequently, the thesis presents replication-based scheduling (RBS), a specialized scheduling paradigm for the execution of parallel real-time tasks on multiprocessor systems, together with a related response-time analysis for fixed-priority systems. This scheduling approach achieves high system utilization by employing a flexible allocation and execution scheme, featuring low implementation complexity and limited expected runtime overheads. Finally, a response-time analysis for self-suspending tasks executing under EDF scheduling is derived, with direct applications in the timing characterization of parallel computation and hardware acceleration patterns under EDF. The performance of the techniques proposed in the thesis is assessed and compared with that of existing techniques by means of an experimental evaluation, which also accounts for the choice of different resource allocation techniques in the system design phase.