c ' TASK ASSIGNMENT HEURISTICS FOR PARALLEL A N D DISTRIBUTED CFD APPLICATIONS

Abstract. This paper proposes a task graph (TG) model to represent a single discrete step of multi-block overset grid computational fluid dynamics (CFD) applications. The TG model is then used to not only balance the computational workload across the overset grids but also t o reduce inter-grid communication costs. We have developed a set of task assignment heuristics based on the constraints inherent in this class of CFD problems. Two basic assignments, the smallest task first (STF) and the largest task first (LTF), are first presented. They are then systematically costs. To predict the performance of the proposed task assignment heuristics, extensive performance evaluations are conducted on a synthetic TG with tasks defined in terms of the number of grid points in predetermined overlapping grids. A TG derived from a realistic problem with eight million grid points is also used as a test case. mhr3?_ce! +>, +egr;"2ti"x +e stll.73 cf Frccns:2g z-its &:'.e:7&rp:cpsz: ~ : :. ~ * ~ ~.: & ~ c ~ Key words. Overset grids, task graphs, performance prediction, parallel processing, high per-formance computing. AMS subject classifications. 05C90, 68U01, 65Y05 1. Introduction. Th