ABSTRACT

Shared counters are among the most basic coordination struc- tures in multiprocessor computation, with applications rang- ing from barrier synchronization to dynamic load balanc- ing. Introduced in this paper are diffracting trees, novel distributed-parallel data structures for shared counting. Diff- racting trees combine a randomized coordination method together with a combinatorial data structure, to yeild a log- arithmic depth counter that improves on the log2 depth of counting networks, and overcomes the resiliency draw- backs of combining trees. Empirical evidence collected on a simulated distributed shared-memory multiprocessor shows that diffracting trees substantially outperform both combin- ing 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.