Automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasks with non-preemptible sections and precedence constraints

Abstract

Diese Diplomarbeit behandelt die automatische Berechung der competitive ratio von online Schedulung Algorithmen mit firmen Echtzeitanforderungen und nicht-präemptiven Bereichen und Reihenfolgenbeschränkungen. Zu diesem Zweck wurde ein existierendes Framework [Chatterjee et. al. 2018] um diese Funktionalität erweitert. Dabei mussten beträchtliche theoretische und implementierungstechnische Herausforderungen bewältigt werden. Zum Einen impliziert das Vorliegen von Event- und/oder Zeit-basierten Reihenfolgenbeschränkungen, dass der Online- und der Offline-Algorithmus bei der Berechnung der competitive ratio nicht notwendigerweise dieselbe job sequence verarbeiten. Zum Anderen ist EDF unter Reihenfolgenbeschränkungen nicht mehr optimal, wodurch die ursprüngliche Implementierung des Offline-Algorithmus nicht mehr verwendbar war, sondern basierend auf EDF* neu entwickelt werden musste. Schlussendlich wurden Teile des Algorithmus parallelisiert und in CUDA implementiert. Mit der parallelen Rechenleistung einer GPU resultiert daraus eine Performance-Verbesserung um mehrere Größenordnungen, sodass nunmehr auch größere und komplexere task sets analysiert werden können.

This thesis deals with automatically computing the competitive ratio of online real-time scheduling algorithms for firm deadline task with non-preemptible sections and precedence constraints. For this purpose, an existing framework for automatic competitive analysis [Chatterjee et. al. 2018] is extended with the needed functionality. Several challenges, both theoretical and implementation-wise, make this very difficult. First of all, event-based and time-based precedences require online and offline algorithms to work on different job sequences when computing the competitive ratio. Moreover, as EDF is no longer optimal in the presence of precedences, we could not use the original implementation of the offline algorithm but had to develop a new one based on EDF*. Finally, in order to be able to analyze more complex task sets, parts of the algorithm are implemented in CUDA. Leveraging the parallel processing power of a GPU, this increases the achieved performance of the framework by several orders of magnitude.