Dynamic Rescheduling of Tasks for the Macro-Dataflow Paradigm

  Ka Kay Ho and Bruno R. Preiss. January 1996[13].

A major deficiency of static scheduling techniques is their inability to handle data-dependent looping and conditional branching which cause non-determinismic task execution times, in effect, dynamic alterations of the task graph.

This paper presents a heuristic, hybrid dynamic/static task-scheduling strategy which attempts to handle non-deterministic task execution times. The goal of this strategy is to achieve an improvement in execution time over static scheduling without being overwhelmed by overhead costs. In the proposed approach, the tasks are initially scheduled statically using estimates of task completion times. During run time, tasks are migrated following heuristic rules to take advantage of idle periods on processors. Results from simulations indicate that this technique can produce a performance improvement over the static approach when operating in certain problem domains. The proposed strategy is compared with ``ideal'' static scheduling in order to characterize its efficiency.

Copyright 1996 by Ka Kay Ho and Bruno R. Preiss.

Full text.