Extending a Work-Stealing Framework with Probabilistic Guards

摘要

We propose probabilistic guards and analyze their performance. To reduce the total task division cost, probabilistic guards can prevent thief workers from stealing small tasks from victim workers probabilistically. In this study, we have implemented probabilistic guards on a work-stealing framework called Tascell and have confirmed that they perform well. In theory, a thief may repeat an unbounded number of probabilistically prevented steal attempts until success if a victim uses a probabilistic guard that rejects steal attempts with a non-zero probability. Therefore, in this paper, we also propose a mechanism that invalidates probabilistic guards on demand by setting an upper limit to the number of repeated probabilistically prevented steal attempts. We evaluate its potential effects on probabilistic guards by measuring the actual numbers of repeated attempts until success. We also evaluate the performance of probabilistic guards with various upper limits. Finally, we propose and evaluate virtual probabilistic guards that act as probabilistic guards without repeating probabilistically prevented steal attempts and they exhibit superior performance.