Programming Model
The programming model's constructs are of two categories. The skeleton patterns which represent a generic parallelization strategy, and the muscles which are provided by programmers and fill the pattern to transform it into a specific application.
Skeleton Patterns
A skeleton pattern represents a parallelization strategy, which can be combined by nesting a pattern inside another. Currently the supported skeleton patterns are:
- Farm: is also known as master-slave, and represents task replication.
Skeleton<P,R> nested = ...; Skeleton<P,R> farm = new Farm<P,R>(nested);
- Pipe: represents staged computation where data must be executed over a sequence of stages.
Skeleton<P,X> stage1 = ...; Skeleton<X,R> stage2 = ...; Skeleton<P,R> pipe = new Pipe<P,R>(stage1, stage2);
- For: represents finite iteration, where data is computed a fixed number of times.
int i = ...; Skeleton<P,R> nested = ...; Skeleton<P,R> forSkel = new For<P,R>(nested, i);
- While: represents conditional iteration, where data is computed while a condition holds.
Condition<P> condition = ...; Skeleton<P,R> nested = ...; Skeleton<P,R> whileSkel = new While<P,R>(nested, condition);
- If: represents conditional branching where the data's computation choice is condition.
Condition<P> condition = ...; Skeleton<P,R> trueCase = ...; Skeleton<P,R> falseCase = ...; Skeleton<P,R> ifSkel = new If<P,R>(condition, trueCase, falseCase);
- Map:represents data parallelism where a data element is subdivided, computed with the same code, and then results are merged.
Split<P,X> split = ...; Skeleton<X,Y> nested = ...; Merge<Y,R> merge = ...; Skeleton<P,R> map = new Map<P,R>(split, nested, merge);
- Fork: represents data parallelism where a data element is subdivided, each sub-element is computed with a different code, and then results are merged.
Split<P,X> split = ...; Skeleton<X,Y> nested[] = ...; Merge<Y,R> merge = ...; Skeleton<P,R> fork = new Fork<P,R>(split, nested, merge);
- DaC: represents divide and conquer recursive data parallelism, where data elements are subdivided while a condition holds, computed, and merged back to a single result.
Condition<P> condition = ...; Split<P,P> split = ...; Skeleton<P,R> nested = ...; Merge<R,R> merge = ...; Skeleton<P,R> dac = new DaC<P,R>(condition, split, nested, merge);
Muscles
Muscle codes are responsible for providing the application specific code to the skeleton pattern. There are four types of Muscle codes: Condition, Split, Merge and Execute. Muscles are identified with an interface, which defines an homonym method used for computation.
It is important to note that muscle methods will likely be executed concurrently. Hence if the method's implementation is not stateless, it must be guarded with the synchronized keyword.
However, using synchronized will serialize all access to the method, thus disabling parallelism in skeletons such as Farm. Therefore, synchronized should be avoided, and if required, finer grained synchronization (i.e. in sub method calls from inside the muscle) should be preferred.
Condition: given a data input of type P returns either true or false.
public interface Condition<P> extends Muscle<P, Boolean> {
public boolean condition(P param) throws Exception;
}
Split: for a given data input of type P, subdivides the elements into an arbitrary sized list of type R[].
public interface Split<P,R> extends Muscle<P,R> {
public R[] split(P param) throws Exception;
}
Merge: for a given arbitrary sized list of type P[] merges the list into a single data element of type R.
public interface Merge<P,R> extends Muscle<P,R> {
public R merge(P[] param) throws Exception;
}
Execute: for a given data element of type P computes and produces new data element of type R.
public interface Execute<P,R> extends Muscle<P,R>{
public R execute(P param) throws Exception;
}
