An Incremental Parallel Scheduling Approach to Solving Dynamic and Irregular Problems.
Wei Shu, Min‐You Wu · 1995
Global parallel scheduling is a new approach for runtime load balancing. In parallel scheduling, all processors are cooperated together to schedule work. Parallel scheduling accurately balances the load by using global load information. As an alternative strategy to the commonly used dynamic scheduling, it provides a high-quality, low-overhead load balancing. This paper presents a parallel scheduling algorithm for tree structured interconnection networks. 1. Introduction Application problem structures can be classified into two types: problems with a predictable structure, also called static problems, and problems with an unpredictable structure, called dynamic problems. There are two basic scheduling strategies: static scheduling and dynamic scheduling. The static scheduling distributes the work load before runtime, and can be applied to static problems. Most existing static scheduling algorithms are sequential, executed on a single processor system. Dynamic scheduling performs sch...