Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2002-06-05
2004-07-06
Tran, Anh Q. (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000, C326S047000
Reexamination Certificate
active
06759869
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to uses made of field programmable gate arrays (FPGAs), in particular to use of an FPGA to route information from selected input points to selected output points.
BACKGROUND
FPGAs are frequently used for telecommunication. An essential aspect of telecommunication is the ability to route information from any source to any desired destination. A crossbar switch accomplishes this purpose.
FIG. 1
shows a simple crossbar switch. Eight input lines IN
0
through IN
7
carry input signals and eight output lines OUT
0
through OUT
7
provide output signals. An array of connectors can be selectively turned on to provide any of the input signals as an output signal. For example, turning on connector C
0
,
0
connects input line IN
0
to output line OUT
0
. Turning on connector C
0
,
7
connects input line IN
0
to output line OUT
7
. It is important that an output line not be driven by more than one input signal so that no contention occurs, and for this reason, crossbar switches are often implemented as multiplexers.
FIG. 2
shows a multiplexer implementation of the crossbar switch of
FIG. 1
, in which multiplexer control signals select one and only one of the input signals to provide as an output signal. For example, multiplexer control signals A
0
select which of the eight input signals IN
0
through IN
7
will be provided as output signal OUT
0
.
As the number of input and output signals increases, the size of the crossbar switch becomes larger in proportion to the product of the number of input and output signals. For example, an array accommodating 1000 input signals and 1000 output signals would require a million connectors. If implemented with multiplexers, the crossbar switch would require 1000 multiplexers, each with 1000 input signals. U.S. Pat. No. 6,288,568 to Bauer and Young entitled “FPGA Architecture With Deep Look-Up Table RAMs” describes an FPGA architecture having lookup tables that can generate a function of eight input signals.
FIG. 3
is a copy of
FIG. 20
of the Bauer and Young patent and represents one configurable logic block (CLB) of to an FPGA. One possible function that can be generated by this flexible structure is a multiplexer. In
FIG. 3
, the lookup tables are 4-input lookup tables (LUTs), and thus each LUT can implement a 2-input multiplexer. The inputs applied on three of the lines F
1
, F
2
, F
3
, and F
4
or G
1
, G
2
, G
3
, and G
4
to each 4-input LUT are two multiplexer data inputs and one multiplexer control input. Eight lookup tables are present in the CLB of
FIG. 3
, each labeled LUT-F or LUT-G.
To form a conventional crossbar switch, the LUTs are each configured to implement a 2-input multiplexer with these three inputs. Sixteen data signals can be applied to these eight LUTs, two to each LUT. The lowest order multiplexer control bit C
0
is applied to all eight LUTs and serves as the control bit for each of the eight 2:1 multiplexers. The next lowest order control bit C
1
is applied to each of four multiplexers labeled F
5
, which receive outputs from pairs of the LUTs. Thus the outputs of the F
5
multiplexers are 4:1 multiplexer outputs. Pairs of the F
5
multiplexers feed F
6
multiplexers as controlled by control bit C
2
, and pairs of the F
6
multiplexers feed the F
7
multiplexer as controlled by control bit C
3
. The F
7
multiplexer thus provides the output of a 16:1 multiplexer. Another structure the same as
FIG. 3
but receiving 16 different input signals receives the same control signals C
0
through C
3
. The F
8
multiplexer receives input signals from two F
7
multiplexers and is controlled by a still higher order control bit C
4
to produce a 32:1 multiplexer output signal. Thus an adjacent pair of CLBs can implement a 32:1 multiplexer.
Of course, providing these data and control signals requires routing through the FPGA. This routing has not been shown because it is easy to understand that the necessary route for each signal is formed by programmably connecting together the interconnect lines to get the data and control input signals from their origins and to get the output signals to their destinations.
Still wider multiplexer functions are formed by using another level of hierarchy. For example, a 1024:1 multiplexer can be formed in a very large FPGA by configuring 32 additional pairs of CLBs to each implement a 32:1 multiplexer, then finally forming a higher level structure, also from two CLBs, in which the input signals are the F
8
output signals from the 32 pairs of CLBs. Thus the output of this final structure is the output of a 1024:1 multiplexer, and has consumed 64+2 CLBs or 66 CLBs. A square crossbar switch (1024 inputs and 1024 outputs) would require 1024 of these structures or a total of 67,584 CLBs.
One of the largest FPGA available from Xilinx Inc. today has on the order of 8,000 CLBs, so such a switch can not be implemented this way in such an FPGA but would require about 9 FPGAs.
It would be desirable to implement a large crossbar switch in an FPGA in a manner that is denser than this prior art implementation, preferably one that will fit into a single FPGA.
SUMMARY OF THE INVENTION
According to the invention, a switch such as a crossbar switch is implemented in an FPGA by using the FPGA's configuration memory cells to control multiplexers that perform the routing of signals through the switch. Thus, the multiplexer control is established during configuration or reconfiguration of the FPGA and the multiplexer input data passes through the configuration multiplexers. This contrasts with the above described prior art implementation babe both the multiplexer input signals and the multiplexer control signals are applied to inputs pins of the FPGA after it has been configured. In one embodiment, the invention is implemented in an FPGA in which each CLB of the FPGA has several LUTs, for example eight 4-input LUTs, and an input multiplexer (IMUX) routes signals to each LUT. The IMUX receives control signals from the configuration memory cells. Rather than changing the switch configuration by changing control input signals, the switch configuration is changed by reconfiguring one or several IMUXs of the FPGA.
As an optional feature of the invention, an input signal applied to a single pin is deserialized and applied to several different internal input lines. In one embodiment, each input signal on one input pin is applied to four different input lines. Likewise, four output signals are serialized and placed onto a single output pin. For an FPGA with a given number of pins, this increases the amount of logic the FPGA can process. An FPGA having on the order of 250 input pins and 250 output pins (or 500 I/O pins) can implement a 1000×1000 crossbar switch by making use of a 4:1 serializer/deserializer (SERDES) feature. If each input and output signal is applied to two pins as a low voltage differential signal (LVDS), and a 4:1 SERDES is used, 1000 physical pins are required for a 1000×1000 crossbar switch.
Of course, consideration must be made for how the user changes or partly changes the configuration in order to reconfigure the IMUXs. Changing control signals in the IMUX is slower than simply applying a new multiplexer control signal to a LUT, as described above for a prior art crossbar switch implementation. However, in some applications this is acceptable because data needs to flow at high speed, but its destination changes only occasionally. Some FPGAs are reconfigured by shifting data into a configuration frame register in the FPGA and loading the frame register data into the designated frame. It may be necessary to load a full frame of data during a partial reconfiguration. In Virtex-II FPGAs available from Xilinx, Inc., this is true. An IMUX can be reconfigured by loading four frames of data. Typically, the user will want to disconnect one input terminal from an output terminal and connect another input terminal to the output terminal. This operation requires loading no more than six frames of configuration data and takes about
Alfke Peter H.
Bauer Trevor J.
Fewer Colm P.
Young Steven P.
Liu Justin
Tran Anh Q.
Webostad W. Eric
Xilinx , Inc.
Young Edel M.
LandOfFree
Large crossbar switch implemented in FPGA does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Large crossbar switch implemented in FPGA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large crossbar switch implemented in FPGA will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3209947