Evenly Distributed Depth is the Worst for Distributed Snooping
Report ID: TR-427-93Author: Cox, Michael / Hanrahan, Pat
Date: 1993-06-00
Pages: 4
Download Formats: |Postscript|
Abstract:
In the purely object-parallel approach to multiprocessor rendering, each processor is assigned responsibility to render a subset of the graphics database. When rendering is complete, pixels from the processors must be merged and globally z-buffered. On an arbitrary multiprocessor interconnection network, the straightforward algorithm for pixel merging requires $ar{d} A$ total network bandwidth per frame, where $ar{d}$ is the depth complexity of the scene and $A$ is the area of the screen or window. In another paper we have presented a {em distributed snooping algorithm} for pixel merging that requires $log(ar{d}) A$ expected network bandwidth per frame. In that paper, to simplify the analysis we required the assumption that depth is ``evenly'' distributed over the screen, and we claimed that this assumption represented a worst-case for expected traffic. In the current paper we prove this claim.