Iterative Averaging

Motivation

Iterative Averaging is the process of updating an array to so that each index becomes the average of the indices one before and one after it. After repeating this for many iterations, the array may converge to one set of numbers. For example, when given the following array, we can perform iterations of this algorithm until the array eventually converges:

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0.5

1

0

0

0

0

0

0

0

0

0.25

0.5

1

$\vdots$

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Note that the ends of the array remain the same value from the previous iteration.

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.

For more information on the algorithm and how we can use Phasers to make it better, review Topic 3.5 from the RiceX course.

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

class AbstractSwappable

getSrc()

getDst()

swap()

class SwappableDoubleArrays implements AbstractSwappable

new SwappableDoubleArrays(int registrations, double[] originalData)

Sequential Iterative Averaging

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

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

SwappableDoubleArrays data = new SwappableDoubleArrays(1, originalArray);
	for (int iteration = 0; iteration < iterationCount; iteration++) {
		double[] arrayPrev = data.getSrc();
		double[] arrayNext = data.getDst();
		for (Slice<double[]> slice : slices) {
			for (int index = slice.getMinInclusive(); index < slice.getMaxExclusive(); index++) {
				arrayNext[index] = (arrayPrev[index - 1] + arrayPrev[index + 1]) * 0.5;
			}
		}
		data.swap();
	}
	return data.getSrc();
}

This is a demo of the Iterative Averaging algorithm done sequentially. Take a look at the code in your repo. Some important questions/notes to think about:

• What does the SwappableDoubleArrays do and why is it useful in this algoritm?
• Why is data.getSrc() returned and not data.getDst()?
• Note that none of the slices contain the indices 0 or originalArray.length. If it did, the code would throw an OutOfBoundsException

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 double[] iterativelyAverage(List<Slice<double[]>> slices, double[] originalArray, int iterationCount) (parallel implementation required)

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

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

Before you get started on this, make sure you review the Background

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