Learning to Parallelize with OpenMP by Augmented Heterogeneous AST Representation

Le Chen, Quazi Ishtiaque Mahmud, Hung Phan, Nesreen K. Ahmed, Ali Jannesari

Abstract

Writing efficient parallel code remains a significant challenge in software engineering, often requiring specialized expertise to navigate the complexities of frameworks like OpenMP. Traditional auto-parallelization tools frequently fall short, either being too conservative in their static analysis or too resource-intensive in their dynamic execution. This paper introduces Graph2Par, a deep learning-based approach that identifies parallelizable code loops with 85% accuracy. By representing source code as a Heterogeneous Augmented Abstract Syntax Tree (Augmented-AST) and utilizing a Heterogeneous Graph Transformer (HGT), Graph2Par captures the deep structural and logical relationships necessary to identify parallelization opportunities that traditional compilers and token-based machine learning models often overlook.

Introduction

Despite the ubiquity of multi-core processors, the majority of software continues to run sequentially. Manual parallelization using OpenMP is a meticulous process, prone to subtle concurrency bugs and data races. To alleviate this, developers have historically turned to auto-parallelization tools, which generally fall into three categories, each with distinct drawbacks:

  1. Static Analysis Tools: Compilers like PLUTO or autoPar are often overly conservative. If they cannot mathematically prove 100% safety—often due to complex pointer arithmetic or function calls—they default to sequential execution, missing significant performance gains.
  2. Dynamic Analysis Tools: These tools identify parallelism by monitoring program execution. While accurate, they are slow, require representative input data, and cannot be easily integrated into a standard compilation workflow.
  3. Machine Learning Models: Recent attempts to use NLP-based models (treating code as a sequence of tokens) often fail to grasp the underlying structural logic of the program, such as data dependencies and control flow.

Graph2Par bridges this gap by treating code as a complex graph, allowing for a structural "understanding" of the program without the overhead of execution.

Methodology: The Augmented-AST

The primary innovation of Graph2Par is the Heterogeneous Augmented Abstract Syntax Tree (Augmented-AST). Rather than viewing code as a flat string, the model processes a multi-layered graph representation that integrates three critical views:

  • Syntactic Structure (AST): Captures the hierarchical nesting of code elements (e.g., identifying a for loop and its constituent statements).
  • Control Flow (CFG): Maps the potential paths the program may take during execution, including jumps and function calls. This allows the model to "see through" function calls that typically act as black boxes for static analyzers.
  • Lexical Proximity: Includes "texture edges" that connect neighboring tokens, ensuring the model maintains local context and understands the proximity of variables and operators.

To process this data, the researchers employed a Heterogeneous Graph Transformer (HGT). Unlike standard graph neural networks, the HGT is designed to distinguish between different types of edges and nodes. This allows the model to assign different weights to a "parent-child" syntax relationship versus a "data-flow" relationship, effectively learning the latent features that characterize parallelizable code.

The OMP_Serial Dataset

To train and evaluate the model, the authors curated the OMP_Serial dataset, a comprehensive benchmark for OpenMP parallelization. The dataset consists of:

  • Real-world Data: Approximately 16,000 C source files harvested from GitHub.
  • Synthetic Data: Loops generated via templates from established benchmarks like NAS and PolyBench to ensure a diverse range of parallel patterns.
  • Scale: The final dataset includes 18,598 parallelizable and 13,972 non-parallelizable loops, labeled with specific OpenMP pragmas such as private, reduction, simd, and target.

Key Results and Insights

Graph2Par demonstrates a significant advancement over both algorithmic and learning-based baselines.

Superior Detection and Accuracy

The model achieved an overall 85% accuracy in detecting parallelizable loops. In a direct comparison with traditional tools, Graph2Par identified over 17,000 parallel loops within the test set, whereas the algorithmic tool Pluto identified only 1,759. This highlights the "conservative gap" in traditional compilers that Graph2Par successfully narrows.

Pragma Prediction

Beyond simple binary classification, the model proved highly effective at suggesting specific OpenMP clauses. It achieved an F1-score of 0.91 for reductions and 0.87 for private variables, indicating a sophisticated understanding of how data is handled within a loop.

Comparison with State-of-the-Art

Graph2Par consistently outperformed PragFormer, the previous state-of-the-art token-based model. This result validates the authors' hypothesis that structural graph representations are superior to natural language processing techniques when applied to source code analysis.

Discovery Power

In a practical case study, Graph2Par successfully identified 48 parallel loops that were missed by three major algorithmic tools (DiscoPoP, PLUTO, and autoPar) simultaneously, proving its utility as a complementary tool for developers.

Limitations and Future Work

While Graph2Par represents a leap forward, certain challenges remain. The model showed lower performance when predicting simd and target pragmas, suggesting that these specific optimizations may require additional hardware-specific or vectorization-specific information not currently captured by the Augmented-AST.

Additionally, the current iteration of Graph2Par functions primarily as a classifier. The authors envision future work evolving this into a generative model capable of automatically writing complete, complex OpenMP pragmas. Finally, as a static approach, it remains unable to account for runtime-dependent data values that might occasionally inhibit parallelization in specific execution environments.

Conclusion

Graph2Par demonstrates that by combining rich structural representations with heterogeneous graph transformers, deep learning can significantly outperform traditional static analysis in the domain of parallel programming. By identifying thousands of opportunities missed by standard compilers, this research paves the way for more intelligent, automated performance optimization tools.

Summary updated

BibTeX
@inproceedings{chen2023learning,
  author = {Le Chen and Quazi Ishtiaque Mahmud and Hung Phan and Nesreen K. Ahmed and Ali Jannesari},
  title = {{Learning to Parallelize with OpenMP by Augmented Heterogeneous AST Representation}},
  booktitle = {MLSys},
  year = {2023},
  url = {https://openreview.net/forum?id=VwGAadkgiU},
}
Figure