分布式并行算法.pdfVIP

LLB: A Fast and Effective Scheduling Algorithm for Distributed-Memory Systems Andrei R˘adulescu Arjan J.C. van Gemund Hai-Xiang Lin Faculty of Information Technology and Systems Delft University of Technology P.O.Box 5031, 2600 GA Delft, The Netherlands Abstract The heuristic algorithms used for compile-time task scheduling on distributed-memory systems can be divided This paper presents a new algorithm called List-based into (a) scheduling algorithms for an unbounded num- Load Balancing (LLB) for compile-time task scheduling ber of processors (e.g., DSC [12], EZ [9], STDS [2] and on distributed-memory machines. LLB is intended as a DFRN [6]) and (b) scheduling algorithms for a bounded cluster-mapping and task-ordering step in the multi-step number of processors (e.g., MCP [10], ETF [5] and class of scheduling algorithms. Unlike current multi- CPFD [1]). The problem in the unbounded case is easier, step approaches, LLB integrates cluster-mapping and task- because the constraint on the number of processors need not ordering in a single step. The benefits of this integration are be considered. Therefore, scheduling in the unbounded case twofold. First, it allows dynamic load balancing in time, can be performed with good results at a lower cost com- because only the ready tasks are considered in the mapping pared to the bounded case. However, in practical situations, process. Second, communication is also considered, as op- the necessary number o