Difference between revisions of "Raytrace Scheduler"
| Line 1: | Line 1: | ||
=Where to Start= | =Where to Start= | ||
==Demo== | ==Demo== | ||
| + | {{CodeToInvestigate|SplitFourWayRayTracer|rayTrace|raytrace.demo}} | ||
| + | |||
| + | {{Parallel|public void rayTrace(RayTraceContext context)}} | ||
| + | |||
[[File:StaticScheduleRayTracer.png|thumb]] | [[File:StaticScheduleRayTracer.png|thumb]] | ||
| − | |||
==Fun== | ==Fun== | ||
| Line 9: | Line 12: | ||
Recursively divide the given region into 4 tasks for each of the four quadrants until you get below the threshold. | Recursively divide the given region into 4 tasks for each of the four quadrants until you get below the threshold. | ||
When you get below the threshold, call the <code>renderSection</code> method to render the section. | When you get below the threshold, call the <code>renderSection</code> method to render the section. | ||
| + | |||
| + | {{CodeToImplement|DivideAndConquerRayTracer|rayTraceKernel|raytrace.fun}} | ||
| + | |||
| + | {{Parallel|private void rayTraceKernel(RayTraceContext context, int xMin, int yMin, int xMax, int yMax, int areaThreshold)}} | ||
| + | |||
===WorkStealingRayTracer=== | ===WorkStealingRayTracer=== | ||
[[File:WorkStealingRayTracer.png|thumb]] | [[File:WorkStealingRayTracer.png|thumb]] | ||
| Line 16: | Line 24: | ||
As you can see in the <code>WorkStealingRayTracer.rayTrace</code> method, the parallelism comes from the fact that the <code>renderMyTasksUntilEmptyThenStealWorkFromOthers</code> 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. | As you can see in the <code>WorkStealingRayTracer.rayTrace</code> method, the parallelism comes from the fact that the <code>renderMyTasksUntilEmptyThenStealWorkFromOthers</code> 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. | ||
| + | |||
| + | {{CodeToImplement|WorkStealingRayTracer|renderMyTasksUntilEmptyThenStealWorkFromOthers|raytrace.fun}} | ||
| + | |||
| + | {{Sequential|private void renderMyTasksUntilEmptyThenStealWorkFromOthers(RayTraceTaskContext taskContext, List<ConcurrentLinkedDeque<Section>> quadrants, int id)}} | ||
Revision as of 08:03, 24 April 2018
Contents
Where to Start
Demo
| 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 you get below the threshold, call the renderSection 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, List<ConcurrentLinkedDeque<Section>> quadrants, int id) 
(sequential implementation only)
