Interconnection network for a field programmable gate array

CROSS-REFERENCES TO RELATED APPLICATIONS

0001This patent application claims priority from Provisional Patent Application No. 60/223,047, filed Aug. 4, 2000, and is a continuation of U.S. patent application Ser. No. 09/923,294, filed Aug. 3, 2001 is now a U.S. Pat. No. 6,693,456, all of which are hereby incorporated by reference.

BACKGROUND OF THE INVENTION

0002The present invention relates to integrated circuit interconnections and, in particular, to the interconnection architecture of FPGA (Field Programmable Gate Array) integrated circuits.

0003FPGAs are integrated circuits whose functionalities are designated by the users of the FPGA. The user programs the FPGA (hence the term, “field programmable”) to perform the functions desired by the user.

0004A very significant portion of an FPGA's design is the integrated circuit's interconnection network between the logic cells or blocks, which perform the functions of the FPGA. Heretofore, the current practice for designing an FPGA interconnection architecture has been empirical and on an ad hoc basis. The goal of the FPGA designer has been to create an interconnect structure which is sufficiently flexible to implement the required wiring for any circuit design intended for the FPGA, and yet occupies a minimal amount of area of the integrated circuit and with a minimal amount of transmission delay. In today's FPGA products, the interconnect network typically occupies about 90% of the chip area and the actual logic cells occupy only about 5% of the chip. In other words, most of the area of the integrated circuit is not dedicated to the circuits performing desired functions of the FPGA, but rather to the interconnections between those circuits.

0005Furthermore, the current practice for designing FPGA interconnects is empirical and on an ad hoc basis. The users of these FPGA products spend most of their design time trying to make their circuits route to obtain the desired functions and to meet the timing constraints. The rule of thumb is to only utilize 50% of the available logic cells in order to guarantee they can all be routed through the interconnect network. If the timing constraints are relatively high speed, then the rule of thumb is to only utilize 33% of the logic cells in order to avoid the need for detours and longer delays in the routing.

0006Hence, there is a need for an FPGA interconnection network architecture by which routing through the resulting interconnect network is guaranteed and that the timing constraints of the interconnect network are predictable. The present invention provides for such an interconnection network.

SUMMARY OF THE INVENTION

0007The present invention provides for an integrated circuit having a plurality of logic cells; and a programmable network interconnecting the logic cells. The programmable interconnection network has a plurality of interconnection network input terminals; a plurality of programmable switches, each programmable switch having a plurality of input terminals and output terminals with the programmable switch arranged so that signals on any input terminal are passed to any output terminal. The plurality of programmable switches interconnecting the plurality of interconnection network input terminal to the interconnection network output terminal are arranged in a Benes network so that connections between the interconnection network input terminals and interconnection network output terminals are rearrange able.

0008The plurality of programmable switches are arranged in hierarchical levels with a first level of the programmable switches having input terminals connected to the interconnection network input terminals and a last level of the programmable switches having output terminals connected to the interconnection network output terminals. The levels of the programmable switches intermediate the first and last level are arranged in a plurality of first rank sub-interconnection networks equal to the number of switch output terminals. Each first rank sub-interconnection network is connected to an output terminal of each programmable switch in the first level and connected to an input terminal of each programmable switch in the last level. In a similar arrangement, the first rank sub-interconnection networks themselves are formed from second rank sub-interconnection networks and so forth.

BRIEF DESCRIPTION OF THE DRAWINGS

0009<figref idref="DRAWINGS">FIG. 1</figref> is a diagram of the interconnection architecture of a current SRAM-based FPGA;

0010<figref idref="DRAWINGS">FIG. 2A</figref> is a diagram of one operation of a 2×2 switch for a Benes network; <figref idref="DRAWINGS">FIG. 2A</figref> is a diagram of another operation of a 2×2 switch for a Benes network; <figref idref="DRAWINGS">FIG. 2C</figref> is a block diagram of the elements of a 2×2 switch;

0011<figref idref="DRAWINGS">FIG. 3A</figref> illustrates the organization of an 8×8 Benes network with 2×2 switches in accordance with one embodiment of the present invention; <figref idref="DRAWINGS">FIG. 3B</figref> illustrates the interconnection between the switches at the first rank of hierarchy; <figref idref="DRAWINGS">FIG. 3C</figref> illustrates the interconnection between the switches at the next lower rank of hierarchy; <figref idref="DRAWINGS">FIG. 3D</figref> shows the complete interconnection of the 8×8 Benes network; <figref idref="DRAWINGS">FIG. 3E</figref> is an example of a permutation of connections in the 8×8 Benes network to reverse the order of input signals at the output terminals of the network;

0012<figref idref="DRAWINGS">FIG. 4A</figref> shows how the 8×8 Benes network is folded for an FPGA interconnection network in accordance with an embodiment of the present invention; <figref idref="DRAWINGS">FIG. 4B</figref> shows the resulting folded Benes network; <figref idref="DRAWINGS">FIG. 4C</figref> illustrates the <figref idref="DRAWINGS">FIG. 4B</figref> folded network in which the interconnections have been inverted by level;

0013<figref idref="DRAWINGS">FIG. 5</figref> shows two exemplary logic cells connected to a combined switch of the <figref idref="DRAWINGS">FIG. 4C</figref> network in which the combined switch provides for corner turn routing in accordance with an embodiment of the present invention;

0014<figref idref="DRAWINGS">FIG. 6A</figref> illustrates the four elementary states of the combined switch; <figref idref="DRAWINGS">FIG. 6B</figref> illustrates 10 additional states of an enhanced combined switch for corner turn routing in accordance with the present invention;

0015<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram of the enhanced combined switch described with respect to <figref idref="DRAWINGS">FIGS. 6A and 6B</figref>;

0016<figref idref="DRAWINGS">FIG. 8</figref> illustrates the four states with the input stage of the combined switch having fanout capability;

