An efficient counting network

Abstract

We present a novel counting network construction, where the number of input wires w is smaller than or equal to the number of output wires t. The depth of our network is Θ(lg2w), which depends only on w. In contrast, the amortized contention of the network depends on the number of concurrent processes n and the parameters w and t. This offers more flexibility than all previously known networks, with the same number w of input and output wires, whose contention depends only on two parameters, w and n. In case n>wlgw, by choosing t>wlgw the contention of our network is O(nlgww), which improves by a logarithmic factor of w over all previously known networks with w wires. © 2010 Elsevier B.V.