Abstract
Scheduling Coarse-Grain Iterative Task Computation onMessage-Passing Architectures
by: T. Yang
Abstract:
Scheduling task computation and predicting its performance on message-passingarchitectures are important for program parallelization. In this paper weconsider the scheduling of a weighted iterative task graph (ITG) in thepresence of communication overhead. An ITG represents a sequence of paralleltask computation. Each iteration contains the execution of a set of tasks andthere exists task dependence within an iteration and between iterations. Weprovide a lower bound for optimal scheduling when the weights of iterative taskgraphs change monotonically in the course of iterations. We devise a validschedule without searching task instances of all iterations and examine theasymptotic performance of this schedule compared to an optimal solution.Finally, we present case studies and experimental results on nCUBE-2 to verifyour solutions.
Keywords:
Scheduling, directed acyclic graphs, iterative task graphs,performance prediction, communication, coarse-grain parallelism.
Date:
April 1994
Document: 1994-07
