Raycasting is a DVR (Direct Volume Rendering) technique. DVR is a class of techniques for graphically visualizing 3D data. The data can be from any source as long is it is representable by discrete sample values at each point in a three dimensional grid. Common sources of such data include CT (Computed Tomography), MRI (Magnetic Resonance Imaging), and ultrasound scans. The data can come from simulation or direct measurement of physical phenomena. Direct volume rendering is by nature highly memory intensive. For example, a high resolution representation of a human female, The Visible Female dataset, is 36 gigabytes. A raycasting algorithm must typically visit each byte of this data to produce an image. A further challenge is to optimize DVR algorithms for data locality. Desktop workstations do not currently have the memory or compute power to visualize such large datasets quickly. Yet quick response to user requests for view changes are important to allow interactive exploration. We describe a software system, the MPIRE (Massively Parallel Interactive Rendering Environment), developed at SDSC (San Diego Supercomputer Center), which brings the power of a supercomputer to the desktop via the Web and allows interactive explorations of massive datasets. Currently MPIRE runs on two very different supercomputers; the Cray T3E and the MTA (Tera Multithreaded Architecture). We compare and contrast the architectures of these machines and characterize the porting effort and performance of MPIRE on each.

Complex physical phenomena are often best investigated by visual inspection. There is no substitute for seeing for ones-self the contours of the problem under scrutiny; whether it be the ocean floor, the human brain, or the reactive surface of a molecule. Today, computers aid in the work of science by turning masses of numbers into pictures on the screen. If view changes can be completed quickly, the scientist can interact with the data in real time, virtually skimming the ocean floor, slicing through a diseased organ or inspecting the shape of a protein docking site. However, when the dataset to be visualized is large, the practical challenge of turning data bytes into image pixels can be immense. Specifically, changing the view point and forming a new image of a multi-gigabyte dataset in under 10 seconds is beyond the current capabilities of most desktop system. Clearly, powerful supercomputers such as the Cray T3E and the MTA (Tera Multithread Architecture) [1, 5, 6] provide an alternative. But most researchers do not have a supercomputer sitting next to them. What they do have (in many cases) is a PC or workstation running Netscape with Java. Using SDSC's (San Diego Supercomputer Center's) MPIRE (Massively Parallel Interactive Rendering Environment) software [3], this is enough to deliver the power of the supercomputer to the desktop.

The MTA and the T3E embody very distinct approaches to supercomputing. The machines are different architecturally and this leads to different programming styles. The T3E reflects current mainstream thinking on how to build a supercomputer from commodity components. The MTA is an experimental machine which is constructed from custom components. At SDSC we are tasked with evaluating the Tera MTA approach. While we have studied the MTA's performance on a number of benchmarks and applications [2], this paper presents our first evaluation of a full user application on the MTA.

Below we give a quick overview of volume rendering in general and an intuitive explanation of the steps involved in raycasting [4]. We then describe the software architecture of MPIRE and go on to describe the porting process to the two supercomputers. Porting involves mapping an algorithm (an abstract recipe for performing a calculation) to an architecture (a physical realization of a machine.) One must have an understanding of both the architecture and the algorithm to obtain a high performance port. Lastly, since performance is the ultimate measure of supercomputers, we give performance measurements on both machines.

Volume rendering takes a (regular or irregular) 3D grid of datapoints and constructs a 2D regular grid of pixels called a raster. A pixel is a tuple of color and opacity, the resulting raster grid can be displayed by a computer screen as an image. Since volume rendering algorithms have to visit each datapoint to construct an accurate image, and since each pixel of the raster has to be colored in, it's easy to see that the runtime of the algorithm is:

where n is the dimension of the volume and p the dimension of the image (volume and image assumed symmetrical for simplicity of analysis). Raycasting is one of a class of algorithms that employ no intermediate polygon representation of the data but build up the values of the raster by direct reference to the dataset. This class of algorithms is termed DVR (Direct Volume Rendering). DVR algorithms are the choice for scientific visualization applications when the density of interesting features is high and the accuracy of representation is crucial.

The raycasting process is easily understood by analogy. Imagine an eye looking through a window at a 3D object. If the window were replaced by a perfect picture of the outside view, then the eye would be fooled into thinking that the picture was the actual object (see Figure 1).

