add a new gate to the circuit and return its output vector; if the gate already exists, no gate is added, and the existing outputs are returned

This concentrator is derived from Batcher's bitonic sorting network by just comparing the most significant address bits, and removing these from the outputs in case rmMSB is true (so that the next bits are considered in the next stage of the radix-based sorting network). It leads to a binary sorter of depth O(log(n)^2) and size O(nlog(n)^2). See also

• Batc68
• JaSc18

This circuit implements a Batcher-Banyan network (see [Nara88]) which consists of a (Batcher) sorting network that sorts the inputs by their addresses

• Nara88
• JaSc18

This circuit implements Batcher's bitonic merge network that is based on a network with compare-and-swap modules which are combined in half cleaners. Essentially, Batcher's bitonic merge network is a binary tree whose nodes are half cleaners whose width is doubled in each level of the tree (the leftmost half cleaner in the root node should reverse the second half of its input which is done in the call in BitonicSorter). See also

• Batc68
• JaSc18

This circuit implements Batcher's bitonic sorting network that is based on the merge sort paradigm, i.e., first splitting the given list into halves, sorting these recursively with the same algorithm, and then merging the sorted halves into a single sorted list. The merging step is done here by Batcher's bitonic merge network (function BitonicMerger) where however the second half of its input has to be reversed to obtain a bitonic sequence. See also

• Batc68
• JaSc18

This concentrator is defined in [ChCh96] and recursively implements a binary sorter that is based on the observation that all internal vectors can be made compact vectors in the sense that all 1s in these vectors occur as a contiguous sequence. The concentrator is based on the generalized cube network which is the BY-BF-FS (banyan/butterfly network with outgoing flip shuffle permutation). The network used is isomorphic to the Omega-network and also to Batcher's bitonic merger.

To route the input vector to a sorted binary vector, all internal results are becoming compact sequences [ChCh96]. The configuration is obtained by first splitting the input vector successively in halves in that we put a binary tree above it, and then compute for each node the number of 1s it covers. Using carry ripple adders requires 2*log(n)+1 steps to do this. The routing is then based on these numbers; details can be found in

• ChCh96
• JaSc18

This concentrator is defined in [ChOr94] and implements recursively a binary sorter using the parallel merge sort paradigm (see ChOr94Merger). Hence, the given input vector is split into two halves which are sorted recursively, and are then merged by ChOr94Merger for n>2. See also function ChOr94Merger and

• ChOr94
• JaSc18

This concentrator is defined in [ChOr94] and implements recursively a binary sorter using the parallel merge-sort paradigm. Merging is done here for so-called bi-sorted binary sequences, i.e., sequences whose two halves are sorted sequences. The merging circuit used in the design is able to merge two bi-sorted sequences into a single sorted sequence. This is done by the observation that if two sorted binary lists xUpp and xLow are split into halves, i.e., xUpp=x1*x2 and xLow=x3*x4, then two of these halves are clean, i.e. contain only 0s or only 1s, and the other two halves are sorted. The merging circuit has to identify the clean and the sorted quaters and forwards the sorted quarters to a recursive merge module. Finally, it concatenates the already clean quarters with the sorted result of the recursive call. See also

• ChOr94
• JaSc18

Checking the correctness of a binary/ternary sorter/concentrator: The function simulates the given LeveledCircuit for all possible inputs and will check whether it is a binary/ternary sorter/concentrator. The result will be an optional tuple (env,xVec,yVec) holding a potential counterexample where 0,1,2 means 0,⊥,1 in ternary and 0,1 obviously means 0,1 in binary. For binary inputs, all bits of an input are constant so that 2**n vectors have to be checked. Their length is log2(n)+1 since we use one message bit. Ternary inputs look like |v0;v1;|v0|v1...v1| using two message bits, one validity bit v0, and log(n) address bits. If input checkSorter holds, it is checked that the output sequence is of the form 0..0⊥..⊥1..1, and otherwise, it is checked that it is a concentrated vector, i.e., 0s are only allowed in the upper half if the lower half is full of 0s, and 1s are only allowed in the lower half if the upper half is full of 1s. Finally, if checkRBS is true, then all input vectors are ignored where the number of 0s or the number of 1s exceeds n/2.

