Directed Taskgraph Scheduling Using Simulated Annealing.
Erik H. D'Hollander, Yves Devis · Ghent University Academic Bibliography (Ghent University) · 1991
Simulated annealing is recognized as a novel method to optimize the load in multicomputer systems, subject to the interprocessor communication overhead.Recently, highly nonlinear mapping and load balancing of undirected taskgraphs has been solved in a successful way.In this paper the scope is extended to directed taskgraphs, representing the data and control dependencies in common programs.The annealing algorithm operates in stages.In each stage an annealing packet of ready tasks is formed and the tasks are allocated to the idle processors.The cost function is based on the priority level of the tasks in the taskgraph and the intertask communication requirements.The resulting schedule of four programs on three architectures show a significant speedup improvement compared to the Highest Level First list algorithm.