A Hierarchical CLH Queue Lock.
In: Euro-Par 2006 Parallel Processing (9783540377832); 2006, p801-810, 10p
Buch
Zugriff:
Modern multiprocessor architectures such as CC-NUMA machines or CMPs have nonuniform communication architectures that render programs sensitive to memory access locality. A recent paper by Radović and Hagersten shows that performance gains can be obtained by developing general-purpose mutual-exclusion locks that encourage threads with high mutual memory locality to acquire the lock consecutively, thus reducing the overall cost due to cache misses. Radović and Hagersten present the first such hierarchical locks. Unfortunately, their locks are backoff locks, which are known to incur higher cache miss rates than queue-based locks, suffer from various fundamental fairness issues, and are hard to tune so as to maximize locality of lock accesses. Extending queue-locking algorithms to be hierarchical requires that requests from threads with high mutual memory locality be consecutive in the queue. Until now, it was not clear that one could design such locks because collecting requests locally and moving them into a global queue seemingly requires a level of coordination whose cost would defeat the very purpose of hierarchical locking. This paper presents a hierarchical version of the Craig, Landin, and Hagersten CLH queue lock, which we call the HCLH queue lock. In this algorithm, threads build implicit local queues of waiting threads, splicing them into a global queue at the cost of only a single CAS operation. In a set of microbenchmarks run on a large scale multiprocessor machine and a state-of-the-art multi-threaded multi-core chip, the HLCH algorithm exhibits better performance and significantly better fairness than the hierarchical backoff locks of Radović and Hagersten. [ABSTRACT FROM AUTHOR]
Copyright of Euro-Par 2006 Parallel Processing (9783540377832) is the property of Springer eBooks and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Titel: |
A Hierarchical CLH Queue Lock.
|
---|---|
Autor/in / Beteiligte Person: | Luchangco, Victor ; Nussbaum, Dan ; Shavit, Nir ; Nagel, Wolfgang E. ; Walter, Wolfgang V. ; Lehner, Wolfgang |
Quelle: | Euro-Par 2006 Parallel Processing (9783540377832); 2006, p801-810, 10p |
Veröffentlichung: | 2006 |
Medientyp: | Buch |
ISBN: | 978-3-540-37783-2 (print) |
DOI: | 10.1007/11823285_84 |
Sonstiges: |
|