TY - JOUR

T1 - Sorting and counting networks of arbitrary width and small depth

AU - Busch, C.

AU - Herlihy, M.

N1 - Funding Information:
⁄ A preliminary version of this paper appears in the Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’99), pp. 64–73, Saint-Malo, France, June 1999. Part of this work was done while the first author was at Brown University. The second author was supported by NSF Grant CCR-9912401.

PY - 2002

Y1 - 2002

N2 - We present the first construction for sorting and counting networks of arbitrary width that requires both small depth and small constant factors in the depth expression. Let ω be the product ω = p0 · p1 ⋯ pn-1, whose factors are not necessarily prime. We present a novel network construction of width ω and depth O(n2) = O(log2 ω), using comparators (or balancers) of width less than or equal to max(Pi). This construction is practical in the sense that the asymptotic notation does not hide any large constants. An interesting aspect of this construction is that it establishes a family of sorting and counting networks of width ω, one for each distinct factorization of ω. A factorization in which max(pi) is large and n is small yields a network that trades small depth for large comparators (or balancers), and a factorization where max(pi) is small and n is large makes the opposite tradeoff.

AB - We present the first construction for sorting and counting networks of arbitrary width that requires both small depth and small constant factors in the depth expression. Let ω be the product ω = p0 · p1 ⋯ pn-1, whose factors are not necessarily prime. We present a novel network construction of width ω and depth O(n2) = O(log2 ω), using comparators (or balancers) of width less than or equal to max(Pi). This construction is practical in the sense that the asymptotic notation does not hide any large constants. An interesting aspect of this construction is that it establishes a family of sorting and counting networks of width ω, one for each distinct factorization of ω. A factorization in which max(pi) is large and n is small yields a network that trades small depth for large comparators (or balancers), and a factorization where max(pi) is small and n is large makes the opposite tradeoff.

UR - http://www.scopus.com/inward/record.url?scp=0036489337&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036489337&partnerID=8YFLogxK

U2 - 10.1007/s00224-001-1027-1

DO - 10.1007/s00224-001-1027-1

M3 - Article

AN - SCOPUS:0036489337

VL - 35

SP - 99

EP - 128

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -