Nearest Neighbor Algorithms for Load Balancing in Parallel Computers

With nearest neighbor load balancing algorithms, a processor makes balancing decisions based on localized workload information and manages workload migrations within its neighborhood. This paper compares a couple of fairly well-known nearest neighbor algorithms, the dimension-exchange (DE, for short) and the diffusion (DF, for short) methods and their several variants---the average dimension-exchange (ADE), the optimally-tuned dimension-exchange (ODE), the local average diffusion (ADF) and the optimally-tuned diffusion (ODF). The measures of interest are their efficiency in driving any initial workload distribution to a uniform distribution and their ability in controlling the growth of the variance among the processors' workloads. The comparison is made with respect to both one-port and all-port communication architectures and in consideration of various implementation strategies including synchronous/asynchronous invocation policies and static/dynamic random workload behaviors. It t..