Access Restriction

Author Aspnes, James ♦ Herlihy, Maurice ♦ Shavit, Nir
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Counting networks ♦ Hot-sports ♦ Network routing ♦ Parallel processing
Abstract Many fundamental multi-processor coordination problems can be expressed as counting problems: Processes must cooperate to assign successive values from a given range, such as addresses in memory or destinations on an interconnection network. Conventional solutions to these problems perform poorly because of synchronization bottlenecks and high memory contention.Motivated by observations on the behavior of sorting networks, we offer a new approach to solving such problems, by introducing counting networks, a new class of networks that can be used to count. We give two counting network constructions, one of depth log $\textit{n}(1$ + log $\textit{n})/2$ using $\textit{n}$ log $\textit{}(1$ + log $\textit{n})/4$ “gates,” and a second of depth log2 $\textit{n}$ using $\textit{n}$ log2 $\textit{n}/2$ gates. These networks avoid the sequential bottlenecks inherent to earlier solutions and substantially lower the memory contention.Finally, to show that counting networks are not merely mathematical creatures, we provide experimental evidence that they outperform conventional synchronization techniques under a variety of circumstances.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1994-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 41
Issue Number 5
Page Count 29
Starting Page 1020
Ending Page 1048

Open content in new tab

   Open content in new tab
Source: ACM Digital Library