Report ID
1994-07
Report Authors
T. Yang
Report Date
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.
Document
1994-07.ps418.23 KB