Parallel Processing and Computer Graphics: (Research Monographs in Parellel & Distributed Computing S.)

The distributed memory multiprocessor is currently viewed as perhaps the most practical means of achieving large-scale parallelism from general purpose computer systems. The construction of powerful multiprocessors has been facilitiated by the arrival of VLSI devices, attractive for their low cost per processor, and the ease with which networks may be expanded. One major use of computing resources which lends itself well to the application of parallel processing is in computer graphics. Of all the computer graphics techniques, those which are used for the synthesis of photo-realistic images are the most computationally demanding. One such technique, called ray tracing, is well suited for executing on distributed memory multiprocessor systems. The widespread use of distributed memory multiprocessors has been slow to appear, the most significant reason for this being that they are believed by many to be inherently difficult to program. This book considers carefully the design of a multiprocessor solution for the ray tracing problem. Particular emphasis is placed upon establishing a general purpose approach, so that the techniques developed may be applied to other problems. The areas of difficulty of programming distributed memory multiprocessors are identified in the hope that they may be set apart from the functions of a ray tracing program, with the intention of simplifying the role of the application programmer. The design of a multiprocessor solution for ray tracing is shown to revolve around two distinct functions, namely task management (allocation of processing to processors) and data management (distribution of data amongst the processors). A close marriage between the schemes for these management functions is necessary to enable an efficient implementation. Techniques are described for each of these functions and experimental results are presented using a set of standard graphics environments.

Table of Contents:
Part 1 Introduction to computer graphics: the ultimate display; illumination models; visible surface algorithms; ray tracing - ray-surface intersection, acceleration techniques, enhanced ray tracing. Part 2 Parallel processing and computer graphics: introduction to parallel processing - classifications of parallel computers, the SISD computer organization, the SIMD computer organization, the MIMD computer organization, the Inmos transputer, the transputer instruction set, programming the transputer; parallel processing for graphics - polygon serial systems, the geometry system, the 8 x 8 display, pixel planes, pixel serial systems, the zone management processor system; parallel processing for realistic image systhesis - general purpose vector processors, general purpose multi-computers, special purpose hardware, general purpose multiprocessors. Part 3 Design of a multiprocessor solution for ray tracing: motivations - a custom solution, a general solution, a compromise solution; previous solutions - object space subdivision, image space subdivision; a taxonomy of concurrent solutions for ray tracing - conceptual architecture, design of concurrent systems, the processor farm, an alternative solution, interconnection topology, process models, communication protocols, intra-worker communications, inter worker communication, implementation, programming interface, an analogy with the Linda paradigm, goals of Linda, programming with Linda, ray tracing with Linda, discussion. Part 4 Task management: standard graphics environments; metrics for processor load; load distribution; task granularity; load balancing strategies - no load balancing, static load balancing, dynamic load balancing; algorithms for task management - algorithm 1-task buffers, algorithm 2-distributed work stacks, a model performance; performance enhancements. Part 5 Dynamic data management: coherence - coherence in ray tracing, data coherence; caching techniques - placement policies, replacement policies, implementation in software; evaluation of caching techniques - effects of cache size and data coherence, performance estimation, effects of caching techniques; characteristics of a direct mapped cache; voxel addressing schemes; cache partioning; performance evaluation for the SPD models; variable-sized cache positions. (Part contents)