AN IMPROVED INTERCONNECT STRUCTURE IN PROGRAMMABLE DEVICES
Field of the Invention
The present invention pertains to an improved interconnect structure in programmable devices.
Background of the Invention
When Integrated Circuits (ICs) were first introduced, they were extremely expensive and were limited in their functionality. Rapid strides in semiconductor technology have vastly reduced the cost while simultaneously increased the performance of IC chips. However, the design, layout, and fabrication process for a dedicated, custom built IC remains quite costly. This is especially true for those instances where only a small quantity of a custom designed IC is to be manufactured. Moreover, the turn-around time (i.e., the time from initial design to a finished product) can frequently be quite lengthy, especially for complex circuit designs. For electronic and computer products, it is critical to be the first to market. Furthermore, for custom ICs, it is rather difficult to effect changes to the initial design. It takes time, effort, and money to make any necessary changes.
In view of the shortcomings associated with custom ICs, field programmable gate arrays (FPGAs) offer an attractive solution in many instances. Basically, FPGAs are standard, high-density, off-the-shelf ICs, which can be programmed by the user to a desired configuration. Circuit designers first define the desired logic functions, and the FPGA is programmed to process the input signals accordingly. Thereby, FPGA implementations can be designed, verified, and revised in a quick and efficient manner. Depending on the logic density requirements and production volumes, FPGAs are superior alternatives in terms of cost and time-to-market.
FPGA essentially consists of an outer ring of I/O blocks surrounding an interior matrix of configurable logic blocks. The I/O blocks residing on the periphery of an FPGA are user programmable, such that each block can be programmed independently to be an input or an output and can also be tri-stated. Each logic block typically contains programmable

combinatorial logic and storage registers. The combinatorial logic is used to perform Boolean functions on its input variables. Often, the registers are loaded directly from a logic block input, or they can be loaded from the combinatorial logic.
Interconnect resources occupy the channels between the rows and columns of the matrix of logic blocks and also between the logic blocks and the I/O blocks. These interconnect resources provide the flexibility to control the interconnection between two designated points on the chip. Usually, a metal network of lines runs horizontally and vertically in the rows and columns between the logic blocks. Programmable switches connect the inputs and outputs of the logic blocks and I/O blocks to these metal lines (called input & output connection boxes). Crosspoint switches and interchanges at the intersections of rows and columns are used to switch signals from one line to another (called switch boxes). Often, long lines are used to run the entire length and/or breadth of the chip.
The functions of the I/O blocks, logic blocks, and their respective interconnections are all programmable. Typically, a configuration program stored in an on-chip memory controls these functions. The configuration program is loaded automatically from an external memory upon power-up, on command, or programmed by a microprocessor as part of system initialization.
A typical symmetrical FPGA architecture is shown in the Figure 1. Figure shows basic components and their connectivity. Figure 1 shows a switch box and 4 connection boxes of logic block connecting to a bi-directional single length track routing fabric. The four connection boxes are identical. The Configurable logic block has its inputs connected to the routing fabric via a matrix, usually known as the connection box. Routing channels interact with each other with a matrix, known as switch box. The switch box can be of different topologies. Recently much work has been concentrated on a superior switch box called Hyper Universal, which provides enhanced routability at the expense of some extra resources

