Towards the Scalability of Dynamic Loop Scheduling Techniques via Discrete Event Simulation

Abstract

To improve their performance, scientific applications often use loop scheduling algorithms as techniques for load balancing data parallel computations. Over the years, a number of dynamic loop scheduling (DLS) techniques have been developed. These techniques are based on probabilistic analyses, and are effective in addressing unpredictable load imbalances in the system arising from various sources, such as, variations in application, algorithmic, and systemic characteristics. Modern, high-end computing facilities can now offer petascale performance (10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">15</sup> flops), and several initiatives have already begun with the goal of achieving exascale performance (10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">18</sup> flops) towards the end of the current decade. Efficient and scalable algorithms are therefore required to utilize the petascale and exascale resources. In this paper, a study of the scalability of DLS techniques via discrete event simulation is presented, both in terms of number of processors, and problem size. To facilitate the scalability study, a dynamic loop scheduler was designed and was implemented using the SimGrid simulation framework. The results of the study demonstrate the scalability of the DLS techniques and their effectiveness in addressing load imbalance in large scale computing systems.