Nearest-neighbor algorithms for load-balancing in parallel computers

Abstract

Two nearest-neighbor algorithms, the dimension-exchange and the diffusion methods and their variants - optimally tuned dimension-exchange (ODE) and optimally tuned diffusion (ODF) are compared. The comparison is made with respect to both one-port and all-port communication architectures and in considerations of various implementation strategies including synchronous/asynchronous invocation policies and static/dynamic random workload behaviors. Result show that the dimension exchange method outperforms the diffusion method in one-port communication model. In particular, the ODE algorithm is best suited for statically synchronous implementations of a load-balancing process regardless of its underlying communication models. The strength of the diffusion method is in asynchronous implementations in the all-port communication model; the ODF is algorithm performs best in that case.