Spar - parallelization constructs

The parallelization model

Using parallel constructs, the user divides the program into a number of medium-grain tasks, and the compiler automatically maps the code and data onto a distributed-memory system. The mapping is chosen to minimize the communication between processors, and maximize the utilization of the processors.

To simplify the cost estimation and scheduling mechanisms required for automatic mapping, Automap currently restricts programs to a class conforming to the SPC (Series-Parallel Contention) programming model. Clearly, there will be loss of parallelism due to this restriction, but this has been conjectured to be small. Compelling evidence in support of this claim is provided in the paper ``On the Loss of Parallelism by Imposing Synchronization Structure''. Nevertheless, future versions of the Spar compiler may lift this restriction (if only to support Java threads).

Design considerations

Ideally, parallelization would be handled by the compiler without concerning of the programmer, but until now attempts to make such compilers have not been successful. In Automap we accept that language constructs for parallelization are necessary, but we try to make them as accessible as possible. This requires more work by the compiler, and possibly the resulting programs will be less efficient, but we assume that these negative effects are limited. The costs we incur are comparable in nature to the costs of high-level languages compared to hand-written assembly programs. Often these costs are an acceptable tradeoff for the shorter program development time.

Another advantage of our abstract parallelization constructs is that they are more likely to be portable, since the details of program optimization for a given machine are handled by the compiler. Again, there is a clear analogy with high-level programming languages.

In Spar we provide the foreach construct, which specifies that the iterations can be executed in arbitrary order, but that each iteration is to be executed sequentially. This model is fairly easy to understand for the programmer, and requires less complicated analysis by the compiler than analyzing strict sequential for loops. In principle the semantics are the same for sequential or parallel execution. Moreover, reduction operations can be formulated quite elegantly, which is not possible with the forall or with explicitly parallel loops.

The language constructs

Given a block such as:

each { s1; s2; } 

The statements s1 and s2 are executed in arbitrary order. It is guaranteed, even for compound statements, that every statement in the each block is executed sequencially. Thus, in this example it will look to the programmer as if the compiler chooses one of the execution orders

s1; s2; 

or

s2; s1; 

even if the statements are compound.

The foreach statement is a parameterized version of the each statement. For example,

foreach( i :- 0:n ) {
    a[i].init();
} 

invokes the init method of n members of array a. As for the each statement, it is guaranteed that every iteration is executed without interference from other iterations. Thus, an iteration can only influences other iterations when it has been completed.

To allow easier analysis, the foreach has a range syntax rather than the traditional while-like syntax of the for statement of Java. For reasons of orthogonality Spar also allows the range syntax in the for statement, and the while-like syntax in the foreach statement. For the latter statement the compiler has the freedom to parallelize it, but early implementations of the compiler are likely to treat it like a for loop.

Vector ranges

The foreach range can also be described as a vector range. For example, a two-dimensional array b would be initialized completely by:

foreach( i :- [0,0]:b.getSize() ){
    (b@i).init();
} 

Masked iterations

As a further refinement, the range syntax allows masks. For example, if we wanted to initialize only the non-null elements of an array of objects, we could write:

foreach( i :- [0,0]:b.getSize( b ), b@i != null ) {
    (b@i).init();
} 

Last modified Sat May 13 15:50:56 2017 UT by Kees van Reeuwijk.