"Agency scheduling" a model for dynamic task scheduling

This paper describes a class of algorithms for scheduling parallel programs represented by macro dataflow graphs (task precedence graphs) onto a muitiprocessor system such that the total execution time is minimized. The schedule will be computed dynamically during the runtime of the process system. The model allows to represent centralized and fully distributed algorithms as well as intermediate forms. The algorithms are able to schedule static as well as dynamic dataflow graphs. Knowledge of the execution times of the tasks is not necessary. Some variants of the model have been implemented using a multi-transputer system. Practical experiences are included in the paper.