Accelerating Irregular Computations with Hardware Transactional Memory and Active Messages

Maciej Besta, Torsten Hoefler

TL;DR

Atomic Active Messages (AAM) is a novel mechanism that combines Hardware Transactional Memory (HTM) with the Active Messaging model to significantly accelerate irregular graph computations. By "coarsening" multiple fine-grained vertex updates into single hardware transactions, AAM reduces synchronization overhead and achieves over 100% speedup on industry-standard benchmarks like Graph500.

What Problem Does This Paper Address?

Graph analytics—powering everything from social network analysis to machine learning—is notoriously difficult to parallelize efficiently. These computations are "irregular": they are data-driven, lack locality, and involve massive numbers of fine-grained updates to shared data structures.

Traditional synchronization methods like locks or atomic operations (e.g., Compare-and-Swap) often become bottlenecks. Locks are slow and complex to manage, while fine-grained atomics incur high per-operation overhead. Furthermore, in distributed-memory systems, managing data flow between nodes adds another layer of complexity. The authors seek a way to simplify programming while boosting performance across both shared- and distributed-memory architectures.

Methods

The authors introduce Atomic Active Messages (AAM), which leverages two key technologies:

  1. Hardware Transactional Memory (HTM): Instead of using locks, code blocks (transactions) are executed speculatively. The hardware ensures they either complete atomically or roll back if a conflict occurs.
  2. Active Messages (AM): A communication model where messages carry their own "handlers"—functions that execute immediately upon arrival at the destination node.

The "secret sauce" of AAM lies in two optimization techniques:

  • Coarsening: Rather than executing one transaction per vertex update, the runtime groups $M$ updates into a single, coarser hardware transaction. This amortizes the fixed overhead of starting and committing transactions.
  • Coalescing: In distributed settings, multiple active messages destined for the same remote node are bundled together to save network bandwidth and reduce message-processing overhead.

The authors also developed an ownership protocol to handle transactions that span multiple nodes by physically relocating required graph elements to the executing node's local memory before starting the transaction.

Datasets

The researchers evaluated AAM using a mix of synthetic and real-world datasets:

  • Synthetic Graphs: Kronecker graphs (modeling power-law distributions typical of social networks) and Erdős-Renyi graphs (random graphs with binomial/Poisson distributions).
  • Real-World Graphs (SNAP Library): A diverse set including communication networks (wiki-Talk), social networks (LiveJournal, Orkut), road networks, and citation graphs.
  • Benchmarks: The system was integrated into and compared against high-performance frameworks like Graph500, Galois, and PBGL.

Key Insights and Ideas

  • The "Sweet Spot" for Transaction Size: There is a critical trade-off in transaction coarsening. Larger transactions ($M$) reduce overhead but increase the probability of aborts due to memory conflicts or hardware limitations (like buffer overflows). Finding the optimal $M$ is key to performance.
  • Hardware Matters: The architecture significantly impacts HTM efficiency. For example, IBM Blue Gene/Q's HTM (which uses a large L2 cache for speculative state) handles much larger transactions ($M \approx 80-144$) than Intel Haswell's L1-based HTM ($M \approx 2$).
  • Linear Performance Model: The authors successfully validated a simple linear model to predict when HTM will outperform traditional atomics. While a single HTM transaction is more expensive than a single atomic operation, coarsening allows HTM to eventually "cross over" and become more efficient as $M$ increases.
Figure 2: (§ 5.3) The validation of the performance model.

Key Results

  • Intra-node Speedups: On the IBM Blue Gene/Q supercomputer, AAM-HTM achieved up to a 102% speedup over the highly optimized Graph500 BFS baseline. On Intel Haswell, it delivered up to a 27% speedup.
  • Distributed Performance: For PageRank on distributed-memory machines, AAM outperformed the Parallel Boost Graph Library (PBGL) by 3–10x, largely due to efficient message coalescing and better utilization of intra-node parallelism.
  • Phase-by-Phase Efficiency: As shown in Figure 1, AAM-HTM significantly reduces the time spent in the most intensive phases of a Breadth-First Search (BFS) traversal compared to traditional atomics.
Comparison of BFS phase durations: AAM-HTM (purple) consistently outperforms traditional atomics (black) during the most compute-intensive iterations.

Limitations and Future Work

  • Manual Tuning: Currently, the optimal transaction size $M$ must be determined through empirical analysis for different architectures and graph types. The authors suggest that future work could involve online algorithms for the automatic selection of $M$.
  • Hardware Constraints: The performance on commodity hardware (like Haswell) is limited by small L1 caches, which cause frequent transaction aborts if too much data is touched. Future HTM designs with larger speculative buffers would benefit AAM significantly.
  • Compiler Integration: The authors envision a compiler pass that could automatically pattern-match graph operators and transform them into coarsened AAM transactions.

Summary updated

Abstract

We propose Atomic Active Messages (AAM), a mechanism that accelerates irregular graph computations on both shared- and distributed-memory machines. The key idea behind AAM is that hardware transactional memory (HTM) can be used for simple and efficient processing of irregular structures in highly parallel environments. We illustrate techniques such as coarsening and coalescing that enable hardware transactions to considerably accelerate graph processing.We conduct a detailed performance analysis of AAM on Intel Haswell and IBM Blue Gene/Q and we illustrate various performance tradeoffs between different HTM parameters that impact the efficiency of graph processing. AAM can be used to implement abstractions offered by existing programming models and to improve the performance of irregular graph processing codes such as Graph500 or Galois.
BibTeX
@inproceedings{besta2015accelerating,
  author = {Maciej Besta and Torsten Hoefler},
  title = {{Accelerating Irregular Computations with Hardware Transactional Memory and Active Messages}},
  booktitle = {HPDC},
  year = {2015},
  doi = {10.1145/2749246.2749263},
}
Figure