Iterative Averaging

Motivation

X10/Habanero like Phasers have been added to Java since JDK7. We will gain some experience with using Phasers in a parallel for-loop context. Phasers allow us to change the structure of our loops and reduce overhead in the algorithm.

Background

Guide to the Java Phaser

class Phaser

bulkRegister

arriveAndAwaitAdvance

arriveAndDeregister (note: not required for this studio, but good to know about.)

Warning: Our use of the forall loop with Phasers does not accurately convey their finicky nature. More than other features, Phasers seem to require more care to get performance improvements.

Code to Investigate

Sequential Iterative Averaging

class:	SequentialIterativeAverager.java	DEMO:
methods:	iterativelyAverage
package:	iterativeaveraging.demo
source folder:	src//java

method: public void iterativelyAverage(List<Slice<double[]>> slices, double[] a, double[] b, int iterationCount) (sequential implementation only)

for (int iteration = 0; iteration < iterationCount; iteration++) {
	double[] arrayPrev = ((iteration & 1) == 0) ? a : b;
	double[] arrayNext = ((iteration & 1) == 0) ? b : a;
	for (Slice<double[]> slice : slices) {
		for (int index = slice.getMinInclusive(); index < slice.getMaxExclusive(); index++) {
			arrayNext[index] = (arrayPrev[index - 1] + arrayPrev[index + 1]) * 0.5;
		}
	}
}

PageRank

$PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}$

parallel

for (int iteration : new IntegerRange(0, iterationCount)) {
	forall(slices, (slice) -> {
		PageRank[] arrayPrev = ((iteration & 1) == 0) ? a : b;
		PageRank[] arrayNext = ((iteration & 1) == 0) ? b : a;
		slice.forEachIndex((index) -> {
                 	arrayNext[index] = calculateNextRank(index, arrayPrev);
          	});
	});
}

parallel phased

Phaser phaser = new Phaser();
phaser.bulkRegister(slices.size());
forall(slices, (slice) -> {
	for (int iteration : new IntegerRange(0, iterationCount)) {
		PageRank[] arrayPrev = ((iteration & 1) == 0) ? a : b;
		PageRank[] arrayNext = ((iteration & 1) == 0) ? b : a;
		slice.forEachIndex((index) -> {
                 	arrayNext[index] = calculateNextRank(index, arrayPrev);
          	});
		phaser.arriveAndAwaitAdvance();
	}
	// note: arriveAndDeregister not required for this application
	phaser.arriveAndDeregister();
});

Code to Implement

class:	ForForallIterativeAverager.java
methods:	iterativelyAverage
package:	iterativeaveraging.studio
source folder:	student/src/main/java

method: public void iterativelyAverage(List<Slice<double[]>> slices, double[] a, double[] b, int iterationCount) (parallel implementation required)

class:	ForallForPhasedIterativeAverager.java
methods:	iterativelyAverage
package:	iterativeaveraging.studio
source folder:	student/src/main/java

method: public void iterativelyAverage(List<Slice<double[]>> slices, double[] a, double[] b, int iterationCount) (parallel implementation required)

Testing Your Solution

Correctness

class:	IterativeAveragingTestSuite.java
package:	iterativeaveraging.studio
source folder:	testing/src/test/java

Performance

class:	IterativeAveragingTiming.java
package:	iterativeaveraging.studio
source folder:	src/main/java