Notes on sorting and counting networks

Abstract

Implementing counting networks on shared-memory multiprocessor machines often incurs a performance penalty proportional to the depth of the networks and the extent to which concurrent processors access the same memory location at the same time. In this work, we examine the dependence of performance on the width of the balancers used in constructing such networks. Our main result is a construction of counting networks (and, hence, sorting networks) with perfect power width pk, for any integers p≥2 and k≥1. This construction is built on balancers of width p, and generalizes in a novel way the periodic counting network of Aspnes, Herlihy and Shavit [3], built on balancers of width 2. This result provides a partial answer to a question of Aharonson and Attiya [1]. The depth of these networks is k2, thus implying decrease in depth of counting networks through an increase in balancer width. Furthermore, we provide a formal analysis of the performance of our construction as measured by contention [8]. Through a novel use of recurrence relations, we show that our counting networks incur a contention of Θ(nk2/pk−1) in the presence of n concurrent processors. This bound implies a trade-off between depth and contention. © Springer-Verlag Berlin Heidelberg 1993.