jump to navigation

Three ways to Parallelize a Raytracer 8 July 2008

Posted by Matthew Fulmer in Uncategorized.
trackback

I’ve done a bit of reading on how to parallelize raytracing, especially given the memory constraints of the cell. There are three approaches I’ve discovered so far:

  1. Distribute the rays: Each node runs a full raytracer on the full scene, and processes a subset of the rays from start to finish
  2. Distribute the processing: One node handles ray creation, another ray intersection, another shading, another shadows. Every node needs access to different aspects of the entire scene.
  3. Distribute the scene: Each node handles every ray segment that intersects it’s slice of the scene.

For my purposes, I’m interested in two things:

  1. How well this will work on the Cell processor, where each node has only 256K of memory, and
  2. How well the approach maps to the E Concurrency model , which I also call the vat model, below.

Distribute the Rays

The first approach is unquestionably the best when the entire scene fits into local memory of each node, as it is pretty easy on network bandwidth. Using this approach, once the scene is availible to all nodes, the raytracing problem is embarassingly parallel: every ray shooting out of the camera can be processed with zero communication among the nodes. However, if the scene does not fit in memory, the node will have to fetch parts of it and cache them locally.

Distribute the Computation

The second approach is closest to what the Cell was meant to do: act as a stream processor. However, this does not scale up to any number of nodes, nor does it scale down; it requires each node to be developed as part of a stream. This is rather network-intensive; most rays will make at least one pass through every node.

Distribute the Scene

The third is the closest to how vats natively operate. Scenes are usually stored in a tree structure, with the root pointing to a number of children. In this scheme, Many of the child pointers in the tree would be local pointers, but some would be far refs; entire subtrees of the scene graph would be seperated from the root and reside in a seperate vat. This would be very easy to program for.

A raytracer would be started on the vat with the root node of the scene, and as the program progressed, it would send remote messages to the parts of the scene stored in other vats, distributing the computation as a side-effect of sending regular, asynchronous messages to various parts of the scene. This is network intensive; every ray passes through several slices of the scene, and it is also unfair; slices with a light will have to process nearly every ray, while slices in the corner may get only a handful of rays.

Advertisements

Comments»

1. Zekdapsegada - 2 August 2008

Thanks !

2. Bookmarks about Maps - 15 December 2008

[…] – bookmarked by 3 members originally found by benrasmusen on 2008-11-07 Three ways to Parallelize a Raytracer https://mtfulmer.wordpress.com/2008/07/08/three-ways-to-parallelize-a-raytracer/ – bookmarked by 4 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: