1. Field
The present disclosure describes methods and techniques for interconnecting a collection of processing elements in which multiple metallization layers may be used. For example, the present disclosure describes a method and apparatus for interconnecting compute, memory and/or logic blocks in a Field Programmable Gate Array (FPGA), System-on-a-Chip (SoC), Programmable System-on-a-Chip (PSOC), multi-processor chip, structured Application Specific Integrated Circuits (ASIC), or heterogeneous combinations of such elements.
2. Description of Related Art
VLSI technology has advanced considerably since the first gate arrays and FPGAs. Feature sizes have shrunk, die sizes and raw capacities have grown, and the number of metal layers available for interconnect has grown. The most advanced VLSI processes now sport 7-9 metal layers, and metal layers have grown roughly logarithmically in device capacity. Multi-level metalization, and particularly the current rate of scaling, may provide additional capability for interconnect requirements for typical designs which grow faster than linearly with gate count. The accommodation of the growing wire requirements by using multiple wire layers in the third dimension, may allow the maintenance of constant density for arrays of processing elements such as FPGAs, processor arrays, gate arrays, and similar devices.
Interconnection networks typically referred to as meshes, Tree of Meshes, and Mesh of Trees are known in the art. Such networks are instances of limited-bisection networks. That is, rather than supporting any graph connectivity, like a crossbar or Benes network, these networks are designed to exploit the fact that a typical N-node circuit or computing graph can be bisected (cut in half) by cutting less than O(N) hyperedges. This is significant as the bisection width of a network, BW, directly places a lower bound on the size of the network when implemented in very large scale integration (VLSI). See, for example, C. Thompson, “Area-time complexity for VLSI,” Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, May 1979, pp. 81-88. With a crossbar or Benes network, the bisection width is O(N), as is the subsequent bisection of each half of the network. This means the horizontal and vertical width of the design, when implemented in a constant number of metal layers, must be O(N) which implies O(N2) VLSI layout area. In contrast, a network which only has BW<O(N) bisection width may be implemented in less area as described below.
A common way of summarizing the wiring requirements for circuits is Rent's Rule, as described by B. S. Landman and R. L. Russo, “On pin versus block relationship for partitions of logic circuits,” IEEE Transactions on Computers, vol. 20, pp. 1469-1479, 1971. Landman and Russo articulate this model for relating the number of gates N and the total number of input and outputs signals, IO, where IO=cNp. This relationship assumes that maximization of locality is desired, i.e., the groups of N gates are selected so as to minimize the number of signals which connect gates in a group to gates in other groups. In Rent's Rule, c and p are parameters that can be tuned to fit the IO versus N connectivity relationship for a design; c is a constant factor offset which roughly corresponds to the IO size of the leaf cells in a design, and p defines the growth rate. Hence, p can be viewed as a measure of locality. With p=1, the design has O(N) bisection bandwidth and hence has little locality. Asp decreases, the design has more locality and admits to smaller implementations. Landman and Russo, and a large body of subsequent work, observe that typical designs have 0.5≦p≦0.75.
Returning to the bisection based area lower bound, assuming a fixed number of wiring layers, the bisection width is as follows:
      BW    (          chip      ⁢                          ⁢      half        )    =            IO      (              chip        ⁢                                  ⁢        half            )        =          IO      (              N        2            )      which can be used to determine the wiring requirements:
                              A          wire                ⁢                >                              BW            ⁡                          (                              N                2                            )                                ×                      BW            ⁡                          (                              N                2                            )                                                                      ⁢                              >                                                            c                  ⁡                                      (                                          N                      2                                        )                                                  p                            ×                                                c                  ⁡                                      (                                          N                      4                                        )                                                  p                                              =                                    (                                                c                  2                                                  8                  p                                            )                        ⁢                          N                              2                ⁢                p                                                        Rent's Rule provides a way of succinctly characterizing the wiring requirements for typical, limited-bisection designs. The equation above shows a lower bound on the wiring requirements for any layout of a graph with Rent characteristics (c,p). That is, any physical network which supports such a graph must have at least this much wiring.
