A Method for Creating Near-Optimal Instances of a Certified Write-All Algorithm

摘要

This paper shows how to create near-optimal instances of the Certified Write- All algorithm called AWT that was introduced by Anderson and Woll. This algorithm is the best known deterministic algorithm that can be used to simulate n synchronous parallel processors on n asynchronous processors. In this algorithm n processors update n memory cells and then signal the completion of the updates. The algorithm is instantiated with q permutations, where q can be chosen from a wide range of values. When implementing a simulation on a specific parallel system with n processors, one would like to use an instance of the algorithm with the best possible value of q, in order to maximize the efficiency of the simulation. This paper shows that the choice of q is critical for obtaining an instance of the AWT algorithm with near-optimal work. For any ε > 0, and any large enough n, work of any instance of the algorithm must be at least n~(1+(1-ε))(2 ln ln n/ln n)~(1/2). Under certain conditions, however, that q is about e~(1/2 ln n ln ln n)~(1/2) and for infinitely many large enough n, this lower bound can be nearly attained by instances of the algorithm with work at most n~(1+(1+ε))(2 ln ln n/ln n)~(1/2). The paper also shows a penalty for not selecting q well. When q is significantly away from e~(1/2 ln n ln ln n)~(1/2) then work of any instance of the algorithm with this displaced q must be considerably higher than otherwise.