1 Comparison Networks: An Analogy See the Wikipedia article on Sorting Networks.
ID: 3746317 • Letter: 1
Question
1 Comparison Networks: An Analogy
See the Wikipedia article on Sorting Networks. Just read down to, but not including, the zero-one principle. We will be concerned with comparison networks, in general, not just sorting networks. The size of a comparison network is the number of comparators, and the depth is the number of levels of comparators. For example, in the Wikipedia article, the initial sorting network for four inputs has size five and depth three. The parallel bubble sort network for six inputs has size fifteen and depth nine. In general, a parallel bubble sort network for n inputs has size n(n 1)/2 and depth 2n 3. 1.
Let n be a power of 2.
(a) Show how to construct an efficient comparison network with n inputs where the output on the top wire is the minimum value and the output on the bottom wire is the maximum value. Primarily minimize the depth and secondarily minimize the size. Just describe the network; do not justify.
(b) What is the (exact) size of your network?
(c) What is the (exact) depth of your network?
It turns out that comparison networks are very important on Mars, where they have many applications. A merging network inputs two sorted lists each of size n/2 and outputs the total list of values in order. The Martians have discovered merging networks with depth about lg n. (Such merging networks were independently discovered on Earth by Batcher.) The Martians are especially interested in sorting networks. They have proven that any sorting network must have depth at least lg n (and size at least about n lg n). They know that there are sorting networks with depth O((log n) 2 ), but do not know whether they can attain depth O(log n). A problem similar to sorting that Martians often need to solve is half sorting: The input is two lists each of size n/2, and the output is the two lists independently sorted. Not surprisingly, sorting and half sorting are closely related.
2.
(a) Show that if sorting can be solved on a comparison network in depth O(log n) then half sorting can be solved on a comparison network in depth O(log n).
(b) Show that if half sorting can be solved on a comparison network in depth O(log n) then sorting can be solved on a comparison network in depth O(log n).
Explanation / Answer
In computer science, comparator networksare abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks.
Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,[1] who subsequently patented the idea.[2]
Sorting networks can be implemented either in hardware or in software. Donald Knuthdescribes how the comparators for binary integers can be implemented as simple, three-state electronic devices.[1] Batcher, in 1968, suggested using them to construct switching networks for computer hardware, replacing both buses and the faster, but more expensive, crossbar switches.[3] Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPUcommunity for constructing sorting algorithms to run on graphics processing units.[4]
It turns out that comparison networks are very important on Mars, where they have many
applications. A merging network inputs two sorted lists each of size n/2 and outputs the total list
of values in order. The Martians have discovered merging networks with depth about lg n. (Such
merging networks were independently discovered on Earth by Batcher.)
The Martians are especially interested in sorting networks. They have proven that any sorting
network must have depth at least lg n (and size at least about n lg n). They know that there are
sorting networks with depth O((log n)
2
), but do not know whether they can attain depth O(log n).
A problem similar to sorting that Martians often need to solve is half sorting: The input is two
lists each of size n/2, and the output is the two lists independently sorted. Not surprisingly, sorting
and half sorting are closely related.
our two “reductions” show:
Corollary. There exists a depth O(log n) sorting network if and only if there exists a depth
O(log n) half sorting network.
The Martians extended this result to show that many other important comparison problems
are equivalent to sorting and half sorting: Any one of these special problems is solvable in depth
O(log n) if and only if all of them are solvable in depth O(log n).
2.
Recently two Martian computer scientists Koco and Nevil made a startling discovery.
Definition. A function f(n) is polylog(n) if there exists a constant k such that f(n) = O((log n)
k
).
We will just say polylog when the parameter n is implicit.
Theorem. If there exists a depth O(log n) sorting network then, for every problem solvable on a
comparison network in polylog depth there exists a depth O(log n) comparison network.
For details, see their article in the prestigious Martian Online Journal Of Computer Science
(otherwise known as MOJO CS).
To finish the analogy: Let L (for Log depth) be the class of problems solvable in depth O(log n)
on a comparison network with n inputs. Let PL (for PolyLog depth) be the class of problems
solvable on a comparison network in polylog depth. The theorem of Koco and Nevil shows that
sorting is PL-complete (in other words, if sorting is in L, then every problem in PL is also in L).
The open problem on Mars is: Does L = PL?
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.