With further developments taking place, the connection boxes of a logic cluster shown in Figure 1 are not in the four adjacent channels but on all four sides of a particular switch box making connection box and switch box appear as one single entity as shown in Figure 2.
The disjoint switch box is very popular because of its simplicity and easy layoutability. A disjoint switch box is shown in Figure 3. A disjoint switch box has similar one to one connection on all the sides i.e. line number 1 of side left is connected to line number of 1 of right, top and bottom and so on. Such a switch box makes it easier for router to predict the routability and because of less number of crisscross connections it is easy to layout in silicon. However disjoint switch box gives a reduced routability as compared to other switch boxes like Wilton, Universal & Hyper-Universal.
The invention also proposes to marry the features of a disjoint switch box and various other switch-boxes to give a balanced tradeoff of routability easy layoutability & software friendliness.
A typical configurable logic block would be as shown in Figure 4. The logic block shown has a full matrix on the input side of its connectivity with the routing fabric, known as INMUX and internal feedback matrix for merged nets. It could also possibly have a full matrix on the output side to connect to the routing fabric. Generic FPGA structures are referred to in M. I. Masud. FPGA routing structures: A novel switch block and depopulated interconnect matrix architectures. Master's thesis, Department of Electrical and Computer Engineering, University of British Columbia, December 1999.
Another structure is given in G. Lemieux, P. Leventis, and D. Lewis. Generating highly-routable sparse crossbars for PLDs. In ACM/SIGDA Int. Symp. on FPGAs, pages 155— 164, Monterey, CA, February 2000.
But unlike universal switch-boxes, disjoint switch boxes are better with respect to predicting routing and are easy to layout on silicon.

The invention proposes to marry the features of a disjoint switch-box and various other switch-boxes to give a balanced tradeoff of routability, easy layoutability & software friendliness. The shortcomings of disjoint switch box have been overcome by a combination of disjoint and other type of switch boxes to yield a switch-box cluster with ease of layoutability, software friendly structure & increased routability.
Objects and Summary of the Invention
To obviate the above drawbacks the invention provides for a domain based routing architecture where routing architecture is divided into various domains.
Another object is to provide easy routing predictability and improved routing flexibility as well as improved compile times for EDA tools.
To achieve the aforesaid objects the invention provides an improved interconnect structure in programmable devices comprising:
- one or more independent groups of input lines, each said group having
predetermined number of said input lines;
an equal number of groups of routing lines; and
a connection mechanism for connecting lines in each input group to the lines
in each corresponding group of routing lines and lines of each group of
routing lines with the routing lines of same group, thereby forming domain based routing structures, each said domain being disjoint with the other domain.
The output lines of a logic block are connected to any said group of routing lines.
Said group of routing lines contains plurality of routing lines.
Said connection mechanism includes switch box (s) and connection boxes.

Each said group of input lines drives a domain using connection boxes.
Said one or more independent groups of input lines drive at least one domain using said routing lines.
Each said domain includes a switch box.
All domains include a common switch box.
Said group of input lines is connected to the address/data lines of a memory in programmable devices.
Said routing lines are unidirectional/bi-directional.
Said switch box includes disjoint switch boxes.
Said switch box includes universal switch boxes.
Said switch box includes Wilton switch boxes.
Said switch box includes hyper universal switch boxes.
Said programmable device includes FPGA.
A method for interconnecting programmable devices comprising the steps of:
forming atleast one independent group of input lines, each group having a predefined number of said input lines; - providing equal number of groups of routing lines, each group comprising plurality of routing lines;
connecting each said group of input lines to a corresponding group of routing lines and lines of each group of routing lines with the routing lines of same

group thereby forming a domain based routing structure enhancing software implementation as well as layouts.
Said group of input lines is formed depending upon logical equivalence or functionality of said input lines.
Brief Description of the Accompanying Drawings
The invention will now be described with reference to the accompanying drawings.
Figure 1 shows a symmetrical FPGA architecture with basic components. Figure 2 shows a symmetrical architecture with different connectivity. Figure 3 shows a simple Disjoint Switch Box topology. Figure 4 shows a generic logic cluster with in muultiplexer and input sets.
Figure 5 shows a routing fabric broken in four routing domains in switch box, connection box and in multiplexer for bi-directional routing tracks using a single switch box.
Figure 6 illustrates a routing fabric broken into four routing domains in whole core.
Figure 7 illustrates a routing fabric broken in four routing domains in switch box, connection box and IN MUX for uni-directional routing tracks.
Figure 8 re-layout of figure 5 using multiple switch boxes.
Figure 9 shows a universal switch boxes doing intra domain switching with a routing fabric broken into four domains.

