EECC 756 Spring 2008 Assignment 2 Due 5 13 2008 Professor Dr Shaaban TA John Olender Last Modified 04 24 08 Start working on this assignment early It will require significantly more thought and implementation effort than the previous assignment Introduction In this assignment you will be parallelizing a ray tracer using both static and dynamic partitioning Ray tracing is considered an excellent candidate for parallelization as each ray may be fired and computed independently of one another There can easily be millions of pixels to render in a given image each requiring its own ray tracing results This means there is a significant amount of work nearly all which may be be done in parallel A Ray Traced Scene with Procedural Shading There is one notable catch with ray tracing In ray tracing the transport of light in a scene is calculated recursively by tracing the path of the light backwards from the camera This recursive tracing is allows reflection and refraction to accounted for when rendering the scene However this recursive part of the algorithm leads to a fairly unpredictable execution time per ray especially in scenes where there are many reflective or transparent surfaces Your task in this assignment is to implement each of the following partitioning schemes determine which gives the best performance increase over a sequential version of the program and explain why each performed as they did Static partitioning strips of rows Static partitioning block Static partitioning cyclical assignment of rows Dynamic partitioning centralized task queue To test each of these algorithms two scenes will be given to render One will be a sparse scene in which there are few geometries to interact with The other scene will be one which is significantly more dense and evenly distributed over the scene Additionally you will be testing to see which task grain size fares best in the dynamic partitioning implementation Environment Required This assignment requires the use of an X11 Server in conjunction with the standard SSH connection to the cluster For more information and links to download a free X server for Windows please visit the course website SSH page To verify that your SSH client is properly forwarding X11 data to your local X server run the command glxgears while logged into the cluster head node If you are able to see an X window with gears rotating on the screen your environment is properly set up to view the assignment Depending on demand from the class and availability of the TA an image export function may be added to allow display of output when an X server supporting OpenGL is not available Provided Files All files that are supplied for this assignment are located in the export home 756pub 2008 assignment2 directory The files provided include header files to access the ray tracing API object files for linking your program with and a sample sequential implementation of the ray tracer In the sample implementation a master MPI process performs all rendering of the scene It is provided to show how to interact with the GLUT windowing system and provides an example of the necessary calls to have your program exit cleanly To build your program first build an object file using the following command mpicc O2 Wall c o YourProgram o YourProgram c I export home 756pub 2008 files assign2 include Next build your executable by passing in the supplied object files mpicc O2 Wall o YourProgram YourProgram o export home 756pub 2008 files assign2 o lglut lGL lGLU lm I recommend practicing this process using the sample code provided and running the resulting executable before going further with the assignment It will ensure that you have all the files you need for proper compilation as well as verifying that your development environment is set up correctly It is also highly recommended to use a build script or makefile to automate the building of your programs Last it may be useful to make a symbolic link ln s to the assignment directory in order to cut down on the path lengths See the ln man page for more information on symbolic links Ray Tracer Info The ray tracing engine is provided to you in this assignment You are not required to know any of the internal logistics of the ray tracing algorithm except that its execution time can vary greatly depending on a particular part of the scene You will be provided with a set of header and object files which you will use when implementing your parallel solutions However the program was designed to require as little knowledge about the inner workings as possible Your implementations will use a few functions which have already implemented for the ray tracer A sequential version of the program will be provided to demonstrate some of the API calls that are responsible to have the ray tracer function properly This sequential program first generates a camera and a scene using simple function calls then fires rays at each pixel in the view window The rayTrace function is registered as a callback function with GLUT and is called whenever a paint request is made by the program such as a window resize corrupted window etc More in depth information about the ray tracing API will be provided is on the MPS course website MPI Info When implementing your parallel renderer in MPI there are a few things that you need to know about the windowing system that the underlying ray tracer code uses The program is written in C and uses the OpenGL Utility Toolkit GLUT a simple windowing system for OpenGL programs It achieves most of its functionality by using callback routines requiring a different approach to MPI programming than normal The master process is in charge of both showing a GLUT window to show the results of the ray tracer as well as coordinating and collecting information from the slave processes Thus the master process is required to implement the rayTrace callback function In addition the master process is responsible for making a call to rtuiMain which will give control of the execution of the program to GLUT It is important to realize that the master process will be called by GLUT when a repainting of the window is needed requiring your program s design to be slightly different than regular MPI program Since GLUT takes control of the master process s execution of the program MPI Finalize cannot be called during the normal execution of the program It is necessary to register a function to be called before the program exits which preforms the necessary cleanup for