The Beneš Network

Although the cross-bar switch is capable of connecting fully an arbitrary input-output permutation, involves an impractically high hardware cost. In 1964 Beneš devised a method of reducing an N x N cross-bar switch to two N/2 x N/2 cross-bar switches and two N-input exchange switches [1] , as illustrated in Figure 1.

The resulting N/2 x N/2 cross-bar switches can be similarly reduced, and through this recursive trade-off between complexity and network latency a full connection network can be produced at a significantly lower cost than a full cross-bar switch. This network, illustrated in Figure 2, is constructed entirely from 2-input 2-output switch-nodes, arranged as a sequence of stages connected by inverse shuffle permutations. [The inverse shuffle, σ^-1(x), is simply a right-circular rotation of the binary representation of x as opposed to a left-circular rotation for the ordinary shuffle permutation σ(x)].

The input-output mappings performed by the 2 x 2 switch-nodes may be either strict permutations of the inputs, or may include the upper and lower broadcast mappings u_i(x) and l_i(x), where

u_i(x) = a_n, ... , a_i+1, 0, a_i-1, ... , a₁ and l_i(x) = a_n, ... , a_i+1, 1, a_i-1, ... , a₁

A general 2 x 2 switch-node routing function, E_i, can therefore be defined as a choice of one of the four switch settings illustrated in Figure 3, expressed formally as

E_i(x) = {ε_i | I | u_i | l_i}(x)

If only strict permutations are allowed, i.e. only ε_i(x) and I(x), then a single control-bit per switch-node is all that is required to configure the network. If upper and lower broadcasts are allowed, then two control bits per switch-node are needed. A Beneš network using strict permutation switches is capable of connecting all N! permutations of N inputs, and if upper and lower broadcasts are supported then all N^N well-defined input-to-output mappings can be connected. The Beneš network is known as a rearrangeable network since the switch settings can always be rearranged to accommodate any change of input-to-output mapping.