Multiplexer Structures for Use in Making Controllable Interconnections in Integrated Circuits.

This invention relates to multiplexer-type structures for use in making controllable interconnections in integrated circuits such as programmable logic devices.

Pedersen et al. U.S. Pat. No. 5,241,224 teaches that instead of a large cross-point type switch capable of connecting any input to the switch to any output from the switch in order to route signals through an integrated circuit such as a programmable logic device, a more economical arrangement of multiplexers can often be used to provide a sufficient subset of such signal routing capability. In a programmable logic device, for example, other programmable circuitry associated with the communication network selects which of the multiplexer inputs is actually enabled when the device is used. The objective of the '224 patent is to provide enough interconnection capability so that the signal routing required in most applications of the circuit can be accomplished without unduly burdening the circuit with large amounts of interconnection capability that will be unused in a large number of cases. To accomplish this objective the '224 patent teaches connecting each input signal conductor to two different multiplexers, and avoiding connection of any two input conductors to the same two multiplexers. The '224 patent also teaches that the input conductors and the multiplexers they feed should preferably form an acyclic chain.

Although the multiplexer connection arrangements taught in the '224 patent have been highly successful, it has been found that those arrangements may have one or more disadvantages in some situations. For example, the '224 patent multiplexer connection arrangements are relatively complicated to select and implement. In other words, it may be relatively difficult to design a multiplexer connection arrangement that satisfies the '224 patent criteria. And because the '224 patent criteria tend to produce multiplexer connection arrangements that are highly irregular or random, substantial effort may be required to physically implement them in the integrated circuit. There is little or no repetition in the '224 patent multiplexer connection arrangements that can be relied on to help speed the detailed circuit design process. All of these factors tend to increase the manufacturing cost of the integrated circuit.

Another possible disadvantage of the '224 patent multiplexer connection arrangements is that they may call for connection of two or more adjacent input conductors to the same multiplexer. This may further complicate the task of physically implementing the circuit, and it may even prevent placing the input conductors as close together as would otherwise be possible and desirable in order to make the most efficient use of the area of the integrated circuit.

In view of the foregoing, it is an object of this invention to provide improved multiplexer-based interconnection structures or communication networks for use in integrated circuits such as programmable logic devices.

It is a more particular object of this invention to provide integrated circuit interconnection structures or communication networks which make use of multiplexers and which have most or all of the advantages of the '224 patent arrangements without any of the above-mentioned possible disadvantages of the '224 patent arrangements.

These and other objects of the invention are accomplished in accordance with the principles of the invention by providing multiplexer-based communication networks for integrated circuits which are characterized by multiplexer allocation graphs having a girth parameter of four and a regular structure which repeats as the size of the graph increases. Such graphs (known as "cages" of girth four) are used to provide a straightforward basis for designing a communication network of any size. The design task does not become significantly more complex as the size of the communication network increases. The arrangement of connections between the input signal conductors and inputs to the multiplexers can be derived from the cage in a simple and straightforward manner. Moreover, that arrangement of connections can be quite regular, if desired, to facilitate the process of physically implementing the connections in the integrated circuit. The arrangement of connections can also be readily made to avoid having to connect two or more adjacent input signal conductors to the same multiplexer input. This also facilitates the physical implementation task, and it may make it possible to place the input signal conductors closer to one another.

Further features of the invention, its nature and various advantages will be more apparent from the accompanying drawings and the following detailed description of the preferred embodiments.

FIG. 1 is an elementary diagram of the type known as a multiplexer allocation graph that is useful in explaining the principles of such graphs.

FIG. 2 is a more conventional circuit diagram of the circuitry represented by FIG. 1.

FIG. 3 is another elementary multiplexer allocation graph.

FIG. 4 is a more conventional circuit diagram of the circuitry represented by FIG. 3.

FIG. 5 is still another elementary multiplexer allocation graph.

FIG. 6 is a more conventional circuit diagram of the circuitry represented by FIG. 5.

FIG. 7 is a flow chart depicting a prior technique for devising a multiplexer connection pattern for multiplexer-based networks.

FIGS. 8-10 are representative regular multiplexer allocation graphs or cages of the type that are employed in accordance with this invention.

FIG. 11 is a plot showing the dimensions of several sizes of multiplexer allocation cages of the type that are employed in accordance with this invention.

FIG. 12 is a diagram of a typical multiplexer connection pattern that is relatively undesirable from the standpoint of this invention.

FIG. 13 is a diagram of a typical multiplexer connection pattern that results from the practice of this invention.

FIG. 14 is an illustrative diagram of the type that can be used in accordance with this invention to help make assignments of input conductors to multiplexers so as to produce desirable multiplexer connection patterns of the type shown in FIG. 13.

FIG. 15 is a diagram illustrating the entire process in accordance with this invention of producing a representative multiplexer input connection pattern from a multiplexer allocation cage of the preferred type.

FIG. 16 is a plot showing the dimensions of illustrative sizes of communication networks that can be produced in accordance with this invention.

FIGS. 17-20 show several alternatives to illustrative multiplexer connection patterns in accordance with this invention.

In communication networks that conform to the requirements taught in the '224 patent, each input to the network drives a unique pair of output multiplexers. As shown in FIG. 1, for example, if network input IN1 drives network outputs MUX6 and MUX7, then no other network input will drive both MUX6 and MUX7. (FIG. 1 is a type of diagram referred to herein as a multiplexer allocation graph. FIG. 2 is a more conventional circuit diagram of the communication network represented by FIG. 1. In a multiplexer allocation graph such as FIG. 1, the vertices represent multiplexers and the edges represent communication network inputs.)

Networks with multiple inputs driving the same pair of outputs are detected by "parallel" edges in the associated multiplexer allocation graph. FIG. 3 shows such a multiplexer allocation graph for two network inputs IN1 and IN2 and two multiplexers MUX6 and MUX7. FIG. 4 is the more conventional circuit diagram depiction of the communication network represented by FIG. 3. One of the objectives of the '224 patent is to avoid communication networks characterized by multiplexer allocation graphs with "parallel" edges of the type illustrated by FIG. 3.

In order to avoid "parallel" edges in a multiplexer allocation graph, the graph must have a "girth" of three or more. The girth of a multiplexer allocation graph is the number of edges in its shortest cycle. FIG. 5 shows a multiplexer allocation graph having a girth of three. (FIG. 6 is the more conventional circuit diagram depiction of the communication network represented by FIG. 5.) The graph of FIG. 5 has a girth of three because, starting at any vertex, the minimum number of edges of the graph that must be traversed in order to return to that vertex is three. For example, starting at vertex MUX9, there is no path through the graph and back to MUX9 which does not involve at least three edges of the graph. (The path IN4, IN3, and IN5 is an example of one such path.)

The multiplexer allocation graph of the typical communication network which results from use of the '224 patent criteria for network design is three. In effect, although the '224 patent does not specifically mention multiplexer allocation graphs, the '224 patent teaches that "routability" through a multiplexer-type communication network is improved by increasing the girth of the associated multiplexer allocation graph from two (as in FIG. 3) to three. (Routability refers to the ability of the communication network to effect a wide variety of different connection patterns without required connections being blocked.)

The typical technique for designing communication networks in accordance with the '224 patent criteria is shown in FIG. 7. This technique starts in step 10 with the network's required dimensions (i.e., the number of inputs and the number of outputs). A backtracking algorithm (step 12) is then used to search for conforming solutions. The multiplexer allocation graph of a candidate solution is constructed in step 14 and tested in step 16 to make sure that its girth is greater than two. If not, steps 12, 14, and 16 are repeated until a candidate solution which passes the test of step 16 is found.

