BatcherBitonicSorter k computes the sorting network of Batcher's bitonic sorter for exp(2,k) inputs which has a depth of k/2(k+1) using exp(2,k-1) many comparators in each step. The resulting array consists of the single steps, where each step consist of an array of comparators that are independent of each other (and can therefore run in parallel).

BatcherOddEvenSorter k computes the sorting network of Batcher's odd/even merge sorter for exp(2,k) inputs which has a depth of k/2(k+1) using exp(2,k-1) comparators in each step. The resulting array consists of the single steps, where each step consist of an array of comparators that are independent of each other (and can therefore run in parallel).

Compute a sorting network with the minimal known depth. Some of these networks were particular ones as found in the literature, while others are combinations of Batcher's OddEven merger with these. See the following references for these networks:

Compute a sorting network with the minimal known size. Some of these networks were particular ones as found in the literature, while others are combinations of Batcher's OddEven merger with these. See the following references for these networks:

Compute the boolean expressions for a compare-and-swap network

The following algorithm computes the configuration of a Clos network whose three columns consist of r1,r2, and r3 rows, respectively. The number of inputs/outputs is determined by the length of the permutation p. Functions prPaull will be called in each step and can be used to print the Paull matrix in each step, and function report will be given strings about adding and rearranging connections. For example, use

     let report (s:string) =
         printf "%s\n" s
     let prPaull (r1,r2,r3) edges =
         PrintPaullLatex (r1,r2,r3) (GetPaullMatrix (r1,r2,r3) edges)
 

ConfigureInverseBanyanButterfly computes the configuration of an inverse BanyanButterfly network for the given partial permutation. In contrast to the Benes network, the configuration is unique, if it exists, but for many permutations, there is no configuration. Even though switches can only be in `through' or `crossed' state, we distinguish further states do draw the networks with more information:

• None: both inputs were None, so no routing was required.
• Some(0): both inputs agreed on `through' state.
• Some(1): both inputs agreed on `crossed' state.
• Some(2): lower input wants `through' state, the upper is None.
• Some(3): lower input wants `crossed' state, the upper is None.
• Some(4): upper input wants `through' state, the lower is None.
• Some(5): upper input wants `crossed' state, the lower is None.
• If both states are different to None, but don't agree on a state they are mapped to one of the states 2,...,5.

DowdSorter implements the periodic balanced sorting network of Dowd et al, which consists for n=2^k inputs of k identical blocks of depth k. It is therefore almost twice as deep as Batcher's networks, but allows to reuse the block of depth k in a hardware implementation.

extract a Paull matrix from a set of edges (i,k,j) meaning that left switch i is conntected via middle switch k to right switch j

the cgi program

PairwiseSorter implements Parberry's pairwise sorting network that has exactly the same depth and size as Batcher's OddEven sorting network.

print a Paull matrix as HTML code

print a Paull matrix as Latex code

ScheduleComparatorNetwork is given an array of pairs (i,j) denoting a sequence of comparators. The function returns an array of arrays such that each array inside contains the pairs that are independent of each other. Hence, it schedules the given comparator array according to its depth.

This function generates the sorting selector-tree network for n=exp(2,k) inputs/outputs.

Symbolic simulation of a comparator network; the function will compute the sequence of BDDs that represent the set of boolean vectors that can occur after each level of the given comparator network.

This function checks whether a given network of comparators is a sorting network using Averest's BDD package. By the zero/one principle, it is sufficient to check the network for values 0/1 only, and then output i should be 1 iff the input vector contains more than m-i-1 ones. We can therefore compare with the boolean threshold functions or the more efficiently constructed output functions of the Batcher networks.

This function computes a BDD for the Boolean formula that asserts that a given comparator network is a sorting network. The formula makes use of Boolean variables g{i,j,k} that assert whether a comparator for inputs i and j is placed at level k of a comparator network. Constraints state that there is at most one comparator per input channel in every layer and that at the end, the inputs x{i} are always sorted. To this end, the function performs a universal quantification over the BDD constructed for the constraint formula. The inputs of the function are the number of inputs of the comparator network and its depth, the result is a BDD that encodes all sorting networks for these numbers. It works however only for small numbers!

print a BanyanButterfly configuration as svg graphics

print a BanyanPerfectShuffle configuration as svg graphics

print a Benes configuration as svg graphics

Write an SVG image of a scheduled (layered) sorting network with an optional array of integers to be sorted. Parameter xDist is the number of pixels between channels and between comparators (e.g. 20).