Title :
Adaptively scheduling parallel loops in distributed shared-memory systems
Author :
Yan, Yong ; Jin, Canming ; Zhang, Xiaodong
Author_Institution :
High Performance Comput. & Software Lab., Texas Univ., San Antonio, TX, USA
fDate :
1/1/1997 12:00:00 AM
Abstract :
Using runtime information of load distributions and processor affinity, the authors propose an adaptive scheduling algorithm and its variations from different control mechanisms. The proposed algorithm applies different degrees of aggressiveness to adjust loop scheduling granularities, aiming at improving the execution performance of parallel loops by making scheduling decisions that match the real workload distributions at runtime. They experimentally compared the performance of the algorithm and its variations with several existing scheduling algorithms on two parallel machines: the KSR-1 and the Convex Exemplar. The kernel application programs used for performance evaluation were carefully selected for different classes of parallel loops. The results show that using runtime information to adaptively adjust scheduling granularity is an effective way to handle loops with a wide range of load distributions when no prior knowledge of the execution can be used. The overhead caused by collecting runtime information is insignificant in comparison with the performance improvement. The experiments show that the adaptive algorithm and its five variations outperformed the existing scheduling algorithms
Keywords :
distributed memory systems; parallel algorithms; parallel machines; parallel programming; processor scheduling; resource allocation; shared memory systems; software performance evaluation; subroutines; Convex Exemplar; KSR-1; adaptive parallel loop scheduling; adaptive scheduling algorithm; aggressiveness; control mechanisms; distributed shared-memory systems; execution performance; kernel application programs; load distributions; loop scheduling granularity adjustment; parallel machines; performance evaluation; processor affinity; runtime information; scheduling decisions; Adaptive algorithm; Adaptive scheduling; Control systems; Dynamic scheduling; Heuristic algorithms; Kernel; Parallel machines; Processor scheduling; Runtime; Scheduling algorithm;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on