Show simple item record

dc.contributor.authorHardavellas, N.en
dc.contributor.authorKarakos, D.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.editorSchipe A.en
dc.creatorHardavellas, N.en
dc.creatorKarakos, D.en
dc.creatorMavronicolas, Mariosen
dc.description.abstractImplementing 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.en
dc.source7th International Workshop on Distributed Algorithms, WDAG 1993en
dc.subjectArtificial intelligenceen
dc.subjectComputer scienceen
dc.subjectRecurrence relationsen
dc.subjectEconomic and social effectsen
dc.subjectCounting networksen
dc.subjectShared memory multiprocessoren
dc.subjectFormal analysisen
dc.subjectMemory locationsen
dc.subjectPerformance penaltiesen
dc.subjectSorting networken
dc.subjectTrade offen
dc.titleNotes on sorting and counting networksen
dc.description.volume725 LNCSen
dc.description.endingpage248 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notesConference code: 165879en
dc.description.notesCited By :9</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record