The Tree-of-Meshes (ToM) network is described in F. T. Leighton, “New lower bound techniques for VLSI,” in Twenty-Second Annual Symposium on the Foundations of Computer Science. IEEE, 1981. FIG. 1 illustrates the ToM topology with multiple compute blocks 101 connected to other compute blocks 101 by interconnects 103, where c=3 and p=0.5. The ToM network is further described in S. Bhatt and F. T. Leighton, “A framework for solving VLSI graph layout problems,” Journal of Computer System Sciences, vol. 28, pp. 300-343, 1984, as a stylized, limited-bisection network which could be used as a template for the layout of any limited bisection design and could be the basis of a configurable routing network. Bhatt and Leighton use (α, F) as their parameterization rather than Rent's Rule's (c,p), but they define an equivalent space (F=cNmaxp, α=2p). By tuning the child to parent channel width growth of each of the tree stages, the ToM network can be parameterized to support the (c, p) wiring requirements for any circuit. Significantly, if a design is recursively partitioned and its IO versus partition size relationship does not exceed the (c,p) of a ToM network, a (4c,p) ToM network will always be able to route it. Using asymptotically the same number of switches, but organizing them differently, the factor of four can be reduced. Using a crossbar type interpretation of the ToM,
  a  ⁢          ⁢      (                            3          ⁢          c                2            ,      p        )  network supports the (c, p) design. See, for example, A. DeHon, “Rent's Rule Based Switching Requirements,” Proceedings of the System-Level Interconnect Prediction Workshop SLIP '2001), ACM, March 2001, pp. 197-204.
C. E. Leiserson, “Fat-trees: Universal networks for hardware efficient supercomputing,” IEEE Transactions 011 Computers, vol. C-34, no. 10, pp. 892-901, October 1985, describes adapting the ToM network into a Fat Tree. Leiserson further defines a linear switch population version called the Butterfly Fat Tree (BFT) in R. J. Greenberg and C. E. Leiserson, Randomness in Computation, ser. Advances in Computing Research, JAI Press, 1988, vol. 5, ch. Randomized Routing on Fat-Trees, earlier version MIT/LCS/TM-307. FIG. 2 shows a BFT network having c=1, p=0.5 and an arity of 4.
The Hierarchical Synchronous Reconfigurable Array (HSRA), described in W. Tsu, K. Macy, A. Joshi, R. Huang, N. Walker, T. Tung, O. Rowhani, V. George, J. Wawrzynek, and A. DeHon, “HSRA: High-Speed, Hierarchical Synchronous Reconfigurable Array,” Proceedings of the International Symposium on Field Programmable Gate Arrays, February 1999, pp. 125-134, is logically equivalent to a BFT. FIG. 3 shows a HSRA with c=3, p=0.5 and an arity of 2. Both the BFT and HSRA are “linearly populated” in that they have only a linear number of switches (linear in the number of child input channels) in each hierarchical switch box rather than the quadratic number required by a full ToM network. One consequence of linear population is that the BFT or HSRA requires a total number of switches that is linear in the number of endpoints supported for any p<1.
As briefly discussed above, another network known in the art is the Manhattan interconnect scheme, also known as Symmetric or Island-style interconnection. In the Manhattan interconnect, a routing channel containing W wires track between every row and column of processing elements. FIG. 4 shows the standard model of a Manhattan interconnect scheme. Each compute block 101 (look-up table (LUT) or island of LUTs) is connected to adjacent channels by a connect box (C-box) 102. At each channel intersection is switch box (S-box) 104, which allows wires to be linked into longer signal runs or make Manhattan turns. In the C-box 102, each compute block 101 input/output pin is connected to a fraction of the wires in a channel. At the S-box 104, each channel on each of the 4 sides of the S-box connects to one or more channels on the other sides of the S-box 103.
The Manhattan interconnect scheme may be analyzed on the basis of the number of sides of the compute block 101 on which each input or output of a gate appeared (7), the fraction of wires in each channel each of these signals connected to (Fc), and the number of switches connected to each wire entering an S-box 104 (Fs). Regardless of the detail choices for these numbers, they have generally been considered constants, and the asymptotic characteristics are independent of the particular constants chosen.
For example, assume each side of the compute block has I inputs or outputs to the channel. If the compute block comprises a single-output k-LUT, then
  I  =                    T        ×                  (                      k            +            1                    )                    4        .  The number of switches Csw in a C-box 102 is Csw=2·Fc·I·W, where W is the width of the channel. Each S-box requires the following number of switches
      S    sw    =                    (                  4          2                )            ·              F        s            ·      W        =          2      ·              F        s            ·              W        .            
As shown in FIG. 4, a compute segment 100 typically comprises a compute block 101, two C-boxes 102 and one S-box 104. Therefore, the total number of switches per compute segment 100 is: Bsw=2·Csw+Ssw=2W(2·Fc·I+Fs). As indicated above Fs are generally considered constants, so it can be seen that the number of switches required per compute segment 100, i.e., per compute block 101, is Bsw=O(W). That is, the number of switches is linear in W, the channel width.
A loose bound on the channel width may be found by looking at the bisection width of a design. A Manhattan mesh arranged in √{square root over (N)}×√{square root over (N)} processing elements has √{square root over (N)}+1 horizontal and vertical elements. The total bisection width of the mesh in the horizontal or vertical direction is then: BWmesh=(√{square root over (N)}+1)W. That is, the design requires at least BWmesh bandwidth across the √{square root over (N)} row (or column) channels which cross the middle of the chip containing the design. To support a design characterized by Rent Parameters (c,p), the Manhattan mesh will need:
            BW      mesh        ≥                  c        ⁡                  (                      N            2                    )                    p                          (                              N                    +          1                )            ⁢      W        ≥                            c          ⁡                      (                          N              2                        )                          p            .      The plus one can be dropped without affecting the asymptotic implications, providing:
                    (                              N                    +          1                )            ⁢      W        ≥                  c        ⁡                  (                      N            2                    )                    p                          W        ≥                              (                          c                              2                p                                      )                    ⁢                      N                          (                              p                -                0.5                            )                                          =              O        ⁡                  (                      N                          (                              p                -                0.5                            )                                )                      ,  which gives a lower bound on channel width which a Manhattan mesh will need to support a Rent characterized (c,p) design. However, the mesh will generally require more wire channels than this because: 1) the calculation is based only on bisection wires, but the channels may need to be wider to hold wires in some of the recursive cuts; and 2) the calculation assumes optimal wire spreading, but it may not be possible to spread wires evenly across all channels without increasing channel widths in the orthogonal channels.
From the equations above, the total number of switches per compute block can be defined by:Bsw=O(W(N))=O(N(p−0.5))Therefore, as larger designs are implemented, if the interconnect richness is greater than p=0.5, the switch requirements per compute block grow for systems using the Manhattan interconnect scheme. That is, the aggregate switching requirements grow superlinearly with the number of compute blocks supported.
Many designs use segments that span more than one S-box. See, for example, FIG. 5, which shows segments that span two switchboxes. Designs having length 4-8 buffered segments may require less area than designs that do not use such segments. The segment length may be represented by Lseg and in FIG. 5, Lseg=2. However, such fixed segmentation schemes usually only change the constants related to the number of switches require and generally do not change the asymptotic growth factor in the required number of switches, described above. For example, using a single segmentation scheme of length Lseg will change the switch requirements for an S-box to
      S    sw    =                    (                  1                      L            seg                          )            ⁢              (        2        )            ⁢                        F          s                ·        W              =                  (                  2                      L            seg                          )            ⁢                        F          s                ·                  W          .                    
Generally, the W will be different between the segmented and non-segmented cases, where the segmented cases will require larger W's. However, the asymptotic lower bound relationship as described above will still apply. Similarly, a mixed segmentation scheme will also change the constants, but not the asymptotic requirements. Therefore, the Manhattan interconnect scheme, whether segmented or not, still generally results in a superlinear growth in the switching requirements with an increase in the number of compute blocks.
A hierarchical segmentation scheme may allow for the reduction of switchbox switches. For example, a hierarchical scheme may have a base number of wire channels Wb and the channels may be populated with Wb single length segments, Wb length 2 segments, Wb length 4 segments, and so forth. Using the equation presented above for calculating the number of switchbox switches in a single segmentation scheme with Wb substituted for W and summing across the geometric wire lengths, the total number of switches per switchbox is:
      S    sw    =                    (                              ∑                                          L                seg                            =              1                                      N              level                                ⁢                                          ⁢                      (                          1                              L                seg                                      )                          )            ⁢              (        2        )            ⁢                        F          s                ·                  W          b                      =                  (                              1            1                    +                      1            2                    +                      1            4                    +          …                )            ≤              4        ·                  F          s                ·                  W          b                    In such a hierarchical segmentation scheme, the total wire width of a channel is:W=Nlevel·Wb 