Detailed Description of the Invention
Referring to Figure 4, the IN MUX 40 input is segregated into various sets (A, B, C & D) based on different criteria for an example logical equivalence or functionality. If IN MUX 40 is a full matrix then all inputs of IN MUX 40 are logically equivalent i.e. there is just one set of inputs at INMUX 40. If there is no IN MUX then different LUT input may form different sets (say first set for LUT 41 input, second set for LUT 42 inputs and so on). If there is memory in place of LUT then address lines may form one set, data line may form another set and so on.
The domains may not necessarily be created by the connectivity to input matrices but could also be possible in other cases. E.g. direct connectivity to the cluster of LUTs can lead to domain formation on the bases of connectivity to a particular LUT i.e. tracks connected to a particular LUT are of the same domain. In memories, domains can be formed on different criteria e.g. there could be one domain of data lines, another domain of address lines, yet another domain of control signals and the like.
However in the figure, IN MUX 40 inputs have been segregated into four sets, say A, B, C and D, using any aforesaid method.
Figure 5 shows a detailed view of a logic tile. Logic Tile contains a logic block 50 (IN MUX is part of logic blocks), connection box 51 and switch box 52. All the lines (inputs) of the logic block are divided into four sets A, B, C and D. They are connected to the routing lines, which are again divided into different sets and interact with their corresponding lines on all sides of a switch box thereby forming a domain.
Connection box 51 is designed in such a way that different sets interact with different logic block input sets. In figure tracks on each side are divided into four parts and one fourth lines (1 to 4) of each side are connected to set A, another one fourth lines (5 to 8) of each side are connected to set B, another one fourth lines (9 to 12) of each side are connected to set C and remaining one fourth lines (13 to 16) of each side are connected to set D. The routing tracks are divided into four parts as shown, however they can be

divided into any number of sets, usually equal to number of sets in logic block input and each routing track interacts with one input line but flexibility at connection box can be changed to any value provided first one fourth lines are being connected to set A and so on. The aforesaid figure shows one possible method of connecting routing lines to respective set on logic block of input lines whereas there may be various other possible methods can be deployed to achieve the same goal.
The switch box 52 is disjoint in nature i.e. line number 1 of left is always connected to line number 1 of top, bottom and right and so on for each line and side.
The connection between the lines of input multiplexer, say set A, and routing lines is as follows. The required number of routing lines of first side are connected to set A vide connection box which in turn is connected to the corresponding lines on all other sides of a switch box 52. Thus, all these lines are connected to set A in connection box. In brief, line number 1 will always remain connected to set A on all sides even after passing through switch box and connection box. All lines interacting with set A belong to domain 1, all lines interaction with set B belong to domain 2, all lines interacting with set C belong to domain 3 and all lines interacting with set D belong to domain 4.
Figure 6 shows a whole chip formed by replication of tiles described in figure 5 thereby extending domains to whole FPGA fabric.
The combination of "set definition at logic block", "connection box topology" and "switch box topology" forms routing domains and divides complete routing structure into various domains, which are mutually exclusive.
The biggest benefit of routing domains is achieved during software implementation and silicon implementations. Routing domains have very less connectivity (none in this case as all routing domains are mutually exclusive) with each other, hence logic related to a particular domain can be placed at one place while logic related to another domain can be placed at another place. It gives very high degree of flexibility during silicon

floonplanning. Different domains can be placed separately keeping different silicon issues into consideration and thereby provide better performance of silicon in terms of delay and/or area and/or development efforts.
Also FPGA implementation toolset can utilize this feature to improve performance. During routing, software routes nets between source and sink as per track availability of the routing tracks. The sink is available on a particular routing domain (usually just one), which is valid throughout the chip on all sides; the source need not search the track availability on other domains. Rather the source needs to search the track availability in a particular domain, which belongs to sink. Thus domain based routing architecture reduces search space for software considerably.
Figure 7 is an example of domain based routing structure in the case of unidirectional lines. In unidirectional switch box, an incoming line of a domain in one side drives the corresponding outgoing line an all other sides and so on for each side and incoming/outgoing lines. So a domain contains logic block input sets and incoming & outgoing lines with appropriate switch box and connection topology.
Figure 8 shows another embodiment that shows the routing lines have been divided into domains and the whole switch box is a cluster of disjoint switch boxes. Each switch box is connected to a particular set of routing lines/tracks. The segregation of tracks into four domains is based on their connectivity to the input matrices and switch matrix connectivity. In this embodiment, neither intra-domain nor inter-domain switching is possible with respect to tracks. To increase the routability of such switchboxes while maintaining the domain concept the architecture can be depicted as shown in Figure 9 using universal switch box.
To enhance routability, other switch boxes like Wilton, Universal & Hyper-Universal can be used in place of disjoint switch box. Another embodiment of invention proposes to make a tradeoff between Disjoint and other high routability switch boxes to get the best of both types of switch boxes.

