Hi Nimit --
First, this would be a great stack overflow question if you would be
willing to post it there (in the sense that I think it's a common question
and that others would find value in it).
Yes, recursive parallelism is supported in Chapel. The main thing to know
is that Chapel's type inference machinery is currently not very good with
recursive procedures, and therefore such routines need to declare an
explicit return type.
I'll demonstrate a few ways to write this using a (naive) recurisve
computation of fibonacci, just because of its famiarity.
In the first, I'll use a `cobegin` statement which says to execute each
of its child statements in a separate task. See the users' guide for
details:
https://chapel-lang.org/docs/latest/users-guide/taskpar/cobegin.html
---
proc fib(n): n.type {
assert(n >= 0);
if n == 0 || n == 1 then
return 1;
else {
var f1, f2: n.type;
cobegin with (ref f1, ref f2) {
f1 = fib(n-1);
f2 = fib(n-2);
}
return f1 + f2;
}
}
for i in 0..10 do
writeln(fib(i));
---
The main downside to this approach is that, because the cobegin introduces
a new scope, the 'f1' and 'f2' variables need to be declared outside of it
(i.e., there's no opportunity to have their types inferred) and then they
need to be passed in by reference to the tasks so that they can be
modified.
The second way is to use the begin statement
(https://chapel-lang.org/docs/latest/users-guide/taskpar/begin.html):
---
proc fib(n): n.type {
assert(n >= 0);
if n == 0 || n == 1 then
return 1;
else {
var f1$: sync n.type;
begin f1$ = fib(n-1);
var f2 = fib(n-2);
return f1$ + f2;
}
}
for i in 0..10 do
writeln(fib(i));
---
This fires off one task to compute one of the recursive calls, storing its
result in a synchronized variable to make sure we don't return before it
is complete. Then the original task calls the second recursive call and
we return the sum. The users guide doesn't yet have a sync variable
section, but the idea is that, by default, reads block until the variable
is written and writes block until it is read. Here's a primer for more
information:
https://chapel-lang.org/docs/latest/primers/syncsingle.html
I think the way we'd really like to write this is using a concept
we've discusssed but not implemented called a begin expression,
which would look something like this:
---
proc fib(n): n.type {
assert(n >= 0);
if n == 0 || n == 1 then
return 1;
else {
return (begin fib(n-1)) + fib(n-2); // or maybe '+ (begin fib(n-2))'
}
}
for i in 0..10 do
writeln(fib(i));
---
This would effectively put a synchronized variable in place of each of the
begin expressions to ensure that we didn't try to compute the sum before
returning it.
Hope this is helpful,
-Brad
On Thu, 25 Jan 2018, Nimit Bhardwaj wrote:
Just was thinking of parallel recursion, I explain what it is (its just my
thinking, it may be hypothetical), suppose I have an algorithm which is
using recursion, just suppose its just sum of array algorithm, I want to
know if there is a way in chapel which can use recursion to work in
parallel, to support it I provide a simple algorithm below to add the
numbers of array:
Algo sumOfArray(A, i, j):
if j - i + 1 == 2:
return A[i] + A[j]
else if j - i + 1 == 1:
return A[i]
else:
mid = (i + j) / 2 //this integer division
return sumOfArray(A, i, mid) + sumOfArray(A, mid + 1, j)
The above algorithm works as given, it sums the sum of left and right
subsection of array from mid of array, this type of recursion is simple, in
sense that it makes the *disjoint* sections, disjoint in sense that ranges
between different recursions don't overlap with i and j, so any recursion
which is disjoint, even if its updating the data structure can be executed
parallely, so I want to know if there is a way to run these two calls as in
the above algorithm sumOfArrays parallely, this idea will also work in
segment trees, where even the ranges made are disjoint.
I want to know if there is any way to work parallely, this comes in handy,
I want to implement and see the effect of parallelism for a segment tree.
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Chapel-users mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-users
