A simple dynamic loadbalancing scheme for paralle

Authors: Naohito Sato JeanMarc Jézéquel

Publish Date: 1999/4/12

Volume: , Issue: , Pages: 260-269

PDF Link

Abstract

We propose a simple and efficient loadbalancing scheme for parallel molecular dynamics simulation on distributed memory machines It decomposes spatial domain of particles into disjoint parts each of which corresponds with a processor and dynamically changes its shape to keep about the same number of particles throughout the simulation In contrast to other similar schemes ours requires no longdistance interprocessor communications but only those among adjacent processors thus little communication overheads whereas it still guarantees fast reduction of loadimbalance among the processors It owes these advantages mainly to the following features 1 The sufficiently correct global load information is effectively obtained with stepwise propagation of appropriate information via nearest neighbor communication 2 In addition to the global loadbalancing another loadbalancing procedure is also invoked on each processor without global load information in order to suppress rapid increase or decrease of loads Thus informations from remote processors can provide reliable values even after a certain period of delay Further we discuss how to select loads to migrate among processors so that spatial locality of the processors may be preserved Through preliminary evaluation on an uniprocessor workstation we have shown the scheme has strong potential for largescale parallel molecular dynamics simulation on distributed memory machines or workstation clusters

Keywords: