Towards transactional memory support for GCC

Martin Schindewolf, Albert Cohen, Wolfgang Karl, Andrea Marongiu, Luca Benini, Inria Saclay Île-de-france2015

TL;DR

This paper presents a design for integrating transactional memory (TM) support into the GNU Compiler Collection (GCC). This work aims to make parallel programming easier and more productive by providing an alternative to traditional lock-based concurrency, and it highlights the research challenges and opportunities that arise from this integration.

What Problem Does This Paper Address?

Parallel programming on multi-core processors is notoriously difficult, primarily due to the complexities of managing shared memory access and avoiding race conditions. Traditional synchronization mechanisms like locks are error-prone and can lead to deadlocks and performance bottlenecks. Transactional Memory (TM) offers a promising alternative by allowing programmers to define blocks of code as atomic transactions, similar to database transactions. However, the lack of a universally accepted TM semantics and production-quality compiler support has hindered its widespread adoption. This paper addresses this gap by proposing and detailing a design for a TM extension within GCC, aiming to bridge the divide between academic research and practical software development.

Methods

The core of this work is the design and implementation of a transactional memory extension for the GCC compiler. The approach is inspired by Intel's work and aims for language independence, not being tied to specific parallel programming models like OpenMP. The design involves two main compiler passes:

  • Expansion Pass (gtm_exp): This pass instruments shared memory accesses within transactional blocks by inserting calls to a Software Transactional Memory (STM) library (TinySTM in this case). It also handles function cloning for functions called within transactions and recombines basic blocks.
  • Checkpointing Pass (gtm_checkpoint): This pass implements a mechanism to revert the program state in case a transaction aborts. It uses setjmp and longjmp to save and restore registers and stack variables, ensuring atomicity. The pass operates on SSA (Static Single Assignment) form to efficiently manage live-in variables.

The design also introduces new GIMPLE tree codes and modifies the control flow graph to manage transactional sections.

Datasets

Not discussed in the paper. The paper focuses on the compiler design and its potential applications, with experimental results presented for synthetic benchmarks.

Key Insights and Ideas

  • Orthogonality to Existing Models: A key design goal was to make the TM extension orthogonal to other parallel programming models, allowing it to coexist and potentially integrate with them later.
  • STM as a Foundation: The design relies on Software Transactional Memory (STM) libraries, emphasizing the crucial role of compiler optimizations in mitigating STM overhead.
  • Checkpointing for Rollback: The setjmp/longjmp based checkpointing mechanism is a practical approach to handle transaction rollbacks, aiming to be efficient for common use cases.
  • Leveraging GCC Infrastructure: The design leverages GCC's intermediate representation (GIMPLE) and optimization passes (like SSA form) to facilitate the implementation and potential for further optimizations.
  • Research Opportunities: The paper highlights several areas for future research, including optimizing TM barriers, exploring hybrid hardware/software TM, and integrating TM with automatic parallelization for irregular reductions.

Key Results

The paper primarily focuses on the design and implementation of the TM extension for GCC. While it doesn't present extensive quantitative results from large-scale benchmarks, it does show performance comparisons for a synthetic loop containing a histogram reduction (Figure 4). These results indicate that:

  • In scenarios with low contention (random image data), the transactional approach generally outperforms lock-based synchronization.
  • High contention on array elements significantly impacts TM performance, leading to more frequent transaction rollbacks and restarts, which can be more costly than lock-based approaches.
  • The performance is influenced by the amount of work within the loop (parameter M) and the degree of contention.

The paper also discusses the potential for significant performance improvements with transactional approaches for irregular reduction parallelization compared to locks, especially when adequately tuning parameters.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • False Conflicts: The paper identifies "false conflicts" as a key issue in TM, where transactions abort even when they don't logically conflict, leading to performance degradation.
  • Over-instrumentation: The current approach instruments all pointer-based accesses, which can lead to unnecessary overhead. Future work aims to use GCC's escape information to restrict instrumentation to shared locations.
  • Quiescence Overhead: The quiescence mechanism, used to ensure ordering, can incur significant performance penalties. Research is needed to speed up transaction execution while maintaining compatibility with easy lock-based code trans-ification.
  • Overhead Amortization: The overhead of starting and committing transactions needs to be amortized by computation, especially in scenarios with high contention and little work.
  • Irrevocable Transactions: The paper discusses the need for irrevocable transactions (for system calls or legacy code) and suggests further research into their implementation and optimization.
  • Link-Time Optimization (LTO) and JIT: The potential of LTO and JIT compilation for TM workloads is highlighted as an area for future exploration.
  • Integration with OpenMP: While designed to be language-independent, future work may involve integrating TM support into GCC's OpenMP passes and runtime.
  • Automatic Parallelization: The paper proposes extending the automatic parallelization pass to support sparse, generalized reductions using TM, potentially enabling speculative execution.

Summary updated

Abstract

Transactional memory is a parallel programming model pro-viding many advantages over lock-based concurrency. It is one important attempt to exploit the potential of multicore architectures while preserv-ing software development productivity. This paper describes the design of a transactional memory extension for GCC, and highlights research challenges and perspectives enabled by this design. Key words: GCC, Transactional Memory, STM
BibTeX
@misc{schindewolf2015towards,
  author = {Martin Schindewolf and Albert Cohen and Wolfgang Karl and Andrea Marongiu and Luca Benini and Inria Saclay Île-de-france},
  title = {{Towards transactional memory support for GCC}},
  year = {2015},
}
Figure