Difference between revisions of "Iterative Averaging"

From CSE231 Wiki
Jump to navigation Jump to search
Line 32: Line 32:
 
<math>PR(u) = \sum_{v \in B_u} \frac{PR(v)}{L(v)}</math>
 
<math>PR(u) = \sum_{v \in B_u} \frac{PR(v)}{L(v)}</math>
  
  <nowiki>int iterationCount = 53;
+
  <nowiki>for (int iteration : new IntegerRange(0, 52)) {
Phaser phaser = new Phaser();
+
forall(slices, (slice) -> {
 +
PageRank[] arrayPrev = ((iteration & 1) == 0) ? a : b;
 +
PageRank[] arrayNext = ((iteration & 1) == 0) ? b : a;
 +
for (int index = slice.getMinInclusive(); index < slice.getMaxExclusive(); index++) {
 +
arrayNext[index] = calculateNextRank(index, arrayPrev);
 +
}
 +
});
 +
}</nowiki>
 +
 
 +
<nowiki>Phaser phaser = new Phaser();
 
phaser.bulkRegister(slices.size());
 
phaser.bulkRegister(slices.size());
 
forall(slices, (slice) -> {
 
forall(slices, (slice) -> {
for (int iteration = 0; iteration < iterationCount; iteration++) {
+
for (int iteration : new IntegerRange(0, iterationCount)) {
 
PageRank[] arrayPrev = ((iteration & 1) == 0) ? a : b;
 
PageRank[] arrayPrev = ((iteration & 1) == 0) ? a : b;
 
PageRank[] arrayNext = ((iteration & 1) == 0) ? b : a;
 
PageRank[] arrayNext = ((iteration & 1) == 0) ? b : a;
Line 44: Line 53:
 
phaser.arriveAndAwaitAdvance();
 
phaser.arriveAndAwaitAdvance();
 
}
 
}
//note: arriveAndDeregister not required for this application
+
// note: arriveAndDeregister not required for this application
 
phaser.arriveAndDeregister();
 
phaser.arriveAndDeregister();
});</nowiki>
+
});
 +
</nowiki>
  
 
=Code to Implement=
 
=Code to Implement=

Revision as of 17:27, 7 March 2018

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.

Background

class Phaser

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

Guide to the Java Phaser

Attention niels epting.svg 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: Java.png
methods: iterativelyAverage
package: iterativeaveraging.demo
source folder: src//java

method: public void iterativelyAverage(List<Slice<double[]>> slices, double[] a, double[] b, int iterationCount) Sequential.svg (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;
		}
	}
}

Phased PageRank

for (int iteration : new IntegerRange(0, 52)) {
	forall(slices, (slice) -> {
		PageRank[] arrayPrev = ((iteration & 1) == 0) ? a : b;
		PageRank[] arrayNext = ((iteration & 1) == 0) ? b : a;
		for (int index = slice.getMinInclusive(); index < slice.getMaxExclusive(); index++) {
			arrayNext[index] = calculateNextRank(index, arrayPrev);
		}
	});
}
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;
		for (int index = slice.getMinInclusive(); index < slice.getMaxExclusive(); index++) {
			arrayNext[index] = calculateNextRank(index, arrayPrev);
		}
		phaser.arriveAndAwaitAdvance();
	}
	// note: arriveAndDeregister not required for this application
	phaser.arriveAndDeregister();
});

Code to Implement

class: ForForallIterativeAverager.java Java.png
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.svg (parallel implementation required)

class: ForallForPhasedIterativeAverager.java Java.png
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.svg (parallel implementation required)

Testing Your Solution

Correctness

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

Performance

class: IterativeAveragingTiming.java Noun Project stopwatch icon 386232 cc.svg
package: iterativeaveraging.studio
source folder: src/main/java