Saturday, October 17, 2009

ParaSail's implicit parallelism

As mentioned in the original overview of ParaSail, implicit parallelism is at the heart of ParaSail (and of its name!).  Every procedure/function call with multiple parameters involves implicit parallelism, in that all of the parameters are evaluated in parallel.  Handoff semantics is used for writable parameters, meaning that a (non-concurrent) object that is writable by one parameter evaluation, isn't available to any other parameter evaluation.  Operations on concurrent objects are not ordered.

Furthermore, in a sequence of statements, the only default limitation on parallelism is that imposed by operations on non-concurrent objects.  Parallelism can be inhibited by using ";;" instead of merely ";" to separate two statements.  This forces sequencing for operations on concurrent objects, which would otherwise not have any specified order.  By contrast, "||" can be used to indicate that parallelism is expected, and it is an error if there are conflicting operations on non-concurrent objects in the statements on either side of the "||".  That is, two statements separated by "||" are executed effectively in parallel, just as though there were embedded within two different parameter evaluations to a single procedure or function call.

For example:
    X := F(A, B);
    Y := G(B, C);;
    Z := H(R, S) || Z2 := Q(R, T);
As implied above by the formatting, "||" has highest precedence (binds most tightly), ";" next, and ";;" lowest (binds least tightly).  So in the above, the assignments to X and Y are ordered only if that would be required by the shared use of B (at least one of them has B as a writable parameter).  The assignments to Z and Z2 occur in parallel, and it would be an error if the shared use of R is unsafe (e.g. because R is writable by one or both, and is not a concurrent object).  The assignments to X and Y will complete before beginning the assignments to Z and Z2 (though of course, a "very intelligent" compiler might still find parts that can be executed in parallel because they can't possibly affect one another).  In all cases the evaluations of the parameters to a single procedure/function call happen in parallel.

Parentheses can be used to override the precedence for the statement separators:
    (M := N(A, B) ;; P := T(A, X)) ||
      (J := K(X, Y); M2 := N2(Y, Z));
In the above the assignment to M completes before the assignment to P starts.  The assignments to J and M2 occur in parallel unless the shared use of Y makes that unsafe.  And the assignments to M and P occur in parallel with the assignments to J and M2, and it is an error if there are conflicts due to shared use of X.

Note that ";" is both a statement separator and a statement terminator.  On the other hand, ";;" and "||" are only meaningful as statement separators.

Implicit parallelism also shows up in ParaSail loops.  The iterations of a for loop in ParaSail are executed as though each iteration were separated from the next by a ";", but with no particular ordering on the iterations.  A particular ordering may be specified by using the forward or reverse keyword, which effectively puts a ";;" between the iterations. Alternatively, the concurrent keyword may be used to indicate that the iterations should be effectively separated by "||", in which case it is an error if there are any conflicts due to operations on a non-concurrent variable.  For example:
    // compute sum of array A 
    for I in 1..10 loop
        Sum += A[I];
    end loop;

    // find last element equal to Z
    for I in 1..10 reverse loop
        if A[I] == Z then
             Last_Z := I;
             exit loop;
        end if;
    end loop;

    // sum the arrays B and C to produce A
    for I in 1..10 concurrent loop
        A[I] := B[I] + C[I];
    end loop;
Not too surprisingly, an exit loop statement is only permitted in a forward or reverse loop.

As illustrated above, parallelism is the default in ParaSail.  It is our belief that that is the only way that programmers will learn to take full advantage of the multicore world.  That is, in ParaSail, it is more work to create non-parallel algorithms than to create parallel ones, so programmers, being fundamentally a lazy lot, will end up writing mostly parallel algorithms in ParaSail.

We will cover ParaSail's structured synchronization mechanism (concurrent interfaces) in another post.

7 comments:

  1. If you wanted to really force programmers to think parallel-think, then you might just make "concurrent" the default, and force programmers to explicitly mark non-concurrent regions / stmts somehow.

    Stated differently, why not let the compiler flag ALL non-concurrent stmts unless the programmer explicitly marks them as non-concurrent?

    -Fred Mueller

    ReplyDelete
  2. You might be right. I chose somewhat of a middle ground, where "unordered" is the default for loops. By piggybacking on the DAG-oriented semantics of ";" plus the "unordered" default, I think you give the compiler enough to chew on to get a fair amount of parallelism. Also since there is essentially no aliasing and no global variables, the parallelization problem is significantly easier.

    ReplyDelete
  3. There would be no parallelism in:
    // compute sum of array A
    for I in 1..10 loop
    Sum += A[I];
    end loop;

    except if your compiler is able to infer that it's a reduction with an associative operator, in which case it can be parallelized (O(log n) instead of O(n)). I'd better write something like:
    Sum = reduce(+, A)

    ReplyDelete
  4. Good point. The example was meant to be illustrative, but about the only possible parallelism would be the fetching of the A[I] values. A more interesting example would hopefully illustrate more opportunities for parallelism.

    ReplyDelete
  5. Another approach would be to recognize that since for-loop iterations are by default unordered in ParaSail, the "+" operator is necessarily associative, and the compiler should automatically reassociate further to achieve the O(log n) performance.

    ReplyDelete
  6. Hi Tucker! I was wondering how familiar you are with the language Fortress which is being developed. It has implicit parallelism, too. See: http://bit.ly/6mCM3j

    ReplyDelete
  7. Yes, I have been following the development of Fortress. Fortress seems more focused on the high-performance computing market, rather than the safety-critical, real-time, embedded systems application domain.

    ReplyDelete