Patent Publication Number: US-6989690-B1

Title: Methods of implementing scalable routing matrices for programmable logic devices

Description:
FIELD OF THE INVENTION 
   The invention relates to programmable logic devices (PLDs). More particularly, the invention relates to a scalable routing matrix that can be utilized in a PLD. 
   BACKGROUND OF THE INVENTION 
   Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the Complex Programmable Logic Device (CPLD), typically includes two or more logic blocks (function blocks) interconnected by an interconnect switch matrix, or routing matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (PLAs) and Programmable Array Logic (PAL) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration sequence. 
   Another type of PLD is the Field Programmable Gate Array, or FPGA. An FPGA also includes both programmable logic blocks and a programmable interconnect structure interconnecting the logic blocks. The programmable functions in FPGAs are most commonly controlled by configuration data stored in static memory cells. 
   Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, e.g., using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable. 
     FIG. 1  illustrates an exemplary well-known CPLD. The CPLD of  FIG. 1  includes a routing matrix (RM)  101 , a plurality of function blocks  102 – 102   n , a corresponding plurality of input/output (I/O) blocks (IOBs)  103 – 103   n , and supporting logic such as boundary scan and in-system programming logic (BSC &amp; ISP)  106 . I/O pads  104 – 104   n  are coupled to respective IOBs  103 – 103   n , which in turn communicate with function blocks  102 – 102   n . Function blocks  102 – 102   n  communicate with routing matrix  101 . Each function block includes a PLA AND/OR plane and a plurality of macrocells MC 1 –MC 16 . 
   Clock and control signals (CLOCK &amp; CTRL SIGNALS)  109  are provided to function blocks  102 – 102   n  and I/O blocks  103 – 103   n . In some CPLDs, a boundary scan path (BSC PATH)  108  connects the I/O blocks  103 – 103   n  in a boundary scan chain for testing and/or programming purposes via boundary scan I/O pads  107 . In some CPLDs, fast input connections  105 – 105   n  optionally provide faster interconnections between IOBs  103 – 103   n , function blocks  102 – 102   n , and routing matrix  101 . (Note that in the present specification, the same reference characters are used to refer to terminals, signal lines, and their corresponding signals.) 
   Clearly, the larger the number of programmable interconnections provided by routing matrix  101 , the easier it will be to implement large amounts of logic in the CPLD, e.g., fully utilizing all of the available macrocells and function blocks. However, an overly large routing matrix, such as a routing matrix providing every possible interconnection between every input terminal and every output terminal of the matrix, would adversely affect the cost of the CPLD. Therefore, most CPLDs support only a subset of the possible interconnections, as shown, for example, in  FIGS. 2–3 . 
     FIG. 2  illustrates a small routing matrix having twelve input signals  0 – 11  and six output signals MUX 0  through MUX 5 . Output signals MUX 0  through MUX 5  are provided by six corresponding multiplexers  200 – 205 . Each of multiplexers  200 – 205  has four input signals selected from the twelve input signals  0 – 11 . The selection of an input signal as an input to a multiplexer is shown as an open circle (e.g., circle  206 ) at the intersection of the signal line and the input line to the multiplexer. For example, output signal MUX 0  is provided by multiplexer  200  from any of input signals  0 ,  3 ,  6 , and  9 . Multiplexers  201 – 205  are driven by their selected input signals as shown in  FIG. 2 . 
     FIG. 3  illustrates the same routing matrix as  FIG. 2 , but in the form of a routing matrix pattern. By comparing  FIGS. 2 and 3 , it is clear that each numerical value in routing matrix pattern  300  corresponds to one of the input signals  0 – 11  shown in  FIG. 2 , and each row of values in routing matrix pattern  300  corresponds to a set of input terminals coupled to a different multiplexer  200 – 205  to provide output signals MUX 0 –MUX 5 . 
   The exemplary routing matrix shown in  FIGS. 2 and 3  is a straightforward implementation that provides little routing flexibility. There are many routing combinations (corresponding to many logical circuits) that cannot be routed using the pictured routing matrix. For example, if a CPLD user wishes to route the three input signals  0 ,  3 , and  6  to three of the output multiplexers, the design will fail to route. In this example, signal  0  can be routed to output terminal MUX 0 , and signal  3  can be routed to output terminal MUX 3 , but signal  6  cannot be provided to any of the remaining output terminals MUX 1 , MUX 2 , MUX 4 , or MUX 5 . 
     FIGS. 4 and 5  illustrate a more versatile routing matrix than that of  FIGS. 2 and 3 . As shown in  FIG. 4 , this routing matrix is the same size as that of the previous example, also having twelve input signals  0 – 11  and six output signals MUX 0  through MUX 5 . Output signals MUX 0  through MUX 5  are provided by six corresponding multiplexers  400 – 405 . Each of multiplexers  400 – 405  has four input signals selected from the twelve input signals  0 – 11 . Again, the selection of an input signal as an input to a multiplexer is shown as an open circle (e.g., circle  406 ) at the intersection of the signal line and the input line to the multiplexer. For example, output signal MUX 0  is provided by multiplexer  400  from any of input signals  0 ,  3 ,  6 , and  11 . Multiplexers  401 – 405  are driven by their selected input signals as shown in  FIG. 4 . 
     FIG. 5  illustrates the same routing matrix as  FIG. 4 , but in the form of a routing matrix pattern. By comparing  FIGS. 4 and 5 , it is clear that each numerical value in routing matrix pattern  500  corresponds to one of the input signals  0 – 11  shown in  FIG. 4 , and each row of values in routing matrix pattern  500  corresponds to a set of input terminals coupled to a different multiplexer  400 – 405  to provide output signals MUX 0 –MUX 5 . 
   Note that the less repetitive nature of the selected signals in the example of  FIGS. 4–5  results in a more flexible routing matrix. For example, unlike the routing matrix of  FIGS. 2 and 3 , the routing matrix of  FIGS. 4 and 5  can route the three signals  0 ,  3 , and  6  successfully. Signal  0  can be routed to output terminal MUX 0 , signal  3  can be routed to output terminal MUX 5 , and signal  6  can be routed to output terminal MUX 4 . 
   The routing matrix illustrated in  FIGS. 4 and 5  is flexible, but it is also small. Deriving a suitable pattern of programmable interconnections is relatively simple for a routing matrix of this size. However, PLD routing matrices are typically much larger than these simple examples. Further, it is frequently desirable to produce “families” of related PLDs having routing matrices of varying sizes. Each routing matrix must be laid out, and routing software must be developed to support each of the routing matrices. Therefore, the process of creating and supporting routing matrices for each member of a PLD family can be a significant task. It is desirable, therefore, to provide methods of implementing routing matrices that simplify these tasks while providing flexible routing options to the PLD user. 
   SUMMARY OF THE INVENTION 
   The invention provides methods of implementing routing matrices for programmable logic devices (PLDs). Each method includes generating a seed matrix, a distribution matrix, adjustment values for the distribution matrix, and a routing matrix pattern. The routing matrix is then implemented using the routing matrix pattern. 
   The seed matrix includes N rows and N columns of numerical signal values, where N is an integer greater than one, e.g., a prime number. Each signal value appears at most once in each column and at most once in each row of the seed matrix. The distribution matrix includes S rows and T columns of sub-matrices, where each sub-matrix corresponds to a column of the seed matrix. Each column of the distribution matrix differs from each other column of the distribution matrix in at least (S−1) of the sub-matrices in the column. Each column of the distribution matrix has a corresponding adjustment value, where each adjustment value is an integral multiple of N. A routing matrix pattern is generated by adding the corresponding adjustment value to each signal value in each sub-matrix in each column of the distribution matrix. 
   The routing matrix for the PLD is generated by applying the routing matrix pattern to provide programmable interconnections between input and output terminals of the routing matrix. Each signal value in the routing matrix pattern corresponds to one of the input terminals, and each row of signal values in the routing matrix pattern corresponds to a set of the input terminals programmably coupled to a different one of the output terminals. 
   The routing matrices generated using the methods of the invention are both flexible and scalable. By adding additional columns of sub-matrices to an existing distribution matrix, an existing routing matrix can be expanded to accommodate a larger number of input signals. Hardware and software implementation of the new and larger routing matrices is simplified by maintaining this relationship between the variously-sized routing matrices. For example, this method can be used to create a set of PLDs (e.g., a family of CPLDs) of graduated sizes. 
   The invention also encompasses products (e.g., routing matrices and PLDs) generated utilizing the methods described herein. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention is illustrated by way of example, and not by way of limitation, in the following figures. 
       FIG. 1  illustrates an exemplary well-known Complex Programmable Logic Device (CPLD). 
       FIG. 2  illustrates a first routing matrix that might be used, for example, in the CPLD of  FIG. 1 . 
       FIG. 3  illustrates the routing matrix pattern for the routing matrix of  FIG. 2 . 
       FIG. 4  illustrates a second routing matrix that might be used, for example, in the CPLD of  FIG. 1 . 
       FIG. 5  illustrates the routing matrix pattern for the routing matrix of  FIG. 4 . 
       FIG. 6  illustrates an exemplary seed matrix that can be used to generate a routing matrix. 
       FIG. 7  illustrates exemplary generalized distribution and adjustment matrices that can be applied, for example, to the seed matrix of  FIG. 6  to generate a routing matrix. 
       FIG. 8  illustrates exemplary first distribution and adjustment matrices that can be applied, for example, to the seed matrix of  FIG. 6  to generate a routing matrix. 
       FIG. 9  illustrates the routing matrix pattern that results from the application of  FIG. 8  to the seed matrix of  FIG. 6 . 
       FIG. 10  illustrates exemplary second distribution and adjustment matrices that can be applied, for example, to the seed matrix of  FIG. 6  to generate a routing matrix. 
       FIG. 11  illustrates the routing matrix pattern that results from the application of  FIG. 10  to the seed matrix of  FIG. 6 . 
       FIG. 12  illustrates an exemplary set of related PLDs created by applying the methods of the present invention. 
       FIG. 13  illustrates the steps of an exemplary method of implementing a routing matrix for a programmable logic device (PLD). 
       FIG. 14  illustrates the steps of a first exemplary method of implementing a set of PLDs according to another aspect of the present invention. 
       FIG. 15  illustrates the steps of a second exemplary method of implementing a set of PLDs according to yet another aspect of the present invention. 
   

   DETAILED DESCRIPTION OF THE DRAWINGS 
   In the following description, numerous specific details are set forth to provide a more thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention can be practiced without these specific details. 
     FIGS. 6 and 7  illustrate three exemplary matrices that can be used to generate routing matrices according to the present invention.  FIGS. 8 and 9  provide a first specific example.  FIGS. 10 and 11  provide a second specific example. The first and second specific examples are related to each other in a useful fashion, as is clarified below. 
     FIG. 6  illustrates a matrix called a “seed matrix”. A seed matrix is an N×N (N by N) matrix of numerical values, where N is an integer greater than one. Each element of the seed matrix is a number that corresponds to an input signal of the routing matrix to be implemented. In the examples of  FIGS. 6–11 , N is thirteen. In other words, the signal values used in the seed matrix are 0, 1, 2, . . . , 11, and 12. However, other values of N can be used. For example, N can be any prime number greater than one. N can also be X to the power of Y, where X is any prime number and Y is any positive integer. In one embodiment, X is two, Y is three, and N is eight. 
   In seed matrix  600  of  FIG. 6 , each column of signal values 0–12 has an assigned letter A–M. This letter is used to designate the sub-matrix (e.g., the column of signal values) corresponding to the letter. 
   Note that no signal value occurs twice in any column. Further, no signal value occurs twice in any row. This ensures that the pattern of available interconnections in the resulting interconnect matrix is flexible, and that each input signal (corresponding to each signal value) has an equal number of possible connections to the available output signals. 
     FIG. 7  illustrates a generalized distribution matrix  701  that can be applied, for example, to seed matrix  600  of  FIG. 6 . However, distribution matrix  701  can also be applied to other seed matrices. Further, other distribution matrices can be applied to seed matrix  600 .  FIG. 7  also illustrates an adjustment matrix  702  that can be used in conjunction with distribution matrix  701  to produce a routing matrix pattern. Adjustment matrix  702  can be applied to distribution matrices other than matrix  701 , and other adjustment matrices can be applied to distribution matrix  701 . 
   A distribution matrix is a matrix of the sub-matrices from the seed matrix. In other words, each letter in distribution matrix  701  of  FIG. 7  corresponds to an entire column of the seed matrix in  FIG. 6 . The seed matrix includes S rows and T columns of the sub-matrices, where S and T are integers greater than one. In a distribution matrix according to the present invention, each column of the distribution matrix differs from every other column of the distribution matrix in at least S−1 (S minus one) of the sub-matrices in the column. In other words, if any two columns in the distribution matrix have the same letter in the same row, then no two other rows can contain the same letter in both columns. 
   An adjustment matrix is a matrix having one row and T columns. In other words, the adjustment matrix is the same width as the distribution matrix. Each adjustment value in the adjustment matrix is an integral multiple of N. In the various example illustrated herein, the adjustment values are, in order from left to right, 0, N, 2N, 3N, . . . . However, the adjustment values can occur in any order, and multiples of N can be skipped, if desired. Because each signal value is simply a numerical designation of an input signal to the routing multiplexer, the exact numbers used to designate the signals are not important provided the other requirements of the invention are met. 
   In distribution matrix  701  and adjustment matrix  702 , S is three and T has an undetermined value. By providing different values of T, a set of related routing matrices can be generated that can usefully share hardware and software design resources. An example of this application of the invention is shown in  FIGS. 8–11 . 
     FIG. 8  illustrates an exemplary distribution matrix  801  and adjustment matrix  802  that can be applied (for example) to seed matrix  600  of  FIG. 6 . Distribution matrix  801  is a 3×5 matrix, i.e., S is three and T is five. All thirteen sub-matrices A–M from seed matrix  600  of  FIG. 6  are represented in distribution matrix  801 . Sub-matrices A and B occur twice. As required, each column is different from each other column in at least two (S−1) of the sub-matrices. In fact, in distribution matrix  801 , no two columns include any corresponding sub-matrices in the same positions. 
   Adjustment matrix  802  includes one adjustment value for each column of distribution matrix  801 . Therefore, adjustment matrix  802  is a 1×T matrix. In adjustment matrix  802 , the adjustment values follow the pattern 0, N, 2N, 3N, 4N. 
     FIG. 9  illustrates the routing matrix pattern  900  that results from the application of  FIG. 8  to the seed matrix of  FIG. 6 . To generate the routing matrix pattern, the corresponding adjustment value for each column is added to each signal value in each sub-matrix in each column of the distribution matrix. For example, the area labeled “A” in  FIG. 9  corresponds to sub-matrix A (the first column) in seed matrix  600  of  FIG. 6 . No adjustment has been made to these signal values, because the adjustment value for the first column of the distribution matrix is 0. As another example, the area labeled “F+13” in  FIG. 9  includes the values of sub-matrix F, with the adjustment value of 13 added to each signal value in sub-matrix F. The adjustment value of 13 comes from the second column of adjustment matrix  802 . Similarly, the area labeled “B+52”, in  FIG. 9  includes the values of sub-matrix B, with the adjustment value of 52 added to each signal value in sub-matrix B. The adjustment value of 52 comes from the fifth column of adjustment matrix  802 . 
   Note that an extra column  901  of output signals MUX 0 –MUX 38  is added at the left side of routing matrix pattern  900 . When routing matrix pattern  900  is implemented in a routing matrix (e.g., using the method demonstrated in  FIGS. 2–5 ), output signals MUX 0 –MUX 38  can be implemented as programmable multiplexers, as shown in  FIGS. 2 and 4 . When implementing the routing matrix, each signal value in routing matrix pattern  900  corresponds to one of the input signals or input terminals  0 – 64 , and each row of signal values in routing matrix pattern  900  corresponds to a set of the input terminals  0 – 64  coupled to a different one of the output terminals MUX 0 –MUX 38 . Thus, the routing matrix corresponding to the routing matrix pattern of  FIG. 9  has 65 input terminals and 39 output terminals. 
     FIG. 10  illustrates second exemplary distribution and adjustment matrices that can be applied, for example, to the seed matrix of  FIG. 6  to generate another routing matrix. The routing matrix generated in this second example is a superset of the routing matrix of  FIGS. 8–9 . Therefore, both the hardware (e.g., the layouts) and the software (e.g., routing software) for the two examples can be shared to a large extent. This sharing can simplify the task of implementing a set of related PLDs, e.g., a family of variously-sized CPLDs. 
     FIG. 10  illustrates an exemplary distribution matrix  1001  and adjustment matrix  1002  that can be applied (for example) to seed matrix  600  of  FIG. 6 . Distribution matrix  1001  is a 3×6 matrix. Note that distribution matrix  1001  is the same as distribution matrix  801 , but with a new column added. In the exemplary embodiment, the new column is added at the right side of the distribution matrix. However, in other embodiments, the new column can be added anywhere in the distribution matrix. For ease of hardware and software implementation, the new column is preferably added at either the left side or the right side of the matrix. 
   The new column includes sub-matrices D, K, and C from seed matrix  600 . Note that sub-matrix C occurs in the same position in the new column and the first column of distribution matrix  1001 . However, it is permitted that any two columns exhibit a corresponding sub-matrix in one row (but not in more than one row). Sub-matrix D also occurs in the same position in the new column and the second column of distribution matrix  1001 . Sub-matrix K also occurs in the same position in the new column and the fourth column of distribution matrix  1001 . In each case, however, no second sub-matrix exhibits the same correspondence between the two columns. Therefore, distribution matrix  1001  fulfills the requirements for a distribution matrix. 
   Adjustment matrix  1002  includes one adjustment value for each column of distribution matrix  1001 . Therefore, adjustment matrix  802  is a 1×6 matrix. Note that adjustment matrix  1002  is the same as adjustment matrix  802 , but with a new column added. In the exemplary embodiment, the new column is added at the right side of the distribution matrix. In other embodiments, the new column can be added anywhere in the adjustment matrix. Further, the new column need not be added in the same place as the new column in the distribution matrix. However, for ease of hardware and software implementation, the new column is preferably added at either the left side or the right side of the matrix, in the same location as the new column of the distribution matrix. In adjustment matrix  1002 , the adjustment values follow the pattern 0, N, 2N, 3N, 4N, 5N. 
     FIG. 11  illustrates the routing matrix pattern  1100  that results from the application of  FIG. 10  to the seed matrix of  FIG. 6 . To generate the routing matrix pattern, the corresponding adjustment value for each column is added to each signal value in each sub-matrix in each column of the distribution matrix. For example, the area labeled “C+65” in  FIG. 11  includes the values of sub-matrix C, with the adjustment value of 65 added to each signal value in sub-matrix C. The adjustment value of 65 comes from the new (rightmost) column of adjustment matrix  1002 . 
   Note that an extra column  1101  of output signals MUX 0 –MUX 38  is added at the left side of routing matrix pattern  1100 . When routing matrix pattern  1100  is implemented in a routing matrix using the method demonstrated in  FIGS. 2–5 , for example, output signals MUX 0 –MUX 38  can be implemented as programmable multiplexers, as shown in  FIGS. 2 and 4 . When implementing the routing matrix, each signal value in routing matrix pattern  1100  corresponds to one of the input signals or terminals  0 – 77 , and each row of signal values in routing matrix pattern  1100  corresponds to a set of the input terminals  0 – 77  coupled to a different one of the output terminals MUX 0 –MUX 38 . Thus, the routing matrix corresponding to the routing matrix pattern of  FIG. 11  has 77 input terminals and 39 output terminals. 
   Note that the routing matrix pattern of  FIG. 11  is a superset of the routing matrix pattern of  FIG. 9 . A set of PLDs can be created that include variously-sized routing matrices derived in this fashion. For example, a set of related PLDs can be created in which a first PLD includes the first four columns of routing matrix pattern  1101 , a second PLD includes the first five columns of routing matrix pattern  1101 , a third PLD corresponds to routing matrix pattern  1101 , and a fourth PLD includes an additional seventh column (not shown) created by adding another column to distribution matrix  1001  and adjustment matrix  1002  of  FIG. 10  and applying the new matrices to seed matrix  600  of  FIG. 6 . 
     FIG. 12  illustrates a set of related PLDs created by applying the methods of the present invention. In a first PLD, programmable logic blocks (LBs)  1201  are programmably interconnected by routing matrix (RM)  1202  via J input signal lines and K output signal lines. Routing matrix  1202  is generated from an N×N seed matrix, as described in the previous examples. 
   A second PLD includes logic blocks  1203  programmably interconnected by routing matrix  1204  via J+N input signal lines and K output signal lines. Routing matrix  1204  is a superset of routing matrix  1202 . The routing matrix pattern for routing matrix  1204  includes an additional column also derived from the same seed matrix as the first PLD. Thus, routing matrix  1204  includes routing matrix  1202  plus additional programmable interconnections  1205 . Note that the number of input signals from the logic blocks has increased by N relative to the first PLD. 
   A third PLD includes logic blocks  1206  programmably interconnected by routing matrix  1207  via J+2N input signal lines and K output signal lines. Routing matrix  1207  is a superset of routing matrix  1204 . The routing matrix pattern for routing matrix  1207  includes an additional column also derived from the same seed matrix as the first and second PLDs. Thus, routing matrix  1207  includes routing matrix  1202  plus additional programmable interconnections  1205  and  1208 . Note that the number of input signals from the logic blocks has increased by N relative to the second PLD. 
   Routing matrices  1202 ,  1204 , and  1207  can be used to implement a set of PLDs including routing matrices of graduated sizes, as shown in  FIG. 12 . Hardware and software implementation of the resulting set of PLDs is simplified by maintaining this relationship between the variously-sized routing matrices. 
     FIG. 13  illustrates the steps of an exemplary method of implementing a routing matrix for a PLD, e.g., a CPLD. This method can be used, for example, to implement a routing matrix corresponding to the routing matrix patterns of  FIG. 9  or  11 . 
   In step  1301 , a seed matrix is generated, e.g., as shown in  FIG. 6 . The seed matrix includes N rows and N columns of numerical signal values, where N is an integer greater than one. Each signal value appears at most once in each column and at most once in each row of the seed matrix. In some embodiments, each signal value appears exactly once in each column and exactly once in each row of the seed matrix. In some embodiments, N is a prime number (e.g., thirteen). In some embodiments, N equals X to the power of Y, where X is any prime number and Y is any positive integer. In one embodiment, X is two, Y is three, and N is eight. 
   In step  1302 , a distribution matrix is generated, e.g., as shown in  FIGS. 7 ,  8 , and  10 . The distribution matrix includes S rows and T columns of sub-matrices, where S and T are integers greater than one. Each column of the distribution matrix differs from each other column of the distribution matrix in at least (S−1) of the sub-matrices in the column. In one embodiment, S is three. 
   In step  1303 , a corresponding adjustment value is generated for each column of the distribution matrix. Each adjustment value is an integral multiple of N. In some embodiments (e.g., in the embodiments of  FIGS. 7 ,  8 , and  10 ), an adjustment matrix is generated, each column including the corresponding adjustment value for a corresponding column of the distribution matrix. In some embodiments (e.g., the embodiments of  FIGS. 7 ,  8 , and  10 ), a first column in the distribution matrix has a corresponding adjustment value of 0, a second column in the distribution matrix has a corresponding adjustment value of N, a third column in the distribution matrix has a corresponding adjustment value of 2N, and so forth. 
   In step  1304 , a routing matrix pattern is generated from the distribution matrix and the adjustment values, e.g., as shown in  FIGS. 9 and 11 . More specifically, the corresponding adjustment value is added to each signal value in each sub-matrix in each column of the distribution matrix. 
   In step  1305 , a routing matrix for the PLD is implemented by applying the routing matrix pattern to provide programmable interconnections between input terminals and output terminals of the routing matrix (e.g., in a fashion similar to that of  FIGS. 2–5 ). Each signal value in the routing matrix pattern corresponds to one of the input terminals. Each row of signal values in the routing matrix pattern corresponds to a set of the input terminals programmably coupled to a different one of the output terminals. 
     FIG. 14  illustrates the steps of a first exemplary method of implementing a set of PLDs according to another aspect of the present invention. This method can also be used, for example, to implement the routing matrices corresponding to the routing matrix patterns of  FIGS. 9 and 11 , and/or the set of PLDs illustrated in  FIG. 12 . 
   In step  1401 , a seed matrix is generated, e.g., as shown in  FIG. 6 . The seed matrix includes N rows and N columns of numerical signal values, where N is an integer greater than one. Each signal value appears at most once in each column and at most once in each row of the seed matrix. In some embodiments, each signal value appears exactly once in each column and exactly once in each row of the seed matrix. In some embodiments, N is a prime number (e.g., thirteen). In some embodiments, N equals X to the power of Y, where X is any prime number and Y is any positive integer. In one embodiment, X is two, Y is three, and N is eight. 
   In step  1402 , a first distribution matrix is generated, e.g., as shown in  FIG. 8 . The first distribution matrix includes S rows and T columns of sub-matrices, where S and T are integers greater than one. Each column of the first distribution matrix differs from each other column of the first distribution matrix in at least (S−1) of the sub-matrices in the column. In the embodiment of  FIG. 8 , S is three and T is five. 
   In step  1403 , a corresponding adjustment value is generated for each column of the first distribution matrix. Each adjustment value is an integral multiple of N. In some embodiments (e.g., in the embodiment of  FIG. 8 ), a first adjustment matrix is generated, each column including the corresponding adjustment value for a corresponding column of the first distribution matrix. In some embodiments (e.g., the embodiment of  FIG. 8 ), a first column in the first distribution matrix has a corresponding adjustment value of 0, a second column in the first distribution matrix has a corresponding adjustment value of N, a third column in the first distribution matrix has a corresponding adjustment value of 2N, and so forth. 
   In step  1404 , a first routing matrix pattern is generated from the first distribution matrix and the adjustment values associated with each column of the first distribution matrix, e.g., as shown in  FIG. 9 . More specifically, the corresponding adjustment value is added to each signal value in each sub-matrix in each column of the first distribution matrix. 
   In step  1405 , a first routing matrix for a first PLD is implemented by applying the first routing matrix pattern to provide programmable interconnections between first input terminals and first output terminals of the first routing matrix (e.g., in a fashion similar to that of  FIGS. 2–5 ). Each signal value in the first routing matrix pattern corresponds to one of the first input terminals. Each row of signal values in the first routing matrix pattern corresponds to a set of the first input terminals programmably coupled to a different one of the first output terminals. 
   Step  1406  can be performed at any time after the generation of the first distribution matrix. In step  1406 , a second distribution matrix is generated by adding a new column of the sub-matrices to the first distribution matrix. The new column differs from each column of the first distribution matrix in at least (S−1) of the sub-matrices in the new column. For example, comparing the distribution matrices of  FIGS. 8 and 10 , the new column in  FIG. 10  includes the sub-matrices D, K, and C. Note that while each of D, K, and C appears in one other column in the distribution matrix, no two of the new sub-matrices occur in the same positions in any of the other columns. 
   In step  1407 , a new adjustment value is generated for the new column of the second distribution matrix. The new adjustment value is an integral multiple of N. In some embodiments, the new adjustment value is N greater than the largest adjustment value of the first distribution matrix. For example, comparing the adjustment matrices of  FIGS. 8 and 10 , the new adjustment value is 65. 
   Step  1408  can be performed at any time after generating the second distribution matrix, the new adjustment value, and the adjustment values for the first distribution matrix. In step  1408 , a second routing matrix pattern is generated from the second distribution matrix and the adjustment values corresponding to each column. 
   In step  1409 , a second routing matrix for a second PLD is implemented by applying the second routing matrix pattern to provide programmable interconnections between second input terminals and second output terminals of the second routing matrix (e.g., in a fashion similar to that of  FIGS. 2–5 ). Each signal value in the second routing matrix pattern corresponds to one of the second input terminals. Each row of signal values in the second routing matrix pattern corresponds to a set of the second input terminals programmably coupled to a different one of the second output terminals. 
   The two routing matrices generated by following the series of steps in  FIG. 14  are closely related to one another. In fact, such a process can be used to generate routing matrices  1202  and  1204 , or routing matrices  1204  and  1207 , of  FIG. 12 . As described in connection with  FIG. 12 , hardware and software implementation of the resulting set of PLDs is simplified by maintaining this relationship between the variously-sized routing matrices. 
   The method of  FIG. 14  can be simplified, for example, as shown in  FIG. 15 .  FIG. 15  illustrates the steps of a second exemplary method of implementing a set of PLDs according to yet another aspect of the present invention. This method can also be used, for example, to implement the routing matrices corresponding to the routing matrix patterns of  FIGS. 9 and 11 , and/or the set of PLDs illustrated in  FIG. 12 . The method of  FIG. 15  differs from the method of  FIG. 14  in that no full-size second distribution matrix is generated. Instead, the second routing matrix is generated directly from the first routing matrix and from an additional routing matrix pattern derived from a new column and a new adjustment value. This method reduces the effort involved in layout out the second routing matrix, for example. 
   In step  1501 , a seed matrix is generated, e.g., as shown in  FIG. 6 . The seed matrix includes N rows and N columns of numerical signal values, where N is an integer greater than one. Each signal value appears at most once in each column and at most once in each row of the seed matrix. In some embodiments, each signal value appears exactly once in each column and exactly once in each row of the seed matrix. In some embodiments, N is a prime number (e.g., thirteen). In some embodiments, N equals X to the power of Y, where X is any prime number and Y is any positive integer. In one embodiment, X is two, Y is three, and N is eight. 
   In step  1502 , a distribution matrix is generated, e.g., as shown in  FIG. 8 . The distribution matrix includes S rows and T columns of sub-matrices, where S and T are integers greater than one. Each column of the distribution matrix differs from each other column of the distribution matrix in at least (S−1) of the sub-matrices in the column. In the embodiment of  FIG. 8 , S is three and T is five. 
   In step  1503 , a corresponding adjustment value is generated for each column of the distribution matrix. Each adjustment value is an integral multiple of N. In some embodiments (e.g., in the embodiment of  FIG. 8 ), an adjustment matrix is generated, each column including the corresponding adjustment value for a corresponding column of the distribution matrix. In some embodiments (e.g., the embodiment of  FIG. 8 ), a first column in the distribution matrix has a corresponding adjustment value of 0, a second column in the distribution matrix has a corresponding adjustment value of N, a third column in the distribution matrix has a corresponding adjustment value of 2N, and so forth. 
   In step  1504 , a routing matrix pattern is generated from the distribution matrix and the adjustment values associated with each column of the distribution matrix, e.g., as shown in  FIG. 9 . More specifically, the corresponding adjustment value is added to each signal value in each sub-matrix in each column of the distribution matrix. 
   In step  1505 , a first routing matrix for the PLD is implemented by applying the routing matrix pattern to provide programmable interconnections between input terminals and output terminals of the first routing matrix (e.g., in a fashion similar to that of  FIGS. 2–5 ). Each signal value in the routing matrix pattern corresponds to one of the input terminals. Each row of signal values in the routing matrix pattern corresponds to a set of the input terminals programmably coupled to a different one of the output terminals. 
   Step  1506  can be performed at any time after the generation of the seed matrix. In step  1506 , a new column is generated of the sub-matrices to the distribution matrix. The new column differs from each column of the distribution matrix in at least (S−1) of the sub-matrices in the new column. Note that this limitation can be met irregardless of the order in which the distribution matrix and the new column are generated. 
   In step  1507 , a new adjustment value is generated for the new column. The new adjustment value is an integral multiple of N. In some embodiments, the new adjustment value is N greater than the largest adjustment value of the distribution matrix. 
   In step  1508 , an additional routing matrix pattern is generated from the new column and the new adjustment value. Therefore, the additional routing matrix pattern includes only one signal value in each row. 
   In step  1509 , a second routing matrix for the second PLD is implemented by applying the additional routing matrix pattern to add to the first routing matrix additional interconnections between newly added input terminals and the existing output terminals. Each signal value in the additional routing matrix pattern corresponds to one of the newly added input terminals programmably coupled to a different one of the existing output terminals. 
   The two routing matrices generated by following the series of steps in  FIG. 15  can be, for example, the same as two routing matrices generated by following the steps illustrated in  FIG. 14 . For example, the method illustrated in  FIG. 15  can be used to generate two routing matrices corresponding to the routing patterns illustrated in  FIGS. 9 and 11 . 
   Those having skill in the relevant arts of the invention will now perceive various modifications and additions that can be made as a result of the disclosure herein. For example, referring to  FIG. 14 , the second routing matrix pattern can be generated by simply taking the first routing matrix pattern and adding another column derived from the new column of the second distribution matrix and the new adjustment value. This and other variations on the methods of the invention are encompassed thereby. As another example, the above text describes the circuits and methods of the invention in the context of Complex Programmable Logic Devices (CPLDs). However, methods of the invention can also be applied to other programmable logic devices (PLDs) that include routing multiplexers. 
   Accordingly, all such modifications and additions are deemed to be within the scope of the invention, which is to be limited only by the appended claims and their equivalents.