0017<figref idref="DRAWINGS">FIG. 9</figref> illustrates an exemplary arrangement to create fanout functions with an FPGA interconnect network in accordance with an embodiment of the present invention;

0018<figref idref="DRAWINGS">FIG. 10</figref> shows a pair of enhanced switches with timing latches in accordance with an embodiment of the present invention;

0019<figref idref="DRAWINGS">FIG. 11A</figref> is a block diagram of an exemplary circuit pipeline with mismatched delay paths; <figref idref="DRAWINGS">FIG. 11B</figref> is a block diagram of a modified <figref idref="DRAWINGS">FIG. 11A</figref> circuit pipeline with the delay paths corrected in accordance with an embodiment of the present invention;

0020<figref idref="DRAWINGS">FIG. 12</figref> is a flow chart of a software generator for an FPGA, in accordance with an embodiment of the present invention;

0021<figref idref="DRAWINGS">FIG. 13A</figref> illustrates an exemplary column-based floorplan layout of an FPGA according to an embodiment of the present invention; <figref idref="DRAWINGS">FIG. 13B</figref> illustrates how two of the <figref idref="DRAWINGS">FIG. 13A</figref> columns are interconnected;

0022<figref idref="DRAWINGS">FIG. 14A</figref> shows the column-based layout of <figref idref="DRAWINGS">FIG. 13B</figref> with all the cells labeled; <figref idref="DRAWINGS">FIG. 14B</figref> illustrates the same topological network arranged in a tree-based layout in accordance with the present invention; and <figref idref="DRAWINGS">FIG. 14C</figref> shows a modification of the <figref idref="DRAWINGS">FIG. 14B</figref> tree-based layout with wirelengths between switch levels minimized.

DESCRIPTION OF THE SPECIFIC EMBODIMENTS

0023Current SRAM (Static Random Access Memory)-based FPGA products conform to the interconnect architecture as illustrated in FIG. <b>1</b>: The basic structure of <figref idref="DRAWINGS">FIG. 1</figref> has logic cells <b>10</b>, which implement the desired circuit logic by the user, connection cells <b>11</b> which connect logic cells <b>10</b> to the interconnect network, and switch cells <b>12</b> which implement the interconnect network. Additional connections are made between a switch cell <b>12</b> and its four neighboring switch cells <b>12</b> in the north, east, west, and south directions. The switch cells <b>12</b>, connection cells <b>11</b>, and all their wires and connections constitute the interconnect network of the FPGA. This basic unit is arrayed to build FPGAs of varying sizes.

0024The flexibility of this architecture lies within the connection cell <b>11</b> and the switch cell <b>12</b>. In common terminology, a fully “populated” connection cell <b>11</b> will connect each pin of the logic cell <b>10</b> to every wire connecting to the switch cell <b>12</b>. A “depopulated” connection cell <b>11</b> will connect each pin of the logic cell to a subset of the wires connecting to the switch cell <b>12</b>, with each pin connecting to a different, possibly overlapping, subset of wires. Similarly, a fully “populated” switch cell will provide full crossbar connections between all the wires on all four of its sides, and a “depopulated” switch cell will only provide a subset of these connections. Lastly, the set of wires between any two cells is called a “channel”, and the number of wires in a channel can be varied.

0025Each possible connection in the FPGA interconnect network requires its own pass gate and controlling configuration bit. A fully populated interconnect network is prohibitively expensive to implement and the current practice has been to build a parameterized software model that can represent varying depopulated interconnect networks. Then various representative logic designs are tried onto the modeled networks. Based on this empirical data, a judgment must be made about what constitutes an “acceptable” interconnect network in terms of routability versus implementation cost. This is an ad hoc process since there are no theoretical guarantees of routability, i.e., that the desired interconnections can actually be made.

0026A further complication in the above empirical process has been that the demands on the interconnect network do not scale linearly with the number of logic cells in the array. In other words, an interconnect network that seems to route most designs on an array with 1K logic cells cannot simply be replicated for a 64K logic cell array. As seen empirically, the routing demands grow exponentially, but these demands are highly dependent on the exact algorithms used to implement the design. Specifically, it depends on the algorithms used to map the original circuit design onto the logic cells, to place the logic cells on the array, and to route (connect) the logic cells to each other. There is currently no precise theoretical model of this growth in wiring demand, although current practice has been to approximate the wiring demand with stochastic models. The use of these models entails some assumptions for certain coefficients, which are based on empirical data, and so current practice is still an ad hoc process.

0027In contrast, the present invention provides for an FPGA interconnection network architecture which creates interconnection networks which are “rearrangeable,” i.e., any permutation of interconnections from the network's input terminals to the output terminals can be implemented. The resulting FPGA network interconnect has guaranteed routing with defined maximum timing delays and is scalable.

0028The present invention uses the so-called Benes network, which has been the subject of research in the telecommunications field, specifically for switching networks. Generally described, a Benes network interconnects a number of network input terminals to a number of network output terminals. Between the input and output terminals are switches, each switch itself having input terminals and a number of output terminals and the ability to pass signals on any input terminal to any output terminal. The switches are connected in hierarchical levels with a first level of switches having input terminals connected to the network input terminals and a last level of the switches having output terminals connected to the network output terminals. The levels of the switches intermediate the first and last levels are arranged in a plurality of first rank sub-interconnection networks equal to the number of switch input (and output) terminals, each first rank sub-interconnection network connected to an output terminal of each switch in the first level and connected to an input terminal of each switch in the last level. The first rank sub-interconnection networks are formed by second level switches having input terminals connected to the output terminals of the first level switches and second-to-the-last level switches having output terminals to the input terminals of the last level of switches. The levels of switches intermediate the second and second-to-the-last level are arranged in a plurality of second rank sub-interconnection networks equal to the number of switch output terminals with each second rank sub-interconnection network connected to an output terminal of each second level switch and connected to an input terminal of each second-to-the-last level switch.

0029A switch level hierarchy is formed because each rank sub-interconnection network is formed like the rank sub-interconnection network above. That is, each rank sub-interconnection network is formed by a plurality of switches in one level, the switches having input terminals connected to output terminals of switches of a sub-interconnect network rank immediately higher; and a corresponding level of switches having output terminals connected to input terminals of switches of the sub-interconnect network ran immediately higher; and the levels of the switches intermediate the switches in the one and corresponding levels arranged in a plurality of lower rank sub-interconnection networks equal to the number of switch output terminals, each lower rank sub-interconnection network connected to an output terminal of each switch in the one level and connected to an input terminal of each switch in the corresponding level. To define the hierarchical level arrangement of the switches.

0030The particular Benes network described immediately below explains the switch hierarchy with specificity. This network is also useful to implement an FPGA according to the present invention.

0000Benes Network With 2×2 Switches

0031The building block of the described Benes network is the 2×2 (2 input, 2 output) switch <b>20</b>, having operations illustrated in <figref idref="DRAWINGS">FIGS. 2A and 2B</figref>. The 2×2 Benes switch <b>20</b> has two possible configuration modes: pass and cross. In pass mode illustrated by <figref idref="DRAWINGS">FIG. 2A</figref>, a signal on input A is passed straight to output C, and a signal on input B is passed straight to output D. In cross mode illustrated by <figref idref="DRAWINGS">FIG. 2B</figref>, a signal on input A crosses over to output D and a signal on input B crosses over to output C. A single configuration or control bit can control these two modes.

0032The switching itself can be implemented with two 2:1 multiplexers or MUX's as shown by FIG. <b>2</b>C. The switch <b>20</b> has two MUXs <b>21</b> and <b>22</b> having two input nodes which are each connected to one of the input terminals, input A or input B, of the switch <b>20</b>. The output node of the MUX <b>21</b> forms the output terminal, output A, and the output node of the MUX <b>22</b> forms the output terminal, output B, of the switch <b>20</b>. Both MUXs <b>21</b> and <b>22</b> are connected to a control line <b>23</b> which carries the configuration or control bit. The entire switch cell only requires 18 transistors in a CMOS (Complementary Metal-Oxide-Semiconductor) implementation of an integrated circuit.

0033These 2×2 switches are connected in a specific topology to build a Benes network. For the purpose of illustration, the arrangement of the 2×2 switches <b>20</b> in an 8×8 Benes network is shown in FIG. <b>3</b>A. For a network with N inputs and N outputs, N being a power of 2, there are (2*(log₂N)−1) levels of switches, each level consisting of N/2 switches. In this example of an 8×8 network, each level has 4 switch cells and there are 5 levels. The interconnection between the switches <b>20</b> can best be understood by viewing the network in a hierarchical arrangement, starting from the outside and proceeding inwards. We can view the two outermost levels, levels <b>1</b> and <b>5</b>, in detail and view the inner levels as hierarchical blocks, as illustrated by FIG. <b>3</b>B. The inner levels can be viewed as two hierarchical blocks, an Upper Network <b>25</b> and a Lower Network <b>26</b>. In level <b>1</b>, each switch cell <b>20</b> has one output going to the Upper Network <b>25</b>, and one output going to the Lower Network <b>26</b>. Similarly in level <b>5</b>, each switch cell has one input from the Upper Network <b>25</b>, and one input coming from the Lower Network <b>26</b>.

0034At the next level of the hierarchy of the Benes network, the details of the Upper Network <b>25</b> and the Lower Network <b>26</b> are expanded in FIG. <b>3</b>C. The Upper Network <b>25</b> is formed by switches <b>20</b> in levels <b>2</b> and <b>4</b>, and Upper and Lower Networks <b>27</b> and <b>28</b> respectively. The Lower Network <b>26</b> is formed by switches <b>20</b> in levels <b>2</b> and <b>4</b>, and its own Upper and Lower Networks <b>29</b> and <b>30</b> respectively. Each of these networks <b>27</b>-<b>30</b> are half the size of the higher level networks <b>25</b> and <b>26</b> and are similarly decomposed into their own Upper and Lower Networks: In this example of an 8×8 network, the bottom of the hierarchy has been reached since the lower level networks <b>27</b>-<b>30</b> are switches <b>20</b> in level <b>3</b>. For larger networks, a similar decomposition into the Upper and Lower Networks may be performed until the bottom of the hierarchy is reached. The complete interconnection of the constituent switches <b>20</b> in the 8×8 Benes network is illustrated by FIG. <b>3</b>D.

0035The Benes network of <figref idref="DRAWINGS">FIG. 3D</figref> is not configured with only the hard-wired connections between the switch cells <b>20</b> illustrated. This network can potentially implement any permutation of signals on input terminals to output terminals. In order to configure the network to implement a specific routing, each switch cell <b>20</b> must be individually configured as either “pass” or “cross” mode described previously. The example of <figref idref="DRAWINGS">FIG. 3E</figref> shows the configuration of the network to implement an order reversal from the inputs to the outputs:

0036Note that there are many variations of the Benes network. The hierarchical sub-division into Upper and Lower networks can be generalized to more than 2 sub-networks, so networks of the size pⁿ, p>2, can be constructed. Also, the sub-division does not require that the sub-networks be of equal size. This generalized construction leads to overall Benes networks with arbitrary numbers of inputs and a proportional number of switch cells. All variants are simply be referred to as Benes networks.