Check correctness of an arithmetic circuit generator genCircuit: This function will generate all bitvectors with n1 and n2 bits, respectively, as arguments, and will then evaluate the circuit on all input vectors. It then checks whether the given function checkFun yields true when given the input and output bitvectors.

Checking whether an interconnection network given as a circuit can route all partial permutations correctly. The function simulates the circuit with all partial permutations where the circuit with n inputs is expected to have inputs x[i] with 2*(log2 n)+1 bits since the target address will have log2(n) bits, and it is also used as the message for each x[i]. Morever, each input has a valid bit so that each x[i] consists of the message x[i][0..q-1]*x[i][q]*x[i][q+1..2q+1] with q:=log2(n). Note that the number of partial permutations of n objects is given as sum_{i=0}^{n} i!*binom(n,i)^2 (see function Global.PartialPermutations). The result is an optional pair (perm,env) where perm is the input vector of type (int option)[], and env the variable environment obtained by the simulation in case a counterexample has been found. If the circuit correctly routes all partial permutations the result is None.

This function verifies a given leveled circuit in that it simulates it on all possible inputs and checks whether the given F# function spec satisfies the input/output combination. It returns all variable assignments where the specification failed.

checking the correctness of a ranking circuit that starts with firstRank for the first valid entry (RankingTree0 needs 1, others 0), e.g. you may use this as follows

• List.map (CheckRankingCircuit 1 RankingTree0) [2;4;8;16];;
• List.map (CheckRankingCircuit 0 RankingTree1) [2;4;8;16];;
• List.map (CheckRankingCircuit 0 RankingTree2) [2;4;8;16];;

generate a circuit for a BoolExpr

generate a circuit for a BtvExpr

generate a circuit for an Expr

generate a circuit to compute the absolute value of a 2-complement number with n-bits (the result is a radix-2 number with n-bits); in case of negative numbers, an addition is required so that the circuit is parameterized by a circuit generator for radix-2 adders

generate a circuit for carry-lookahead addition of 2-complement numbers with size O(n) and depth O(log(n))

generate a circuit for carry-ripple subtraction of 2-complement numbers with size O(n) and depth O(n)

generate an integer division with radix-2 division and addition circuits

Given a circuit generators for division and addition of radix-2 numbers, CircIntDivMod generates a circuit for division of 2-complement numbers.

generate a circuit for non-performing 2-complement division using the specified circuit for radix-2 addition

generate a circuit for non-restoring 2-complement division using the specified circuit for radix-2 addition

generate a circuit for non-restoring 2-complement division using the specified circuit for radix-2 addition with only

generate a circuit for restoring 2-complement division using the specified circuit for radix-2 addition

generate a circuit to check equality of 2-complement numbers with size O(n) and depth O(log(n))

CircIntExp computes the power of x1 by x2 using the given multiplier generator where x2 is a radix-2 number and x1 is a 2-complement number.

generate a circuit for an IntExpr

generate a circuit to compare (less than or equal) radix-2 numbers; size O(n) and depth O(log(n))

generate a circuit to compare (less than) 2-complement numbers with size O(n) and depth O(log(n))

generate an integer remainder with radix-2 division and addition circuits

generate a circuit for non-performing 2-complement remainder using the specified circuit for radix-2 addition

generate a circuit for non-restoring 2-complement remainder using the specified circuit for radix-2 addition

generate a circuit for non-restoring 2-complement remainder using the specified circuit for radix-2 addition with only

generate a circuit for restoring 2-complement remainder using the specified circuit for radix-2 addition

IntMulCRA is a simple paper-and-pencil multiplier for 2-complement numbers that adds up the partial products row by row using carry-ripple adders.

Generate a multiplier for 2-complement numbers using carry-save adders. After generating rows of partial products, we always pick the first three rows and reduce them using a carry save adder in a single step to two rows keeping the other rows untouched. The final two rows are added by a carry-ripple adder so that the circuit has a size of O(n*m) and a depth of O(m+n).

CircIntMulDadda generates a Dadda multiplier for 2-complement numbers. It has a size of O(n*m) and a depth of O(log(n+m)) and requires typically less gates than other logarithmic-depth multipliers.