After successful completion of step 16, step 18 is performed to select a candidate network which corresponds to the multiplexer allocation graph from the preceding steps. (By changing the network inputs associated with the edges of the multiplexer allocation graph and/or by changing the multiplexers associated with the vertices of that graph, many different candidate networks can typically be derived from one multiplexer allocation graph.)

In step 20 the multiplexer input connections associated with the network from step 18 are determined. (As described more fully below, multiplexer connection patterns like the one shown in step 20 indicate by shaded squares connections between input conductors (each represented by a horizontal row of squares) and multiplexers (each represented by a vertical column of squares).) In step 22 the multiplexer input connection pattern from step 20 is tested to see if it will violate any physical constraints if implemented in the integrated circuit. If such physical constraints will be violated, steps 18 through 22 are repeated until a solution which does not violate any physical constraints is found and the process is therefore complete as indicated in step 24. As indicated by the dotted line in FIG. 7 it may be necessary to go all the way back to step 12 if repeating only steps 18 through 22 does not eventually lead to step 24.

As FIG. 7 and the foregoing discussion demonstrate, the process of designing a communication network as taught by the '224 patent can be a protracted, trial-and-error procedure. Moreover, the multiplexer input connection patterns that result tend to appear random or nearly random (see, for example, the typical pattern shown in step 20). As noted in the introductory sections of this specification, such random or nearly random patterns may be less efficient to manufacture than more regular patterns such as are shown in FIGS. 13, 15, and 17-20 and discussed below.

The present invention aims to further improve routability through a multiplexer-type communication network by increasing the girth of the associated multiplexer allocation graph from three to four. One could search for graphs of girth four using the same technique as is shown in FIG. 7. However, that would merely perpetuate the disadvantages of the backtracking technique (namely, a protracted trial-and-error procedure resulting in random multiplexer input connection patterns that are relatively inefficient to manufacture).

In accordance with the preferred embodiments of this invention a more direct approach is taken to producing communication networks characterized by multiplexer allocation graphs of girth four. This more direct approach employs graphs called "cages". Cages are graphs with a specified girth, all of whose vertices have a specified "degree" or "valency", and that are known to have the fewest number of vertices possible, while still satisfying the girth and degree requirements. In accordance with the preferred embodiments of this invention cages of girth four are used as multiplexer allocation graphs for the communication networks produced.

The first three cages of girth four are shown in FIGS. 8-10. The degree of the cage in FIG. 8 is two. The degree of the cage in FIG. 9 is three. And the degree of the cage in FIG. 10 is four. It will be noted that the pattern shown in FIG. 8 repeats and multiplies in the cages of higher degree, and that it is a relatively simple matter to construct the higher degree cages from the basic pattern of FIG. 8. In general, if v is the degree or valency of a cage of girth four, it is known that the number of vertices of that cage is 2v and the number of edges of that cage is v.sup.2. Because edges in multiplexer allocation graphs correspond to network inputs, while vertices correspond to network outputs, communication networks synthesized from multiplexer allocation graphs which are cages having girth four and degree v have v.sup.2 inputs and 2v outputs. The dimensions of the first 15 such networks are shown in Table 1 below and are plotted in FIG. 11.

It will be apparent from the foregoing that using cages of girth four is a very direct way of finding a multiplexer allocation graph of girth four having approximately any number of inputs (e.g., four, nine, 16, 25, etc., inputs). Moreover, this technique always produces highly regular multiplexer allocation graphs such as are shown in FIGS. 8-10 and straightforward extrapolations thereof. The trial-and-error process and the typically highly irregular multiplexer allocation graphs of the '224 patent are therefore avoided.

It will be noted from FIGS. 8-10 that in all cages of girth four the vertices can be divided into two mutually exclusive sets or groups of equal size. Each vertex in each group has a direct connection via an edge to every vertex in the other group, but no direct connection via an edge to any other vertex in the same group. In each of FIGS. 8-10 one of the above-mentioned groups of vertices is on the left, while the other group is on the right.