In Figure 9 the switch box is a cluster of mutually exclusive universal switch boxes. Universal switch boxes give flexibility in layout as the switch box can be broken in mutually exclusive parts and placed apart as per convenience same as described earlier. The router for sure knows that a signal in one domain is restricted to the domain. So predictability is better. This in turn helps to reduce expansion times as well as provides high routability (switching tracks is possible in a domain).
Said figure is only an example of a possible structure of a "Clustered switch box" which preserves the domain concept. Instead of Universal switch box a Wilton, Hyper-Universal or a combination of such switch boxes or a new switch box can be used.
The invention can be applied to a routing fabric for FPGAs based on LUTs, multiplexers, ULMs, or CPLDs etc or memory elements. Anyone skilled in the art can easily see its applicability to afore mentioned architectures.

We claims
1. An improved interconnect structure in programmable devices comprising:
one or more independent groups of input lines, each said group having
predetermined number of said input lines;
an equal number of groups of routing lines; and
a connection mechanism for connecting lines in each input group to the
lines in each corresponding group of routing lines and lines of each group
of routing lines with the routing lines of same group, thereby forming domain based routing structures, each said domain being disjoint with the other domain.
2. An improved interconnect structure as claimed in claim 1 wherein the output lines of a logic block are connected to any said group of routing lines.
3. An improved interconnect structure as claimed in claim 1 wherein said group of routing lines contains plurality of routing lines.
4. An improved interconnect structure as claimed in claim 1 wherein said connection mechanism includes switch box (s) and connection boxes.
5. An improved interconnect structure as claimed in claim 1 wherein each said group of input lines drives a domain using connection boxes.
6. An improved interconnect structure as claimed in claim 1 wherein said one or more independent groups of input lines drive at least one domain using said routing lines.
7. An improved interconnect structure as claimed in claim 1 wherein each said domain includes a switch box.

8. An improved interconnect structure as claimed in claim 1 wherein all domains include a common switch box.
9. An improved interconnect structure as claimed in claim 1 wherein said group of input lines is connected to the address/data lines of a memory in programmable devices.
10. An improved interconnect structure as claimed in claim 3 wherein said routing lines are unidirectional/bi-directional.
11. An improved interconnect structure as claimed in claims 7 or 8 wherein said switch box includes disjoint switch boxes.
12. An improved interconnect structure as claimed in claims 7 or 8 wherein said switch box includes universal switch boxes.
13. An improved interconnect structure as claimed in claims 7 or 8 wherein said switch box includes Wilton switch boxes.
14. An improved interconnect structure as claimed in claims 7 or 8 wherein said switch box includes hyper universal switch boxes.
15. An improved interconnect structure as claimed in claim 1 wherein said programmable device includes FPGA.
16. A method for interconnecting programmable devices comprising the steps of:
forming atleast one independent group of input lines, each group having a predefined number of said input lines;
providing equal number of groups of routing lines, each group comprising plurality of routing lines;

connecting each said group of input lines to a corresponding group of routing lines and lines of each group of routing lines with the routing lines of same group thereby forming a domain based routing structure enhancing software implementation as well as layouts.
17. The method for interconnecting programmable devices as claimed in claim 16 wherein said group of input lines is formed depending upon logical equivalence or functionality of said input lines.
18. An improved interconnect structure in programmable devices substantially as herein described with reference to and as illustrated in the accompanying drawings
19. A method for interconnecting programmable devices substantially as herein described with reference to and as illustrated in the accompanying drawings