CircIntMulGreedy is a logarithmic depth multiplier that first generates all partial products and then aggressively reduces the columns as much as possible using full and half adders.

Generate a Wallace multiplier for 2-complement numbers, which works by a repeated reduction of the summands (rows of partial products) in that groups of three rows are compressed to two rows using a CSA adder. The obtained circuit has a depth of O(log(n+m)) and a size of O(n*m).

generate a circuit to check inequality of 2-complement numbers with size O(n) and depth O(log(n))

The function adds gates for a carry-lookahead subtraction of 2-complement numbers x1 and x2 of the same length n and returns the n+1 bits of the sum bitvector.

generate a circuit for carry-ripple subtraction of 2-complement numbers with size O(n) and depth O(n)

Generate a multiplier with carry-save adders. After generating rows of partial products, we always pick the first three rows and reduce them using a carry save adder in a single step to two rows keeping the other rows untouched. The final two rows are added by a carry-ripple adder so that the circuit has a size of O(n*m) and a depth of O(m+n).

Generate a Wallace multiplier for radix-2 numbers, which works by a repeated reduction of the summands (rows of partial products) in that groups of three rows are compressed to two rows using a CSA adder. This way, the number of rows row[i] for multiplying n by m bits is defined as row[0] := m and row[j+1] := 2*(row[j] div 3) + (row[j] mod 3). At the end, the final two summands are added by a carry-lookahead adder, so that the obtained circuit has a depth of O(log(n+m)) and a size of O(n*m).

generate a circuit for carry-lookahead addition of radix-2 numbers with size O(n) and depth O(log(n))

generate a circuit for carry-ripple addition of radix-2 numbers with size O(n) and depth O(n)

CircNatDivModNPF generates a circuit for non-performing radix-2 division, i.e., a division algorithm that first checks if the shifted divisor is less than or equal to the dividend. If so, it is subtracted, otherwise, the divisor is just shifted. If a subtraction takes place, the corresponding quotient bit is 1, and otherwise 0. The algorithm uses subtraction with x2Len-1 operands. To be used also for integer division, the circuit is given a rInit parameter that is determined by CircIntDivMod and is a bitvector with x2Length zeros for radix-2 division (which is generated by the function in case of value None).

CircNatDivModNonRestoreLong generates a circuit for non-restoring radix-2 division, i.e., by either subtracting or adding the second operand, depending on the sign of the previous result which also determines the previous bit obtained for the quotient. The generated circuit uses x2Len+1 bits for the subtraction/addition operations which is easier to understand compared with the more efficient version CircNatDivModNonRestore.

CircNatDivModNonRestoring generates a circuit for non-restoring radix-2 division, i.e., by either subtracting or adding the second operand, depending on the sign of the previous result which also determines the previous bit obtained for the quotient. The generated circuit uses x2Len bits for the subtraction/addition operations. To be used also for integer division, the circuit is given a rInit parameter that is determined by CircIntDivMod and is a bitvector with x2Length zeros for radix-2 division (which is generated by the function in case of value None).

CircNatDivModRST generates a circuit for a restoring radix-2 division, i.e., a division algorithm that first subtracts the shifted divisor to check whether it was less than the dividend. If so, the result of the subtraction is the new dividend, otherwise, the previous one is retained. otherwise, the divisor is just shifted. To be used also for integer division, the circuit is given a rInit parameter that is determined by CircIntDivMod and is a bitvector with x2Length zeros for radix-2 division (which is generated by the function in case of value None).

generate a nonperforming division with given adders for the quotient

generate a nonrestoring division with given adders for the quotient

generate a non-restoring division with given adders for the quotient

generate a restoring division with given adders for the quotient

generate a circuit to check equality of radix-2 numbers with size O(n) and depth O(log(n))

CircNatExp computes the power of x1 by x2 using the given multiplier generator. The circuits has (2^{x2Len+1}-1)*x1Len many output bits.

generate a circuit for a NatExpr

generate a circuit to compare (less than or equal) radix-2 numbers with size O(n) and depth O(log(n))

generate a circuit to compare (less than) radix-2 numbers with size O(n) and depth O(log(n))

generate a nonperforming division with given adders for the remainder

generate a nonrestoring division with given adders for the remainder

