Dynamic Load Balancing
The "Card Game"

Cards

  • Parallel algorithm uses the Message Passing Interface (MPI) for communication.
  • The total number of observations is divided into chunks or aliquots such that the number of aliquots (naliquot) is larger than the number of processors.
  • The algorithm uses a master/slave relationship among processors.
  • The master process serves as a "card dealer" by first distributing centroid coordinates to all slave processes, and then distributing an aliquot of observations (or "card") to each slave process.
  • Slaves assign each observation in their aliquot to a centroid, and then report the results back to the master.
  • If additional aliquots (or "cards") remain to be processed ("in the deck"), the master will "deal" the slave another "card" for processing.
  • As a result, faster and less-busy nodes effectively perform the majority of the processing for each iteration.
  • If the load on the nodes changes during a run, the distribution of work will automatically be shifted away from busy or slow nodes onto idle or faster nodes.