0037The Benes network is a very powerful and efficient interconnection network with guaranteed routability. Its use has not been more widespread because of the complexity of the algorithm required to determine the appropriate configuration of the switches for a specific routing. The Benes network is “rearrangeable,” but not “non-blocking.” Non-blocking means that any input-to-output connection can always be made, even if there are already existing connections on the network. Rearrangeable is less powerful and means that any input-to-output connection can be made, but some existing connections may need to be rerouted. In the dynamic worlds of telephone switching and data communication networks, a Benes network would require that a routing algorithm be performed every time a new connection is requested. A Benes routing algorithm requires time O(Nlog₂N), but the network itself transmits data in time O(log₂N). It takes longer to reconfigure the network than to actually transmit the data through the network. Hence, current practice in the data communications has to use more expensive non-blocking switches.

0038However, the present invention recognizes that in the FPGA world, routing is not so dynamic. There is no real time set up and tear down of fleeting connections. Instead, in an offline process, a circuit design is mapped onto the FPGA integrated circuit once and the resulting interconnect configuration is used without change. Even in the application of FPGA technology to the burgeoning field of “reconfigurable logic”, multiple configurations may be rapidly swapped in and out of the FPGA, but each configuration itself is never changed. Presently, the offline routing process in an FPGA requires on the order of minutes or even hours of execution time. In contrast, the execution of a Benes routing algorithm requires in the order of 10 seconds (which is completely unacceptable in a data communications network) in accordance with the present invention. This time is spectacularly fast and routability is guaranteed.

0000Specific Implementation of Benes Network in FPGAs

0039There are a number of ways that the Benes network may be adapted to make it more efficient as an interconnection network for an FPGA or MPGA (Mask Programmable Gate Array). In an FPGA, the logic is composed from building blocks called “logic cells”, and the logic cells contain both input and output pins. An example of a typical logic cell is a 2-input NAND gate. So an FPGA interconnection network should have neighboring “leaf cells” which correspond to the logic cells and which contain both inputs and outputs to make the connections to the logic cells. This can be accommodated by “folding in half” the original Benes network, and combining the switch cells <b>20</b> from the first level and last level, the second level and second-to-last level, and so on. This is illustrated in <figref idref="DRAWINGS">FIG. 4A</figref> with the 8×8 network example. The “folding” is made along the dotted line <b>31</b> which runs through the switches <b>20</b> in level <b>3</b>. The switches <b>20</b> are labeled by location in the network to maintain identification through the folding operation. The first number in the labels identifies the level of the switch and the second number its row location. Hence switch with label, “4.3,” is in level <b>4</b> and row <b>3</b>.

0040The resulting folded network is illustrated by FIG. <b>4</b>B. The switches <b>20</b> are combined into two, with the formerly level <b>3</b> switches duplicated for uniformity. While the combined switches <b>32</b> represent a topological change of the 8×8 Benes network, it should be noted that the connections between the cells <b>20</b> remain the same. The combined input and output switch cells <b>32</b> on the left of the folded network, e.g., combined switches <b>1</b>.<b>2</b> and <b>5</b>.<b>2</b>, form the leaf cells for the connection to the pins of the FPGA logic cells.

0041From the connections between the combined switches <b>32</b>, the network of <figref idref="DRAWINGS">FIG. 4B</figref> can be turned “inside out”, that is, the innermost levels of the combined switches <b>32</b> become the outermost and vice versa, as illustrated in <figref idref="DRAWINGS">FIG. 4C</figref>, without affecting the routability of the interconnection network. The levels with shorter connections are moved be closer to the logic cells. This is more suitable for an FPGA.

0000Corner Turning for Interconnection Network

0042With inputs and outputs combined into a single switch cell <b>32</b>, shorter routes between logic cells which don't travel through all 2*(log₂N) levels of switches can be configured. In the original Benes network, every route must travel through all the levels to go from input to output. In the adapted interconnection network, signals from the logic can “turn the corner” before reaching the opposite side of the network. For example, in <figref idref="DRAWINGS">FIG. 5</figref>, logic cell <b>41</b> has an output pin that must be routed to an input pin on logic cell <b>42</b>.

0043Of course, the particular advantage of corner turning in the interconnection network depends on the quality of logic cell placement algorithm for the FPGA. (Note that “placement” for an FPGA logic cell is not the physical placement of selected logic gates to form a desired function, but rather the programming of a selected logic cell to perform the desired function.) The algorithm is designed to minimize the distance between connected logic cells, where distance is not defined as it usually is for an FPGA or MPGA. The usual definition of distance in a placement algorithm is either Euclidean or Manhattan. In present interconnection network, distance is defined as the depth of the first common ancestor in the network because a corner can be turned at this point. The most appropriate placement algorithms build cluster trees with capacity constraints, either top-down or bottom-up. Nonetheless, regardless of the quality of logic cell placement, the present invention still provides the original worst case bound of 2*(log₂N) switches, no matter how highly the network is utilized. In contrast, current FPGA products cannot guarantee a worst case bound on signal delay when the integrated circuit is highly utilized.

0000Enhanced Switch for FPGAs

0044Corner turning requires that the original Benes switch be enhanced. It should noted that the original switch had 2 states responsive to 1 configuration bit. See the description above with respect to <figref idref="DRAWINGS">FIGS. 2A and 2B</figref>. Just by combining the input and output switches cells, the combined switch <b>32</b> has 4 states and requires 2 configuration bits. <figref idref="DRAWINGS">FIG. 6A</figref> illustrates the four permutations of passing signals from the input terminals to the output terminals for the combined switch <b>32</b>.

0045The corner turning feature adds 5 more states for the “output” lower half of the combined switch <b>32</b>. When multiplied by 2 states for the “input” upper half, there are a total of 10 new states for the combined switch <b>32</b>. These additional 10 states are illustrated by FIG. <b>6</b>B. It should be noted that for the corner turning states shown, there are only two possible paths to turn a corner: Each of the two possible corner turning outputs can only be connected to one of the inputs, not both inputs. The unconnected input comes from the same switch as the one the output is going to. While there may be some possible use for this connection in terms of selectively adding variable delays to certain routes, the cost of implementing additional configuration bits to all combined switch cells to support these paths is unjustified.