generate a non-restoring division with given adders for the remainder

generate a restoring division with given adders for the remainder

generate a circuit for paper-and-pencil multiplication of radix-2 numbers; i.e., generate all n*m partial products and add the rows using NatAddCRA; size O(n*n) and depth O(log(n)), for a nxn multiplier is 3(n-1), the number of AND gates is n*n for the partial products, and n-1 half adders, and (n-1)^2 full adders are used.

Generate a multiplier for radix-2 numbers using carry-save adders. After generating rows of partial products, we always pick the first three rows and reduce them using a carry save adder in a single step to two rows keeping the other rows untouched. The final two rows are added by a carry-ripple adder so that the circuit has a size of O(n*m) and a depth of O(m+n).

CircNatMulDadda generates a Dadda multiplier for radix-2 numbers. It has a size of O(n*m) and a depth of O(log(n+m)) and requires typically less gates than other logarithmic-depth multipliers.

CircNatMulGreedy is a logarithmic depth multiplier that first generates all partial products and then aggressively reduces the columns as much as possible using full and half adders.

Generate a Wallace multiplier for radix-2 numbers, which works by a repeated reduction of the summands (rows of partial products) in that groups of three rows are compressed to two rows using a CSA adder. The obtained circuit has a depth of O(log(n+m)) and a size of O(n*m).

generate a circuit to check inequality of radix-2 numbers with size O(n) and depth O(log(n))

generate a circuit for carry-lookahead subtraction of radix-2 numbers with size O(n) and depth O(log(n))

generate a circuit for carry-ripple subtraction of radix-2 numbers with size O(n) and depth O(n)

Initialize the BDD package with the input variables of the given circuit.

Compute BDDs for the outputs of a given circuit. The function retains also all BDDs that have been computed for the internal wires of the circuit and could be optimized in that these are put into the garbage when no longer needed. If optFlag is true, the function will do garbage collection after every level of the circuit.

Compute complexity measures of a leveled circuit: This function returns a tuple (depth,numAND,numXOR,numOR,numHA,numFA,numPG,size) where all components have the obvious meaning, and size is the gate count in terms of 2-input, 1-output gates (where HA, FA, PG, SW are expanded to 2, 5, 3, and 8 gates, respectively).

This generator constructs a crossbar circuit that can connect anyone of its n inputs with anyone of its n outputs as long as the mapping of the inputs to the outputs is a (partial) permutation. To this end, the n input vectors consist of q=x[i].Length-log2(n) bits of the message concatenated with log2(n) bits of the target address. Note that we do not have to distinguish partial permutations here.

enumerate all bitvectors with n digits for a full simulation

evaluate a bitvector as a B-complement number

evaluate a bitvector as a radix-B number

Evaluate a leveled circuit based on a variable assignment varAssign that initially only holds values for the input variables. Based on these input values, the function evaluates each level and adds the values of all variables to the variable assignment that is finally returned.

Levelize the circuit in the global circuit map into microstep levels

The following function takes a generator sortGen for a binary sorter and constructs a binary concentrator of it by using two sorters of half the size and a further half cleaner column as reported in [KoOr90,Nara88] and explicitly in [JaSc18,JaSJ17b]. The construction is therefore as follows:

where the half cleaner module (HC) consists of one column of compare-and-swap modules (the arrows show where the bigger input is moved to) in addition to an ingoing perfect shuffle permutation and an outgoing flip shuffle permutation:

The result is no longer a sorter, but still a concentrator which means that 0s and 1s are put in the preferred halves, so that one half will become clean (only consisting of 0s and 1s) as soon as possible. In general, for the two halves yLow and yUpp of its output vector y, we also have max(yLow) ≤ min(yUpp) but that becomes meaningless as soon as we have more than n/2 0s or 1s.

The following function takes a generator sortGen for a ternary sorter and constructs a concentrator of it by generating two sorters of half the size and a further half cleaner column as reported in [KoOr90,Nara88] and explicitly in [JaSc18,JaSJ17b]:

where the half cleaner module (HC) consists of one column of compare-and-swap modules (the arrows show where the bigger input is moved to) in addition to an ingoing perfect shuffle permutation and an outgoing flip shuffle permutation:

