Loading...
Please wait, while we are loading the content...
Similar Documents
A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems (2001)
| Content Provider | CiteSeerX |
|---|---|
| Author | Zhang, Yi Tsigas, Philippas |
| Description | Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures |
| Abstract | A non-blocking FIFO queue algorithm for multiprocessor shared memory systems is presented in this paper. The algorithm is very simple, fast and scales very well in both symmetric and non-symmetric multiprocessor shared memory systems. Experiments on a 64-node SUN Enterprise 10000 -- a symmetric multiprocessor system -- and on a 64-node SGI Origin 2000 -- a cache coherent non uniform memory access multiprocessor system -- indicate that our algorithm considerably outperforms the best of the known alternatives in both multiprocessors in any level of multiprogramming. This work introduces two new, simple algorithmic mechanisms. The first lowers the contention to key variables used by the concurrent enqueue and/or dequeue operations which consequently results in the good performance of the algorithm, the second deals with the pointer recycling problem, an inconsistency problem that all non-blocking algorithms based on the compare-and-swap synchronisation primitive have to address. In our construction we selected to use compare-and-swap since compare-and-swap is an atomic primitive that scales well under contention and either is supported by modern multiprocessors or can be implemented efficiently on them. |
| File Format | |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Non-blocking Algorithm Scalable Non-blocking Concurrent Fifo Queue Inconsistency Problem Modern Multiprocessor Atomic Primitive Memory System Known Alternative Symmetric Multiprocessor System Concurrent Enqueue 64-node Sun Enterprise Simple Algorithmic Mechanism Compare-and-swap Synchronisation Primitive Shared Memory Multiprocessor System Second Deal 64-node Sgi Origin Non-symmetric Multiprocessor Non-blocking Fifo Queue Algorithm |
| Content Type | Text |
| Resource Type | Proceeding |
