SEMINAR

DEPARTMENT OF COMPUTER ENGINEERING

ABSTRACT

Berkant Barla Cambazoglu

M.S. in Computer Engineering

Supervisor: Assoc. Prof.Dr. Cevdet Aykanat

January 31, 2000

A Hypergraph-Partitioning Based Remapping Model for Image-Space Parallel Volume Rendering

Ray-casting is a popular direct volume rendering technique, used to explore the content of 3D data. Altough this technique is capable of producing high quality visualizations, its slowness prevents the interactive use. The major method to overcome this speed limitation is the parallelization. In this work, we investigate the image-space parallelization of ray-casting for distributed memory architectures. The most important issues in image-space parallelization are load balancing and minimization of the data redistribution overhead introduced at successive visualization instances. Load balancing in volume rendering requires the estimation of screen work load correctly. For this purpose, we tested three different load assignment schemes. Since the data used in this work is made up of unstructured tetrahedral grids, for efficiency purposes, clusters of data is used instead of individual cells. Two different cluster-processor distribution schemes are employed to see the effects of initial data distribution. The major contribution of the thesis comes at the hypergraph partitioning model proposed as a solution to the remapping problem. For this purpose, existing hypergraph partitioning tool PATOH is modified and used as a one-phase remapping tool. The model is tested on a Parsytec CC system, and satisfactory results are obtained. Compared to the two-phase jagged partitioning model, our work incures less preprocessing overhead. At comparable load imbalance values, our hypergraph partitioning model requires 25% less total volume of communication than jagged partitioning, on the average.

Keywords: image-space parallelization, ray-casting, unstructured grids, work load assignment, hypergraph partitioning, load balancing, remapping.

The Seminar will be on January 31, 2000, at 14:00

in EA502