Difference between revisions of "Parallel Raytracer Assignment"

From CSE231 Wiki
Jump to navigation Jump to search
 
(20 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
=Motivation=
 +
[https://en.wikipedia.org/wiki/Ray_tracing_(graphics) Ray tracing] cast (sometimes multiple) rays for each [https://en.wikipedia.org/wiki/Pixel pixel] to compute the illumination of a scene.  Each ray can be computed completely independently of all other rays.  This "embarrassment of riches" of potential parallelism is referred to [https://en.wikipedia.org/wiki/Embarrassingly_parallel embarrassingly parallel].  We will use ray tracing as our application for the [[Centralized_Work_Queue_Assignment|scheduler]] challenge problem.
 +
 +
=Warm Ups=
 +
We build on two warmups to gain experience with the [[Scheduler_Client_Assignment|scheduler]] and the [[Sequential_Raytracer_Assignment|ray trace context]].
 +
 
=Code To Investigate=
 
=Code To Investigate=
 
==RayTraceContext==
 
==RayTraceContext==
Line 8: Line 14:
 
void mark(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive);
 
void mark(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive);
  
void markAndRender(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive);
+
void raytrace(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive);
 
}</nowiki>
 
}</nowiki>
  
Line 31: Line 37:
  
 
public int xMin() {
 
public int xMin() {
return this.xMin;
+
return xMin;
 
}
 
}
  
 
public int yMin() {
 
public int yMin() {
return this.yMin;
+
return yMin;
 
}
 
}
  
 
public int xMaxExclusive() {
 
public int xMaxExclusive() {
return this.xMaxExclusive;
+
return xMaxExclusive;
 
}
 
}
  
 
public int yMaxExclusive() {
 
public int yMaxExclusive() {
return this.yMaxExclusive;
+
return yMaxExclusive;
 
}
 
}
 
}</nowiki>
 
}</nowiki>
Line 53: Line 59:
 
===rayTrace===
 
===rayTrace===
 
{{Parallel|public void rayTrace(RayTraceContext context, Scheduler scheduler)}}
 
{{Parallel|public void rayTrace(RayTraceContext context, Scheduler scheduler)}}
 +
 +
Split the image into four quadrants using the x and y coordinates contained in the RayTraceContext. Recall that the scheduler has a void_fork() method you can use to do this (remember: it's unnecessary to void_fork() the last quadrant. You can just leave some work behind for the continuation).
  
 
==LoopRayTracer==
 
==LoopRayTracer==
Line 58: Line 66:
  
 
===constructor===
 
===constructor===
{{Sequential|public LoopRayTracer(Function<RayTraceContext, List<Section>> sectionsCreator)}}
+
{{Sequential|public LoopRayTracer(int sectionSize}}
  
Hang onto the sectionsCreator in an instance variable.  You will need it. Refer to [https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.html Function<T, R> Interface] documentation if you are unfamiliar with Function.
+
Hang onto the sectionSize in an instance variable.  You will need it.
  
===sectionsCreator===
+
===sectionSize===
{{Sequential|Function<RayTraceContext, List<Section>> sectionsCreator()}}
+
{{Sequential|int sectionSize()}}
  
Return the sectionsCreator you stored in an instance variable.
+
Return the sectionSize you stored in an instance variable.
  
 
===rayTrace===
 
===rayTrace===
 
{{Parallel|public void rayTrace(RayTraceContext context, Scheduler scheduler)}}
 
{{Parallel|public void rayTrace(RayTraceContext context, Scheduler scheduler)}}
 +
 +
Use the sectionSize to create a list of Sections.
 +
 +
To call createSections(), use the Sections class, i.e. Sections.createSections(rayTraceContext, size).
 +
 +
<syntaxhighlight lang="java">
 +
public class Sections {
 +
public static List<Section> createSections(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive, int size) {
 +
List<Section> sections = new LinkedList<>();
 +
for (int y = yMin; y < yMaxExclusive; y += size) {
 +
for (int x = xMin; x < xMaxExclusive; x += size) {
 +
sections.add(new Section(x, y, Math.min(x + size, xMaxExclusive), Math.min(y + size, yMaxExclusive)));
 +
}
 +
}
 +
return sections;
 +
}
 +
 +
public static List<Section> createSections(RayTraceContext rayTraceContext, int size) {
 +
return createSections(0, 0, rayTraceContext.width(), rayTraceContext.height(), size);
 +
}
 +
}
 +
</syntaxhighlight>
 +
 +
Then create a rayTrace task for each section.
  
 
==DivideAndConquerRayTracer==
 
==DivideAndConquerRayTracer==
Line 84: Line 116:
  
 
Return the thresholdPredicate you stored in an instance variable.
 
Return the thresholdPredicate you stored in an instance variable.
 +
 +
===rayTraceKernel===
 +
{{Parallel|private void rayTraceKernel(RayTraceContext context, Scheduler scheduler, int xMin, int yMin, int xMax, int yMax)}}
 +
 +
Use the threshold predicate to know whether or not to continue dividing, or to just render the current rectange. ThresholdPredicate now takes two parameters, which are the height and width of the rectangle.
  
 
===rayTrace===
 
===rayTrace===
{{Parallel|public void rayTrace(RayTraceContext context, Scheduler scheduler)}}
+
 
 +
provided:
 +
 
 +
<syntaxhighlight lang="java">
 +
@Override
 +
public void rayTrace(RayTraceContext context, Scheduler scheduler) {
 +
rayTraceKernel(context, scheduler, 0, 0, context.width(), context.height());
 +
}
 +
</syntaxhighlight>
  
 
=Checking Your Solution=
 
=Checking Your Solution=
Line 93: Line 138:
  
 
==Correctness==
 
==Correctness==
{{TestSuite|_SequentialRayTracerTestSuite|raytrace.group}}
+
{{TestSuite|_ParallelRayTracerTestSuite|raytrace.exercise}}
 +
 
 +
=Pledge, Acknowledgments, Citations=
 +
{{Pledge|parallel-raytracer}}

Latest revision as of 04:13, 26 April 2024

Motivation

Ray tracing cast (sometimes multiple) rays for each pixel to compute the illumination of a scene. Each ray can be computed completely independently of all other rays. This "embarrassment of riches" of potential parallelism is referred to embarrassingly parallel. We will use ray tracing as our application for the scheduler challenge problem.

Warm Ups

We build on two warmups to gain experience with the scheduler and the ray trace context.

Code To Investigate

RayTraceContext

public interface RayTraceContext {
	int width();

	int height();

	void mark(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive);

	void raytrace(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive);
}

Scheduler

public interface Scheduler {
	void void_fork(Runnable runnable);
}

Section

public final class Section {
	private final int xMin;
	private final int yMin;
	private final int xMaxExclusive;
	private final int yMaxExclusive;

	public Section(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive) {
		this.xMin = xMin;
		this.yMin = yMin;
		this.xMaxExclusive = xMaxExclusive;
		this.yMaxExclusive = yMaxExclusive;
	}

	public int xMin() {
		return xMin;
	}

	public int yMin() {
		return yMin;
	}

	public int xMaxExclusive() {
		return xMaxExclusive;
	}

	public int yMaxExclusive() {
		return yMaxExclusive;
	}
}

Code To Implement

SplitFourWayRayTracer

class: SplitFourWayRayTracer.java Java.png
methods: rayTrace
package: raytrace.exercise
source folder: student/src/main/java

rayTrace

method: public void rayTrace(RayTraceContext context, Scheduler scheduler) Parallel.svg (parallel implementation required)

Split the image into four quadrants using the x and y coordinates contained in the RayTraceContext. Recall that the scheduler has a void_fork() method you can use to do this (remember: it's unnecessary to void_fork() the last quadrant. You can just leave some work behind for the continuation).

LoopRayTracer

class: LoopRayTracer.java Java.png
methods: constructor
sectionsCreator
rayTrace
package: raytrace.exercise
source folder: student/src/main/java

constructor

method: public LoopRayTracer(int sectionSize Sequential.svg (sequential implementation only)

Hang onto the sectionSize in an instance variable. You will need it.

sectionSize

method: int sectionSize() Sequential.svg (sequential implementation only)

Return the sectionSize you stored in an instance variable.

rayTrace

method: public void rayTrace(RayTraceContext context, Scheduler scheduler) Parallel.svg (parallel implementation required)

Use the sectionSize to create a list of Sections.

To call createSections(), use the Sections class, i.e. Sections.createSections(rayTraceContext, size).

public class Sections {
	public static List<Section> createSections(int xMin, int yMin, int xMaxExclusive, int yMaxExclusive, int size) {
		List<Section> sections = new LinkedList<>();
		for (int y = yMin; y < yMaxExclusive; y += size) {
			for (int x = xMin; x < xMaxExclusive; x += size) {
				sections.add(new Section(x, y, Math.min(x + size, xMaxExclusive), Math.min(y + size, yMaxExclusive)));
			}
		}
		return sections;
	}

	public static List<Section> createSections(RayTraceContext rayTraceContext, int size) {
		return createSections(0, 0, rayTraceContext.width(), rayTraceContext.height(), size);
	}
}

Then create a rayTrace task for each section.

DivideAndConquerRayTracer

class: DivideAndConquerRayTracer.java Java.png
methods: constructor
thresholdPredicate
rayTraceKernel
package: raytrace.exercise
source folder: student/src/main/java

constructor

method: public DivideAndConquerRayTracer(BiPredicate<Integer, Integer> thresholdPredicate) Sequential.svg (sequential implementation only)

Hang onto the thresholdPredicate in an instance variable. You will need it.

thresholdPredicate determines the threshold for division. If thresholdPredicate.test() is true, then the section is still large enough for more division of work.

thresholdPredicate

method: public BiPredicate<Integer, Integer> thresholdPredicate() Sequential.svg (sequential implementation only)

Return the thresholdPredicate you stored in an instance variable.

rayTraceKernel

method: private void rayTraceKernel(RayTraceContext context, Scheduler scheduler, int xMin, int yMin, int xMax, int yMax) Parallel.svg (parallel implementation required)

Use the threshold predicate to know whether or not to continue dividing, or to just render the current rectange. ThresholdPredicate now takes two parameters, which are the height and width of the rectangle.

rayTrace

provided:

	@Override
	public void rayTrace(RayTraceContext context, Scheduler scheduler) {
		rayTraceKernel(context, scheduler, 0, 0, context.width(), context.height());
	}

Checking Your Solution

Visualization

class: RayTracerViz.java VIZ
package: raytrace.viz
source folder: student/src/main/java

Correctness

class: _ParallelRayTracerTestSuite.java Junit.png
package: raytrace.exercise
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: parallel-raytracer-pledge-acknowledgments-citations.txt

More info about the Honor Pledge