V5

From CSE231 Wiki
Jump to navigation Jump to search

We have created our own implementation of some of the concepts introduced in the X10 parallel programming language (paper) and the continuation of this research in Habanero.

async, finish

async and finish are the fundamental building blocks of task-level parallelism in V5.

These concepts are first covered in RiceX Topic 1.1.

async(body) creates a new child task that can run before, after, or in parallel with all remaining statements of the parent task.

finish(body) executes body and waits for all descenent tasks to complete.

In the example below, a() and b() may execute in parallel, however execution will not continue to c() until a() and b() have completed. This is a result of the semantics of finish which waits for the execution of the body it receives to complete and all of its descendant tasks terminate. a() is assured to have completed as it is a descendant task. b() is assured to have completed since it is in the normal continuation of the body passed to finish.

finish(()-> {
    async(()->{
        a();
    });
    b();
}
c();

future

A future is a task that returns a value.

Futures are covered in RiceX Topic 2.1.

future(body) returns an instance of Future<V>.

Future<Integer> aFuture = future(() -> {
	return calculateSomething();
});

The result of the computation can be retrieved via the future's get() method:

Integer result = aFuture.get();

loop parallelism

Attention niels epting.svg Warning: CSE 231s is all exclusive max, all the time. forall, forasync, and forseq are all exclusive max.

forasync, forall

Parallel loop constructs are provided for ranges [min, max), arrays, and Iterables.

forasync

forasync(0, size, (i)->{
    ...
} );

can be thought of as:

for( int _i=0; _i<size; _i++ ) {
    final int i = _i;
    async( ()->{
        ...
    });
}

forall

forall(0, size, (i)->{
    ...
} );

is just forasync wrapped in a finish:

finish(()-> {
    forasync(0, size, (i)->{
        ...
    } );
});

chunking

the chunked() option to the forasync, forall, forasync2d, and forall2d splits up the work in a way that the runtime system sees fit.

The example code below would create 1,000 tasks, one for each value of i from [0,1000):

forall(0, 1_000, (i)->{
    f(i);
} );

However, by adding the chunked() option the runtime system is free to create fewer tasks, if appropriate.

forall(chunked(), 0, 1_000, (i)->{
    f(i);
} );

If desired, one can specify a chunk size as a hint via chunk(size):

forall(chunked(100), 0, 1_000, (i)->{
    f(i);
} );

grouping

Explicit control of splitting up the work, referred to as grouping in the RiceX videos, is provided by the Slices studio.

forseq

The many permutations of forseq are provided to allow easily switching to a sequential implementation for debugging purposes.

forseq(0, size, (i)->{
    ...
} );

is equivalent to a standard for loop:

for( int i=0; i<size; i++ ) {
    ...
}