Can I read Race Detection in Two Dimensions on EtoBox?

Race Detection in Two Dimensions by Dimitar Dimitrov; Martin Vechev; Vivek Sarkar is a Computer Science article available to read on EtoBox.

What is Race Detection in Two Dimensions about?

Dynamic race detection is a program analysis technique for detecting errors caused by undesired interleavings of concurrent tasks. A primary challenge when designing efficient race detection algorithms is to achieve manageable space requirements. State-of-the-art algorithms for unstructured parallelism require Θ ( __n__ ) space per monitored memory location, where __n__ is the total number of tasks. This is a serious drawback when analyzing programs with many tasks. In contrast, algorithms for programs with a series-parallel (SP) structure require only Θ (1) space. Unfortunately, it is currently not well understood if there are classes of parallelism beyond SP that can also benefit from and be analyzed with Θ (1) space complexity. In this work, we show that structures richer than SP graphs, namely, that of two-dimensional (2D) lattices, can also be analyzed in Θ (1) space. Toward that (a) we extend Tarjan’s algorithm for finding lowest common ancestors to handle 2D lattices; (b) from that extension we derive a serial algorithm for race detection that can analyze arbitrary task graphs with a 2D lattice structure; (c) we present a restriction to fork-join that admits precisely the 2D

Who reads Race Detection in Two Dimensions?

Author

Dimitar Dimitrov; Martin Vechev; Vivek Sarkar

Publisher

Association for Computing Machinery (ACM)

Published

2018

Language

EN

Field

Computer Science (Physical Sciences)