Skip to content

RecursiveParallelism

Jump to bottom
Martin Hartl edited this page Oct 27, 2017 · 2 revisions

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

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

long fibonacci(unsigned int number) {
	if(number < 2)
		return number;
	return fibonacci(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"

using namespace allscale::api::core;

long fibonacci(unsigned int number) {
	auto f = prec(fun(
		[](const unsigned int& number) {
			return number < 2;
		},
		[](const unsigned int& number) { 
			return number;
		},
		[](const unsigned int& number, const auto& rec) {
			return run(rec(number - 1)).get() + run(rec(number - 2)).get();
		}
	));
	return f(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:

struct Assignment {
    
    int column;				// < the number of columns assigned so far
    int row;				// < the row this queen is placed
    const Assignment* rest;	// < the rest of this assignment

    Assignment()
        : column(-1), row(0), rest(nullptr) {}

    Assignment(int row, const Assignment& rest)
        : column(rest.column+1), row(row), rest(&rest) {}

    int size() const {
        return column + 1;
    }

    bool valid(int r) const {
        return valid(r,column+1);
    }

    bool valid(int r, int c) const {
        assert_lt(column,c);
        // check end of assignment
        if (column<0) return true;
        // if in same row => fail
        if (row == r) return false;
        // if on same diagonal => fail
        auto diff = c - column;
        if (row + diff == r || row - diff == r) return false;
        // check nested
        return 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:

int n_queens(const Assignment& a, int size) {
	if(a.size() >= size)
		return 1;

	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:

int nqueens(int size) {
    // create the recursive version
    auto compute = prec(
        [size](const Assignment& args) {
            // check whether the assignment is complete
            return args.size() >= size;
        },
        [](const Assignment&) {
            // if a complete assignment is reached, we have a solution
            return 1;
        },
        [size](const Assignment& a, const auto& rec) {
            return sumIf(0,size,
                [&](int i){ return a.valid(i); },
                [&](int i){ return rec(Assignment(i,a)); }
            );
        }
    );

    // compute the result
    return compute(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.

Part of the AllScale project - http://www.allscale.eu

Clone this wiki locally