Patent ID: 7982497

Claim:
A non-blocking interconnection network, comprising: a plurality of global inputs; a plurality of global outputs; and a plurality of routing circuits collectively coupling the plurality of global inputs to the plurality of global outputs in a non-blocking manner, wherein each routing circuit includes: a first multiplexer including a first set of inputs and a first internal output, the first set of inputs coupled to two global inputs of the plurality of global inputs, the first multiplexer configured to provide a selected input of the first set of inputs to the first internal output in response to a first selection input, a second multiplexer including a second set of inputs and a second internal output, the second set of inputs coupled to the two global inputs of the plurality of global inputs and to a second internal output from a first other one of the routing circuits, the second multiplexer configured to provide a second selected input of the second set of inputs to the second internal output in response to a second selection input, a third multiplexer including a third set of inputs and a first global output, the third set of inputs coupled to the two global inputs of the plurality of global inputs, to the first internal output from the first other routing circuit, and to a second internal output from a second other one of the routing circuits, the third multiplexer configured to provide a third selected input of the third set of inputs to the first global output in response to a third selection input, and a fourth multiplexer coupled to the third set of inputs and including a second global output, the fourth multiplexer configured to provide a fourth selected input of the third set of inputs to the second global output in response to a fourth selection input.