Loading...
Please wait, while we are loading the content...
Similar Documents
Diffracting Trees (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Shavit, Nir Zemach, T. Asaph |
| Abstract | Shared counters are among the most basic coordination structures in multiprocessor computation, with applications ranging from barrier synchronization to concurrent-data-structure design. This paper introduces diffracting trees, novel distributed-parallel structures for shared counting and load balancing. 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 machine and several simulated message passing architectures, shows that diffracting trees scale better and are more robust then both combining trees and counting networks, currently the most effective known methods for implementing concurrent counters. Diffracting trees have already been used to implement highly efficient producer /consumer queues, and we believ... |
| File Format | |
| Volume Number | 14 |
| Journal | ACM Transactions on Computer Systems |
| Language | English |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Randomized Coordination Method Efficient Producer Consumer Queue Several Simulated Message Passing Architecture Resiliency Drawback Multiprocessor Computation Logarithmic Depth Counter Basic Coordination Structure Simulated Distributed Shared-memory Machine Empirical Evidence Concurrent Counter Combinatorial Data Structure Novel Distributed-parallel Structure Concurrent-data-structure Design Load Balancing |
| Content Type | Text |
| Resource Type | Article |
