Scheduling Task Graph Applications on Preloaded Shared-Bus based Heterogeneous Platforms

Modern embedded control applications in Cyber-Physical Systems (CPSs) often have complex inter-dependencies in their functionalities and are hence represented as Directed-Acyclic Task Graphs (DTGs). To meet complex performance as well as deployment-related logistic constraints, these applications may need to be implemented on a distributed and heterogeneous platform. Many-a-times, it becomes necessary to dynamically run a new application like say, an alarm service routine , on an already operational platform, where pre-existing workloads consisting of other application tasks along with their messages are running. However, although there is a significant body of literature dealing with the static scheduling of DTGs on different types of platforms, to the best of our knowledge, there does not exist any prominent work for the dynamic scheduling of dynamically arriving DTG applications on an already preoccupied platform. The primary reason for this dearth in strategies may be attributed to the inherent design as well as computational complexity associated with the dynamic inclusion of a new DTG application by effectively reclaiming the free slots within an already existing schedule. While delivering quick response times to the dynamically arrived application, the newly generated schedule must also ensure that it does not ever cause deadline violations for the already running applications . This work proposes a novel makespan-minimizing scheduling algorithm called DTG Scheduler for Preloaded Platforms ( DSPP ). DSPP is an efficient list-based heuristic strategy for co-scheduling the tasks as well as the inter-task messages of a DTG structured application on preloaded heterogeneous processing elements, interconnected via shared buses. The effectiveness of DSPP has been meticulously examined through simulation, employing benchmark DTGs for evaluation. The conducted experiments reveal the generic efficacy of DSPP across an extensive set of considered test case scenarios. Extensive simulation results show that DSPP can achieve up to ∼ 13% reduction in makespan in the best case and ∼ 10% on average, outperforming existing state-of-the-art methods.