Analysis of Macro-Dataflow Dynamic Scheduling on Nonuniform Memory Access Architectures

This paper studies dynamic scheduling of computational tasks with communication costs using nonuniform memory access architecture. The computing model assumes that data transfer can be partitioned into parallel and sequential parts with respect to the task execution. A scheduling heuristic, called least-communication (LC), together with a two-level scheduler is proposed in an attempt to minimize the finish time. The LC selects the task that removes the largest amount of remaining data transfer, if no such tasks are available the task that has been ready to run at the earliest is selected first. Analysis shows that scheduling n tasks on m processors gives a schedule length ωl_cthat satisfies ωl_c (2 — 1/m)ω_opt + ΔtΣCs(Ti, Ti+1) + (n/m + (1 - 1/m)L)(h_lc - h_0pt), where ω _opt is the length of an optimum solution for scheduling with no communication costs, ∑ Cs is the sum of sequential data transfer for all the arcs (T_i, T_i+1) along a chain of L tasks whose computation and data transfer times cover all the idle times in the schedule, At is the time to transfer one operand to memory, and h_opt and hl_c are the task scheduling overheads in case of optimum and LC scheduling, respectively. The time complexity of LC is O(n²). Testing the finish time of LC and FCFS shows that LC is useful for tasks having moderate granularity and whose computation and communication requirements vary widely for different data sets.