Efficient Parallel Determinacy Race Detection for Structured Futures

In task-parallel code, a determinancy race occurs when two logically parallel instructions access the same memory location in a conflicting way. A determinacy race tends to be a bug as it leads to non-deterministic program behaviors. Researchers have studied algorithms for detecting determinacy races in task-parallel code, with most prior work focuses on computations with nice structural properties (e.g., fork-join or pipeline parallelism). For such computations, one can devise provably efficient algorithms with constant overhead, leading to a asymptotically optimal running time --- O(T_1 / P + T_∞) on P cores for a computation with T_1 work and T_∞ span. More recently, researchers have begun to address the problem of race detecting computations with less structural properties, such as ones that arise from the use of futures. Due to the lack of structural properties, the race detection algorithm incurs higher overhead. % Given a computation with work T_1 and span T_∞, the state-of-the-art parallel algorithm for race detecting programs with futures runs in time O((T_1 lgk + k^2) / P + T_∞(lg k + lgr lgk )) on P cores (Xu ηl, 2020), where k is the total number of futures used, k is the maximum number of future operations per "future task,'' and r is the maximum number of readers between two consecutive writes to a given memory location. Interestingly, it has been shown that when one imposes certain restrictions on the use of futures, referred to as the structured futures, although the restrictions do not entirely eliminate arbitrary dependences among subcomputations, one can race detect such programs more efficiently than that for programs with general futures (i.e., no restrictions). The improved efficiency has only been demonstrated for a sequential algorithm (Utterback ηl, 2019) that race detects while executing the computation sequentially, however. The algorithm requires sequential execution, because the correctness of the algorithm relies on updating the necessary data structures while traversing the computation dag in a specific order. An interesting question remains, whether a parallel algorithm exists for race detecting programs with structured future that achieves better execution time compared to that designed for general futures. This work attempts to answer this question. We propose a parallel algorithm designed to race detect structured futures. By exploiting the restrictions imposed by structured futures, the proposed algorithm allows for a constant-time query while keeping fewer previous accessors around to provide the same correctness guarantees as prior work. Our algorithm runs in time O((T_1 + k^2)/P + T_∞ lg k) on P cores. We have also implemented and empirically evaluated the proposed algorithm. When compared to the state-of-the-art sequential algorithm designed for structured futures, although our algorithm has a longer one-core execution time, its absolute running time wins out when running on two cores or more. When compared to the state-of-the-art parallel algorithm designed for general futures, it indeed incurs lower overhead and performs better.