Improvement of duplication scheduling heuristic algorithm with nonstrict triggering of program graph nodes
B. Benko, Milan Ojsteršek, Viljem Zumer · 2002
The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimised. This scheduling problem is known to be NP-hard, and heuristic algorithms have been proposed to obtain optimal and suboptimal solutions. Duplication scheduling heuristic algorithm solves the max-min problem of parallel processor scheduling by duplicating selected scheduled tasks on some PEs. The max-min problem is caused by the trade-off between maximum parallelism versus minimum communication delay. This paper introduces an extension of the near optimal scheduling heuristic, based on a duplication scheduling heuristic. We have focused our research efforts to three main extensions of the original heuristic.>