TL;DR
This paper presents a highly efficient and scalable parallel algorithm for volume rendering, achieving near real-time performance on a 128-processor CM-5. By adapting the state-of-the-art shear-warp algorithm with novel data partitioning and adaptive load balancing, they significantly reduce communication overhead and improve rendering speed, making interactive volume visualization more feasible.
What Problem Does This Paper Address?
Volume rendering is crucial for visualizing 3D data from sources like medical imaging. Generating a sequence of images for different orientations quickly is essential for interactive exploration, ideally in real-time. While the shear-warp algorithm is known for its speed, achieving real-time performance, especially for large datasets, requires significant speedups beyond what Moore's Law alone can provide. This necessitates parallel computing. However, parallelizing algorithms that exploit spatial coherence (like shear-warp) presents a challenge: optimizations that improve sequential performance can limit concurrency, while approaches that increase concurrency might be slower. This paper tackles the problem of achieving both speed and scalability in parallel volume rendering by efficiently parallelizing the shear-warp algorithm.
Methods
The core of this work is a parallel formulation of the shear-warp algorithm, building upon the sequential version by Lacroute and Levoy. Key innovations include:
- Sheared Volume Space Partitioning: Instead of simply slicing the volume, the data is first "sheared" and then partitioned. This aligns partitioning planes with the viewing rays, allowing intermediate images to be computed independently by each processor without requiring compositing across processor boundaries. This significantly reduces communication overhead, especially when the volume's orientation changes.
- Adaptive Load Balancing: The paper acknowledges that different scanlines can have vastly different computational loads due to optimizations like early termination and run-length encoding. To address this, they employ an adaptive load balancing scheme. This scheme uses load information from previous frames to predict future loads and dynamically reassigns scanlines to processors, ensuring a more even distribution of work.
- Memory Efficiency: The parallel formulation is designed to be memory efficient, aiming to keep the total memory usage across all processors similar to that of the sequential algorithm.
Datasets
The paper evaluates their parallel formulation on two datasets:
- "Brain" Dataset: A 256x256x167 voxel dataset derived from an MRI scan of a human brain. This is the "LARGE" dataset mentioned in the results.
- Subsampled "Brain" Dataset: A 128x128x84 voxel version of the "Brain" dataset. This is the "SMALL" dataset.
These datasets are standard for volume rendering research and are used to compare performance against existing work.
Key Insights and Ideas
- Shearing for Parallelism: The insight that shearing the volume data before partitioning can align processing units with the data flow, drastically reducing the need for inter-processor compositing and thus communication, is a major contribution.
- Adaptive Load Balancing is Crucial: The paper highlights that optimizations like early termination create significant load imbalances. A static partitioning of scanlines leads to poor performance. An adaptive approach, leveraging information from previous frames, is essential for maintaining efficiency as the number of processors increases.
- Scalability is Achievable: The results demonstrate that the shear-warp algorithm, when parallelized with these techniques, scales well to a large number of processors (up to 128 on the CM-5), suggesting that real-time performance for complex datasets is within reach.
- Near Real-Time Performance: Achieving per-frame times of 85 ms for a large dataset on a 128-processor CM-5 is a significant achievement, bringing interactive frame rates closer to reality.
Key Results
- Rendering Speed: The implementation achieved per-frame rendering times of 85 ms for the larger 256x256x167 voxel "brain" dataset on a 128-processor CM-5. This translates to approximately 12 frames per second.
- Scalability: The parallel formulation demonstrated consistent speedup up to 128 processors for the larger dataset, indicating good scalability.
- Load Balancing Impact: Load balancing reduced overall execution time by up to 16% in some cases, with the gains being dataset and processor-count dependent.
- Comparison to Prior Work: The reported rendering times are significantly better than many previously published results, often by an order of magnitude or more.
Limitations and Future Work
- Limitations:
- The paper notes that the experimental results were obtained without using the vector units on the CM-5 nodes, implying potential for even higher performance.
- The analysis for communication overhead in sheared volume partitioning makes a simplifying assumption that each processor is assigned an equal number of scanlines, which is relaxed by the load balancing discussion.
- The smaller dataset was not run with 128 processors due to insufficient parallelism.
- Future Work:
- Developing alternate formulations for even greater parallelism.
- Further reducing communication overhead by fetching voxel data only when required, rather than entire slices.
- Exploring the use of a distributed frame buffer to streamline the assembly of sub-images from different processors.
- Investigating performance on modern, faster hardware platforms and interconnects, and exploring different architectures (MPPs, workstation clusters, multiprocessors with DSPs).
Summary updated