부산대학교 도서관

Summary: ``It is known that any algorithm for {\it work-stealing} in the standard asynchronous shared memory model must use expensive $\ssf{Read}$-$\ssf{After}$-$\ssf{Write}$ synchronization patterns or atomic $\ssf{Read}$-$\ssf{Modify}$-$\ssf{Write}$ instructions. There have been proposed algorithms for relaxations in the standard model and algorithms in restricted models that avoid the impossibility result, but only in some operations. \par ``This paper considers work-stealing with {\it multiplicity}, a relaxation in which every task is taken by {\it at least} one operation, with the requirement that any process can extract a task {\it at most once}. Two versions of the relaxation are considered and two {\it fully} $\ssf{Read}$/$\ssf{Write}$ algorithms are presented in the standard asynchronous shared memory model, both devoid of $\ssf{Read}$-$\ssf{After}$-$\ssf{Write}$ synchronization patterns in all its operations, the second algorithm additionally being {\it fully fence-free}, namely, no specific ordering among the algorithm's instructions is required, beyond what is implied by data dependence. To our knowledge, these are the first algorithms for work-stealing possessing all these properties. Our algorithms are also wait-free solutions of relaxed versions of single-enqueue multi-dequeuer queues. The algorithms are obtained by reducing work-stealing with multiplicity and weak multiplicity to $\ssf{MaxRegister}$ and $\ssf{RangeMaxRegister}$, a relaxation of $\ssf{MaxRegister}$ which might be of independent interest. An experimental evaluation shows that our fully fence-free algorithm exhibits better performance than Cilk THE, Chase-Lev and Idempotent Work-Stealing algorithms.''