A Distributed Procedure for Bandwidth-Centric Scheduling of Independent-Task Applications
Cyril Banino · 2005
The problem of scheduling independent tasks on heterogeneous trees is considered. The nodes of the tree may have different processing times, and links different communication times. The single-port, full overlap model is used for modeling the activities of the nodes. A distributed method for determining the maximum steady-state throughput of a tree is presented. Then, we show how each node can buildup its own local schedule independently of the rest of the platform. In addition, the final schedule is asynchronous and event-driven, meaning that each node (except the root) acts without any time-related information. A local scheduling strategy which aims at minimizing the amount of tasks buffered-at node locations during steady-state is introduced. As a consequence, the lengths of the start-up and wind-down phases are considerably reduced.