Scaling data race detection for partitioned global address space programs

Chang-Seo Park, Koushik Sen, Costin IancuIcs 2013 · DOI

TL;DR

This paper introduces a novel data race detection tool for Partitioned Global Address Space (PGAS) programs, specifically targeting UPC. By combining hierarchical sampling with an aliasing persistence heuristic, they achieve a significant reduction in overhead, making large-scale parallel program debugging more feasible.

What Problem Does This Paper Address?

Modern High-Performance Computing (HPC) systems increasingly rely on hybrid parallelism models, where shared memory abstractions like Partitioned Global Address Spaces (PGAS) are used alongside message passing. This programming style, while powerful, introduces a common and notoriously difficult bug: data races. Data races occur when multiple threads access the same memory location without proper synchronization, and at least one access is a write. Existing data race detection tools often struggle with the scale of modern HPC systems, exhibiting significant performance degradation (slowdowns of 10x-100x) and failing to adequately handle the complexities of hybrid parallelism. Specifically, many tools either focus solely on shared memory or only instrument communication calls, missing races involving direct memory accesses through pointers.

Methods

The core contribution of this paper is the development of a scalable data race detection tool for UPC, an extension of C for PGAS programming. The authors build upon an existing tool, UPC-Thrille, and extend it to track all memory references, including those through C pointers, not just communication calls. To combat the inherent overhead of such comprehensive tracing, they introduce two key techniques:

  • Hierarchical Sampling: This approach combines function-level and instruction-level sampling. Instead of uniformly sampling every instruction, it dynamically controls the granularity of instrumentation. This allows for amortizing the cost of instrumentation decisions across function calls while retaining fine-grained control at the instruction level when necessary.
  • Aliasing Persistence Heuristic: PGAS languages often involve complex memory management where global references are frequently cast to local pointers for performance. The authors exploit the observation that these aliases tend to persist throughout program execution. By caching the "locality" (private or global) of a reference expression once determined, they avoid repeated expensive runtime checks, significantly reducing instrumentation overhead.

Datasets

The authors evaluate their tool using the following benchmarks:

  • NAS Parallel Benchmarks (NPB): Specifically, classes C and D are used, representing a range of scientific computations (e.g., multigrid, sparse-matrix operations, Fast Fourier Transformation). These benchmarks are chosen for their relevance to scientific computing and their use of bulk communication.
  • Fine-grained benchmarks: guppie (random read/modify/write accesses to a global array) and psearch (parallel unbalanced tree search with work stealing) are used to represent communication patterns common in data structure initializations, dynamic load balancing, and remote event signaling.

Key Insights and Ideas

  • Function Sampling is Not for Scientific Programs: Counterintuitively, the authors found that function-level sampling, while effective for some shared-memory applications, performs poorly for scientific programs. As scientific applications often involve deeply nested loops executing billions of instructions, function sampling leads to an overwhelming number of references being tracked within a single function call, causing analysis to not terminate or exhibit extreme slowdowns.
  • Instruction Sampling is Necessary for Scientific Code: Instruction-level sampling, despite its higher per-instruction overhead, provides better control and scalability for scientific workloads because it spreads the tracking of memory references more evenly over program execution.
  • Aliasing Persistence is Crucial for PGAS: The heuristic exploiting the persistence of locality for aliased pointers is vital for reducing overhead in PGAS. The expensive operation of determining global vs. local access can be done once per alias, rather than per access, leading to substantial gains.
  • Synergy is Key: Neither hierarchical sampling nor the aliasing heuristic alone is sufficient to achieve acceptable overheads. It's their combination that unlocks significant performance improvements, reducing overheads from 10x (with individual techniques) to as low as 50% when applied together.

Key Results

  • Significant Overhead Reduction: The combined approach of hierarchical sampling and the aliasing heuristic reduced the maximum overhead from 65x (with instruction sampling alone) to at most 50% when running on 2048 cores.
  • Scalability Achieved: The tool successfully finds all previously known data races in their benchmark programs, even at large scales (up to 2048 cores).
  • Function Sampling Failure: For scientific programs, function sampling often resulted in non-termination or extreme slowdowns (DNF - Did Not Finish), while instruction sampling achieved up to 65x slowdown but completed execution.
  • New Races Found: The extended tool uncovered previously unknown data races in NAS CG, attributed to the ability to track global-to-local memory aliases.

Limitations and Future Work

  • False Negatives with Aliasing Heuristic: The authors acknowledge that the aliasing persistence heuristic could potentially lead to false negatives if the locality of an alias changes dynamically in ways not captured by the runtime caching. They suggest that compiler support could help invalidate cached locality information more precisely.
  • Further Granularity Refinement: While hierarchical sampling considers function and instruction levels, the authors ponder if further refinement, such as considering loop nests, could improve performance. However, they note that instrumenting entire loop nests can also lead to high overhead, suggesting that "peeling off" a few instrumented loop iterations might be a more viable path.
  • Alternative Data Structures: The performance of the Interval Skiplist, used for managing memory ranges, could be improved with data structures offering better scalability characteristics, although the authors note that instrumentation overhead currently dominates.
  • Future Work: The authors plan to extend their work to provide maximum coverage within a given time budget (e.g., guaranteeing no more than 2x slowdown). They also intend to explore more sophisticated sampling strategies, including proportional sampling per region stack, k-region context sampling, and combinations of proportional and exponential back-off.

Summary updated

BibTeX
@inproceedings{park2013scaling,
  author = {Chang-Seo Park and Koushik Sen and Costin Iancu},
  title = {{Scaling data race detection for partitioned global address space programs}},
  booktitle = {Ics},
  year = {2013},
  doi = {10.1145/2464996.2465000},
}
Figure