Figure 1: Raycasting works by casting virtual rays through the data volume, one per pixel in the image plane. The volume is sampled at unit increments along the ray. These samples are combined to determine the color and opacity of the corresponding pixel.

Raycasting accomplishes this trick by breaking the window pane up into small squares (pixels) and tracking the path of a ray originating at the eye through each pixel and out to the object. Based on the substances in the object encountered by the ray, the algorithm assigns a color and opacity to the pixel. Note that the object is represented in the computer by a 3D array of datapoints. So, to come a step a closer to describing the actual algorithm , raycasting fills in an image plane by stepping through the volume, once for each pixel of the raster, in an order prescribed by the viewpoint. For each change in the orientation of the eye relative to the scene, a new calculation must be performed.

Researchers at the San Diego Supercomputer Center have developed a distributed direct volume rendering system which utilizes advances in high performance computing architecture, web programming, and information delivery. Called MPIRE, this system can render multi-gigabyte volume datasets at near-interactive rates and deliver the results to any desktop computer equipped with a web browser.

MPIRE consists of three components. One of these components is a set of software engines for performing the rendering calculations. The engines are based on highly parallel implementations of the splatting (called Splatter) and ray casting (Caster) direct volume rendering algorithms. MPIRE also includes software for performing resource allocation and engine execution on a supercomputer. Finally, MPIRE includes graphical interface panels for interactively controlling the rendering process on the remote supercomputer. Java applet and Application Visualization System (AVS) implementations of the MPIRE interface include buttons, sliders, and other controls for providing truly interactive exploration of the target dataset.

To the user, MPIRE is much like any other menu driven program. After loading a web page containing the MPIRE Java applet, the user configures the desired rendering parameters, target system, and number of processors. A MPIRE engine is then automatically started on the target system over the specified number of processors (if available), the data loaded, and an image created and sent back to the Java applet. The image is automatically updated by the engine as the user modifies the camera position, lighting, coloration, or any other rendering parameter.

This architecture provides accurate, dynamic rendering of multi-gigabyte volume data at rates unattainable by any other means. Researchers using MPIRE at SDSC have achieved rendering rates of 350 million voxels (volume elements) per second -- 9 seconds per image for a 9 gigabyte dataset of the Visible Male [7], using 256 CPUs of the Cray T3E there (see Figure 2).

An intuitive first pass at a parallel implementation of raycasting on a the T3E relies on the observation that each ray can be cast independently. One could imagine a processor assigned to each ray and all processors casting their rays at the same time. In reality there are many more pixels (and thus rays) than processors, so each processor must be tasked with casting a bundle of rays. Further, each processor has limited local memory (128 megabytes in our T3E configuration). It is not possible for each processor to have a private copy of the 36 gigabyte Visible Female [7] for example. But dividing the data across processors in this case suggests that each processor must access the volume data in memory on every other processor for each ray it casts. Doing so is inefficient given that remote memory references take longer than references to local memory. A different approach is to break each ray into sections. A processor can compute the section of the ray corresponding to the data it has. When all of the rays have been cast, each processor is left with a rendered image of just the partition of the data volume stored in its local memory. The corresponding pixels in the images on each processor must then be composited together in the order that they would have been accumulated had the rays not been broken into sections. Thus remote memory references are still required, but since the number of pixels in an image is generally much smaller than the number of samples in a volume, the amount of data that must be exchanged between processors is minimized.

At SC '98 in Orlando, we set a world record for sustained performance on a DVR type calculation over a multi-gigabyte dataset. Using MPIRE on 260 processors of the T3E at SDSC we rendered the Visible Female dataset at full resolution (36 gigabytes) and displayed the results in near-interactive time (~12s per frame) on an SGI workstation on the exhibit floor. This demonstration was our entry in the HPC Challenge competition; the judges awarded us `Most Revealing`.

Like the T3E, memory in the MTA is physically distributed and globally addressable. Unlike the T3E, the MTA has no local memory. All memory is remote from all processors. Our MTA configuration has 4 gigabytes of memory. Instead of each processor having its own memory and exchanging data via messages, all processors can write directly to all memory. One might wonder why other machines do not adapt this scheme since it is easier for the user to program. The answer lies in the complexity of making a single global memory from distributed memory modules. Also, a logically flat memory which is not local to any individual processor takes longer to access for all processors. The cleverness of the Tera MTA architecture is that it is designed to tolerate this long memory latency by finding other work for each processor to do while waiting.

