# ROSE Compiler Framework/autoPar

This is a tool which can automatically insert OpenMP pragmas into input serial C/C++ codes.

## Overview

This tool is an implementation of automatic parallelization using OpenMP. It can automatically insert OpenMP directives into input serial C/C++ codes. For input programs with existing OpenMP directives, the tool will double check the correctness when the right option is turned on.
* The source files are currently located in rose/projects/autoParallelization.
* A standalone executable program (named autoPar ) is generated and installed to the installation tree of ROSE (under ROSE INS/bin).
* Test input files are located at rose/projects/autoParallelization/tests
* You can test the tool in rose_build_tree/projects/autoParallelization by typing "make check"
* There is a section in ROSE manual: 12.7 Automatic Parallelization pdf
* It is used to explore semantics-aware automatic parallelization, as described in our papers:
** A workshop paper: Chunhua Liao, Daniel J. Quinlan, Jeremiah J. Willcock and Thomas Panas, Extending Automatic Parallelization to Optimize High-Level Abstractions for Multicore, In Proceedings of the 5th international Workshop on OpenMP: Evolving OpenMP in An Age of Extreme Parallelism (Dresden, Germany, June 3–05, 2009). pdf
** A journal version of the paper: Chunhua Liao, Daniel J. Quinlan, Jeremiah J. Willcock and Thomas Panas, Semantic-Aware Automatic Parallelization of Modern Applications Using High-Level Abstractions, Journal of Parallel Programming, Accepted in Jan. 2010 pdf
Similar to ROSE, autoPar is released under the BSD license.

## Installation and configuration

autoPar is released as part of the ROSE compiler. Please install ROSE by following the instructions at
* Installation
* type make install-core -j8 to install core ROSE libraries and prebuilt tools.
An executable file autoPar is created during the process of building ROSE. Users can use it to parallelize their codes. autoPar will be installed to the path specified by –prefix=ROSE INSTALLATION PATH. Here are some instructions.
During configuration, you might want to specify a prefix path, such as –prefix=/home/youraccount/opt/roserev-8345. Then, follow the ROSE installation guide to build and install ROSE, often by typing make and make install.
The next step is to set environment variables for search paths for ROSE executables (including autoPar ) and shared libraries. Assume you are using bash, put the following lines into a file (e.g. set.rose) and source it (typing source set.rose)
Now you can use autoPar to parallelize your code. Assume you have a sequential file: file.c, just type autoPar -c file.c. An output file rose file.c will be generated. If autoPar can find anything parallelizable, the output file should have OpenMP pragmas generated.

### Alternative: using the virtual machine image

If you don't want to install everything from scratch, you can download the vmware image of ROSE and directly use the installed copy of ROSE inside of it.
More information about this is at ROSE_Compiler_Framework/Virtual_Machine_Image.
Within the virtual machine, you can cd into
and type
You will see autoPar is used to process input files.

## Command line options

[~build64/projects/autoParallelization/tests]../autoPar—help
Additional useful rose flags
* -rose:skipfinalCompileStep // skip invoking the backend compiler to compile the transformed code, this is useful to workaround some bugs
* --edg:no_warnings // suppress warnings from the EDG C++ frontend

## Example usage

Testing input files can be found at https://github.com/rose-compiler/rose-develop/tree/master/projects/autoParallelization/tests
The corresponding generated testing output files can be found at: https://github.com/chunhualiao/autoPar-demo
We provide two samples below:

### Without using annotations

Input:
Command line and screen output
../autoPar -rose:C99—edg:no_warnings -w -rose:verbose 0 --edg:restrict -rose:autopar:unique_indirect_index -rose:autopar:enable_patch -I../../../../sourcetree/src/frontend/SageIII -c ../../../../sourcetree/projects/autoParallelization/tests/inner_only.c
Output:
Another input:
Output:

### Using annotations

Annotation files provide additional program information which is traditionally hard for compilers to extract, such as aliasing, side effect information.
Multiple annotations files can be loaded in one command line
../autoPar --edg:no_warnings -w -rose:verbose 0 --edg:restrict -rose:autopar:unique_indirect_index -I/home/liao6/rose/freshmaster/sourcetree/src/frontend/SageIII -c -annot /home/liao6/rose/freshmaster/sourcetree/projects/autoParallelization/tests/floatArray.annot -annot /home/liao6/rose/freshmaster/sourcetree/projects/autoParallelization/tests/funcs.annot -annot /home/liao6/rose/freshmaster/sourcetree/projects/autoParallelization/tests/Index.annot /home/liao6/rose/freshmaster/sourcetree/projects/autoParallelization/tests/interp1_elem2.C
Assuming all arrays used as indirect indices have unique elements (no overlapping) ...
Automatically parallelized a loop at line:13
Input
Annotation file
* https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/floatArray.annot
* https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/funcs.annot
Output file

