Batcher-banyan network
AssigneeBell Communications Research, Inc.
InventorsChester M. Day, Jr., James N. Giacopelli
Life of this patent
Estimating the term…
Abstract
A Batcher-banyan network which may be implemented using only two different IC chip designs is disclosed. The chips comprising the Batcher banyan network are arranged in adjacent horizontal and vertical stacks to minimize the lengths of electrical conductors connecting the chips.
Claims13
A Batcher-banyan network implemented in three dimensions comprising:
- a Batcher network including:
- a first stage comprising a stack of horizontally oriented Batcher subnetworks,
- at least second, third and fourth stages each comprising a stack of horizontally oriented fixed over merge subnetworks, and
- at least fifth, sixth and seventh stages comprising vertically oriented stacks of merge networks of increasing order, said fifth, sixth and seventh stages being located to interconnect said first and second stage, said second and third stages, and said third and fourth stages respectively, and
- a banyan network including a stack of vertically oriented banyan subnetworks and a stack of horizontally oriented banyan subnetworks.
A Batcher network comprising alternating horizontal and vertical stacks of chips, each said chip comprising a plurality of Batcher cells, each of said cells including first and second inputs, first and second outputs, selector mean for connecting in a first state the first input to the first output and the second input to the second output and for connecting in a second state the first input to the second output and the second input to the first output, decision means responsive to packets arriving at said inputs for determining whether said selector means is in said first state or said second state and means for disabling said selector means into said first state independent of the addresses in said pacets.
An N.times.N batcher network implemented in three dimensions comprising:
- a horizontally oriented stack of .sqroot.N.times..sqroot.N Batcher subnetworks, where the .sqroot.N is an integer greater than 1,
- at least first, second and third horizontally oriented stacks of .sqroot.N.times..sqroot.N merge networks,
- a vertically oriented stack of 2.times.2 merge subnetworks located between said first and second horizontally oriented stacks of .sqroot.N.times..sqroot.N merge subnetworks,
- a vertically oriented stack of 4.times.4 merge subnetworks located between said second and third horizontally oriented stacks of .sqroot.N.times..sqroot.N merge subnetworks, and
- a vertically oriented stack of 8.times.8 merge subnetworks located between said third and fourth horizontally oriented stacks of .sqroot.N.times..sqroot.N merge subnetworks.
A Batcher network comprising:
- a first plurality of stages comprising stacks of fixed order merge subnetworks,
- a second plurality of stages comprising stacks of increasing order merge subnetworks, said stages of said second plurality being located in between and oriented perpendicular to the stages of the first plurality for interconnecting the stages of the first plurality.
An N.times.N banyan network implemented in three dimensions comprising
- a horizontally oriented stack of .sqroot.N.times..sqroot.N banyan subnetworks, where the .sqroot.N is an interger greater than 1, and
- a vertically oriented stack of .sqroot.N.times..sqroot.N banyan subnetworks connected to said horizontally oriented stack of banyan subnetworks.
A cell for use in a Batcher network comprising
- first and second inputs for receiving first and second packets, respectively, each of said packets including a destination address,
- first and second outputs,
- selector means for connecting in a pass state the first input with the first output and the second input with the second output and for connecting in a cross state the first input with the second output and the second input with the first output,
- decision means responsive to said addresses for determining whether said selector means is in said pass state or said cross state, and
- disabling means associated with said decision means and responsive to a disabling signal for causing said selector to be in one of said states independent of said addresses.
A Batcher network comprising:
- a first stage comprising a plurality of Batcher subnetworks,
- at least second, third and fourth stages each comprising a plurality of fixed order merger subnetworks, and
- at least fifth, sixth and seventh stages comprising pluralities of 2.times.2, 4.times.4 and 8.times.8 merge networks, respectively,
- said fifth stage being located between said first and second stages, said sixth stage being located between said second and third stages, and said seventh stage being located between said third and fourth stages.
Dependencies are inferred from the claim text.