Interconnection Networks

Routing in Clos Networks

The first tool on this page computes configurations for Clos networks. You just have to write the desired permutation p[0],p[1],...,p[N-1] in the text field below, where you may simply write "_" when the value p[i] is not defined (i.e., input i shall not be connected with a target p[i]). The number of inputs/outputs is determined by the length of the permutation. The number of switches in the three columns of the Clos network has to be specified explicitly.

10;2;0;12;5;8;9;7;13;6;4;11;_;_;_;15
r1:	r2:	r3:

Routing in Permutation/Sorting Networks

The first tool on this page computes configurations (if possible) for different interconnection networks for a given (possible incomplete) permutation. You just have to write the desired permutation p[0],p[1],...,p[N-1] in the text field below, where you may simply write "_" when the value p[i] is not defined (i.e., input i shall not be connected with a target p[i]).

10;2;0;12;5;8;9;7;13;6;4;11;_;_;_;15

The tool will then compute a possible configuration of the Beneš network to implement that permutation (in case a partial permutation was given, it will be completed in an arbitrary way and if its length was not a power of 2, it may be extended also accordingly). It also tries to compute a configuration for the Banyan and inverse Banyan networks, but that will not always be possible since Banyan networks can only compute very few permutations. Given a partial permutation, the tool will then route some of the inputs i to their target addresses p[i], while other connections j to p[j] may be impossible due to conflicts. In these cases, you may see switches in different states even though the real switches only have two states (crossed or through): One of the two connections through a switch may be broken due to a conflict (and the one drawn is then the one that has been given priority), but even both may not be there (in case there were no connections requested by the inputs). Finally, we also use some sorting networks as interconnection networks (since routing is a special case of sorting where only permutations are considered). In particular, the tool will show how the given permutation is sorted (and thus routed) with the following sorting networks:

• Batcher's bitonic sorting network
• Batcher's odd/even sorting network
• Parberry's pairwise sorting network
• Dowd's periodic balanced sorting network
• minimal depth network (known so far)
• minimal size network (known so far)

Construct Sorting Networks of Minimal Depth and Size

The next tool below will print the best sorting networks for the specified range of inputs. These networks are either special ones defined in the literature or are combined of these using Batcher's OddEven merger (reduced to the required input lines). The special ones used were taken from the following references

• optimal depth up to 16 inputs: Parb92, BuZa14, BCCS17
• optimal depth for 17 inputs: CCEM15, CCEM18
• best depth for 18-20 inputs: EhMu14, EhMu15a, CCEM15
• best depth for 22 inputs: BaBa08a
• optimal sizes for 9,10 inputs: CCFS14a
• best sizes for 10-23 inputs: VaMi13

Show best/optimal depth and size networks from to inputs.

Verify Comparator Networks for Sorting

With the following tool, you can check whether a given comparator network is a sorting network. You just have to specify the comparator network in terms of a Knuth diagram where for n inputs, you can list pairs (i,j) as shown below to specify a compare-and-swap operation at this place. These are sequentially applied in the given order (and of course, some operations may be also possible in parallel). See the picture of the network on when clicking on the check button.

[(0,1);(2,3);(4,5)] [(1,2);(3,4);(5,6)] [(0,1);(2,3);(4,5)] [(1,2);(3,4);(5,6)]

Symbolic Simulation of Comparator Networks

With the following tool, you can compute the set of boolean vectors that can be produced after each level of a given comparator networks. By inspection of the set of boolean vectors, you may guess suitable comparators for the next level so that you can construct comparator networks manually. Splitters are sorting networks that only consider boolean input vectors where exactly half of their entries are true.

[(0,1);(2,3);(4,5);(6,7)] [(0,2);(1,3);(4,6);(5,7)] [(1,2);(5,6)] [(0,7);(1,6);(2,5);(3,4)]

exactly half of the input bits are true

Generate SMV Files for Optimal-Depth/Size Sorting/Splitting Networks

With the following tool, you can compute an SMV file that describes a model checking problem whose counterexamples describe a sorting or splitting network for the given parameters. The model checking problem is true if no such network exists, and can therefore prove the optimality of networks for a certain depth.

[(0,1);(2,3);(4,5);(6,7)]; []; []; [(0,7);(1,6);(2,5);(3,4)]

#inputs:

depth:

size: (value 0 means no contraint, otherwise this is an upper bound)

initial level shall be a Parberry level (comparing (2i,2i+1); may overwrite above CAS modules)

final level shall be a half cleaner (may overwrite above CAS modules)

only CAS modules of the final level compare lines of different halves

all lines in all levels must be connected by CAS modules

write constraint for inputs in DNF (not recommended)

consider only input vectors where half of the bits are true

flatten formulas to only depend on input variables

Generate BDD for all Sorting Networks

With the following tool, you can compute a BDD for all sorting networks with n inputs and a depth d as specified below. The BDD uses variables g{i,j,k} that state that there is a comparator for lines (i,j) in layer k of the network. Every satisfying assignment is then a sorting network.

inputs:
depth:

Circuit Netlists for Radix-Based Sorting Interconnection Networks

This tool generates circuit netlists for some radix-based sorting interconnection networks.

circuit	Crossbar BitonicSorter Batc68 ChOr94 ChCh96 JaSJ17 KoOr90 Nara94
module	CNC NET TNT
partiality	BIN TRP TRC TRS
optimization	HC0 HC1
number of inputs	4 8 16 32 64 128 256
message bits	1 4 8 16 32 64 128 256