### Generating patches

autoPar accepts an option -rose:autopar:enable_patch to generate a patch file. So users want to examine the directives to be inserted first. Then users can apply the inspected patch to their application.
Input file: https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/jacobi_seq.c
Command line:
* autoPar -rose:C99 --edg:no_warnings -w -rose:verbose 0 --edg:restrict -rose:autopar:unique_indirect_index -rose:autopar:enable_patch -c jacobi_seq.c
Screen output
Generated patch file: cat jacobi_seq.c.patch
After inspecting the patch, you can apply the patch to the original source file
* patch jacobi_seq.c -i jacobi_seq.c.patch -o jacobi_patched.c

### Checking Correctness

AutoPar examines pre-existing OpenMP directives in an application and verifies that they have correctly accounted for private, reductions and other OMP data-sharing attributes.
Sample input
The code above contains a real OpenMP bug someone struggled with while trying to add OMP annotations to their code, submitted here: http://openmp.org/forum/viewtopic.php?f=3&t=821
Running the autoPar OpenMP directive checker produces this result:
The output above from autoPar indicates that the OMP pragma is missing an OpenMP 'private' declaration for the variable 'i', and a reduction annotation for the variable 'total'.

## Algorithm

autoPar is designed to handle both conventional loops operating on primitive arrays and modern applications using high-level abstractions. The parallelizer uses the following algorithm: The loops may contain variables of either primitive data types or STL container types, or both.

### overview

1. Preparation and Preprocessing
* (Optional) Read a specification file for known abstractions and semantics.
* (Optional) Apply optional custom transformations based on input code semantics, such as converting tree traversals to loop iterations on memory pools.
* (Optional) if unique index indices semantics are assumed, turn on normalization of indirect array access (void uniformIndirectIndexedArrayRefs )
** indirect_loop_index = array_Y [current_loop_index] ;array_X[indirect_loop_index] ..; becomes array_X [array_Y [current_loop_index]] ..
* Normalize loops, including those using iterators.
* Apply constant folding to simplify the normalized code
* Find candidate array computation loops with canonical forms (for omp for) or loops and functions operating on individual elements (for omp task).
2. For each candidate:
* Skip the target if there are function calls without known semantics or side effects.
* Call dependence analysis and liveness analysis.
* Classify OpenMP variables (autoscoping) to be private, firstprivate, lastprivate, reduction variables. recognize references to the current element, and find order independent write accesses.
* Eliminate dependencies associated with autoscoped variables, those involving only the current elements, and output dependencies caused by order-independent write accesses.
* Insert the corresponding OpenMP constructs if no dependencies remain.
The key idea of the algorithm is to capture dependencies within a target and eliminate them later on as much as possible based on various rules. Parallelization is safe if there are no remaining dependencies.

### Canonical loops

In page 51 or (59/320): section 2.6, OpenMP 4.0 (http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf), it is defined as
init-expr One of the following:
test-expr One of the following:
relational-op One of the following:
incr-expr One of the following:
var One of the following:
lb and b: Loop invariant expressions of a type compatible with the type of var.
incr: A loop invariant integer expression.

### Dependence analysis

Dependence analysis is the basis for the parallelizer to decide whether a loop is parallelizable. autoPar invokes the dependence analysis from the loop optimizer, which implements algorithms proposed in [35, 36] to effectively transform both perfectly nested loops and non-perfectly nested loops. An extended direction matrix (EDM) dependence representation is used to cover non-common loop nests that surround only one of the two statements in order to handle non-perfectly nested loops. For array accesses within loops, a Gaussian elimination algorithm is used to solve a set of linear integer equations of loop induction variables.
This step relies on the dependence analysis implemented in
* src/midend/programTransformation/loopProcessing/depGraph
A simplified interface function is provided in
https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/autoParSupport.C

### Side effect analysis

Dependence analysis relies on the variable references information collected from side effect analysis
The analysis's source header file is midend/programTransformation/loopProcessing/depInfo/DepInfoAnal.h
* bool AnalyzeStmtRefs( AstInterface& fa, const AstNodePtr& n, CollectObject<AstNodePtr> &wRefs, CollectObject<AstNodePtr> &rRefs);
Several SageInterface functions are provided to make this analysis more accessible to developers

### Autoscoping/variable classification

