Waiting Algorithms for Synchronization in Large-Scale Multiprocessors

Through analysis and experiments, this paper investigates two-phase waiting algorithms to minimize the cost of waiting for synchronization in large-scale multiprocessors. In a two-phase algorithm, a thread first waits by polling a synchronization variable. If the cost of polling reaches a limit L poll and further waiting is necessary, the thread is blocked, incurring an additional fixed cost, B. The choice of L poll is a critical determinant of the performance of two-phase algorithms. We focus on methods for statically determining L poll because the run-time overhead of dynamically determining L poll can be comparable to the cost of blocking in large-scale multiprocessor systems with lightweight threads. Our experiments show that always-block (L poll = 0) is a good waiting algorithm with performance that is usually close to the best of the algorithms compared. We show that even better performance can be achieved with a static choice of L poll based on knowledge of likely waittime distr..