Raytrace Scheduler

Motivation

Gain some exposure to different task scheduling styles.

Background

Ray Tracing

Code To Investigate

class:	SplitFourWayRayTracer.java	DEMO:
methods:	rayTrace
package:	raytrace.demo
source folder:	src//java

method: public void rayTrace(RayTraceContext context) (parallel implementation required)

Fun

DivideAndConquerRayTracer

Recursively divide the given region into 4 tasks for each of the four quadrants until you get below the threshold. When areaThreshold predicate test method returns false, call the rayTraceBaseCase(context, xMin, yMix, xMax, yMax) method to render the section.

class:	DivideAndConquerRayTracer.java
methods:	rayTraceKernel
package:	raytrace.fun
source folder:	student/src/main/java

method: private void rayTraceKernel(RayTraceContext context, int xMin, int yMin, int xMax, int yMax, int areaThreshold) (parallel implementation required)

WorkStealingRayTracer

The renderMyTasksUntilEmptyThenStealWorkFromOthers method will be called on one of the four quadrants, but it will be given the sections that make up all four quadrants. You can use the id to find the particular quadrant being called.

This method should repeatedly draw from the tail of its own double-ended queue to render its own tasks using the Section.render method. If it finishes all of its tasks, and there are still unfinished tasks in the other quadrants, then it should draw tasks from the head of the other quadrants' deques.

As you can see in the WorkStealingRayTracer.rayTrace method, the parallelism comes from the fact that the renderMyTasksUntilEmptyThenStealWorkFromOthers method is called multiple times in parallel. You don't have to worry about spawning new tasks. Also, because ConcurrentLinkedDeque is thread-safe, all operations are atomic, so you you shouldn't need to use isolated. However, you should avoid reading and then writing.

class:	WorkStealingRayTracer.java
methods:	renderMyTasksUntilEmptyThenStealWorkFromOthers
package:	raytrace.fun
source folder:	student/src/main/java

method: private void renderMyTasksUntilEmptyThenStealWorkFromOthers(RayTraceTaskContext taskContext, Deque<Section> myTaskDeque, List<Deque<Section>> otherTaskDeques, int id) (sequential implementation only)