This step categories variables for their data-sharing attributes, based on their live-in (before the execution of a loop) and live-out (after the execution of a loop) analysis results. For instance, a private variable inside a loop is neither live-in nor live-out of the loop, which means the variable is immediately killed (redefined) inside the loop and then used inside the loop somehow, but is never going to be used anywhere after the loop. All loop index variables are also classified as OpenMP private variables to an avoid possible race condition. On the other hand, shared variables are live at both the beginning and the end of the loop. Firstprivate and lastprivate variables are live at either only the beginning or only the end of the loop, respectively.
Reduction variables are handled specially to maximize the opportunities for parallelization. A typical reduction operation inside a loop, such as sum = sum + a[i], causes a loop-carried output dependence, a loop-carried anti-dependence, and a loop independent anti-dependence. We use an idiom recognition analysis to capture such typical operations and exclude the associated loop-carried dependences when deciding if a loop is parallelizable.
This step relies on Liveness analysis, implemented in
* src/midend/programAnalysis/defUseAnaysis/LivenessAnalysis.cpp
* There is a SageInterface function to call this analysis:
Algorithm: private and reduction variables cause dependences (being written). firstprivate and lastprivate variables are never being written in the loop (no dependences)
To recognize reduction variables: RecognizeReduction
* Implemented as void SageInterface::ReductionRecognition(SgForStatement* loop, std::set< std::pair <SgInitializedName*, VariantT> > & results) from https://github.com/rose-compiler/rose-develop/blob/master/src/frontend/SageIII/sageInterface/sageInterface.C

### Semantic specification via annotations

We use a separated file to store annotations for input code. The file essentially specifies the semantics of the input code so the tool can leverage to parallelize the code.
Some annotation files (*.annot) can be found in the project directory at https://github.com/rose-compiler/rose-develop/tree/master/projects/autoParallelization/tests
* https://github.com/rose-compiler/rose/blob/master/projects/autoParallelization/annot/Cmath.annot 156 C standard library functions
* https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/floatArray.annot array semantics
* https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/std_vector.annot std::vector semantics
* https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/funcs.annot user functions
* https://github.com/rose-compiler/rose-develop/blob/master/projects/autoParallelization/tests/Index.annot
Sample annotations are:
Array abstractions:

### Dependence elimination

Not all dependences prevent us from parallelizing loops. We exclude some unharmful dependences in our consideration.
void DependenceElimination(SgNode* sg_node, LoopTreeDepGraph* depgraph, std::vector<DepInfo>& remainings, OmpSupport::OmpAttribute* att, std::map<SgNode*, bool> & indirect_table, ArrayInterface* array_interface/*=0*/, ArrayAnnotation* annot/*=0*/)
* from file https://github.com/rose-compiler/rose/blob/master/projects/autoParallelization/autoParSupport.C
Algorithm, eliminate the following dependencies
* caused by locally declared variables: already private to each iteration
* either source or sink variable is thread local variable
* ignore a dependence relationship with empty source/sink nodes
* commonlevel ==0, no common enclosing loops
* carry level !=0, loop independent,
* at least one array reference in a dependence relationship, but dependence type is SCALAR_DEP or SCALAR_BACK_DEP
* dependencies caused by autoscoped variables (private, firstprivate, lastprivate, reduction, etc.)
* dependencies caused by a pair of indirect indexed array reference, if we know indirect index arrays have unique elements.
Note that why carry level must be 0 to prevent parallelization in our analysis
* This is valid since we run dep analysis on each level of loop.
* For a current loop to be considered, only the dependences carried by the current loop matters.
* The current loop is always the outermost level loop , carry level id is 0.

### An example with debugging info

autoPar -rose:autopar:enable_debug sourcetree/projects/autoParallelization/tests/jacobi_seq.c
Search for "this dep relation cannot be eliminated. saved into remaining depedence set." to find loops with loop-carried dependency which cannot be eliminated.

## Annotations encoding semantics

Used to encode semantic information for types (class) and their operations (operator)
Source files: https://github.com/rose-compiler/rose-develop/tree/master/src/midend/astUtil/annotation

### examples

Arrays and array optimizations (rewrite to raw arrays)
Function side effect annotation: variable sets for read, modify, and alias
has_value and restrict _value annotations: what is "this" and "result" ?

### c function annotations
## Publications

* old technical report: Chunhua Liao, Daniel J Quinlan, Jeremiah J Willcock, and Thomas Panas. Automatic parallelization using OpenMP based on STL semantics. Technical report, Lawrence Livermore National Lab.(LLNL), Livermore, CA (United States), 2008.
* A workshop paper: Chunhua Liao, Daniel J. Quinlan, Jeremiah J. Willcock and Thomas Panas, Extending Automatic Parallelization to Optimize High-Level Abstractions for Multicore, In Proceedings of the 5th international Workshop on OpenMP: Evolving OpenMP in An Age of Extreme Parallelism (Dresden, Germany, June 3–05, 2009). pdf
* A journal version of the paper: Chunhua Liao, Daniel J. Quinlan, Jeremiah J. Willcock and Thomas Panas, Semantic-Aware Automatic Parallelization of Modern Applications Using High-Level Abstractions, Journal of Parallel Programming, Accepted in Jan. 2010 pdf