Evenly Distributed Depth is the Worst for Distributed Snooping

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.