0046Of course, the increased number of states for the combined switch can not be satisfied by the two-MUX structure of FIG. <b>2</b>C. <figref idref="DRAWINGS">FIG. 7</figref> is a block diagram of the combined switch cell <b>32</b>, which is formed by MUXs <b>61</b>-<b>66</b> which operate by the setting of configuration bits on five control line nodes <b>71</b>-<b>75</b>. MUXs <b>61</b> and <b>62</b> each have terminal nodes connected to inputs A and B; control line node <b>71</b> is connected to MUX <b>61</b> and control line node <b>72</b> is connected to MUX <b>72</b>. The output nodes of MUX <b>61</b> and <b>62</b> form the outputs of the combined switch <b>32</b>. MUXs <b>63</b> and <b>65</b> are connected so that the output node of the MUX <b>63</b> forms one input node of the MUX <b>65</b>; in effect, the MUXs <b>63</b> and <b>65</b> form a 3:1 MUX. The input nodes of the MUX <b>63</b> are connected to the reverse direction inputs C and D, and the second input node of the MUX <b>65</b> is connected to the input B. The MUXs <b>64</b> and <b>66</b> form a second 3:1 MUX. The output node of the MUX <b>64</b> forms one input node of the MUX <b>66</b>. The input nodes of the MUX <b>64</b> are also connected to the reverse direction inputs C and D, and the second input node of the MUX <b>66</b> is connected to the input A. The output nodes of MUX <b>65</b> and <b>66</b> form the reverse direction outputs of the combined switch <b>32</b>. The control line node <b>73</b> is connected in common to the MUXs <b>63</b> and <b>64</b>. The control line node <b>74</b> is connected to the MUX <b>65</b> and the control line <b>75</b> is connected to the MUX <b>66</b>.

0047One further enhancement is required for a interconnection network which is highly suitable for FPGAs. That enhancement is fanout support. In an FPGA, the outputs frequently fan out to multiple inputs. At the switch level, fanout can be supported in either the “output” half or the “input” half of the combined switch <b>32</b>. However, in terms of routability for one-to-many connections, the fanout must be in the input half of the combined switch in order to break cyclic dependencies. Therefore, the preferred embodiment of the combined switch cell <b>32</b> has 4 states in the input half of the switch, as represented by the four states in FIG. <b>8</b>.

0048An alternative way of creating the fanout function is with the use of logic cells which are connected through MUXs to the interconnect network. Such an arrangement avoids the placing of additional functionality upon the interconnect network itself. An example of this arrangement is shown in FIG. <b>9</b>. Each logic cell is a 4-LUT (4 input Look Up Table). There are four 4-LUTs <b>76</b>-<b>79</b> (having a total of 16 inputs) with 4 outputs A-D respectively. These outputs A-D are connected to the input nodes of each of 16 MUXs <b>80</b> which have a total of 16 outputs. These outputs (as the inputs to the 4-LUTs <b>76</b>-<b>79</b>), in turn, are connected to the enhanced combined switch cells of the first (and last) levels of the described Benes interconnect network. Through control signals on the MUXs, the outputs A-D can be selectively placed into the interconnect network. With the repetition of one of the 4LUT outputs A-D into the interconnect network, a fanout is effectively created.

0049Hence, with the 7 possible states on the output half of the combined switch, the enhanced switch has a total of 28 states. A switch cell appropriate for an FPGA interconnect network has been created from a simple 2-state switch cell which requires 1 configuration bit and capable of being implemented with 18 transistors in CMOS. The 28-state combined switch cell requires 5 configuration bits and can be implemented with 74 transistors in CMOS. The most expensive enhancement, in terms of silicon area, is the corner turning feature. Without corner turning, the combined switch cell would only have 8 states, which require 3 configuration bits and can be implemented in 46 transistors in CMOS. This is about a 38% reduction in silicon area for the interconnect network alone. For the purpose of analysis, assuming the logic cell is a 4-LUT (4-input Look-Up Table) with a latched output and the array is built with 16K logic cells (a 64K gate equivalent), a 33% reduction in the total FPGA area may be achieved. Table A below compares the results of a combined switch cell with and without corning turning:

0050<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="6"><colspec colname="1" colwidth="35pt" align="left" /><colspec colname="2" colwidth="28pt" align="center" /><colspec colname="3" colwidth="42pt" align="center" /><colspec colname="4" colwidth="35pt" align="center" /><colspec colname="5" colwidth="35pt" align="center" /><colspec colname="6" colwidth="42pt" align="center" /><thead><row><entry namest="1" nameend="6" rowsep="1">TABLE A</entry></row><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row><row><entry /><entry>Switch</entry><entry /><entry /><entry /><entry /></row><row><entry /><entry>Cell</entry></row><row><entry /><entry>Tran-</entry><entry>Logic Cell</entry><entry>Area Per</entry><entry>FPGA</entry><entry>FPGA Area</entry></row><row><entry /><entry>sistors</entry><entry>Transistors</entry><entry>Transistor</entry><entry>Total Area</entry><entry>Percentage</entry></row><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>With</entry><entry>74</entry><entry>270</entry><entry>0.000004</entry><entry>153</entry><entry>100%</entry></row><row><entry>Corner</entry></row><row><entry>Turning</entry></row><row><entry>Without</entry><entry>46</entry><entry>270</entry><entry>0.000004</entry><entry>102</entry><entry> 67%</entry></row><row><entry>Corner</entry></row><row><entry>Turning</entry></row><row><entry namest="1" nameend="6" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0051As discussed previously, corner turning is highly desirable for reducing the signal delay due to routing. The FPGA user should be able to make the design tradeoff whether a specific project needs a faster chip or a smaller chip. The interconnect network according to the present invention provides many options to the FPGA user. An even higher speed, larger area alternative is discussed below.

