diffracting trees (preliminary version)
Shared counters are among the most basic coordination structures in multiprocessor computation, with applications ranging from barrier synchronization to dynamic load balancing. Introduced in this paper are diffracting trees , novel distributed-parallel data structures for shared counting. Diffracting trees combine a randomized coordination method together with a combinatorial data structure, to yield a logarithmic depth counter that improves on the log 2 depth of counting networks, and overcomes the resiliency drawbacks of combining trees. Empirical evidence collected on a simulated distributed shared-memory multiprocessor shows that diffracting trees substantially outperform both combining trees and counting networks, currently the most effective known methods for shared counting. Not only do diffracting trees have higher throughput and lower latency, but unlike any known technique, their latency remains almost constant as the number of processors increases.
trees version sharing coordination multiprocessor processor computation applications barrier synchronization dynamic load balancing paper distributed data structures combinational randomization method yield network resilience evidence simulation effect throughput latency distributed shared memory parallel