The Parallel Pattern DSL language generally supports two types of functions:

• Parallel Patterns
• Sequential Functions

Both are defined similarly.

The declaration of a sequential function uses the keyword seq followed by its name a set of parameters , a colon, its return type and a structured block in curly brackets. Parameter of the type list are references to the original list within the function body.

seq Name (Type1 parameter1, ... , TypeN parameterN) : Type {
...
}

To execute a sequential function simply express a function call with a value for all parameters.

seq identity (Int value) : Int {
return value
}

seq main() : Int {
Int a = identity(2)
return 0
}

The declaration of a parallel pattern uses a keyword to identify the pattern followed by its name a set of parameters, a colon, its return type, a name for the output-variable and a structured block in curly brackets. At the moment the following keywords are supported:

• map
• reduction
• stencil
• dp (dynamic programming)
• recursion

All Patterns need at least one input-parameter of type list. The keyword INDEX can be used to get the current index of the iterations. Input parameter for parallel patterns are read only within the structured block.

patternKeyword Name (Type1 parameter1, ... , TypeN parameterN) : Type returnName{
...
}

When accessing arrays within a parallel pattern the following syntax is necessary: The access should be of the for W * n + b. If W = 1 or b = 0 they can be left out. n must be an INDEX variable (INDEX, INDEX0 etc.) and both W and b should be literals. For dynamic programming the scaling factor W is not allowed.

correct:

res[INDEX] = input[INDEX]
res[INDEX] = input[2 * INDEX + 5]
res[INDEX] = input[INDEX + 5]

incorrect:

var int a = 4
res[INDEX] = input[a]
res[INDEX] = input[a* INDEX]

The map pattern is a pattern, which executes the structured block once for each element of the first parameter.

map incrementAll ([Int] Input) : [Int] res {
   res[INDEX] = Input[INDEX] + 1
}

The parallel pattern incrementAll increments all elements of Input and stores the result in res. Since, Input is read-only the ++ operator for incremantation cannot be used. Furthermore, the keyword INDEX ensures, that we access all elements of Input only once and that the updated values are stored in the same index as the original.

The reduction pattern, also executes the structured block once for each element of the first parameter, but also combines all results to a single value.

reduction sum ([Int] Input) : Int res {
    res += Input[INDEX]
}

The parallel pattern sum sums up all elements in Input and stores it in res. The last statement of a reduction must be a reduction statement of the form:

res += Expression

or

res -= Expression

or

res *= Expression

or

res = min(Expression,Expression)

or

res = max(Expression,Expression)

The stencil requires needs at least two execution arguments to generate the correct loops. To support multi-dimensional stencil operations the keyword INDEX is extended by the number of the dimension, starting with 0. Thus, INDEX0 would be the keyword to navigate through the outer most elements, INDEX1 would be the index at the next deeper level etc..

stencil twoDimensional([[Int]] Input):[[Int]] res {
    res[INDEX0][INDEX1] = Input[INDEX0 + 1][INDEX1] + Input[INDEX0 - 1][INDEX1] + Input[INDEX0][INDEX1 + 1] + Input[INDEX0][INDEX1 + 1]
}

Due to limitations within the underlying theoretical model only one dimensional arrays are allowed as inpu./output. Furthermore, only the current and next time step are available for computation, limiting the the capabilities of this dynamic programming pattern. The dynamic programming pattern can be defined by stating the dynamic programming recusion. INDEX0 is used to differentiate the individual iterations e.g. time steps, this cannot be used to access the function parameters. INDEX1 is used to iterate over the input array. For the execution of dynamic programming patterns we always need a value for the depth of the execution, given as an additional argument.

The following example shows the implementation of the n+2 and n+1 fibonacci-number (8 and 7 in this case):

dp fibonacci([Int] input):[Int] res {
    res[0] = input[1]
    res[1] = input[0] + input[1]
}

seq main(): Int {
    var [Int] start = [1,1]
    var [Int] result = [0,0]
    
    result = fibonacci<<<6>>>(start)
    return 0
}

The recursion pattern is the only way to explicitly utilize recursion. As of right now recursive patterns are not parallelized.

recusion counter(Int input):Int res {
    if input < 4 {
        res = counter<<<>>>(input)
    } else {
        return res
    }
}

To execute a parallel pattern the function call is extended by "<<<" and ">>>" with with additional arguments in between. The first argument states the number of iteration, if not specified the size of the first argument is used. The second argument states the number of threads used to execute the parallel pattern, this value may be changed during optimization. As already stated before the stencil pattern requires at least two arguments, where the first argument denotes the stencil distance. The second argument denotes the number of dimensions. Parallel patterns can only write to already initialized variables.

reduction sum ([Int] Input) : Int res {
   res += Input[INDEX]
}

seq main() : Int {
   [Int] x = [0,1,2,3,4]
   Int a
   a = sum<<<5,2>>>(x)
   return 0
}

This example executes the parallel pattern sum on the first 5 elements of x with 2 threads.

Control Statements are used control the work flow of the execution and can be used within a sequential function and parallel pattern. The use within parallel patterns is not recommended.

These for-loops are used just like in C or C++, with the exception, that no round brackets are necessary.

for var Int i = 0; i < n; i++ {
...
}

These for-loops iterate over each element of a given list and make them accessible by a new Variable. The keyword in states, that for each element x within the Expression the structured block will be executed once. Type is the data type of the variable x used in the structured block.

for var Type x in Expression {
...
}

The while-loop will execute the following structured block several times until the expression evaluates to false.

While Expression {
...
}

Branching can be utilized with the if and else key words. Following the structured block of the if executes when the Expression evaluates to true. If the expression evaluates to false, and an else statement is present it will be executed. The else statement can either start a structured block or another if statement.

if Expression {
...
} else {
...
}

or

if Expression {
...
} else if Expression{
...
}

• mod/%: modulo operator

• +: addition operator

• -: subtraction operator

• *: multiplication operator

• /: division operator

• +=: assignment by addition

• -=: assignment by subtraction

• *=: assignment by multiplication

• /=: assignment by division

• %=: assignment by modulo

• ++: incrementation

• --: decrementation

• <: lesser than

• : greater than

• ==: equal to

• <=: less or equal to

• =: greater or equal to

• !=: not equals

• !/not: logical not
• &&/and: logical and
• ||/or: logical or

• #: size
• []: index access
• in: existence of an element