0000Pipelined Interconnect and Predictable Delays Through the Interconnect Network

0052Even with the enhanced combined switch, the present invention provides for further improvement. The biggest problem in semi-custom VLSI (Very Large Scale Integration) design today is the signal delays due to an integrated circuit's interconnection network. With deep sub-micron fabrication processes and its thin resistive wires, the delay due to interconnect dominates any delay due to the logic cells. This problem is even worse in an FPGA because there is the additional interconnect delay due to the switch cells in the routing. The difficulty arises in trying to either predict or constrain the routing delays.

0053The current practice for VLSI design is to estimate the delay due to routing during the logic design stage. The estimation is done by statistical wire loading models or by rules-of-thumb which limit the levels of logic between clock cycles. Then the actual placement and routing of the logic is performed, and the prior estimates are usually passed on as constraints to these algorithms. However, constraint driven place-and-route algorithms are still an open problem, and so there still must be a timing verification stage after these programs are run. Usually there are timing violations and the designer has different options. He or she can try to tweak the placement and routing to meet the timing constraints. This is largely a matter of patience and luck. If this fails, he can go back and modify the logic design based on the actual timing from the place-and-route. Then he tries to place and route routine again with the hope that the process will converge and there will be no new timing violations. However, placement algorithms have been theoretically proven to be highly sensitive to even small changes, so the delay profile of the modified logic design may be very different from what was hoped. This is usually a highly iterative and lengthy process. In practice, VLSI designers have learned not to be aggressive with their timing estimates and constraints, so that the process will converge more rapidly. Most current FPGA designs only run at 50-100 MHz.

0054With an interconnect network according to the present invention, a totally different design methodology is possible. All the problems arising from variable interconnect delays and the need to predict and constrain them are avoided. The described interconnect network provides for a uniform multi-stage network as illustrated in <figref idref="DRAWINGS">FIG. 10. A</figref> representative pair of neighboring enhanced switches <b>48</b> and <b>49</b> are shown. The inputs of the switch cells <b>48</b> and <b>49</b> have latches <b>50</b> to pipeline the signals routed through the network. The latches <b>50</b> in the switch cell <b>48</b> are responsive to one edge of a clock signal and the latches <b>50</b> in the switch cell <b>49</b> are responsive to the other edge of the clock signal. Alternating switch levels in the interconnect network can thus be rising or falling edge-triggered of a clock signal. In a fully pipelined design, the clock can operate as fast as the slowest stage in the network, and should be capable of supporting clock rates up to 1000 MHz.

0055To maximize throughput, every switch level of the interconnect network may be latched. On the other hand, if such a high clock rate is not needed, every few levels may be latched for a lower clock rate and throughput. Each latch requires 10 transistors to implement, so that each unlatched switch cell is 46% smaller than its latched version. Alternatively, latches may be included in every level, but with a 2:1 MUX, one input being the output of the latch and the other being the input to the latch. The MUX serves as a field programmable bypass to the latch, and allows field control of the number of switch levels between the latches. In this manner, the number of switch levels between latches and whether they include the bypass MUXs is placed under the control of the FPGA user.

0056For a fully pipelined design, a logic cell's input signals must arrive at the same time. The described interconnect network can disable corner turning (either in the routing algorithm or in the FPGA network generator) so that every route passes through exactly 2*(log₂N) levels and the delay is known a priori. Then the only source of signal delay variation arises from the differing levels of logic along the paths for different input pins for a given logic cell in the user's logic design.

0057<figref idref="DRAWINGS">FIG. 11A</figref> represents such an example. Two sets of data are presented in queues, one set for logic cell <b>51</b> and the other set for logic cell <b>52</b>. The corresponding data from both sets are to be processed by logic cell <b>54</b>. With the assumption that each route has a delay of 1 ns and each logic cell <b>51</b> and <b>52</b> has a delay of 1 ns, then the upper path (with logic cell <b>51</b>) has a delay of 2 ns and the lower path (with logic cells <b>52</b> and <b>53</b> and a path between the two logic cells) has a delay of 4 ns. This design will not operate correctly in a fully pipelined mode. By the time Data <b>1</b> arrives at logic cell <b>54</b> along the bottom path, Data <b>1</b> has already passed logic cell <b>54</b> along the upper path. Instead Data <b>2</b> is present.

0058But with a minor modification, the present invention allows the design to be pipelined and to operate the clock at 1 ns. <figref idref="DRAWINGS">FIG. 11B</figref> shows the insertion of a buffer <b>55</b> along the upper path between the logic cells <b>51</b> and <b>54</b>. Buffers can be inserted without affecting the logic of the design. In fact, most commercial place-and-route tools will insert buffers on signals with long routing lines in order to improve their overall delay; this is done transparently for the user. The present invention allows buffer insertion to be made simply because the signal delays through the interconnect network are known.

0059Hence the present invention offers a methodology for fully pipelined design as follows: analyze a given netlist to identify existing mismatches in delay paths; optionally, the user may modify his or her netlist to eliminate the mismatches; for each mismatch, insert buffers to lengthen the shorter paths until the delay paths match; determine what size array is required for the modified netlist; and perform place-and-route without corner turning. This methodology does not require iteration as current methodologies do. This is because of two properties of interconnection network of the present invention: 1) the delay of every routing path is known a priori; and 100% routability for a given array is guaranteed, a property of the Benes network.

0060The described methodology supports fully pipelined operation at very high clock rates. It should be noted that pipelining yields a signal processing throughput proportional to the clock rate, but the signal processing latency is still proportional to the levels of logic and interconnect.

0000Latency Control

