TL;DR
This paper presents a novel semantic-aware parallelizer built on the ROSE source-to-source compiler infrastructure. It extends automatic parallelization beyond primitive data types to C++ applications using high-level abstractions like STL containers, enabling more efficient utilization of multicore processors.
What Problem Does This Paper Address?
Modern multicore processors offer significant computational power, but harnessing it requires parallel programming, which is notoriously difficult. While automatic parallelization tools have made strides, they primarily focus on C and Fortran code dealing with primitive data types. This leaves a significant gap for C++ applications that heavily rely on high-level abstractions such as the Standard Template Library (STL). These abstractions, while simplifying development, obscure implementation details, making it challenging for traditional compilers to perform static analysis and identify parallelization opportunities. This paper aims to bridge this gap by enabling automatic parallelization for C++ code that uses these complex, high-level abstractions.
Methods
The core of this work is a semantic-aware parallelizer built using the ROSE source-to-source compiler infrastructure. ROSE is chosen because it preserves high-level abstractions in its Abstract Syntax Tree (AST), allowing for more detailed analysis. The parallelizer employs the following key steps:
- Specification File: A crucial component is a specification file that captures known semantics of high-level abstractions (e.g., STL containers, user-defined types). This file can include information about whether a class behaves like a fixed-sized array, its member functions for accessing elements and size, and even side effects of functions. This allows the compiler to "understand" the behavior of these abstractions beyond what static analysis alone can reveal.
- Preprocessing and Transformation: The system preprocesses the input code by reading the specification file and applying optional custom transformations. A notable example is converting recursive tree traversals (common in AST analysis tools) into loop iterations over memory pools, which is more amenable to analysis and optimization. Loops are also normalized, including those using iterators.
- Candidate Identification: The parallelizer identifies candidate loops and functions for parallelization. This includes canonical form loops for
omp fordirectives and functions/loops operating on individual elements foromp taskdirectives. - Semantic-Aware Analysis: For each candidate, the parallelizer performs dependence analysis and liveness analysis. Crucially, it leverages the semantic information from the specification file to:
- Classify OpenMP variables (autoscoping).
- Recognize references to the "current element" being accessed, especially important for iterator-based loops.
- Identify order-independent write accesses, which can be safely parallelized with appropriate synchronization.
- Dependency Elimination and Parallelization: Dependencies are eliminated based on autoscoped variables, current element accesses, and order-independent writes. If no remaining dependencies are found, the corresponding OpenMP constructs (
omp fororomp task) are inserted.
Datasets
Not discussed in the paper. The paper focuses on demonstrating the parallelization of specific code kernels and a real-world application.
Key Insights and Ideas
- Semantics are Key: The paper strongly emphasizes that understanding the semantics of high-level abstractions is paramount for effective automatic parallelization. Simply analyzing the code structure is insufficient when dealing with complex C++ constructs.
- ROSE as an Enabler: The ROSE compiler infrastructure's ability to preserve high-level AST information is critical. This allows the semantic-aware parallelizer to access and leverage the details that traditional compilers often discard.
- Bridging the Gap: The work effectively bridges the gap between traditional parallelization techniques for primitive types and the needs of modern C++ applications using abstractions like STL.
- Extensibility is Crucial: The approach highlights the need for extensible compiler infrastructures that can accommodate user-defined semantics, paving the way for broader adoption of automatic parallelization.
- Transforming Traversal: The idea of transforming recursive tree traversals into memory pool iterations for analysis is a clever optimization that improves efficiency and analysis capabilities.
Key Results
The paper presents preliminary results on three test kernels:
- Jacobi Iteration (C): A standard benchmark operating on a 500x500 double-precision array.
- 2-norm Calculation (C++ vector): A calculation on 100 million elements using
std::vector. - Compass Checker (C++): A real-world static analysis tool kernel involving AST traversal, demonstrating parallelization of a more complex, domain-specific abstraction.
The results show that the parallelizer can extract parallelism from both primitive types and high-level abstractions. The semantic-driven optimization of replacing tree traversal with memory pool iteration for the Compass checker yielded a 35% performance improvement on a single thread compared to the original sequential execution. All tests showed near-linear speedup with increasing threads, with the exception of the Compass checker, where a critical section limited scalability beyond 7-8 threads.
Limitations and Future Work
- Ongoing Project: The authors acknowledge that the implementation is ongoing and released as part of the ROSE distribution.
- Manual Specification: Currently, the specification of semantics relies on a manual specification file. Future work aims to express this in C++ syntax for easier handling and potentially automate some of this process.
- Limited OpenMP 3.0 Support: The current experiments primarily target
omp forandomp taskdirectives. The authors are working on OpenMP 3.0 implementation and other OpenMP compilers as backends. - Performance Bottlenecks: For the Compass checker, the critical section limited scalability. The authors suggest that more aggressive optimization, such as searching only relevant memory pools, could further improve performance but is not yet automated.
- Future Directions:
- Applying the method to larger-scale C++ applications.
- Recognizing and incorporating more complex semantics.
- Extending support for dynamic control flows (e.g., pointer chasing).
- Investigating the impact of polymorphism.
- Exploring the interaction between automatic parallelization and conventional loop transformations.
- Leveraging semantics for better OpenMP optimizations and correctness analysis.
Summary updated