LeggedRaces

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

Legged Races

interface Participant

takeStep

Looping

Java For Loop

Java For Each Loop

forall

Phasers

class Phaser (Guide to the Java Phaser)

register

bulkRegister

arriveAndAwaitAdvance

arrive

awaitAdvance use via PhaserUtils.awaitAdvanceForPhase(phaser, phase)

PhaserUtils

awaitAdvanceForPhase

If you are on or past the phase you want to await, then calling phaser.awaitAdvance() directly is fine. If you might be on a prior phase, then invoke PhaserUtils.awaitAdvanceForPhase(phaser, phase). If in doubt, invoking awaitAdvanceForPhase is safer.

	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();
				}
			}
		}
	}

The Core Questions

• What are the tasks?
• What is the data?
• 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

Single Everyone Bound Together Races

AllTogetherLeggedRace

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

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

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
methods:	takeSteps
package:	leggedrace.exercise
source folder:	student/src/main/java

DefaultPhaserCreator Utility

class:	DefaultPhaserCreator.java
methods:	get
package:	leggedrace.exercise
source folder:	student/src/main/java

method: public Phaser get() (sequential implementation only)

Construct a new Phaser and return it.

PhasedAllTogetherLeggedRace

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

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

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

This time, we want to simulate a 3-legged race with multiple teams participating. In this implementation, you will build on what you did with the fork loop implementation to incorporate an array of phasers. Start this off by instantiating an array of phasers. It is up to you to determine how many phasers you need in the array. There are multiple solutions that use different numbers of phasers. Think carefully about how you can have participants signal and wait on phasers in order to make sure no participant takes two steps before their partner catches up to them.

PhaserPerTeamLeggedRace

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

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

Warning:When you create an array, the contents will initially be null.

PhaserPerParticipantLeggedRace

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

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

Use provided int getPartnerIndex(int) to find the partner for a participant

   	private static int getPartnerIndex(int index) {
          	boolean isOddIndex = (index&0x1) == 0x1;
          	if( isOddIndex ) {
                 	return index - 1;
          	} else {
                 	return index + 1;
          	}
   	}

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.

Correctness

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