0061The present invention permits even further efforts to reduce latency. One potential drawback of using a multi-stage network as an interconnect network is the potentially long latency of a route. Although corner turning reduces the average length of the routing, the worst case length is still 2*(log₂N) levels, as explained above. While the performance of an FPGA with the described interconnection architecture is superior than existing FPGA products, there is room to control worst case latency. This can be done without giving up guaranteed routability, known delays, or pipeline support, but at the expense of more silicon area.

0062Because of the hierarchical structure of a Benes network, the Benes network can be recursively constructed. The Upper Network and Lower Network are themselves expanded into Benes networks, each with half the number of inputs and outputs of the original network. See FIG. <b>3</b>B. In essence, each of these sub-networks simply guarantees a means of routing any of its inputs to any of its outputs. Functionally, this is a crossbar switch. A Benes network is a much more area efficient method of implementing a rearrangeable crossbar. The size of a Benes network grows by N*log₂N, whereas the size of a crossbar grows by N². However, maximum latency can be reduced if just the lowest levels of Benes networks are substituted with crossbars. The following Table B illustrates the relative areas, in 0.18-micron technology, for a 16K logic cell array:

0063<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="42pt" align="center" /><colspec colname="2" colwidth="56pt" align="center" /><colspec colname="3" colwidth="56pt" align="center" /><colspec colname="4" colwidth="63pt" align="center" /><thead><row><entry namest="1" nameend="4" rowsep="1">TABLE B</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row><row><entry>Inputs to</entry><entry /><entry /><entry /></row><row><entry>Sub-Network</entry><entry>Levels Reduced</entry><entry>Benes Total mm2</entry><entry>Crossbar Total mm2</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="42pt" align="char" char="." /><colspec colname="2" colwidth="56pt" align="char" char="." /><colspec colname="3" colwidth="56pt" align="char" char="." /><colspec colname="4" colwidth="63pt" align="char" char="." /><tbody valign="top"><row><entry>16</entry><entry>7</entry><entry>9.7</entry><entry>11.0</entry></row><row><entry>32</entry><entry>9</entry><entry>12.1</entry><entry>24.2</entry></row><row><entry>64</entry><entry>11</entry><entry>14.5</entry><entry>54.3</entry></row><row><entry>128</entry><entry>13</entry><entry>17.0</entry><entry>122.0</entry></row><row><entry>256</entry><entry>15</entry><entry>19.4</entry><entry>273.7</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Thus the replacement of the 16×16, 32×32, or even the 64×64 sub-networks in the described interconnect networks are viable and attractive options. Nonetheless, the option which should be selected depends on the constraints of the specific application. <br /> Parameterized Array Generation

0064In accordance with the present invention, the described interconnect network has several options which trade off area, latency, and throughput. To take advantage of this flexibility, different families of FPGA products, each family optimized for different design objectives, may be created. Perhaps a better way is to provide an FPGA array generator program to the end user. Such a generator-based methodology allow the user to explore various tradeoffs for his or her specific application. In addition, the generator allows the end user to specify the size and shape of the array desired. This enables the user to fit an FPGA component onto a larger VLSI chip floorplan with other components, a further advantage of the present invention.

0065A summary of the features of the interconnect network options that have been described so far is listed in Table C:

0066<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="5"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="56pt" align="left" /><colspec colname="3" colwidth="42pt" align="left" /><colspec colname="4" colwidth="35pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="4" rowsep="1">TABLE C</entry></row><row><entry /><entry namest="offset" nameend="4" align="center" rowsep="1" /></row><row><entry /><entry>Objective</entry><entry>Corner Turning</entry><entry>Crossbars</entry><entry>Latches</entry></row><row><entry /><entry namest="offset" nameend="4" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Typical</entry><entry>Yes</entry><entry>No</entry><entry>No</entry></row><row><entry /><entry>Minimum Area</entry><entry>No</entry><entry>No</entry><entry>No</entry></row><row><entry /><entry>Minimum Latency</entry><entry>Yes</entry><entry>Yes</entry><entry>No</entry></row><row><entry /><entry>Maximum Throughput</entry><entry>No</entry><entry>Yes</entry><entry>Yes</entry></row><row><entry /><entry namest="offset" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0067Each of these options is a control on the software generator having a top level flow chart as shown in <figref idref="DRAWINGS">FIG. 12</figref>, in accordance with the present invention. The Corner Turning control either includes or excludes the corner turning MUX's and their configuration bits for all switch cells. The Crossbar control offers a set of choices (e.g., 4, 8, 16, or 32) for the level of sub-network to be replaced with crossbars. The Latch control offers a set of choices (e.g., 0, 1, 2, or 3) for the number of levels of unlatched switches between latched switches. In addition, the generator offers a “novice user” mode for users who are not familiar with the details of the described interconnect network. In the novice user mode, there are only three choices: Minimum Area, Minimum Latency, or Maximum Throughput. Selection one of these choices instructs the generator to set the Corner Turning, Crossbars, and Latches options with appropriate defaults.

0068Besides the above options for the generation of the interconnect network, the generator also accepts parameters for the other components of the FPGA array. The user can specify the total number of primary IO's (Input/Output terminals) for the array. Optionally, the number of IO's per side (north, east, west, or south) can be specified. If the number of IO's per side is not specified, the total number of IO's are evenly distributed around the array. In addition, if the sides have been specified, a list of the exact offset location for each IO may optionally be specified. The generator performs all the necessary design rule checks. For the logic cells, the user can specify the total number of logic cells desired and the generator then rounds up to the nearest power of two. After the number of logic cells is specified, the generator offers a choice of feasible layouts with their various width and height dimensions. Optionally, the user may specify either a maximum width or a maximum height, and the generator automatically selects the layout which most closely conforms to this constraint.

0069Lastly, the Generator can be incorporated into a broader automated methodology which includes the user's design logic synthesis. From the output of the logic synthesis program, the methodology automatically determines the number of primary IO's and logic cells, and then invokes the generator with these parameters. An optional “fudge” factor can be specified by the user (e.g. 10%) to instruct the generator to create an array with the specified number of additional logic cells over the number required by the synthesized logic.

