Parallel Ray Tracing in pH: An Exploration ofFunctional ProgrammingWes Beebee, Karin Cheung, and Jeffrey SheldonDecember 3, 19996.837 Final Project AbstractTraditionally, computer graphics development has relied on the use of imperative, sequentialprogramming languages, such as C or C++, to achieve the necessary computational efficiency. Thispaper explores the introduction of functional programming as a higher-level substitute for imperativelanguages, through the development of a ray tracer in pH. This implementation choice arises from pH’spurely functional infrustructure as well as its ability to execute in parallel. Furthermore, our ray tracingexperiment incorporates the challenges of performance optimization, as well as lessons learned in dataflow analysis and producer/comsumer relationships. Finally, detailed performance results were recordedin execution comparisons between two different compilers, GHC and pHC, as well as variousmulti-processor arrangements. IntroductionIn computer graphics research, much development of realistic graphics displays concentrates its effortson creating efficient surface-rendering techniques, specifically methods of visible-surface detection andillumination modeling. While numerous algorithms have been devised to approach this problem,developers commonly use ray casting and ray tracing procedures, where a ray is sent out from each pixelposition to locate surface intersections. This simple idea proves extremely effective in determiningvisible surfaces in a scene, obtaining global reflection and transmission effects, producing shadoweffects, incorporating transparency features, and considering multiple light-source illumination. Generally, computer graphics software, such as that of ray casting and ray tracing, focuses oncomputational efficiency. Therefore, implementations of these methods typically employ languages suchas C and C++, which function through state mutation, using a specified order of execution. Thistraditional method of programming, however, has several weaknesses. First, while the ability to mutatestate has its advantages, such intrusiveness allows possibilities of incorrectly modifying memorylocations, one of the most frequent problems in computer programming. Furthermore, the sequentialorder of execution restrains the speed of the software, by forcing the system to evaluate each instructionline by line. This sequential characteristic of languages like C, including Java, Pascal, and so on, isreferred to as being imperative. One can easily imagine a more abstract programming language that no longer permits modification ofthe machine state, such that the order in which instructions are executed no longer matters, except incertain data dependency situations. In fact, many research circles have developed an interest in creatingsuch a system, namely a functional language. Functional languages emphasize a clean design withminimal conceptual overhead, in the belief that issues of implementations and speed are best left to thecompiler. One such functional language, developed at the MIT Laboratory for Computer Science, is pH,a parallel dialect of the functional language Haskell. What exactly is a functional language? A functional language like pH is inherrently difference from animperative language such as C. A functional language is a single expression which is executed byevaluating that expression. The idea of functional programming is very similar to that of a spreadsheetprogram. In a spreadsheet, one specifies the value of each cell in terms of the value of the other cells.The focus is on what is to be computed, not how it is computed. We do not specify the order in which expressions are evaluated, but instead take for granted thatthey will be computed with respect to their dependencies We do not tell the program how to allocate memory, rather we expect the program will allocatememory as it is needed We specify a value by its expression, rather than a sequence of commands which calculates itsvalue For example, SQL, the standard database query language, is inherently functional. A query within SQLconsists of projections, joins, and selections, tools which allow the programmer to say what relationshould be computed without saying how it should be computed. This focus on a high level ‘what’without the low level ‘how’ is the crucial difference between a functional language and an imperativeone. In regard to rendering techniques, an experimentation of ray casting and ray tracing in pH allows a highlevel abstraction of the core rendering system that is purely functional. A lighting model, for instance,could be abstracted out of the care of the rendering engine, making it very simple to swap one lightingmodel for another. Furthermore, pH is a fully type-safe language, unlike C++, which holds promise inreducing debugging time and allowing static analysis to assist in program verification. Possiblerendering-efficiency benefits of pH will also be analyzed in this exploration. Since pH relies on thefunctional nature of the language and the lack of a sequential order of events, the compiler is free toanalyze data dependencies to determine opportunities for parallelism. Therefore, the remainder of the paper analyzes our experimentation in creating a ray tracer in pH. Afteran initial discussion of design motivations, this study will describe the design of the ray tracer, includinga description of the syntax definitions, the world representation, the ray tracer itself, and the actualpainting of pixels to the screen. Next, this exploration will review what aspects of using a functionallanguage made the system easier or more difficult to implement, as well as a proposal of why theseadvantages or limitations existed. Lastly, the paper will discuss the results of the final ray tracer, usingbenchmarking tests to evaluate the value of implementing a ray tracer in a parallel, functional languagesuch as pH. GoalsThis project seeks to introduce a new way of thinking about computer graphics, a method ofapplication-building that has the potential to revolutionize the way graphics software is developed today.In analyzing the current standards of application development, we have noted several shortcomings ofgraphics programming languages which are commonly used today in building applications like those wehave implemented in class, ray casting and ray tracing. The necessity of creating very fast, very efficientprograms in graphics has driven the field
View Full Document
Unlocking...