The next step in the production of a communication network in accordance with this invention is to determine how the circuitry represented by the multiplexer allocation graph is to be implemented in the integrated circuit. The network inputs are usually routed to adjacent parallel "wires" in the circuit, while the multiplexers for the network's outputs are constructed from perpendicular columns of circuitry, each of which connects to the necessary input wires. The two-dimensional pattern of connections between the input wires and the multiplexer circuitry may be referred to as the "multiplexer pattern". For convenience such patterns are represented herein as shown in step 20 in FIG. 7. The particular pattern shown there has six input "wires" extending parallel to one another in the horizontal direction, and four multiplexers respectively represented by the four vertical columns. A shaded square represents a connection between the input wire (row) and the multiplexer (column) that intersect at that square. An unshaded square represents no connection between the input wire (row) and multiplexer (column) intersecting at that square. Although the input wires are thus always shown herein as extending horizontally, while the multiplexers are shown extending vertically, it will be understood that these components can have any orientation (usually perpendicular to one another) on the integrated circuit.

There is a strong relationship between a multiplexer pattern and the physical network that it represents. Individual shaded squares in the pattern usually correspond to vias on contacts between layers of a chip, although it is not uncommon for a single connection in a multiplexer pattern to control several layers of a tightly drawn design. Unseen in an abstract multiplexer pattern are constraints between layers which, if violated, would make the network unmanufacturable.

It can be helpful for the inputs of each multiplexer to be "spread out" (vertically in the multiplexer pattern diagrams shown herein) to provide predictable area for the multiplexer circuitry. The illustrative multiplexer pattern shown in FIG. 12 (16 input conductors and eight output multiplexers) is relatively poor in this respect. For example, the rightmost multiplexer in FIG. 12 is connected to the bottom three inputs. The close proximity of these input lines lead to layout inefficiencies, or those inefficiencies may preclude the input lines from being located as close to one another as would otherwise be most efficient and economical. In the better multiplexer pattern shown in FIG. 13 the four inputs to each multiplexer are spread out among each of the four quarters of the input lines, thereby ensuring uniform area for each multiplexer's layout.

A technique which can be used to derive "good" multiplexer patterns of the type illustrated by FIG. 13 is demonstrated in FIG. 14. The v.sup.2 cells in FIG. 14 represent the network inputs. The v rows and v columns in FIG. 14 represent the network's 2v outputs. Because each cell is a member of exactly one row and one column, each input of the network is connected to exactly two multiplexers. In the particular example shown in FIG. 14 v is 10, so the network has 100 input conductors (numbered 0 through 99) and 20 multiplexers (numbered MUX0 through MUX19). The fourth group of 10 network inputs is partly shaded to show how the input conductors in each group feed all of the multiplexers exactly once. (Note that the rows in FIG. 14 are all associated with one of two mutually exclusive groups of cage vertices between which there are no direct edge connections, while the columns in FIG. 14 are all associated with the other of these two groups of cage vertices. Note also that it facilitates spreading the multiplexer connections horizontally in patterns of the type shown in FIG. 13 to separate the multiplexers associated with these two groups of vertices into two separate groups on the integrated circuit.)

A two-dimensional table of the type shown in FIG. 14 is actually a representation of the correspondingly sized multiplexer allocation graph which is a cage of girth 4. A table of the type shown in FIG. 14 is prepared by subdividing the v.sup.2 input conductors into v groups, each group including v adjacent input conductors. Each group of inputs is then arrayed in order along a respective "diagonal" of the two-dimensional table. A "diagonal" of the table may be either continuous (as in the case of the diagonal from input 0 to input 9 in FIG. 14) or two discontinuous segments (as in the case of the segment from input 30 to input 36 together with the segment from input 37 to input 39 in FIG. 14). The result of this procedure is to spread out the inputs of each multiplexer so that each multiplexer has one input per band with no vertically adjacent multiplexer inputs in the final multiplexer pattern. In particular, in progressing from one input conductor group to the next adjacent input conductor group, the input conductors from each group that are adjacent to one another are selected so that neither multiplexer fed by either input conductor is one of the multiplexers fed by the other input conductor. This is the same as saying that in the associated multiplexer allocation cage the edges associated with these two input conductors do not have a vertex in common. The vertical spreading of the multiplexer input connections which results from the foregoing ensures room for all of the multiplexer transistors in the integrated circuit.

