M.Sc Thesis

M.Sc StudentSapir Tali
SubjectParallel Raytracing Using the XMT Paradigm
DepartmentDepartment of Computer Science
Supervisors PROF. Chaim Craig Gotsman
PROF. Uzi Vishkin


XMT is a parallel computation model, which advocates the use of parallel algorithms for a shared memory multiple-processors-on-a-chip architecture. Such an architecture will be possible and worthwhile in the billion-transistor era. The goal of this research is to parallelize the computer graphics raytracing application in the XMT framework, and investigate the performance achievable using a simple simulator. This should motivate developers and manufacturers to adopt XMT.

   The XMT model provides: 1) a convenient and intuitive means for parallel programming, using PRAM style algorithms and automatic dynamic load balancing 2) Support for fine-grained parallelism (using low-overhead threads) in contrast with the coarse-grained parallelism usually offered. 3) Greater resource utilization, which compensates for the delay engendered by shared memory.

   Raytracing is an algorithm designed to render photorealistic images in computer graphics. The algorithm models shadows, reflectivity and transparency. In order to create a reasonable sized image, thousands and millions of rays are needed and the runtime can be very long. Raytracing lends itself naturally to parallelism, and especially for fine-grained parallelism as required by the XMT framework. Each ray may be processed by a single thread.

   Our results show meaningful speedups for raytracing in XMT, which scale well to higher degrees of parallelism