Ph.D Thesis

Ph.D StudentLevy Tamir
SubjectOn Merging Networks
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Ami Litman
Full Thesis textFull thesis text - English Version


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 é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.