## InterconnectNetworks Module

This file implements algorithms about interconnection and sorting networks used in computer systems. In particular, there are functions to determine the configurations of Beneš and Banyan networks with 2-way switches. Since routing is a special case of sorting (where only permutations are considered), we also consider sorting networks as interconnection networks. In particular, Batcher's Bitonic and OddEven divide/sort/merge based networks are considered, with the isomorphic version of Parberry's pairwise sorting network, and also Dowd's periodic balanced network that allows the reuse of the periodic block. For all of these configurations, there are functions to write the resulting network in form of SVG images. There is also a function to verify whether a given comparator network is a sorting network, and also a function to determine a

### Functions and values

 Function or value Description  BatcherBitonicSorter k  Full Usage: BatcherBitonicSorter k Parameters: k : int Returns: (int * int)[][] 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). k : int Returns: (int * int)[][]  BatcherOddEvenSorter k  Full Usage: BatcherOddEvenSorter k Parameters: k : int Returns: (int * int)[][] 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). k : int Returns: (int * int)[][]  BestDepthNetwork n  Full Usage: BestDepthNetwork n Parameters: n : int Returns: (int * int)[][] 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: n : int Returns: (int * int)[][]  BestSizeNetwork n  Full Usage: BestSizeNetwork n Parameters: n : int Returns: (int * int)[][] 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: n : int Returns: (int * int)[][]  CheckAll (r1, r2, r3) n  Full Usage: CheckAll (r1, r2, r3) n Parameters: r1 : int r2 : int r3 : int n : int Returns: int[] * int r1 : int r2 : int r3 : int n : int Returns: int[] * int  ComputeBooleanExpressionsOfCmpNet x  Full Usage: ComputeBooleanExpressionsOfCmpNet x Parameters: x : (int * int)[][] Returns: BoolExpr[][] * Set>[][] Compute the boolean expressions for a compare-and-swap network x : (int * int)[][] Returns: BoolExpr[][] * Set>[][]  ConfigureBenes p  Full Usage: ConfigureBenes p Parameters: p : int[] Returns: bool[,] p : int[] Returns: bool[,]  ConfigureClos prPaull report (r1, r2, r3) p  Full Usage: ConfigureClos prPaull report (r1, r2, r3) p Parameters: prPaull : int * int * int -> Set -> unit report : string -> unit r1 : int r2 : int r3 : int p : int option[] Returns: Set 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)  prPaull : int * int * int -> Set -> unit report : string -> unit r1 : int r2 : int r3 : int p : int option[] Returns: Set  ConfigureInverseBanyanButterfly p  Full Usage: ConfigureInverseBanyanButterfly p Parameters: p : int option[] Returns: int option[,] 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. p : int option[] Returns: int option[,]  DowdSorter k  Full Usage: DowdSorter k Parameters: k : int Returns: (int * int)[][] 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. k : int Returns: (int * int)[][]  GetPaullMatrix (r1, r2, r3) edges  Full Usage: GetPaullMatrix (r1, r2, r3) edges Parameters: r1 : int r2 : 'a r3 : int edges : Set Returns: Map<(int * int), Set<'b>> 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 r1 : int r2 : 'a r3 : int edges : Set Returns: Map<(int * int), Set<'b>>  InterconnectNetworkTool qscoll  Full Usage: InterconnectNetworkTool qscoll Parameters: qscoll : NameValueCollection the cgi program qscoll : NameValueCollection  ParberryPairwiseSorter k  Full Usage: ParberryPairwiseSorter k Parameters: k : int Returns: (int * int)[][] PairwiseSorter implements Parberry's pairwise sorting network that has exactly the same depth and size as Batcher's OddEven sorting network. k : int Returns: (int * int)[][]  PrintPaullHtml (r1, r2, r3) paull  Full Usage: PrintPaullHtml (r1, r2, r3) paull Parameters: r1 : int r2 : 'a r3 : int paull : Map<(int * int), Set> print a Paull matrix as HTML code r1 : int r2 : 'a r3 : int paull : Map<(int * int), Set>  PrintPaullLatex (r1, r2, r3) paull  Full Usage: PrintPaullLatex (r1, r2, r3) paull Parameters: r1 : int r2 : 'a r3 : int paull : Map<(int * int), Set> print a Paull matrix as Latex code r1 : int r2 : 'a r3 : int paull : Map<(int * int), Set>  ScheduleComparatorNetwork x  Full Usage: ScheduleComparatorNetwork x Parameters: x : (int * int)[] Returns: (int * int)[][] 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. x : (int * int)[] Returns: (int * int)[][]  SortingSelectorTree k  Full Usage: SortingSelectorTree k Parameters: k : int Returns: (int * int)[][] This function generates the sorting selector-tree network for n=exp(2,k) inputs/outputs. k : int Returns: (int * int)[][]  SymbSimComparatorNetwork onlyHalf n x  Full Usage: SymbSimComparatorNetwork onlyHalf n x Parameters: onlyHalf : bool n : int x : (int * int)[][] 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. onlyHalf : bool n : int x : (int * int)[][]  VerifyComparatorNetwork x  Full Usage: VerifyComparatorNetwork x Parameters: x : (int * int)[][] Returns: bool * BoolExpr[] * BddAdr[] * BddAdr[] * BddAdr[] 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. x : (int * int)[][] Returns: bool * BoolExpr[] * BddAdr[] * BddAdr[] * BddAdr[]  mkComparatorNetworkBDD n d  Full Usage: mkComparatorNetworkBDD n d Parameters: n : int d : int Returns: BddAdr 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! n : int d : int Returns: BddAdr  printBanyanButterflyToSVG inverse ostr p c  Full Usage: printBanyanButterflyToSVG inverse ostr p c Parameters: inverse : bool ostr : TextWriter p : int option[] c : int option[,] print a BanyanButterfly configuration as svg graphics inverse : bool ostr : TextWriter p : int option[] c : int option[,]  printBanyanPerfectShuffleToSVG inverse ostr p c  Full Usage: printBanyanPerfectShuffleToSVG inverse ostr p c Parameters: inverse : bool ostr : TextWriter p : int option[] c : bool option[,] print a BanyanPerfectShuffle configuration as svg graphics inverse : bool ostr : TextWriter p : int option[] c : bool option[,]  printBenesToSVG ostr p c  Full Usage: printBenesToSVG ostr p c Parameters: ostr : TextWriter p : int[] c : bool[,] print a Benes configuration as svg graphics ostr : TextWriter p : int[] c : bool[,]  printSortingNetworkToSVG ostr xDist a x  Full Usage: printSortingNetworkToSVG ostr xDist a x Parameters: ostr : TextWriter xDist : int a : int[] option x : (int * int)[][] 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). ostr : TextWriter xDist : int a : int[] option x : (int * int)[][]