Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1995-01-01

Filename

WUCS-95-05.PDF

Technical Report Number

WUCS-95-05

Abstract

Effective load balancing algorithms are crucial in fully realizing the performance potential of parallel computer systems. This paper proposes a general matrix iterative model to represent a range of dynamic load balancing algorithms. The model and associated performance measures are used to evaluate and compare vairous load balancing algorithms and derive optimal algorithms and associated parameters for a given application and multiprocessor system. The model is parameterized to represent three load balancing algorithms - the random strategy, diffusion and complete redistribution algorithms. The model is validated by comparing the results with measured performance on a realistic workload. The parallel N-body simulation applicaton used for this purpose has a number of interesting properties and is representattive of a wide class of realistic scientific applications. The performance of the three algorithms are compared and optimal algorithm parameters derived for the application. The random strategy outperforms both the diffusion (12% better) and the redistribution (30% better) algorithms and its performance is within 25% of the ideal load balance case. General performance models such as the one presented in this paper can be used to guide the algorithm designer in choosing the best algorithm and associated parameters for a given environment.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7Z60M7K

Download

Share

COinS