4
$\begingroup$

I was reading about Benes Network construction in this book. Their construction is easy for a number of inputs and outputs that is an exponent of two.

However it seems to me that for a number of i/o that falls between $2^{n}$ and $2^{(n+1)}$ one has to construct a network with $2^{(n+1)}$ ports and leave many unattached, which is wasteful. Is there a synthesis method for Benes networks or maybe an alternative topology that has the same properties (re-arrangeable not blocking) for arbitrary number of I/O?

$\endgroup$
3
$\begingroup$

Wasting ports to achieve an exact number of terminals is a common attribute of staged networks (butterfly, benes, folded-clos, etc.). The mesh, torus, and flattened butterfly topologies are a bit better because each dimension can have a different width, but this results in having uneven bisection bandwidth along each dimensional cut. The HyperX topology is a generalization of the flattened butterfly that allows each dimension to be configured independently in terms of width and weight (number of links connecting each pair of routers). The paper describes an algorithm to find the "optimal" configuration given a requirement for system size, bisection bandwidth, and router radix. An implementation of this algorithm is here. Given the requirements, it finds a satisfactory topology configuration that minimize cost (like wasted ports).

$\endgroup$
2
$\begingroup$

This paper [1] presents a method to construct arbitrarily sized benes networks using a recursive approach.

  1. Arbitrary Size Benes Networks by Chihming Chang and Rami Melhem in Parallel Processing Letters, Volume 7, 1997
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.