A Tool for a Two-level Dynamic Load Balancing Strategy in Scientific Applications

Carino, R.L., & Banicescu, I. (2007). A Tool for a Two-level Dynamic Load Balancing Strategy in Scientific Applications. In Dana Petcu (Ed.), Scalable Computing: Practice and Experience (Special Issue on Practical Aspects of Large-Scale Distributed Computing). SWPS. 8(3), 249-261.

This paper describes a dynamic load balancing tool intended for computational investigators who have little familiarity with programming for a message-passing environment. Motivated by the PAR DOALL directive available in some compilers for shared-memory systems, the tool is designed to simplify the manual conversion of sequential programs containing computationally intensive one- or two-dimensional loops with independent iterates into parallel programs that execute with high efficiency on general-purpose clusters. The tool implements a dynamic loop scheduling strategy to address load imbalance which may be induced by the non-uniformity of loop iterate times, and by the heterogeneity of processors. The tool is based on the Message Passing Interface library for wide availability. Experimental results of two scientific applications that utilize the tool on a Linux cluster are presented to demonstrate sample achievable performance, and to underscore the effectiveness of the two-level dynamic load balancing strategy.