RecursiveParallelism

Nested Recursive Parallelism

The objective of this tutorial is to illustrate the use of the prec operator. The codes presented in this tutorial are snippets extracted from the (not much longer) full implementation of the covered development steps. These steps can be obtained from the associated Nested Recursive Parallelism tutorial sources directory.

Overview

This tutorial covers the following steps:

• Sequential Implementation Fibonacci - an initial implementation of the fibonacci function
• Parallelization Fibonacci - distributing computation to parallel resources of the fibonacci function
• Sequential Implementation N-Queens - an initial implementation for the n-queens problem
• Parallelization N-Queens - distributing computation to parallel resources of the n-queens problem

Sequential Implementation Fibonacci

A basic recursive C implementation of the fibonacci function can be done in a few lines of code:

longfibonacci(unsignedint number) {
if(number < 2)
return number;
returnfibonacci(number - 1) + fibonacci(number - 2);
}

A full version of this example can be obtained from here.

If the number is smaller than 2 the recursion base is reached and the current number is returned. Otherwise it will recursively call itself and return the sum of the two calls.

Note that this implementation of the fibonacci function is for learning purposes only and will perform bad compared to iterative implementations.

Parallelization Fibonacci

The AllScale API provides an operator called prec which is used to parallelize recursive functions. The parallel version of the fibonacci function using the AllScale API can be implemented like this:

#include"allscale/api/core/prec.h"usingnamespaceallscale::api::core;longfibonacci(unsignedint number) {
auto f = prec(fun(
[](constunsignedint& number) {
return number < 2;
},
[](constunsignedint& number) { return number;
},
[](constunsignedint& number, constauto& rec) {
returnrun(rec(number - 1)).get() + run(rec(number - 2)).get();
}
));
returnf(number).get();
}

A full version of this example can be obtained from here.

To use the prec operator the prec.h header has to be included. To utilize the prec operator we need three lambdas. All of them take a single argument number which was the argument of the function in the sequential implementation. The first lambda checks if the number should be handled as recursion base or recursion step. If the return value is true, the recursion base is called which is the second lambda. The third lambda additionally takes a second argument which is used to perform the recursive call.

That's it! The code is now parallel. prec will automatically fall back to a sequential implementation if there is already enough parallelism to saturate a system's concurrent resources.

Sequential Implementation N-Queens

This section deals with a slightly more complex problem, namely the n-queens problem. We first define the struct Assignment which keeps track of the current assignment:

structAssignment {
int column; // < the number of columns assigned so farint row; // < the row this queen is placedconst Assignment* rest;	// < the rest of this assignmentAssignment()
: column(-1), row(0), rest(nullptr) {}
Assignment(int row, const Assignment& rest)
: column(rest.column+1), row(row), rest(&rest) {}
intsize() const {
return column + 1;
}
boolvalid(int r) const {
returnvalid(r,column+1);
}
boolvalid(int r, int c) const {
assert_lt(column,c);
// check end of assignmentif (column<0) returntrue;
// if in same row => failif (row == r) returnfalse;
// if on same diagonal => failauto diff = c - column;
if (row + diff == r || row - diff == r) returnfalse;
// check nestedreturn rest->valid(r,c);
}
};

Additionally to the assignment the struct also provides a method to check if the next queen can be placed at a certain position.

For the actual algorithm to compute the number of valid n-queens chessboards the code may look like this:

intn_queens(const Assignment& a, int size) {
if(a.size() >= size)
return1;
int solution = 0;
for(int i = 0; i < size; i++) {
if(a.valid(i))
solution += n_queens(Assignment(i, a), size);
}
return solution;
}

A full version of this example can be obtained from here.

The current chessboard is represented by the struct Assignment. The function valid checks if the next queen can be placed at the desired position r.

A single recursive call checks all possible next position of the queen and only recursively calls if the position of the queen is valid. The call n_queens(Assignment(), N) will return the number of solutions to place N queens on a N x N field. The recursion base of the recursive function is reached if a.size() >= size which means that all queens are on the board and don't threaten each other.

Parallelization N-Queens

The version using the prec operator may look like this:

intnqueens(int size) {
// create the recursive versionauto compute = prec(
[size](const Assignment& args) {
// check whether the assignment is completereturn args.size() >= size;
},
[](const Assignment&) {
// if a complete assignment is reached, we have a solutionreturn1;
},
[size](const Assignment& a, constauto& rec) {
returnsumIf(0,size,
[&](int i){ return a.valid(i); },
[&](int i){ returnrec(Assignment(i,a)); }
);
}
);
// compute the resultreturncompute(Assignment()).get();
}

The prec operator is utilized as for the fibonacci function with the only big difference in the lambda for the recursion step. Here the number of recursive calls depends on the size of the chessboard. Therefore the sumIf sums the result of the recursive calls for queen positions 0 to size - 1. The recursive calls are only done for valid positions of the queen. If the position is invalid we know that the number of solutions will be zero.

A full version of this example can be obtained from here.