Diffusive dynamic load balancing by terrain parcel swaps for event-driven simulation of communicating vehicles
William P. Niedringhaus · 2002
A diffusive dynamic load balancing algorithm is presented for a wargaming simulation which is parallelized by partitioning the battlefield terrain among the nodes. Each node simulates vehicles on its local terrain partition. Vehicles communicate with sets of nearby vehicles within a given radius r, a region called the communication circle. A message is sent (i.e. consumes network bandwidth) unless the communication circle is local-that is, entirely within the originating node's terrain partition. The algorithm continuously accomplishes two (somewhat contradictory) goals: (I) dynamic load balancing through repartitioning the terrain via swaps of small discrete terrain parcels and vehicles therein, and (2) maximizing the proportion of communication circles that are local and thus require no network bandwidth. Item (2) in essence means regularizing the shapes of each node's terrain partition, so that lopsided dimensions, marked concavities, long thin peninsulas, etc., are avoided.>