0070Because the array is field programmable, the user may wish to specify more logic cells than are absolutely required by the given design. These extra cells can be used in the field to accommodate future bug fixes and enhancements. It is even possible to accommodate a user who has only a general idea of the logic design, but can specify the maximum gate count anticipated, and does so in order to begin the manufacturing of his or her ASIC (Application Specific Integrated Circuit) before the final logic design is finished. It is also possible to accommodate the user who wants a single array to be able to accept more than one design. For example, the user may want his product to be able to interface many alternative external memory devices, each requiring different protocols or timing, and the final selection of interface is field configurable.

0000Layout for FPGA Array

0071There are two viable floorplans to map the topology of present invention's interconnect network onto a physical layout, i.e., on the surface of the substrate of an integrated circuit. The first floorplan is tree-based, and the second floorplan is column-based. Each floorplan has its own advantages and disadvantages.

0072The most straightforward mapping is column-based. With the previous illustrations of the Benes interconnect network and columns of logic cells added, the layout is nearly completed. See FIG. <b>13</b>A. There are two logic cells <b>81</b> per switch cell <b>82</b>, connected in the so called “butterfly” pattern, consistent with the Benes network topology: More generally, an input-output pin-pair of a logic cell forms the leaves of the Benes interconnect network. So if a logic cell has many pins, there are a number of switch cells connected to it. For example, if the logic cell is a 4-input, 1-output Look Up Table (see FIG. <b>9</b>), the single output pin is fanned out 4 times to form 4 pin-pairs for each cell, and there are 2 switch cells in the first level of the Benes network connecting to each logic cell.

0073For multiple column arrays, levels of switch cells are added to each column's sub-network. The new levels are connected together between columns in a topology consistent with a Benes network. See <figref idref="DRAWINGS">FIG. 13B</figref> in which a level of switch cells <b>83</b> are added to make the connection between two <figref idref="DRAWINGS">FIG. 13A</figref> column arrays. For each additional doubling of the number of cell columns, an additional column of switch cells must be added to each of the cell columns, and the span for connecting these new columns to each other doubles as well. As before, each column's top-level inputs and outputs are connected to the primary I/O of the FPGA.

0074The strength of this column floorplan is that the number of cells in a column can be any power of 2, and the number of rows can also independently be any power of 2. This enables the generation of arrays containing numbers of cells that are any power of 2, and with a selection of various aspect ratios. On the other hand, the weakness of this column floorplan is that the long inter-column connections for several levels can all pass in parallel over the same area. The floorplan may be limited by the metal pitch constraints of the semiconductor process used to manufacture the FPGA; and the floorplan may also have crosstalk problems. These issues must be addressed carefully in the leaf cell design for the software generator.

0075The other viable floorplan maps the Benes topology onto a hierarchical tree layout. It is most clearly understood by showing the cell-to-cell correspondence with the column floorplan. <figref idref="DRAWINGS">FIG. 14A</figref> shows a 16 logic cell column floorplan (the same as shown in <figref idref="DRAWINGS">FIG. 13B</figref>) with the cells labeled for identification; <figref idref="DRAWINGS">FIG. 14B</figref> shows the equivalent network laid out in a hierarchical tree floorplan. The advantage of this tree floorplan is that the maximum wire length for any connection is only a quarter of the width of the substrate surface; whereas in the column floorplan, the maximum wire length is a half the width of the chip. Furthermore, in the tree floorplan the switches can be “slid” along their hierarchical connection paths in order to evenly distribute the wire lengths between levels and to thus minimize the longest wire length. <figref idref="DRAWINGS">FIG. 14B</figref> is used as an example of sliding the switches towards the center, where the maximum wire length is now 2, instead of the original 3. The resulting layout is illustrated in FIG. <b>14</b>C.

0076This rearrangement, in turn, minimizes the size of the circuit drivers in the switch cells. This can be significant if the same switch cell is used everywhere in the generator. Minimizing the longest wire is also significant in pipeline operation because the clock rate is limited by the slowest level in the network. On the other hand, the disadvantage of this tree floorplan is that it does not pack the substrate surface perfectly and leaves some open spaces. Additionally, the aspect ratio of the array is fixed.

0077All these various floorplans still implement the same topology of the disclosed interconnect network. In fact, a straightforward software method can mechanically transform between the various floorplans, even after place-and-route has been performed. Other than the physical locations of the cells, the only remaining question is the delay of the physical interconnect wires. This can be approximated with simple resistance and capacitance models since interconnect wires have no branches. These simple models cannot account for the crosstalk and interlayer parasitics, but they should be sufficient for all the design stages before full-chip verification.

0000Applicability to MPGA

0078Finally, the disclosed Benes interconnect network can also be applied to MPGAs (Mask Programmable Gate Arrays). This is accomplished as a post-processing step where each switch cell used in the routing is replaced with either a metal via or an end-to-end concatenation of two same layer metal wires, depending on the orientation of the wires. The advantage over existing MPGA interconnect architectures is the guaranteed routability, support for pipelining, as well as the fast execution speed of the place-and-route algorithms.

0079While the foregoing is a complete description of the embodiments of the invention, it should be evident that various modifications, alternatives and equivalents may be made and used. For example, while the foregoing description is that of an FPGA integrated circuit, the present invention works equally well in an FPGA which forms only a portion of an integrated circuit. Furthermore, while logic cells are interconnected in an FPGA, the interconnection network of the present invention may be used to interconnect arbitrary components, such as multiple processors or peripheral blocks, of an integrated circuit. In fact, the interconnection network might be even on a separate integrated circuit and is used to interconnect separate integrated circuit devices. Accordingly, the above description should not be taken as limiting the scope of the invention which is defined by the metes and bounds of the appended claims.