Difference between revisions of "Raytrace Scheduler"
Jump to navigation
Jump to search
| (11 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | = | + | This Exercise Has Been Updated |
| − | == | + | <!-- |
| − | SplitFourWayRayTracer | + | =Motivation= |
| + | Gain some exposure to different task scheduling styles. | ||
| + | |||
| + | =Background= | ||
| + | [https://en.wikipedia.org/wiki/Ray_tracing_(graphics) Ray Tracing] | ||
| + | |||
| + | <youtube>iLHNF7SgVN4</youtube> | ||
| + | |||
| + | =Code To Investigate= | ||
| + | Static Scheduler-like ray tracer. | ||
| + | |||
| + | {{CodeToInvestigate|SplitFourWayRayTracer|rayTrace|raytrace.demo}} | ||
| + | |||
| + | {{Parallel|public void rayTrace(RayTraceContext context)}} | ||
| + | |||
| + | [[File:StaticScheduleRayTracer.png|thumb]] | ||
| + | |||
==Fun== | ==Fun== | ||
===DivideAndConquerRayTracer=== | ===DivideAndConquerRayTracer=== | ||
| − | Recursively divide the given region into 4 tasks for each of the four quadrants until you get below the threshold. | + | [[File:DivideAndConquerRayTracer.png|thumb]] |
| − | When | + | Recursively divide the given region into 4 tasks for each of the four quadrants until you get below the threshold (see the IntPredicate areaThreshold instance variable). |
| + | When areaThreshold predicate test method returns false, call the <code>rayTraceBaseCase(context, xMin, yMix, xMax, yMax)</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)}} | ||
| + | |||
===WorkStealingRayTracer=== | ===WorkStealingRayTracer=== | ||
| + | [[File:WorkStealingRayTracer.png|thumb]] | ||
The <code>renderMyTasksUntilEmptyThenStealWorkFromOthers</code> 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 <code>id</code> to find the particular quadrant being called. | The <code>renderMyTasksUntilEmptyThenStealWorkFromOthers</code> 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 <code>id</code> 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 <code>Section.render</code> 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. | This method should repeatedly draw from the tail of its own double-ended queue to render its own tasks using the <code>Section.render</code> 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 <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, Deque<Section> myTaskDeque, List<Deque<Section>> otherTaskDeques, int id)}} | ||
| + | --> | ||
Latest revision as of 15:50, 26 April 2022
This Exercise Has Been Updated
