System, apparatus and method for data path routing configurable to perform dynamic bit permutations
View Patent ↗A system, apparatus and a method for routing data over fewer switches and interconnections among reconfigurable logic elements, and for adapting routing resources to dynamically perform complex bit-level permutations, such as shifting and bit reversal operations. In one embodiment, an exemplary silo routing circuit is formed upon a semiconductor substrate and routes data among a number of reconfigurable computational elements. The silo routing circuit comprises a plurality of input terminals and a plurality of output terminals. Further, the silo routing circuit includes a multi-stage interconnection network (“MIN”) of switches configurable to form data paths from any input terminal to any output terminal.
1. A silo routing circuit formed upon a semiconductor substrate to route data among a number of reconfigurable computational elements, the silo routing circuit comprising:
a plurality of input terminals and a plurality of output terminals, said plurality of input terminals including an input terminal and said plurality of output terminals including a first output terminal and a second output terminal;
a multi-stage interconnection network (“MIN”) of a plurality of switches configurable to form data paths from any of said plurality of input terminals to any of said plurality of output terminals; and
a subset of a plurality of configuration data terminals configured to select a selected subset of switches to form one path of said data paths from said input terminal to either said first output terminal or to said second output terminal, said second output terminal being at a distance from said first output terminal, said distance being defined by a bit vector applied to said subset of configuration data terminals said distance being a displacement in a quantity of output terminals from said first output terminal, each input terminal from said plurality of input terminals and each output terminal from said plurality of output terminals are uniquely identified as consecutive numbers from input zero (“P. 0 ”) to input “N” (“P.N”) and from output zero (“Q.0”) to output “N” (“Q.N”), respectively each input terminal from said plurality of input terminals and each output terminal from said plurality of output terminals are similarly numbered from a row of switches from said plurality of switches, each switch of said row of switches being a binary switch having at least a first input configured to receive data from said row of switches and a second input configured to receive data from another row of switches located 2 M−k rows from said row of switches.
2. The silo routing circuit of claim 1 , wherein each switch of said selected subset is further configured to either statically route data from said input terminal to either said first output terminal or said second output terminal in accordance with a bit of said bit vector, or to dynamically route data from said input terminal to a third output terminal in accordance with a dynamic control signal.
3. The silo routing circuit of claim 2 , wherein static routing of data requires loading said bit vector into a configuration register and dynamic routing of data does not.
4. The silo routing circuit of claim 2 , wherein each switch of said selected subset includes an embedded storage element to internally store said bit, where said bit is transported via an input terminal rather than via a dedicated interconnection for carrying only said bit.
5. The silo routing circuit of claim 2 , wherein static routing of data is the unaltered transfer of data from at least one reconfigurable computational element to another and dynamic routing of data includes performing a bit permutation.
6. The silo routing circuit of claim 1 , wherein said distance, D, is determined as
D=Q−P,
if said input terminal, P, is numbered less than second output terminal, Q, and
D=Q−P+N,
if said input terminal, P, is numbered greater than second output terminal, Q.
7. The silo routing circuit of claim 1 , wherein said silo routing circuit is configured to couple to another silo routing circuit that includes said another row.
8. The silo routing circuit of claim 1 , further comprising:
a vertical extension circuit configured to select a vertical input from either a top silo routing circuit or a bottom silo routing circuit, whichever includes said another row; and
a horizontal extension circuit configured to select either said vertical input or said input terminal as said first input into at least one switch in a first stage.
9. The silo routing circuit of claim 8 , further comprising: a “distance-1” stage circuit for minimizing blockage conditions, said “distance-1” stage circuit including at least one switch for selecting as said first input data from either said input terminal of said row or from another input terminal from an adjacent row.
10. A silo routing circuit formed upon a semiconductor substrate to route data among a number of reconfigurable computational elements, the silo routing circuit comprising:
a plurality of input terminals and a plurality of output terminals, said plurality of input terminals including an input terminal and said plurality of output terminals including a first output terminal and a second output terminal;
a multi-stage interconnection network (“MIN”) of a plurality of switches configurable to form data paths from any of said plurality of input terminals to any of said plurality of output terminals; and
a subset of a plurality of configuration data terminals configured to select a selected subset of switches to form one path of said data paths from said input terminal to either said first output terminal or to said second output terminal, said second output terminal being at a distance from said first output terminal, said distance being defined by a bit vector applied to said subset of configuration data terminals, said distance being a displacement in a quantity of output terminals from said first output terminal, each input terminal from said plurality of input terminals and each output terminal from said plurality of output terminals are uniquely identified as consecutive numbers from input zero (“P. 0 ”) to input “N” (“P.N”) and from output zero (“Q.0”) to output “N” (“Q.N”), respectively, each input terminal from said plurality of input terminals and each output terminal from said plurality of output terminals are similarly numbered from a row of switches from said plurality of switches, each switch of a row of switches being a binary switch having at least a first input configured to receive data from said row of switches and a second input configured to receive data from one other row of switches located either only at 2 M−k rows in one direction from said row of switches or only at 2 M−k rows in another direction from said row of switches.
11. The silo routing circuit of claim 10 , wherein fewer interconnects are necessary to route said second input to said one other row being in either only said one direction or only said another direction from said row than to route said second input to said another row located at 2 M−k rows in any direction from said row, said fewer interconnects resulting in reduced circuit area.