Back to Search
Start Over
Revisiting the combining synchronization technique
- Source :
- PPOPP
- Publication Year :
- 2012
- Publisher :
- Association for Computing Machinery (ACM), 2012.
-
Abstract
- Fine-grain thread synchronization has been proved, in several cases, to be outperformed by efficient implementations of the combining technique where a single thread, called the combiner , holding a coarse-grain lock, serves, in addition to its own synchronization request, active requests announced by other threads while they are waiting by performing some form of spinning. Efficient implementations of this technique significantly reduce the cost of synchronization, so in many cases they exhibit much better performance than the most efficient finely synchronized algorithms. In this paper, we revisit the combining technique with the goal to discover where its real performance power resides and whether or how ensuring some desired properties (e.g., fairness in serving requests) would impact performance. We do so by presenting two new implementations of this technique; the first (CC-Synch) addresses systems that support coherent caches, whereas the second (DSM-Synch) works better in cacheless NUMA machines. In comparison to previous such implementations, the new implementations (1) provide bounds on the number of remote memory references (RMRs) that they perform, (2) support a stronger notion of fairness, and (3) use simpler and less basic primitives than previous approaches. In all our experiments, the new implementations outperform by far all previous state-of-the-art combining-based and fine-grain synchronization algorithms. Our experimental analysis sheds light to the questions we aimed to answer. Several modern multi-core systems organize the cores into clusters and provide fast communication within the same cluster and much slower communication across clusters. We present an hierarchical version of CC-Synch, called H-Synch which exploits the hierarchical communication nature of such systems to achieve better performance. Experiments show that H-Synch significantly outper forms previous state-of-the-art hierarchical approaches. We provide new implementations of common shared data structures (like stacks and queues) based on CC-Synch, DSM-Synch and H-Synch. Our experiments show that these implementations outperform by far all previous (fine-grain or combined-based) implementations of shared stacks and queues.
- Subjects :
- Computer science
Concurrent data structure
Distributed computing
020206 networking & telecommunications
020207 software engineering
Thread (computing)
Parallel computing
02 engineering and technology
Data structure
Computer Graphics and Computer-Aided Design
Lock (computer science)
Synchronization
Synchronization (computer science)
0202 electrical engineering, electronic engineering, information engineering
Implementation
Queue
Software
Subjects
Details
- ISSN :
- 15581160 and 03621340
- Volume :
- 47
- Database :
- OpenAIRE
- Journal :
- ACM SIGPLAN Notices
- Accession number :
- edsair.doi.dedup.....d8673aab261fcd69a7308d1fbe4cc4ba