Prec

Prec

The AllScale API provides the prec operator to execute recursive functions in parallel. The prec operator is the foundation of all parallelism in AllScale. If you wish to read about the concept of the prec operator take a look at A Context-Aware Primitive for Nested Recursive Parallelism.

The prec operator is a higher order function combining three input functions. Each of the three functions take an element of the same type which is the argument passed through the recursive calls. The first function takes this element and checks whether the base case is reached. The second function calculates the base case. The third function calculates the recursive step case. This function takes an additional argument which is the function for the recursive call.

Examples

A simple version of the fibonacci function could be implemented like this:

auto fib = prec(
    [](int x)->bool { return x < 2; },
    [](int x)->int { return fib_seq(x); },
    [](int x, const auto& f) {
        return add( f(x-1), f(x-2) );
    }
);

The pick function allows to define multiple recursive step cases. If more than one step case is given, the reference API will pick the first variant if further parallelism can be exploited. If the code will run sequentially the last variant will be picked.

auto fib = prec(
    [](int x)->bool { return x < 2; },
    [](int x)->int { return fib_seq(x); },
    pick(
        [](int x, const auto& f) {
            return add(f(x-1), f(x-2));
        },
        [](int x, const auto& f) {
            return add(f(x-2), f(x-1));
        }
    )
);

The group function allows for mutual recursion. Each of the step cases will receive each function of the group as function arguments.

auto def = group(
    // function A
    fun(
        [](int x)->bool { return x == 0; },
        [](int)->int { return 1; },
        [](int, const auto& A, const auto& B, const auto& C)->int {
            assert_eq(1,A(0).get());
            assert_eq(2,B(0).get());
            assert_eq(3,C(0).get());
            return 1;
        }
    ),
    // function B
    fun(
        [](int x)->bool { return x == 0; },
        [](int)->int { return 2; },
        [](int, const auto& A, const auto& B, const auto& C)->int {
            assert_eq(1,A(0).get());
            assert_eq(2,B(0).get());
            assert_eq(3,C(0).get());
            return 2;
        }
    ),
    // function C
    fun(
        [](int x)->bool { return x == 0; },
        [](int)->int { return 3; },
        [](int, const auto& A, const auto& B, const auto& C)->int {
            assert_eq(1,A(0).get());
            assert_eq(2,B(0).get());
            assert_eq(3,C(0).get());
            return 3;
        }
    )
);

To select one of the functions the number of the function is given as template argument to the prec function:

auto A = prec<0>(def); // call to the first function (function A)
auto B = prec<1>(def); // call to the second function (function B)
auto C = prec<2>(def); // call to the third function (function C)

assert_eq(1,A(1).get());
assert_eq(2,B(1).get());
assert_eq(3,C(1).get());