Difference between revisions of "LeggedRaces"

From CSE231 Wiki
Jump to navigation Jump to search
 
(49 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
In a legged race, a group of people must try to move forward as quickly as possible with their legs tied to each other. In other words, the group can only be as quick as its slowest link and they must try to move in unison. In many ways, this concept mirrors parallel phasers. In this studio, you will use phasers and forall loops in order to simulate a legged race.
 
In a legged race, a group of people must try to move forward as quickly as possible with their legs tied to each other. In other words, the group can only be as quick as its slowest link and they must try to move in unison. In many ways, this concept mirrors parallel phasers. In this studio, you will use phasers and forall loops in order to simulate a legged race.
  
=Background=
+
You will complete four methods that cover two different types of races. The first three versions are an "n+1 legged race". This is where all participants are a part of the same group. Each person's legs are tied to their neighbors, and thus it is impossible for one person to take a second step before everyone else has taken their first step. The final method is a "3 legged race". Participants have a partner who they are tied to and can continue to take steps as long as their partner is keeping up with them.
<youtube>acDrcvwvd8I</youtube>
+
 
 +
<!--
 +
=Lecture=
 +
<youtube>GwlFbdX1Nhg</youtube>
 +
<youtube>whPAPmylbEU</youtube>
 +
-->
  
 
=Code To Use=
 
=Code To Use=
==Legged Races==
+
==Phaser==
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/leggedrace/core/Participant.html interface Participant]
 
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/leggedrace/core/Participant.html#takeStep-int- takeStep]
 
 
 
==Looping==
 
[https://docs.oracle.com/javase/tutorial/java/nutsandbolts/for.html Java For Loop]
 
 
 
[https://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html Java For Each Loop]
 
  
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/edu/wustl/cse231s/v5/V5.html#forall-T:A-edu.wustl.cse231s.v5.api.CheckedConsumer- forall]
 
 
==Phasers==
 
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html class Phaser] ([http://www.baeldung.com/java-phaser Guide to the Java Phaser])
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html class Phaser] ([http://www.baeldung.com/java-phaser Guide to the Java Phaser])
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html#register-- register]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html#register-- register]
Line 25: Line 20:
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html#awaitAdvance-int- awaitAdvance] use via PhaserUtils.awaitAdvanceForPhase(phaser, phase)
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html#awaitAdvance-int- awaitAdvance] use via PhaserUtils.awaitAdvanceForPhase(phaser, phase)
  
[http://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/edu/wustl/cse231s/concurrent/PhaserUtils.html PhaserUtils]
+
==PhaserUtils==
: [http://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/edu/wustl/cse231s/concurrent/PhaserUtils.html#awaitAdvanceForPhase-java.util.concurrent.Phaser-int- awaitAdvanceForPhase]
+
[http://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/concurrent/PhaserUtils.html PhaserUtils]
 +
: [http://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/edu/wustl/cse231s/concurrent/PhaserUtils.html#awaitAdvanceForPhase-java.util.concurrent.Phaser-int- awaitAdvanceForPhase]
  
If you are on or past the phase you want to await, then calling <code>phaser.awaitAdvance()</code> directly is fine.  If you might be on a prior phase, then invoke <code>PhaserUtils.awaitAdvanceForPhase(phaser, phase)</code>.  If in doubt, invoking awaitAdvanceForPhase is safer.
+
If you are on or past the phase you want to await, then calling <code>phaser.awaitAdvance(phase)</code> directly is fine.  If you might be on a prior phase, then invoke <code>PhaserUtils.awaitAdvanceForPhase(phaser, phase)</code>.  If in doubt, invoke PhaserUtils.awaitAdvanceForPhase(phaser, phase) as it will await until the phase is arrived upon no matter what.
  
<nowiki> public static int awaitAdvanceForPhase(Phaser phaser, int phase) {
+
{{CollapsibleCode|PhaserUtils|
 +
<syntaxhighlight lang="java">
 +
public static int awaitAdvanceForPhase(Phaser phaser, int phase) {
 
return awaitAdvanceForPhase(phaser, phase, () -> Thread.yield());
 
return awaitAdvanceForPhase(phaser, phase, () -> Thread.yield());
 
}
 
}
Line 45: Line 43:
 
}
 
}
 
}
 
}
}</nowiki>
+
}
 +
</syntaxhighlight>}}
 +
 
 +
==Legged Races==
 +
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/leggedrace/core/Participant.html interface Participant]
 +
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/leggedrace/core/Participant.html#takeStep-int- takeStep]
  
=Questions To Ask Yourself=
+
<!--
# What are my tasks?
+
=The Core Questions=
# What work does each task need to do?
+
*What are the tasks?
# Upon what does each task depend?  That is: what does each task have to wait for before it may proceed?
+
*What is the data?
# What could have possibly been more important than adding a random stopping to tie their shoes animation to the visualization?
+
*Is the data mutable?
 +
*If so, how is it shared?
 +
Here are some additional questions to help guide you down the right path
 +
*What work does each task need to do?
 +
*Upon what does each task depend?  That is: what does each task have to wait for before it may proceed?
 +
*What could have possibly been more important than adding a random stopping to tie their shoes animation to the visualization?
 +
-->
  
 
=Code To Implement=
 
=Code To Implement=
==SequentialLeggedRace==
+
<youtube>Ey5NhJFXAu4</youtube>
 +
 
 +
==Single Everyone Bound Together Races==
 +
===AllTogetherLeggedRace===
 +
 
 +
{{CodeToImplement|AllTogetherLeggedRace|takeSteps|leggedrace.exercise}}
 +
 
 +
{{Parallel|public void takeSteps(Participant[] participants, int stepCount)}}
 +
 
 +
[[File:LoopOfForkLoops_LeggedRace.svg | 400px]]
  
{{CodeToImplement|SequentialLeggedRace|takeSteps|leggedrace.studio}}
+
In this implementation, the participants should all take each individual step in parallel.  However, the steps should be taken each in turn sequentially.  Think about where to place the fork loop so that the program only progresses to the next stepIndex after every participant has performed a takeStep with the current index value.
  
{{Sequential|public void takeSteps(Participant[] participants, int stepCount)}}
+
===X10PhasedAllTogetherLeggedRace===
  
In this implementation, try to solve the problem sequentially. Your method should go through the array of participants and make each one takeStep until you do this for every stepIndex up until the stepCount for every participant.
+
{{CodeToImplement|X10PhasedAllTogetherLeggedRace|takeSteps|leggedrace.exercise}}
  
Hint: Basically, you will need two for loops. One that iterates up until the stepCount and another which goes through the array of participants.
+
[[File:X10PhasedForkLoop_LeggedRace.svg | 600px]]
  
==ForallLeggedRace==
+
<!-- ===DefaultPhaserCreator Utility===
  
{{CodeToImplement|ForallLeggedRace|takeSteps|leggedrace.studio}}
+
{{CodeToImplement|DefaultPhaserCreator|get|leggedrace.exercise}}
  
{{Parallel|public void takeSteps(Participant[] participants, int stepCount)}}
+
{{Sequential|public Phaser get()}}
  
In this implementation, the participants should all take each individual step in parallel. However, the steps should be taken each in turn sequentially. Think about where to place the forall loop so that the program only progresses to the next stepIndex after every participant has performed a takeStep with the current index value.
+
Construct a new [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html Phaser] and return it. -->
  
==ForallPhasedLeggedRace==
+
===PhasedAllTogetherLeggedRace===
  
{{CodeToImplement|ForallPhasedLeggedRace|takeSteps|leggedrace.studio}}
+
{{CodeToImplement|PhasedAllTogetherLeggedRace|takeSteps|leggedrace.exercise}}
  
 
{{Parallel|public void takeSteps(Participant[] participants, int stepCount)}}
 
{{Parallel|public void takeSteps(Participant[] participants, int stepCount)}}
  
In this solution, you will flip your sequentialLoop/parallelLoop pattern into a parallelLoop/sequentialLoop pattern with a phaser.
+
[[File:ForkLoopWithPhaser LeggedRace.svg | 600px]]
 +
 
 +
In this solution, you will flip your sequentialLoop/parallelLoop pattern into a parallelLoop/sequentialLoop pattern with a phaser. For this, there should only be one Phaser, which is bulk registered such that each participant can wait on the same Phaser. In order to simplify the code, look into [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Phaser.html#arriveAndAwaitAdvance-- arriveAndAwaitAdvance()].
 +
 
 +
==Teams Of 2 Races==
 +
As Daniel Tiger correctly observed, [https://www.pbs.org/video/mister-rogers-neighborhood-it-can-be-very-hard-to-wait/ it is very, very, very hard to wait].  It is also wasteful.  Here we will use multiple Phasers to simulate a 3-legged race with multiple teams participating.
  
==ForallPhasedPointToPointLeggedRace==
+
===PhaserPerTeamLeggedRace===
  
{{CodeToImplement|ForallPhasedPointToPointLeggedRace|takeSteps|leggedrace.studio}}
+
[[File:PhaserPerTeam_LeggedRace.svg | 600px]]
 +
 
 +
{{CodeToImplement|PhaserPerTeamLeggedRace|constructor<br/>phaserCreator<br/>takeSteps|leggedrace.exercise}}
  
 
{{Parallel|public void takeSteps(Participant[] participants, int stepCount)}}
 
{{Parallel|public void takeSteps(Participant[] participants, int stepCount)}}
Line 88: Line 113:
 
{{Warning|When you create an array, the contents will initially be null.}}
 
{{Warning|When you create an array, the contents will initially be null.}}
  
In this implementation, you will build on what you did with the forall implementation to incorporate an array of phasers. Start this off by instantiating an array of phasers
+
=Testing Your Solution=
Use provided <code>int getPartnerIndex(int)</code> to find the partner for a participant.
+
==Visualization==
 +
{{Viz|LeggedRaceViz|leggedrace.viz|main}}
 +
 
 +
Click on the buttons on the right to visualize your solutions when you have implemented them. Here are examples of what the correct visualization should look like for each method.
 +
 
 +
[[File:SequentialLeggedRaceGIF.gif|SequentialLeggedRace]]
  
<nowiki>  private static int getPartnerIndex(int index) {
+
[[File:ForAllLeggedRaceGIF.gif|ForallLeggedRace]]
          boolean isOddIndex = (index&0x1) == 0x1;
 
          if( isOddIndex ) {
 
                return index - 1;
 
          } else {
 
                return index + 1;
 
          }
 
  }</nowiki>
 
  
=Testing Your Solution=
+
[[File:ForAllPhasedLeggedRaceGIF.gif|ForallPhasedLeggedRace]]
==Visualization==
 
{{Viz|LeggedRaceVisualizationApp|leggedrace.viz}}
 
  
Click on the buttons on the right to visualize your solutions when you have implemented them.
+
[[File:ForAllPhasedP2PLeggedRaceGIF.gif|ForallPhasedPointToPointLeggedRace]]
  
[[File:LeggedRaceScreenShot.png]]
 
 
==Correctness==
 
==Correctness==
{{TestSuite|LeggedRaceTestSuite|leggedrace.studio}}
+
{{TestSuite|__LeggedRaceTestSuite|leggedrace.exercise}}
 
 
{{TestSuite|PartialCreditLeggedRaceTestSuite|leggedrace.studio}}
 
  
When you are passing the tests and your visualization looks good, demo it to an instructor.
+
=Pledge, Acknowledgments, Citations=
 +
{{Pledge|exercise-legged-races}}

Latest revision as of 20:43, 19 April 2023

Motivation

In a legged race, a group of people must try to move forward as quickly as possible with their legs tied to each other. In other words, the group can only be as quick as its slowest link and they must try to move in unison. In many ways, this concept mirrors parallel phasers. In this studio, you will use phasers and forall loops in order to simulate a legged race.

You will complete four methods that cover two different types of races. The first three versions are an "n+1 legged race". This is where all participants are a part of the same group. Each person's legs are tied to their neighbors, and thus it is impossible for one person to take a second step before everyone else has taken their first step. The final method is a "3 legged race". Participants have a partner who they are tied to and can continue to take steps as long as their partner is keeping up with them.


Code To Use

Phaser

class Phaser (Guide to the Java Phaser)

register
bulkRegister
arriveAndAwaitAdvance
arrive
awaitAdvance use via PhaserUtils.awaitAdvanceForPhase(phaser, phase)

PhaserUtils

PhaserUtils

awaitAdvanceForPhase

If you are on or past the phase you want to await, then calling phaser.awaitAdvance(phase) directly is fine. If you might be on a prior phase, then invoke PhaserUtils.awaitAdvanceForPhase(phaser, phase). If in doubt, invoke PhaserUtils.awaitAdvanceForPhase(phaser, phase) as it will await until the phase is arrived upon no matter what.

PhaserUtils  
	public static int awaitAdvanceForPhase(Phaser phaser, int phase) {
		return awaitAdvanceForPhase(phaser, phase, () -> Thread.yield());
	}

	public static int awaitAdvanceForPhase(Phaser phaser, int phase, Runnable runnable) {
		while (true) {
			int currentPhase = phaser.awaitAdvance(phase);
			if (currentPhase < 0 || currentPhase > phase) {
				return currentPhase;
			} else {
				if (runnable != null) {
					runnable.run();
				}
			}
		}
	}

Legged Races

interface Participant

takeStep


Code To Implement

Single Everyone Bound Together Races

AllTogetherLeggedRace

class: AllTogetherLeggedRace.java Java.png
methods: takeSteps
package: leggedrace.exercise
source folder: student/src/main/java

method: public void takeSteps(Participant[] participants, int stepCount) Parallel.svg (parallel implementation required)

LoopOfForkLoops LeggedRace.svg

In this implementation, the participants should all take each individual step in parallel. However, the steps should be taken each in turn sequentially. Think about where to place the fork loop so that the program only progresses to the next stepIndex after every participant has performed a takeStep with the current index value.

X10PhasedAllTogetherLeggedRace

class: X10PhasedAllTogetherLeggedRace.java Java.png
methods: takeSteps
package: leggedrace.exercise
source folder: student/src/main/java

X10PhasedForkLoop LeggedRace.svg


PhasedAllTogetherLeggedRace

class: PhasedAllTogetherLeggedRace.java Java.png
methods: takeSteps
package: leggedrace.exercise
source folder: student/src/main/java

method: public void takeSteps(Participant[] participants, int stepCount) Parallel.svg (parallel implementation required)

ForkLoopWithPhaser LeggedRace.svg

In this solution, you will flip your sequentialLoop/parallelLoop pattern into a parallelLoop/sequentialLoop pattern with a phaser. For this, there should only be one Phaser, which is bulk registered such that each participant can wait on the same Phaser. In order to simplify the code, look into arriveAndAwaitAdvance().

Teams Of 2 Races

As Daniel Tiger correctly observed, it is very, very, very hard to wait. It is also wasteful. Here we will use multiple Phasers to simulate a 3-legged race with multiple teams participating.

PhaserPerTeamLeggedRace

PhaserPerTeam LeggedRace.svg

class: PhaserPerTeamLeggedRace.java Java.png
methods: constructor
phaserCreator
takeSteps
package: leggedrace.exercise
source folder: student/src/main/java

method: public void takeSteps(Participant[] participants, int stepCount) Parallel.svg (parallel implementation required)

Attention niels epting.svg Warning:When you create an array, the contents will initially be null.

Testing Your Solution

Visualization

class: LeggedRaceViz.java VIZ
package: leggedrace.viz
source folder: student/src/main/java

Click on the buttons on the right to visualize your solutions when you have implemented them. Here are examples of what the correct visualization should look like for each method.

SequentialLeggedRace

ForallLeggedRace

ForallPhasedLeggedRace

ForallPhasedPointToPointLeggedRace

Correctness

class: __LeggedRaceTestSuite.java Junit.png
package: leggedrace.exercise
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: exercise-legged-races-pledge-acknowledgments-citations.txt

More info about the Honor Pledge