|
Abstract : |
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 rst waits by polling a synchronization variable. If the cost of polling reaches a limit Lpoll and further waiting is necessary, the thread is blocked, incurring an additional xed cost, B. The choice of Lpoll is a critical determinant of the performance of two-phase algorithms. We focus on methods for statically determining Lpoll because the run-time overhead of dynamically determining Lpoll can be comparable to the cost of blocking in large-scale multiprocessor systems with lightweight threads. Our experiments show that always-block (Lpoll =0)isagoodwaiting 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 Lpoll based on knowledge of likely waittime distributions. Motivated by the observation that di erent synchronization types exhibit di erent wait-time distributions, we prove that a static choice of Lpoll can yield close to optimal on-line performance against an adversary that is restricted to choosing wait times from a xed family of probability distributions. This result allows us to make an optimal static choice of Lpoll based on synchronization type. For exponentially distributed wait times, we prove that setting Lpoll = ln(e,1)B results in a waiting cost that is no more than e=(e,1) times the cost of an optimal o-line algorithm. For uniformly distributed wait times, we prove that setting Lpoll = 1 2 (p 5, 1)B results in a waiting cost that is no more than ( p 5+1)=2 (the golden ratio) times the cost of an optimal o-line algorithm. Experimental measurements of several parallel applications on the Alewife multiprocessor simulator corroborate our theoretical ndings. 1, |
