Averest


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<Set<BoolExpr>>[][]

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

x : (int * int)[][]
Returns: BoolExpr[][] * Set<Set<BoolExpr>>[][]

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<int * int * int> -> unit
    report : string -> unit
    r1 : int
    r2 : int
    r3 : int
    p : int option[]

Returns: Set<int * int * int>

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<int * int * int> -> unit
report : string -> unit
r1 : int
r2 : int
r3 : int
p : int option[]
Returns: Set<int * int * int>

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<int * 'b * int>

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<int * 'b * int>
Returns: Map<(int * int), Set<'b>>

InterconnectNetworkTool qscoll

Full Usage: InterconnectNetworkTool qscoll

Parameters:

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<int>>

print a Paull matrix as HTML code

r1 : int
r2 : 'a
r3 : int
paull : Map<(int * int), Set<int>>

PrintPaullLatex (r1, r2, r3) paull

Full Usage: PrintPaullLatex (r1, r2, r3) paull

Parameters:
    r1 : int
    r2 : 'a
    r3 : int
    paull : Map<(int * int), Set<int>>

print a Paull matrix as Latex code

r1 : int
r2 : 'a
r3 : int
paull : Map<(int * int), Set<int>>

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:

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)[][]