Another way to look at the foregoing procedure comes from the theory of cages of girth four. It is known from that theory that the edges in any such cage of degree v can be colored with v colors, no two edges of the same color having any vertex in common. For convenience herein all edges of a given color in such a consideration of a cage of girth four are referred to as a "band" of edges. Each group of input conductors in the foregoing discussion therefore corresponds to the edges of a given color or the edges in a given band. FIG. 15 illustrates the entire process (for a cage of girth four and degree four) from the starting multiplexer allocation cage through the resulting multiplexer pattern. On the left FIG. 15 shows by means of heavy or emphasized edges how the multiplexer allocation graph can be colored using four colors to divide the 16 edges in the graph into four bands of four edges each. To the right of the "colored" graphs, FIG. 15 shows a redrawing of only the edges in each band, with the vertices of the graphs relocated to correspond to the locations of the multiplexers along two perpendicular edges of the two-dimensional tables shown to the right of the redrawn graphs. In the two-dimensional tables the numbers of the input conductors are arrayed along diagonals on a band-by-band basis. And on the extreme right in FIG. 15 the resulting multiplexer pattern is shown for each band. The composite of these multiplexer patterns is shown in FIG. 13. As pointed out above, the FIG. 13 multiplexer pattern has the desirable feature that there are no connections to any multiplexer that are immediately adjacent to one another. The multiplexer patterns of this invention are also much more regular than the apparently random patterns that are typical of the prior art as illustrated, for example, by FIG. 12.

It will be apparent from the foregoing, and especially FIG. 13, that if it is desired to produce a network having 2v outputs but fewer than v.sup.2 inputs, one can simply delete inputs from the top or bottom of the multiplexer pattern with no adverse effect on the advantageous features of the pattern. Alternatively or in addition, one can delete any number of whole bands from the pattern with no adverse effect. Table 2 below shows what sizes of networks result when whole numbers of multiplexer allocation bands are deleted from a network generated for v=12.

Generally, by ignoring k bands of a synthesized multiplexer pattern, a network with v.sup.2 -kv inputs is created. The sizes of all networks that can be synthesized from cages of girth four for v=2 through v=16 with whole numbers of bands are plotted in FIG. 16. Of course networks of sizes other than those corresponding to the points plotted in FIG. 16 can be produced by deleting individual input conductors from the top or bottom of the multiplexer pattern as mentioned above.

If desired, ease of manufacture of regular multiplexer patterns such as those described above may be further increased by permuting the input conductors in a regular way. Some useful permutations of the regular multiplexer pattern shown in FIG. 17 are shown in FIGS. 18, 19, and 20. In FIG. 18, for example, every second input conductor is separated from the remaining input conductors and moved down to a separate sub-group of conductors. In FIG. 19 each input conductor from the lower half of the group is moved up between a respective pair of the input conductors in the upper half of the group. In FIG. 20 the group is divided into four vertical sub-groups and the conductors are taken one after another from the sub-groups in a repeating sequence. These permutations help to spread out the multiplexer input connections in both the horizontal and vertical directions. If such permutations are employed for the multiple groups of input conductors in a network (e.g., the four groups of conductors in the network shown in FIG. 13), the same permutation rule is preferably applied to the input conductors in each group.

It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, communication networks of any size can be produced using this invention as described above.