Minimum cost adaptive synchronization
Edward Mascarenhas, Felipe Knop, Vernon J. Rego · 1997
We present a novel adaptive synchronization algorithm, called the minimum average cost (MAC) algorithm, in the context of the PARASOL parallel simulation system.PARASOL is a multithreaded system for parallel simulation on shared-and distributedmemory environments, designed to support domainspecific Simulation Object Libraries.The proposed MAC algorithm is based on minimizing the cost of synchronization delay and rollback at a process, whenever its simulation driver must decide whether to either proceed optimistically or to delay processing.In the former case the risk is rollback cost, in the event of a straggler's arrival.In the latter case the risk is unnecessary delay, in the event a latecomer is not a straggler.In addition to the MAC algorithm and an optimal delay computation model, we report on some early experiments comparing the performance of MAC-based adaptive synchronization to optimistic synchronization.