TY - GEN
T1 - Turning nondeterminism into parallelism
AU - Tripp, Omer
AU - Koskinen, Eric
AU - Sagiv, Mooly
PY - 2013
Y1 - 2013
N2 - Nondeterminism is a useful and prevalent concept in the design and implementation of software systems. An important property of nondeterminism is its latent parallelism: A nondeterministic action can evaluate to multiple behaviors. If at least one of these behaviors does not conflict with concurrent tasks, then there is an admissible execution of the action in parallel with these tasks. Unfortunately, existing implementations of the atomic paradigm-optimistic as well as pessimistic-are unable to fully exhaust the parallelism potential of nondeterministic actions, lacking the means to guide concurrent tasks toward nondeterministic choices that minimize interference. This paper investigates the problem of utilizing parallelism due to nondeterminism. We observe that nondeterminism occurs in many real-world codes. We motivate the need for devising coordination mechanisms that can utilize available nondeterminism. We have developed a system featuring such mechanisms, which leverages nondeterminism in a wide class of query operations, allowing a task to look into the future of concurrent tasks that mutate the shared state during query evaluation and reduce conflict accordingly. We evaluate our system on a suite of 12 algorithmic benchmarks of wide applicability, as well as an industrial application. The results are encouraging.
AB - Nondeterminism is a useful and prevalent concept in the design and implementation of software systems. An important property of nondeterminism is its latent parallelism: A nondeterministic action can evaluate to multiple behaviors. If at least one of these behaviors does not conflict with concurrent tasks, then there is an admissible execution of the action in parallel with these tasks. Unfortunately, existing implementations of the atomic paradigm-optimistic as well as pessimistic-are unable to fully exhaust the parallelism potential of nondeterministic actions, lacking the means to guide concurrent tasks toward nondeterministic choices that minimize interference. This paper investigates the problem of utilizing parallelism due to nondeterminism. We observe that nondeterminism occurs in many real-world codes. We motivate the need for devising coordination mechanisms that can utilize available nondeterminism. We have developed a system featuring such mechanisms, which leverages nondeterminism in a wide class of query operations, allowing a task to look into the future of concurrent tasks that mutate the shared state during query evaluation and reduce conflict accordingly. We evaluate our system on a suite of 12 algorithmic benchmarks of wide applicability, as well as an industrial application. The results are encouraging.
KW - Concurrency control
KW - Nondeterminism
KW - Parallelism
KW - Serializability
KW - Synchronization
UR - http://www.scopus.com/inward/record.url?scp=84888157286&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84888157286&partnerID=8YFLogxK
U2 - 10.1145/2509136.2509533
DO - 10.1145/2509136.2509533
M3 - Conference contribution
AN - SCOPUS:84888157286
SN - 9781450323741
T3 - Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, OOPSLA
SP - 589
EP - 604
BT - SPLASH Indianapolis 2013
T2 - 2013 28th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2013
Y2 - 29 October 2013 through 31 October 2013
ER -