The result is no longer a sorter, but still a concentrator which means that 0s and 1s are put in the preferred halves, so that one half will become clean (only consisting of 0s and 1s) as soon as possible. In contrast to HalfCleanerBinaryOpt which only considers the msbs of the input vectors in the half cleaner, this function also considers their valid bit (bits 0..q-1 form the message, bit q is the valid bit, and bits q+1..q+log2(n) are the address bits with q+log2(n) as msb).

reset the circuit generator with a name stub for the internal wires

This circuit generator is a parallel version of Narasimha's concentrator [Nara94] that is published in [JaSJ17]: As Narasimha's concentrator, this circuit is based on a RB-FS-RV permutation network (reverse banyan/ flip shuffle with reverse output permutation) and configures switch i of each column by the parity of the input vector's prefix x[0..2i], so that half of the 0s in x[0..2i+1] are send to the lower and upper subnetworks (same with the 1s since each prefix x[0..2i+1] consists of an even number of inputs). In case that the prefix x[0..2i+1] contains an odd number of 0s (and therefore also an odd number of 1s, the additional 0 is sent to the lower and the additional 1 is sent to the upper subnetwork. See also

• Nara94
• JaSJ17
• JaSc18

The difference between JaSJ17 and Nara94 is that the computations of the parity bits to configure the switches in JaSJ17 is done by a parallel prefix tree that reduces the depth of the concentrator from O(n) to only O(log(n)^2).

As for all the concentrator circuits implemented in this F# modules, each input x[i] is an input bitvector that is the concatenation of a message x[i][0..q-1] with q bits, a valid bit x[i][q] (that is viewed as part of the message for the binary sorters/concentrators/networks), and a destination address x[i][q+1..q+k] such that x[i][q+k] is the most significant bit of the destination address. Clearly, we have k=log2(x.Length). Also, all the concentrators/binary sorters concentrate the inputs according to the most significant bit x[i][q+k-1] and may or may not remove this bit during or after the concentration which is determined by the input parameter rmMSB. For constructing interconnection networks based on radix-based sorting, it is required to remove the msb so that the different stages sort by the different address bits, but if other constructions like HalfCleanerBinaryOpt or HalfCleanerTernaryOpt are used, the msb has to be retained for the latter.

Koppelman-Oruc-like Concentrator [KoOr90], i.e., binary sorting by first computing ranks and then self-routing by using the ranks as local target addresses. This version of the KoOr90 idea first computes the ranks of the 0s (by ranking the negated inputs) so that it can also be used with RadixBasedTernaryInterconnect to implement partial permutations. For routing the 0s to their local target address, i.e., their rank, we use a RB-FS-RV (reverse-banyan/flip-shuffle network with reverse output) permutation network, as used in Nara94 and JaSJ17 whose configuration is however determined in a different way using the ranks: Inputs are partitioned by the least significant bit of their rank. So, we first obtain two partitions with rank ...0 rank ...1, and after that, we have four partitions with ranks ...00, ...10, ...01, and ...11. In each stage, each group is split into two further groups with new address bits 0 and 1, respectively. Finally, we obtain for example for 8 inputs the ranks 000, 100, 010, 110, 001, 101, 011, and 111 so that the reverse output permutation (reversing the address bits) will map them to the right output.

The configuration of switch i based on the least significant bits r[2i][0] and r[2i+1][0] of the ranks as well as on the most significant bits xb[2i] and xb[2i+1] of inputs x[2i] and x[2i+1] is explained by the following truth table:

xb[2i]	xb[2i+1]	r[2i][0]	r[2i+1][0]	config
0	0	0	1	0	-> x[2i] to low-net, x[2i+1] to upp-net
0	0	1	0	1	-> x[2i] to upp-net, x[2i+1] to low-net
0	1	1	*	1	-> x[2i] to upp-net
0	1	0	*	0	-> x[2i] to low-net
1	0	*	1	0	-> x[2i+1] to upp-net
1	0	*	0	1	-> x[2i+1] to low-net
1	1	*	*	*	-> don't care

Explanation: The goal is to route the 0s to the local target address given by their rank, hence,

