A Load Balancing Tool for Distributed Parallel Loops
Carino, R.L., & Banicescu, I. (2003). A Load Balancing Tool for Distributed Parallel Loops. Proc. 2003 International Workshop on Challenges of Large Applications in Distributed Environments. Seattle, WA: IEEE Computer Society Press. 39-46.
Abstract
Large scale applications typically contain parallel loops with
many iterates. The iterates of a parallel loop may have variable
execution times which translate into performance degradation
of an application due to load imbalance.
This paper describes
a tool for load balancing parallel loops on
distributed-memory systems. The tool assumes that the data for a
parallel loop to be executed is already partitioned among the
participating processors. The tool utilizes the MPI library for
interprocessor coordination, and determines processor workloads
by loop scheduling techniques. The tool was designed
independent of any application; hence, it must be supplied with a
routine that encapsulates the computations for a chunk of
loop iterates, as well as the routines to transfer data
and results between processors. Performance evaluation
on a Linux cluster indicates that the tool reduces the cost of
executing a simulated irregular loop without load balancing
by up to 73%. The tool is
useful for parallelizing sequential applications with
parallel loops,
or as an alternate load balancing routine for existing parallel
applications.