Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Journal of Information Science and Engineering, Vol.18 No.6, pp.1037-1048 (November 2002)


Locality-Preserving Dynamic Load Balancing
for Data-Parallel Applications
on Distributed-Memory Multiprocessors

Pangfeng Liu, Jan-Jan Wu and Chih-Hsuae Yang*
*Department of Computer Science and Information Engineering
National Taiwan University
Taipei, 106 Taiwan
*Institute of Information Science
Academia Sinica
Taipei, 115 Taiwan

Load balancing and data locality are the two most important factors affecting the performance of parallel programs running on distributed-memory multiprocessors. A good balancing scheme should evenly distribute the workload among the available processors, and locate the tasks close to their data to reduce communication and idle time. In this paper, we study the load balancing problem of data-parallel loops with predictable neighborhood data references. The loops are characterized by variable and unpredictable execution time due to dynamic external workload. Nevertheless the data referenced by each loop iteration exploits spatial locality of stencil references. We combine an initial static BLOCK scheduling and a dynamic scheduling based on work stealing. Data locality is preserved by careful restrictions on the tasks that can be migrated. Experimental results on a network of workstations are reported.

Keywords: load balancing, data locality, MPI, work stealing, data parallel computation

Full Text () Retrieve PDF document (200211_11.pdf)

Received September 12, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Makoto Takizawa and Myongsoon Park.