Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Scalable concurrent counting
Herlihy M., Lim B., Shavit N. ACM Transactions on Computer Systems13 (4):343-364,1995.Type:Article
Date Reviewed: Aug 1 1996

A number of coordination problems encountered in multiprocessing systems require a counter, that is, an object holding an integer value that can be fetched and incremented as an atomic operation. It is difficult to design counting techniques for which the counter’s throughput increases as concurrency increases. Herlihy, Lim, and Shavit present several algorithms for concurrent counting and report some experiments on their efficiency.

The algorithms they studied are lock-based counters, message-based counters, queue-based counters, combining trees, and counting networks. Lock-based and message-based counters work in the obvious way: a process either acquires a lock in order to increment the counter or sends a message to the processor that is the proprietor of the lock. A queue-based counter allows a set of processes to wait on a locked queue, with the counter value held by the processor that currently holds the lock. If no processes are waiting, the counter value is stored in the lock itself. A combining tree combines requests that enter at a leaf of the tree simultaneously, with one process advancing up the tree while the other waits for the result. A counting network is a highly concurrent data structure that resembles a sorting network.

The algorithms were tested using a simulator of the MIT Alewife multiprocessor, a cache-coherent, distributed-memory multiprocessor that supports the shared-memory programming abstraction. For a small number of processors, the lock-based counter worked best because of its simplicity. As the number of processors increased, however, the best performers were the combining trees and the counting networks, because these methods provided both low contention and a high degree of parallelization. An experiment with a linearized counting network demonstrated that low contention by itself is not sufficient. The authors also found that the combining tree is more sensitive to the arrival rate of requests than the counting network, and that both of these methods are more efficient when implemented with message passing rather than with shared memory.

Reviewer:  P. Abrahams Review #: CR119719 (9608-0599)
Bookmark and Share
 
Multiprocessing/ Multiprogramming/ Multitasking (D.4.1 ... )
 
 
Concurrency (D.4.1 ... )
 
 
Multiple-Instruction-Stream, Multiple-Data-Stream Processors (MIMD) (C.1.2 ... )
 
 
Scheduling (D.4.1 ... )
 
 
Simulation (B.3.3 ... )
 
 
Trees (E.1 ... )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Multiprocessing/Multiprogramming/Multitasking": Date
Algorithms for scheduling homogeneous multiprocessor computers
Ondáš J., Springer-Verlag, London, UK, 1984. Type: Book (9789780387136578)
Aug 1 1985
Parallel programming
Perrott R., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987. Type: Book (9789780201142310)
Jul 1 1988
Operating systems: communicating with and controlling the computer
Keller L., Prentice-Hall, Inc., Upper Saddle River, NJ, 1988. Type: Book (9789780136380405)
Sep 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy