Technical Report PHD-2011-10

Title: On Merging Networks
Authors: Tamir Levy
Supervisors: Ami Litman
Abstract: In this work we studied several aspects of comparator networks. The main focus of this work is on the fields of Bitonic sorters and merging networks; however, some of the tools we developed during this work are applicable to other comparator networks. The main results presented in this work are: 1. Bitonic Sorters of minimal depth – When the number of keys to be sorted is a power of two, minimal depth Bitonic sorters were already known for many years. However, in the general case, the minimal depth of Bitonic sorters was not known. This work establishes a lower bound on this depth and presents Bitonic sorters of this depth. 2. The MinMax model of computation – The comparator networks model of computation is widely used and studied. In this model keys propagate through the network (i.e., the comparators of the network) without being duplicated or dropped. This work studies a similar model of computation, called the MinMax model, where this restriction is lifted. This work shows that the MinMax model is the strongest model of computation in which several principles (0-1 like principles) are maintained. 3. Accelerated comparator networks – these are comparator networks in which several of the outputs are accelerated. That is, some outputs are generated much faster than the other outputs and this without hindering the other outputs. Namely, we present merging networks that produce either the lowest k keys or the highest k keys after a delay of $\ceil{log (k)} + 1$ comparators. Building on that, we construct, for every 0 < k < n, an n-key sorting network that accelerates its k lowest or its k highest outputs. This acceleration is based on a new merging technique, the Tri-section technique, which separates, by a depth one network, two sorted sequences into three sets, such that every key in one set is smaller or equal to any key in the following set. After this separation, each of these sets can be sorted separately and this leads to the desired acceleration. 4. Conclusive sets for comparator networks – handy tools for analysis of comparator networks. These are sets of (not necessarily binary) vectors that verify a specific functionality. This work investigates non-binary conclusive sets and proposes for the functionalities of sorting, merging, halving and Bitonic sorting, conclusive sets of minimal size.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2011
To the main CS technical reports page

Computer science department, Technion