Narrow Results

Communication penalty for parallel computation is related to message startup time and speed of data transmission between the host and processing elements (PEs). We propose two algorithms in this paper to show that the first factor can be alleviated by reducing the number of messages and the second by making the host-PE communication concurrent with computation on the PE array.

The algorithms perform 2ⁿ consecutive sums of 2ⁿ numbers each on a hypercube of degree n. The first algorithm leaves one sum on each processor. It takes n steps to complete the sums and reduces the number of messages generated by a PE from 2ⁿ to n. The second algorithm sends all the sums back to the host as the sums are generated one by one. It takes 2ⁿ+n−1 steps to complete the sums in a pipeline so that one sum is completed every step after the initial (n−1) steps.

We apply our second algorithm to the front-to-back composition for ray casting. For large number of rays, the efficiency and speedup of our algorithm are close to theoretically optimal values.

In the Constructive Solid Geometry (CSG) representation a geometric object is described as the hierarchical combination of a number of primitive shapes using the operations union, intersection, subtraction, and exclusive-union. This hierarchical description defines an expression tree, T, called the CSG tree, with leaves associated with primitive shapes, internal nodes associated with operations, and whose "value" is the geometric object. Evaluation of CSG trees is an important computation that arises in many rendering and analysis problems for geometric models, with ray shooting (also known as "ray casting") being one of the most important. Given any CSG tree T, which may be unbalanced, we show how to convert T into a functionally-equivalent binary tree, D, that is balanced. We demonstrate the utility of this conversion by showing how it can be used to improve the worst-case running time for ray shooting against a CSG model from O(n²) to O(n log n), which is optimal. In addition, the practicality of our method has been demonstrated in experimental benchmarking tests using the BRL-CAD package.