Introduction:Environment Required:Provided Files:Ray Tracer Info:MPI Info:Partitioning Info:Write up:Grading:Additional Resources:EECC 756: Spring 2008Assignment #2Due: 5/13/2008Professor: Dr. ShaabanTA: John OlenderLast Modified: 04/24/08Start 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 ShadingThere 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 queueTo 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/756-pub/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 toshow 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/756-pub/2008_files/assign2/include/Next, build your executable by passing in the supplied object files.mpicc -O2 -Wall -o YourProgram YourProgram.o /export/home/756-pub/2008_files/assign2/*.o -lglut -lGL -lGLU -lmI 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 anduses 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