Waiting Algorithms for Synchronization in Large-Scale Multiprocessors

摘要

A program running on a parallel machine consists of multiple asynchronous threadsthat have to synchronize at various points to ensure program correctness. At a synchronization point, a thread may be forced to wait until the synchronization condition is satisfied. Waiting incurs a cost. This thesis investigates various types of synchronization mechanisms and techniques to minimize wasted processor cycles while waiting algorithms and multithreading are used to reduce the cost of waiting. The utility of these methods are analyzed with mathematical models and demonstrated through simulations. Two-phase waiting algorithms that rely on efficient waiting mechanisms provided by multithreaded processors are shown to be very robust under most operating circumstances.