GPU-Based Parallel EDF-Schedulability Analysis of Multi-modal Real-Time Systems

Real-time multi-modal systems are useful in modeling embedded systems that dynamically change computational requirements over time (e.g., adaptive cruise control systems). For meeting timing constraints of such multi-modal systems, Earliest-Deadline-First (EDF) is an attractive real-time scheduling algorithm due to its optimality on uniprocessor platforms. However, checking EDF-schedulability of a real-time multi-modal system is a difficult problem that requires substantial computational effort. Today´s cost efficient and massively parallel GPU platforms can be effectively leveraged to solve this difficult problem. Existing algorithms for EDF-schedulability of real-time multi-modal systems cannot exploit the entire computational power of a GPU, therefore, in this research, we develop a parallel algorithm leveraging the advantages of a GPU device. Experimental results establish the superior performance of our proposed algorithm upon a low end GPU over the implementation of existing algorithms on a cluster of computers using either MPI or OpenMP. In addition to performance, our proposed algorithm is a cost effective and power efficient alternative against comparable algorithms for multi-core and parallel computing platforms.