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.

This paper presents a hybrid scheduling methodology for task graphs to multiprocessor embedded systems. The proposed methodology is designed for task graphs that are dynamic in nature due to the presence of conditional tasks and tasks whose execution times are unpredictable but bounded. We have presented the methodology as a three-phase strategy, in which task nodes are mapped to the processors in the first (static mapping) phase. In the second (selective duplication) phase, some critical nodes are identified and duplicated for possible rescheduling at runtime, depending on the code memory constraints of the processors. The third (online) phase is a runtime scheduling algorithm that performs list scheduling based on the actual dynamics of the schedule up to the current time. We show that this technique provides better schedule length (up to 20 percent) compared to previous techniques, which are predominantly static in nature, with low overhead and a complexity comparable with existing online techniques. The effects of model parameters like the number of processors, memory, and various task graph parameters on performance are investigated in this paper.