Online Scheduling of Dynamic Task Graphs with Communication and Contention for Multiprocessors

Abstract

This paper presents an online scheduling methodology for task graphs with communication edges for multiprocessor embedded systems. The proposed methodology is designed for task graphs which are dynamic in nature either due to the presence of conditional paths or due to presence of tasks whose execution times vary. We have assumed homogeneous processors with broadcast and point-to-point communication models and have presented online algorithms for them. We show that this technique adapts better to variation in task graphs at runtime and provides better schedule length compared to a static scheduling methodology. Experimental results indicate up to 21.5 percent average improvement over purely static schedulers. The effects of model parameters like number of processors, memory, and other task graph parameters on performance are investigated in this paper.