For sufficiently large Nlevel, W can be raised to the required bisection width. Since Ssw in this hierarchical case does not asymptotically depend on Nlevel, the number of switches per switchbox converge to a constant.
However, such a hierarchical scheme does not eliminate the asymptotic switch requirements. As described above, the switch requirements depend on both the C-box switches and the S-box switches. As long as the C-box switches continue to connect to a constant fraction of W and not Wb, the C-box contribution to the total number of switches per compute block continues to make the total number of switches linear in W and hence growing with N. This indicates that the flat connection of blocks IOs to the channel impedes scalability.
Conventional experience implementing the Manhattan interconnect scheme has led to the observation that switch requirements tend to be limiting rather than wire requirements. For example, an N-node FPGA will need:Nswitch(N)=Bsw·N=O(N(p+0.5))With BW wires in the bisection, the wire requirements will be:
                    A        wire            ⁡              (        N        )              ≥                  (                  BW                      L            /            2                          )            2        =      O    ⁡          (                        N                      2            ⁢            p                                    L          2                    )      For a fixed number of wire layers (L), the wiring requirements will grow slightly faster than switches (i.e., when p>0.5, 2p>p+0.5). Asymptotically, this suggests that if the number of layers, L, grows as fast as
      O    ⁡          (              N                  (                                    2              ⁢              p                        -                          1              /              4                                )                    )        ,then the design will remain switch dominated. Since switches have a much larger constant contribution than wires, it is not surprising that designs require a large N for these asymptotic effects to become apparent.
Therefore, there is a need in the art for an apparatus and method that provides for interconnections in a device such as an FPGA that allows for the use of fewer switches than a Manhattan mesh as the device is scaled up.
While these networks have been described in terms of FPGAs, it should be clear that interconnection networks of this kind are relevant to all scenarios where programmable interconnect nodes are used and these nodes can be gates, LUTs, PLAs, ALUs, processors, memories, arrays of LUTs, or custom functional units. This need is similar whether the network is configured (as typical for FPGAs), time switched, circuit switched, or packet switched. Further, these networks can be configured at the time of fabrication, such as in gate-arrays and structured ASICs.
Leighton also introduced the Mesh of Trees (“New Lower Bound Techniques for VLSI,” Twenty-second Annual Symposium on the Foundations of Computer Science, IEEE, 1981 and Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufman Publishers, Inc. 1992) as shown in FIG. 6. The Mesh of Trees (MoT) can be seen as a hybrid between a Tree-of-Meshes and a Manhattan array. It uses hierarchical interconnect like the Tree-of-Meshes, but builds the trees in rows and columns similar to the Manhattan interconnect. Leighton's Mesh of Trees was explicitly a p=0.5 structure.
FIG. 6 shows a MoT arrangement comprising a binary tree built along each row and column of a grid of compute blocks 101 with switching between compute blocks 101 provided by switch assemblies 110. The compute blocks 101 connect only to the lowest level of the tree. Connection can then climb the tree in order to get to longer segments. Each compute block 101 is simply connected to the leaves of the set of horizontal and vertical trees which land at its site.
Dally introduced the Express Cube (“Express Cubes: Improving the performance of k-ary n-cube interconnection networks” in IEEE Transactions on Computers v40n9p1016-1023) to exploit multiple levels of printed-circuit board wiring and to reduce signal delays. He did not teach how to parameterize the express cube network or how to lay one out efficiently.
G. A. Sai-Halasz in “Performance Trends in High-End Processors,” Proceedings of the IEEE, 83(1):20-36, January 1995 indicate that wiring on an upper layer metal plane will occupy 10-15% of all the layers below it. Integrating this result across wire planes, he argues that there is a useful limit of 6-7 wiring levels.
DeHon (“Compact, Multilayer Layout for Butterfly Fat-Tree” in Proceedings of the Twelfth ACM Symposium on Parallel Algorithms and Architectures, July 2000) showed that the p=0.5 BFT and HSRA could be laid out in constant area per endpoint node (processing element) using a logarithmic number of metal layers.
Therefore, there is a need in the art for a set of techniques that allow one to interconnect processing elements using a limited-bisection network which can be efficiently (with O(N) 2D area) realized using multiple metal layers. Further, there is a need for general techniques to layout graphs efficiently (O(N) 2D area) exploiting multiple metal layers.