Difference between revisions of "Iterative Averaging"
| Line 55: | Line 55: | ||
:<code>new PhasableDoubleArrays(double[] originalData)</code> | :<code>new PhasableDoubleArrays(double[] originalData)</code> | ||
| + | =Code to Implement= | ||
==Sequential Iterative Averaging== | ==Sequential Iterative Averaging== | ||
| − | {{CodeToInvestigate|SequentialIterativeAverager|iterativelyAverage|iterativeaveraging. | + | {{CodeToInvestigate|SequentialIterativeAverager|iterativelyAverage|iterativeaveraging.warmup}} |
| − | {{Sequential|public double[] iterativelyAverage( | + | {{Sequential|public double[] iterativelyAverage(double[] originalArray, int iterationCount)}} |
<!-- | <!-- | ||
| Line 82: | Line 83: | ||
--> | --> | ||
| − | + | {{CodeToImplement|ParallelIterativeAverager|iterativelyAverage|iterativeaveraging.studio}} | |
| − | {{CodeToImplement| | ||
| − | {{Parallel|public double[] iterativelyAverage( | + | {{Parallel|public double[] iterativelyAverage(double[] originalArray, int iterationCount)}} |
For this method, you should not be using Phasers. Instead, implement a parallel version of the Iterative Averaging algorithm shown above sequentially. Make use of the SwappableDoubleArrays class. The return value should be the current version of the array after it has gone through the number of iterations passed in the method. | For this method, you should not be using Phasers. Instead, implement a parallel version of the Iterative Averaging algorithm shown above sequentially. Make use of the SwappableDoubleArrays class. The return value should be the current version of the array after it has gone through the number of iterations passed in the method. | ||
| Line 91: | Line 91: | ||
| − | {{CodeToImplement| | + | {{CodeToImplement|PhasedParallelIterativeAverager|iterativelyAverage|iterativeaveraging.studio}} |
| − | {{Parallel|public double[] iterativelyAverage( | + | {{Parallel|public double[] iterativelyAverage(double[] originalArray, int iterationCount)}} |
Before you get started on this, make sure you review the [[Iterative Averaging#Background | Background section]] in order to understand how to utilize Phasers (it will look different than the RiceX implementation!). This time, we will use Phasers to create a parallel version of the algorithm that has less overhead. Here are a few notes to keep in mind when working on this assignment: | Before you get started on this, make sure you review the [[Iterative Averaging#Background | Background section]] in order to understand how to utilize Phasers (it will look different than the RiceX implementation!). This time, we will use Phasers to create a parallel version of the algorithm that has less overhead. Here are a few notes to keep in mind when working on this assignment: | ||
*Think carefully as to how the loops in this version will be structured. Drawing out the computation graph may help | *Think carefully as to how the loops in this version will be structured. Drawing out the computation graph may help | ||
*Bulk registering a Phaser indicates how many times <code>phaser.arriveAndAwaitAdvance()</code> needs to be called before any of the threads are able to move on. Make sure to register the right number! | *Bulk registering a Phaser indicates how many times <code>phaser.arriveAndAwaitAdvance()</code> needs to be called before any of the threads are able to move on. Make sure to register the right number! | ||
| + | <!-- | ||
*You also bulk register the SwappableDoubleArrays when instantiating it. Similar to Phasers, the integer passed through in the constructor tells the object how many times <code>swap()</code> needs to be called before the source and destination arrays are actually swapped. | *You also bulk register the SwappableDoubleArrays when instantiating it. Similar to Phasers, the integer passed through in the constructor tells the object how many times <code>swap()</code> needs to be called before the source and destination arrays are actually swapped. | ||
| + | --> | ||
| + | |||
| + | {{CodeToImplement|FuzzyPhasedParallelIterativeAverager|iterativelyAverage|iterativeaveraging.studio}} | ||
| + | |||
| + | {{Parallel|public double[] iterativelyAverage(double[] originalArray, int iterationCount)}} | ||
| + | |||
| + | What indices must be complete? What indices have more flexibility? | ||
=Testing Your Solution= | =Testing Your Solution= | ||
Revision as of 05:23, 16 April 2019
Contents
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 |
| 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
Check out the reference page on phasers
- 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. |
The Core Questions
- What are the tasks?
- What is the data?
- Is the data mutable?
- If so, how is it shared?
Code to Investigate
class AbstractPhasable
- getSrcForPhase(phaseIndex)
- getDstForPhase(phaseIndex)
class PhasableDoubleArrays extends AbstractPhasable<double[]>
new PhasableDoubleArrays(double[] originalData)
Code to Implement
Sequential Iterative Averaging
| class: | SequentialIterativeAverager.java | DEMO:  |
| methods: | iterativelyAverage | |
| package: | iterativeaveraging.warmup | |
| source folder: | src//java |
method: public double[] iterativelyAverage(double[] originalArray, int iterationCount) 
(sequential implementation only)
| class: | ParallelIterativeAverager.java | |
| methods: | iterativelyAverage | |
| package: | iterativeaveraging.studio | |
| source folder: | student/src/main/java |
method: public double[] iterativelyAverage(double[] originalArray, int iterationCount) 
(parallel implementation required)
For this method, you should not be using Phasers. Instead, implement a parallel version of the Iterative Averaging algorithm shown above sequentially. Make use of the SwappableDoubleArrays class. The return value should be the current version of the array after it has gone through the number of iterations passed in the method.
| class: | PhasedParallelIterativeAverager.java | |
| methods: | iterativelyAverage | |
| package: | iterativeaveraging.studio | |
| source folder: | student/src/main/java |
method: public double[] iterativelyAverage(double[] originalArray, int iterationCount) (parallel implementation required)
Before you get started on this, make sure you review the Background section in order to understand how to utilize Phasers (it will look different than the RiceX implementation!). This time, we will use Phasers to create a parallel version of the algorithm that has less overhead. Here are a few notes to keep in mind when working on this assignment:
- Think carefully as to how the loops in this version will be structured. Drawing out the computation graph may help
- Bulk registering a Phaser indicates how many times
phaser.arriveAndAwaitAdvance()needs to be called before any of the threads are able to move on. Make sure to register the right number!
| class: | FuzzyPhasedParallelIterativeAverager.java | |
| methods: | iterativelyAverage | |
| package: | iterativeaveraging.studio | |
| source folder: | student/src/main/java |
method: public double[] iterativelyAverage(double[] originalArray, int iterationCount) (parallel implementation required)
What indices must be complete? What indices have more flexibility?
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 |
