carter@IASTATE.EDU (Carter Michael Brannon) (03/10/91)
> Nicholas Wilt (npw@eleazar.dartmouth.edu) writes: > NW:I have seen netters allude to two competing techniques of parallel ray > NW:tracing. Both seem to be targeted for groups of networked machines. > NW:The scheme you propose requires machines to communicate during > NW:computation; this is very different from telling each Sun on a network > NW:"You do this part" and splicing together their results. Your proposal > NW:is very feasible for massively parallel machines which have special > NW:hardware for interprocessor communication, but even a high-speed network > NW:may not have enough bandwidth to make your scheme feasible on a group > NW:of networked machines. Finally a discussion I can take part in! This was my Masters work; I did a ray-tracer on an Intel iPSC/2 hypercube. While my main thrust was to come up with a way to trace very large numbers of objects on a hypercube, a lot of what I learned applies here too. The main thing I found out was that each node of the 'cube really only needed about 15% of the object database to maintain an object database "hit rate" of over 90%. This did not seem to to vary much in the range from 50 objects to 16K objects. My guess is that this same scheme can be employed on a distributed system of workstations. Here's why: - After an initial orgy of misses, each node settles down to a low rate of message activity. The image should be decomposed into small blocks, and a given processor should RT blocks that are "close" to one another on the image. This keeps the hit rate high on all nodes. - Even when a node misses the database, it only needs small amounts of information at a time. Although this wasn't a consideration on the hypercube, it will benefit things greatly on a network! Simply saying, "This workstation will only intersect with these objects" seems too harsh. If you divide the ODB into n pieces, then you should expect no more than an improvement of log(n) time! (Because of the tree-structured nature of the ODB) Not what I would call a good use of n processors. You ALSO have to check multiple intersection against one another and sort them in order of increasing intersection distance. This is something that the Kay algorithm does for you, so why throw it away? If memory is truly not a consideration on workstations (which is questionable), then just duplicate the ODB across all machines. If you have to break the ODB up for whatever reason, you're better off putting a little more work into a more complex data- and control-decomposition. A distributed system really mucks up the otherwise simple ray-tracing algorithm, but such is the cost of loosely- coupled multicomputers! -- Michael B. Carter Scalable Computing Laboratory Ames Laboratory Iowa State University carter@iastate.edu