Dynamic Rescheduling of Tasks for the Macro-Dataflow Paradigm

logo Website of Bruno R. Preiss
next up contents external
Next : Ynot Logic Simulator: A Up: Unpublished Manuscripts Previous: An AttributedTime-Delayed Rendezvous

Dynamic Rescheduling of Tasks for the Macro-Dataflow Paradigm

  Ka  Kay Ho and Bruno  R. Preiss. January 1996[11].
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.

external Full text.



bruno Copyright 2002 by Bruno R. Preiss, P.Eng. All rights reserved.
Tue Jan 1 13:41:25 EST 2002



Data Structures and Algorithms with Object-Oriented Design Patterns in C++
Data Structures and Algorithms with Object-Oriented Design Patterns in C++
ISBN: 0471241342
EAN: 2147483647
Year: 1998
Pages: 101

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net