OK, thanks got it, I found theory at a page, your explanation was good,
thanks
On Thu, Jan 25, 2018 at 11:59 PM, Brad Chamberlain <[email protected]> wrote:
>
> 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/cobe
> gin.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
