Performance Evaluation of Scheduling Precedence-Constrained Computations on Message-Passing Systems

Free registration required

Executive Summary

Scheduling precedence graphs with communication times is the theoretical basis for achieving efficient parallelism in message-passing machines. The lack of global information on the tasks, due to communication, has lead to develop local scheduling heuristics such as the Earliest-Task-First. Using knowledge on computation, communication, and system topology, a class of global priority-based scheduling heuristics called Generalized List Scheduling is proposed. The task-level is evaluated by backward scheduling the computation over the multiprocessor by using the best local heuristic. This leads to realistic measurement of the task priority for use in forward GLS scheduling. Experimental evaluation of local and GLS heuristics is carried out using extensive random graph generation and altering over the communication, inherent parallelism, and system topology.

  • Format: PDF
  • Size: 137.88 KB