Parallel Computing Programming Assignment: Ray Tracing with MPI and OpenMP

By doing this assignment, you will learn how to build a ray-tracer with MPI and OpenMP.Please read the research paper regarding Parallel Ray Tracing using MPI or OpenMP before starting this assignment.

1. Refer to the legacy code in “simple-ray-tracing”, please write your own program of a ray-tracer which is running in with serial algorithm (not parallel algorithm).

2. Now you have your non-parallel ray-tracer built. You need to change to make your ray-tracer program running in parallel by using either MPI or OpenMP. You can choose to use either MPI for distributed system or OpenMP for multi-core shared memory systems. (Please note: only one type of parallel ray-tracer is required to implement, rather than both of them.)

3. To calculate the running time of a task by using your serial ray-tracer and then by using your parallel ray-tracer. The calculation of running time needs to use the algorithm mentioned in the paper [1] section 3.2 - “Time Complexity”.

In this paper we present an implementation of parallel raytracing in both distributed memory and shared memory systems using MPI and OpenMP respectively. We have developed an object oriented solution using C++ and performed experiments in both the platforms. We present the performance model analysis with memory and time complexity analyses. Experimental results show that the implemented static load balancing technique achieves linear speedup and near optimal efficiency in both the cases. We also present a comparison among different load-balance scheduling schemes in OpenMP. 

Ray tracing is a technique of developing an image from a 3D scene by tracing the trajectories of light rays through pixels in a view plane. This technique is well known for its capacity of producing a very high degree of photorealism, which is a clear advantage over the industry standard raster graphics techniques. Although ray tracing is popular for its quality to generate photo-realistic images, for its expensive computational cost it is only applied where the image can be rendered slowly ahead of time. The computer graphics animation in the modern films is an example of such industries. In industries like computer games, where realtime image rendering is a precondition, ray tracing remained prohibitive and the raster graphics techniques were dominating. Possibilities of applications of ray tracing in streamline industries where real-time or fast image generation is necessary were faint until recently. In the recent years the advancement of high performance computing and combinatorial algorithms enabled processing of large amount of computational tasks in a much smaller time. As a consequence ray tracing became potential to be applicable in interactive visualizations.

Case Study

In the recent years increased use of multi-core shared memory and distributed systems, availability of increased computing performance and cost reduction in high performance hardware make the ray-tracing potential to be used in the industry applications. The topic received overwhelming researches and developments interest in the high performance computing (HPC) and computer graphics industries. Hurley’s article “Ray Tracing Goes Mainstream” in Intel’s technical journal in 2005, c.f. [4], advocates that the performance of ray-tracing reached the stage where it is feasible that it will take over from raster graphics in a near future for interactive gaming and other applications. As a consequence of such discussions, in 2007 [12], Shirley et. al. predicted, based on their expertise in computer graphics and computer architecture, that interactive ray tracing would become more prominent in the near future. This is a very active research field in the current world.

Although the computational expensive nature kept ray tracing less-interesting for real-time and interactive visualization and for applications where fast image generation is necessary, many researchers and practitioners developed algorithms and systems for ray tracing. Specially ray tracing techniques became attractive to many ray tracing enthusiasts and they employed hours to days of computer processing power to produce a single image. Examples are available in “the Internet Raytracing Competition”, an internet based competition of ray traced photo-realistic image generation.

We have implemented an object oriented parallel ray tracer using C++ that can be compiled to run either sequentially or in parallel mode using MPI or OpenMP. 4 Fig. 3. Processors (or threads) wise work distribution Load balancing schemes are implemented and also “load matrix” can be prepared for the viewport pixels which allows analysis of load distribution and optimal load balancing for certain scene. These features is decided on compile time based on the defined parameters. In the current implementation only sphere shaped objects are supported.

However, new shape classes can be implemented. Random scene can be generated with given number of objects, light and boundaries of the 3D boxes where the objects and lights can be placed. The scene configurations can be saved in XML file format to be loaded at a later time to use the same configurations for experimentation. This allows to generate scene with different load distributions and can be effective for experimental purposes. The program takes three parameters where first two are input config file name, image output file name.

The last one is optional that take the configuration saving file name. The input file is read by all the processes (for MPI) or by the master thread (for OpenMP). The rendering work is done in parallel where each process (or thread) render only the segments allocated to them. The rendered image is collected to master process using recursive doubling method or the MPI collective communication function ‘MPI Gather’ in case of running with MPI. The image file is saved in TGA file format. The image scene is segmented among the processes (or threads) in similar size while running the program with no load balancing.

The segmentation is done in height order. In case of using implemented load balancing, each process (or thread) starts processing the row with the same process (or thread) rank and incremented by number of the processes (or threads) until reach the image height. Figure 3 shows data distribution for both the cases. Three color values (R, G, B) are stored for each rendered pixels. We have implemented load measurement options that can be enabled with compiled time parameter. Workload have been calculated with the numbers of floating point operations performed in each pixel and stored in the image size matrix.