Abstract Pattern Tree

The Abstract Pattern Tree (APT) is a graph-based description of the algorithmic structure of source code. In general, we can generate an applicable APT from a given Abstract Syntax Tree (AST), if we have appropriate knowledge on the on the source language. In this case we utilized the Monticore framework to create a Domain Specific Language (DSL) for creating a prototype with sufficient knowledge on the source code. Furthermore, Monticore generates the AST for sources in our language. Since, we aim to utilize the APT as an Intermediate Representation (IR) the implementation contains a lot more nodes, than necessary for the optimization of the parallel patterns. In the following, the different Pattern-Nodes will be introduced. For traversing the APT a visitor can be used. The definition of data elements can be found here.

The generation of the APT based on the AST is explained here.

Pattern Node

The most basic node within an APT is the Pattern Node, which will be extended by all following nodes.

Function Node

Abstract definition of function declarations, will be extended by the function nodes. Function nodes do not have a parent node.

Parallel Node

Abstract definition of parallel function definitions, will be extended by the individual parallel nodes.

Map Node

The map node describes the (parallel) map pattern and extends the parallel node. This node contains information on the computation of a single data element from a one dimensional input/output.

Reduce Node

The reduce node describes the (parallel) reduction pattern and extends the parallel node. This node contains information on the computation of a single data element from a one dimensional input as well as the recombination function, defining the reduction step.

Stencil Node

The stencil node describes the (parallel) stencil pattern and extends the parallel node. This node contains information on the computation of a single data element from a multidimensional input/output

Dynamic Programming Node

The dynamic progamming node defines the (parallel) dynamic programming pattern. This node contains information on the computation of a single data element for any given timestep.

Serial Node

The serial node describes function definition without explicit parallelism, extends the function node.

Main Node

The main node is a serial node describing the programm entry point.

Plain Nodes

Other than function nodes there are also pattern nodes, which describe controll statement and actions. Those nodes directly inherit the parameters from pattern node.

Branch Node

The branch node is a pattern node that signals a branching behaviour at this step. The child nodes it contains are all branch case nodes

Branch Case Node

The branch case node describes an idividual path in the current branch. If the parameter hasCondition is true, the first element in the children list is the conditional expression for this path. A value of false in the hasCondition parameter means that the path is chosen, if all others are not selected.

Call Node

The call node defines a function call within an expression. This node acts as an indirect conection between the call and the function definition. The arguments for the call are defined in the parent expression.

Parallel Call Node

The parallel call node defines the call of a parallel pattern. It extends the call node, therefore, building the connection between the call and the pattern definition via the identifier. The first childnodes are always the additional arguments. The number of these additional arguments is defined in additionalArgumentCount. The following child defines the assignment from the pattern-call to the resulting variable.

Additional Arguments

The individual values within the additional arguments are stored in either a MetaValue or a MetaList and currently are only of type Integer. The corresponding value list can be accessed with getValue() or getValues(). Different parallel patterns contain differnt additional arguments:

Map:
1. The first additional argument of the map pattern is a MetaValue containing the width(number of instances) of the pattern
2. The second additional argument contains a MetaValue containing the start offset(the first value for index) of a map.
Reduction:
1. The first additional argument of the reduction pattern is a MetaList containing the following values in the given order:
  1. width of the reduction
  2. arity of the combiner function
  3. depth of the reduction
  4. start offset of the reduction
Dynamic Programming:
1. The first additional argument of the dynamic programming pattern is a MetaValue containing the number of timesteps
2. The second argument is a MetaValue containing the width of the "Map" within the dynamic programming recursion.
3. The third argument is a MetaList containing the start offsets for the timestep and map iterations.
Stencil:
1. The first additional argument of the stencil pattern is a MetaList containing the widths over each dimension starting with the first INDEX variable in accordance to the language.
2. The second additional argument is a MetaList containing the start offsets for each dimension in the same order as the width.

Loop Node

Loop nodes contain the abstract definition for 3 types of loop statements: for-loops, for-each-loops and while-loops.

For-Loop Node

The for-loop node describes the common for loop, where the child nodes are executed for each iteration. For this node the first 3 child nodes are dedicated to controlling the loop.

The initialization of the loop control-variable.
The loop-condition, to test whether the loop-variable is still within the defined range.
The update rule for the loop-variable, after every iteration.

For-Each-Loop Node

The for-each-loop node describes the for loop which iterates over all elements of a given arry. For this node the first child node is dedicated to the expression defining the array.

While-Loop Node

The while-loop node describes the while loop which executes the given child nodes as long a given expression is evaluated to true. For this node the first child node is dedicated to the run condition (expression).

Complex Expression Node

Complex expression nodes are nodes containing a single expression. This expression can potentially contain function calls. If the expression contains function calls they are replaced by function-inline-data elements, which are variables representing a single function call.