• we have to send xb[2i]=0 to the low-net if r[2i][0]=0 holds
• we have to send xb[2i]=0 to the upp-net if r[2i][0]=1 holds
• we have to send xb[2i+1]=0 to the low-net if r[2i+1][0]=0 holds
• we have to send xb[2i+1]=0 to the upp-net if r[2i+1][0]=1 holds

If both inputs x[2i] x[2i+1] are 0, the bits of the ranks must be inequal by construction so that we only have to consider the two cases in the above table (the other two are don't cares). This way, the boolean function p[i] := (x[2i] ? !r[2i+1][0] : r[2i][0]) or equivalent p[i] := (x[2i+1] ? r[2i][0] : !r[2i+1][0]) is obtained for the configuration of the switches. Note further that we need the most significant bits xb[2i] and xb[2i+1] of the inputs for this purpose, so that they can only be removed at the end of the concentrator. Finally, note that for binary sorting, we could also rank and route the 1s and reverse the output, but that not work well with the construction of an interconnection network with RadixBasedTernaryInterconnect that can handle partial permutations. The depth of this binary sorter/concentrator is only O(log(n)) and its size is O(n*log(n)).

write a leveled circuit to a dot (graphviz) graph

This function will generate either a concentrator/sorter or an entire interconnection network based on radix-based sorting. It combines all other generator functions for concentrators and RBS interconnection networks including their optimization by half cleaners. To this end, the following inputs are expected:

• modName:
  • TNT (RadixBasedTernaryInterconnect): for an entire RBS interconnection network with a front-end concentrator
  • NET (RadixBasedInterconnect): for an entire RBS interconnection network
  • CNC: for the construction of a concentrator
• aryName:
  • BIN: binary sorter (splitters' inputs are booleans)
  • TRP (TernaryParSorter): ternary sorter by parallel composition and a MUX stage
  • TRC (TernaryParConcentrator): ternary sorter for RBS inputs by parallel composition
  • TRS (TernarySeqSorter): ternary sorter by sequential composition [Nara94]
• optName:
  • HC0: no optimization applied
  • HC1: apply optimization by half cleaner lemma (uses HalfCleanerBinaryOpt in case of aryName=BIN and HalfCleanerTernaryOpt otherwise)
• cncName:
  • Batc68: binary sorter by [Batc68]
  • ChCh96: binary sorter by [ChCh96]
  • ChOr94: binary sorter by [ChOr94]
  • JaSJ17: binary sorter by [JaSJ17]
  • KoOr90: binary sorter by [KoOr90]
  • Nara94: binary sorter by [Nara94]
• q is the number of message bits
• n is the number of inputs/outputs

This circuit generator constructs Narasimha's concentrator [Nara94] which is actually a binary sorter: The circuit is based on a RB-FS-RV permutation network (reverse banyan/flip shuffle with reverse output permutation) and configures switch i of each column by the parity of the input vector's prefix x[0..2i], so that half of the 0s in x[0..2i+1] are send to the lower and upper subnetworks (same with the 1s since each prefix x[0..2i+1] consists of an even number of inputs). In case that the prefix x[0..2i+1] contains an odd number of 0s (and therefore also an odd number of 1s, the additional 0 is sent to the lower and the additional 1 is sent to the upper subnetwork. See also

• Nara94
• JaSJ17

As for all the concentrator circuits implemented in this F# modules, each input x[i] is an input bitvector that is the concatenation of a message x[i][0..q-1] with q bits, a valid bit x[i][q] (that is viewed as part of the message for the binary sorters/concentrators/networks), and a destination address x[i][q+1..q+k] such that x[i][q+k] is the most significant bit of the destination address. Clearly, we have k=log2(x.Length). Also, all the concentrators/binary sorters concentrate the inputs according to the most significant bit x[i][q+k-1] and may or may not remove this bit during or after the concentration which is determined by the input parameter rmMSB. For constructing interconnection networks based on radix-based sorting, it is required to remove the msb so that the different stages sort by the different address bits, but if other constructions like HalfCleanerBinaryOpt or HalfCleanerTernaryOpt are used, the msb has to be retained for the latter.

generate a new vector of length n with names of new internal wires

parse a leveled circuit from a TextReader

parse a leveled circuit from a file

parse a leveled circuit from a string

print complexity table in Latex