Porting MPIRE to the MTA is simplicity itself. The raycasting loop looks like this:

SampleRay is a function that steps through the shaded volume (v) compositing color and opacity for each argument (R) of type ray. To convince the Tera compiler to multithread this double loop, it was simply necessary to attach the pragmas. No further source code modifications were required. The Tera compiler can often find parallel loops and multithread them without a pragma directive. However, in this case, the compiler was unsure of the side effects of SampleRay and was unwilling to automatically parallelize without a hint from the programmer. It is the simplicity of a flat memory programming model (no hierarchy in the form of cache or local memory) that makes it possible to program the MTA in this very straightforward style. Also, the simple programming model makes the compiler's job easier. There is no equivalent compiler for the T3E. One cannot take a program written for a single processor workstation and compile it to get a multiprocessor message passing program suitable for the T3E. The programmer must supply the effort to decompose the problem into pieces.

Further, recall that the T3E implementation of raycasting requires a pixel composition step due to the distribution of the volume data across the local memory of all processors. This step is unnecessary on the MTA. Each of the processors works on its own part of the image which resides in shared memory addressable by all processors.

The parallel executable resulting from the compile can be run on one or more MTA processors. Since each call to SampleRay corresponds to a thread and since there is hardware for 128 threads per processor, it only makes sense to use more that one processor if there are more than 128 calls to SampleRay. Because a typical image is 400 x 400 = 160K pixels (rays), there is plenty of parallel work in most render jobs to justify the use of multiple MTA processors.

Table 2 shows the time spent in the SampleRay loop and in compositing by the T3E. Recall that the MTA does not need to composite pixels. Comparing the two tables indicates that the MTA is outperforming the T3E by more than 4 to 1 per single processor. Since the clock speeds are roughly comparable, this may at first seem surprising. The reason lies in the memory access patterns of raycasting. A 3D volume partition in the local memory of a T3E node is actually stored as a linear array of addresses. When a ray is cast through the volume, the physical stride between array elements accessed depends on the incident angle of the ray. While some angles may luckily result in unit strides which correspond to the contiguous addresses of a cache line, most will not. Most of the time you will incur the penalty of a cache miss for every memory reference on the T3E. This is not a problem that can be solved by changing the order of data storage. The most efficient data storage order depends on the viewpoint. But the user may choose any viewpoint.

The MTA pays the same penalty per memory reference as the T3E since it has no cache. However, when one thread goes to memory, another thread steps in and issues an instruction. The processor-memory bandwidth of the MTA is 8 bytes per cycle. The T3E's is only 2 bytes per cycle when it misses cache. Raycasting is a massively parallel problem with poor data locality. The critical path for such a problem is processor-memory bandwidth. The ratio of single processor performance between these two architectures is proportional to their memory bandwidth. Further, the MTA processors are kept at a higher rate of utilization due to their ability to context switch between threads when one is waiting for memory.

The rapidly degenerating parallel efficiency of the T3E on this problem is an artifact of problem size. To allow comparison between the two machines we chose a size of problem suitable for 1-4 processors on either. The overhead of starting up the rendering loop on each processor would be better amortized for larger problems on the T3E. The MTA is less sensitive to problem size because its parallel model is very fine grained. Each processor does its fair share of thousands of rays. The T3E splits the volume into smaller pieces for more processors giving each processor less data. If this is carried too far, the overhead of loop startup and message passing becomes a large fraction of total runtime.

Note, that while the MTA is the likely winner for small and medium sized problems, the current configuration has 4 gigabytes of main memory vs. an aggregate total of more than 36 gigabytes on the T3E. This means that the T3E remains our machine of choice for truly large renders, at least until a larger MTA configuration becomes available.

Delivery of a 4 CPU MTA at SDSC came just prior to the deadline for submission to this conference. We hope, by the time of our presentation, to give the results of multi-gigabyte renders on both supercomputers.

MPIRE brings the power of supercomputers to the desktop, allowing researchers to visually explore large datasets interactively. The Tera MTA and Cray T3E are both excellent rendering engines. The Tera MTA has unique architectural features that give it some advantages on problems such as raycasting which, while parallel, exhibit poor data locality.

This work was supported in part by NSF award ASC-9613855 and DARPA contract DABT63-97-C-0028. The development of MPIRE was sponsored by CRI through the University Research and Development Grant Program.