Diffracting trees
Nir Shavit, Asaph Zemach · ACM Transactions on Computer Systems · 1996
Shared counters are among the most basic coordination structures in multiprocessor conputation, with applications ranging from barrier synchronization to concurrent-data-structure design. This article introduces diffracting trees, novel data structures for share counting and load balancing in a distributed/parallel environment. Empirical evidence, collected on a simulated distributed shared-memory machine and several simulated message-passing architectures, shows that diffracting trees scale better and are more robust than both combining trees and counting networks, currently the most effective known methods for implementing concurrent counters in software. The use of a randomized coordination method together with a combinatorial data structure overcomes the resiliency drawbacks of combining trees. Our simulations show that to handle the same load, diffracting trees and counting networks should have a similar widthw, yet the depth of a diffracting tree isO(logw), whereas counting networks have depthO(log2w). Diffracting trees have already been used to implement highly efficient producer/consumer queues, and we believe diffraction will prove to be an effective alternative paradigm to combining and queue-locking in the design of many concurrent data structures.
Cited by 118 works. doi:10.1145/235543.235546 Open-access PDF
Authors
References
- Optimization by Simulated Annealing
- Sorting networks and their applications
- Distributed Algorithms
- Wait-free synchronization
- MIPS RISC architecture
- Algorithms for scalable synchronization on shared-memory multiprocessors
- “Hot spot” contention and combining in multistage interconnection networks
- Hierarchical correctness proofs for distributed algorithms
- The MIT Alewife Machine: A Large-Scale Distributed-Memory Multiprocessor
- Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors