Programming process for 3-level programming logic devices

• US 5,349,691 A
• Filed: 05/04/1993
• Issued: 09/20/1994
• Est. Priority Date: 07/03/1990
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Malik, Abdul, Harrison, David A.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): SHAH, ALPESH
• Application Number:
  US08/058,679
• Time in Patent Office: 504 Days
• Field of Search: 395/800, 395/650, 307/465, 364/716, 364/736, 364/741, 364/750.5, 364/735, 340/825.79, 340/825.8
• US Class Current: 326/38
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: H03K 19/17704 the logic functions being realised by the interconnection of rows and columns

Abstract

A process of programming a programmable logic device (PLD) to carry out a specified logic function. The PLD contains three levels of logic implemented as a plurality of functional blocks, each with AND and OR planes, and a programmable interconnect matrix or logic expander carrying out AND logic. After providing such a PLD with specified size constraints and after specifying a logic function, the function is split or factored into subfunctions or factors. A Boolean factorization procedure chooses factors by replacing pairs of product terms in the first factor with their supercube and minimizing the number input terms and product terms required. Subfunctions or factors which are too large can be simplified by combining pairs of inputs in the interconnect matrix. The product terms of a subfunction or factor can be ordered according to the number of input terms they have and assigned to the functional blocks one at a time. Functional blocks which use many inputs or product terms per output can have some of their assigned subfunctions split so as to pack the PLD more densely. Split subfunctions or factors are recombined in the interconnect matrix. After assigning terms to functional blocks and the matrix, they are loaded into the PLD using a device programmer to configure the logic arrays in the PLD.

Claims

1. A process of programming a programmable logic device for carrying out a specified logic function, the programmable logic device to be programmed being of a type having multiple logic blocks, each logic block of said programmable logic device having input lines, output lines and successive configurable first and second arrays between said input lines and output lines for carrying out first and second levels of logic, said programmable logic device also having input pins, output pins and means, programmably combining selected output lines of said logic blocks, for carrying out a third level of logic, input lines to said logic blocks coupling to selected input pines of said programmable logic device and output lines from said means for carrying out the third level of logic coupling to selected output pins of said programmable logic device, the programming process comprising:

factoring a specified multiple output logic function into multiple factors using apparatus other than the programmable logic device that has been provided to be programmed, each factor being in sum-of-products form, wherein said factoring of said logic function includes replacing at least one pair of existing product terms of said logic function, with a corresponding "supercube" product term whose input terms consist only of those input terms which are present in both product terms of the replaced pair and whose output terms consist of those output terms which are present in either product term of the replaced pair and whose output terms consist of those output terms which are present in either product term of the replaced pair wherein plural sets of factors are determined for said logic function, each set of factors having a certain number of product terms, one particular set of factors that is found upon comparison with the other sets of factors that is found upon comparison with the other sets of factors to have a fewest number of product terms being a selected set for loading into said programmable logic device,

loading each factor of the selected set of factors of said logic function into a logic block of said programmable logic device, the entire set of factors being loaded into a plurality of said logic blocks, wherein loading a factor includes configuring the first array for carrying out said first level of logic such that product terms corresponding to said factor are produced by said first array from signals on said input lines and configuring the second array for carrying out said second level of logic such that said product terms are combined to produce said factor at said output liens, and

configuring said means for carrying out said third level of logic such that outputs from said logic blocks representing said factors are combined to produce said logic function at said output pins.

2. The process of claim 1 wherein said second level of logic provides programmable inversion and said third level of logic provides programmable inversion on its output lines.

3. The process of claim 1 wherein at least one of said factors has multiple outputs.

4. A process of programming a programmable logic device for carrying out a specified logic function, the programmable logic device to be programmed being of a type having multiple functional blocks, each functional block of said programmable logic device having a number of input lines, output lines and successive configurable first and second arrays between said input lines and output lines for carrying out first and second levels of logic, said programmable logic device also having input pins, output pins and a programmable interconnect matrix connected to said inputs and outputs of said functional blocks and to said input pins and output pins of said programmable logic device, said programmable interconnect matrix being configurable by means of programming so as to connect selected input pins of said programmable logic device to selected input lines of said functional blocks and to connect selected output lines of said functional blocks to selected output pins of said programmable logic device for carrying out a third level of logic, the programming process comprising:

assigning subfunctions of a specified logic function to be programmed into said programmable logic device to particular functional blocks using apparatus other than the programmable logic device that has been provided to be programmed, said logic function being representable as a plurality of subfunctions in sum-of-products form, each subfunction having a set of product terms with a certain number of input terms,

selecting input terms to be logically combined in said programmable interconnect matrix whenever the number of input terms required by the subfunctions assigned to a particular functional block exceed the number of input lines to that functional block, the selected input terms being those input terms which are combined to form product terms of the assigned subfunctions,

loading said assigned subfunctions into said particular functional blocks by configuring the first array of each functional block to carry out said first level of logic such that product terms corresponding to said subfunctions are produced by said first arrays from signals on said input lines and by configuring the second array of each functional block to carry out said second level of logic such that said product terms produced by said first arrays are combined in said second arrays to produce said subfunctions at said output lines, and

configuring said programmable interconnect matrix for carrying out said third level of logic such that input terms received from said selected input pins are logically combined in said programmable interconnect matrix to produce combined input terms connected to said selected input liens of assigned functional blocks and such that outputs from said functional blocks representing said subfunctions are logically combined in said programmable interconnect matrix to produce said logic function on said output pins.

5. The process of claim 4 further defined by assigning each subfunction to an output cell in at least one functional block, such that each product term having more input terms than input lines available in an assigned functional block has selected input terms in that product term assigned to be logically combined in said programmable interconnect matrix prior to being loaded into said assigned functional block.

6. The process of claim 4 further defined by selecting input terms to reduce the number of product terms.

7. The process of claim 4 further defined by selecting the polarity of signals leading into and out of said programmable interconnect matrix.

8. The process of claim 4 wherein assigning subfunction to particular functional blocks includes splitting any large subfunction into a plurality of smaller subfunctions whenever a size of that large subfunction exceeds a predetermined size limit of a functional block, and then assigning each of said smaller subfunctions to a functional block.

9. The process of claim 8 wherein said large subfunction to be split exceeds the number of input terms available to a functional block.

10. The process of claim 8 wherein said large subfunction to be split exceeds the number of product terms available to a functional block.

11. The process of claim 8 wherein splitting a subfunction comprises an OR factorization in which product terms of said subfunction are grouped into at least two smaller subfunctions that are mapped onto output cells.

12. The process of claim 8 wherein splitting a subfunction comprises an AND factorization.

13. The process of claim 12 wherein said AND factorization is carried out by a Boolean factorization procedure.

14. The process of claim 4 wherein assigning each subfunction further comprises splitting at least one said subfunction assigned to a functional block into at least two subfunctions, whenever said functional block is assigned subfunctions such that a density measure is less than a predetermined threshold, and splitting subfunctions to use more output cells.

15. A process of programming a programmable logic device for carrying out a specified logic function, the programmable logic device to be programmed being of a type having multiple functional blocks, each functional block having input lines, output lines and successive configurable first and second arrays between said input lines and output lines for carrying out first and second levels of logic, said programmable logic device also having input pins, output pins and a programmable interconnect matrix connected to said inputs and outputs of said functional blocks and to said input pins and output pins of said programmable logic device, said programmable interconnect matrix being configurable by means of programming so as to connect selected input pins of said programmable logic device to selected input lines of said functional blocks and to connect selected output lines of said functional blocks to selected output pins of said programmable logic device for carrying out a third level of logic, the programming process comprising:

assigning subfunctions of a specified logic function to be programmed into said programmable logic device to particular functional blocks using apparatus other than the programmable logic device that has been provided to be programmed, said specified logic function being a multiple output function representable as a plurality of single output subfunctions in sum-of-products form, each subfunction having a set of product terms, the assigning of said subfunctions to particular functional blocks being carried out such that wherever a large subfunction exceeds a size limit of a functional block the assigning of said subfunctions splits said large subfunctional into a plurality of smaller subfunctions and assigns said smaller subfunctions to at least two separate functional blocks,

loading said assigned subfunctions into said particular functional blocks by configuring the first array of each functional block to carry out said first level of logic such that product terms corresponding to said subfunctions are produced by said first arrays from signals on said input lines and by configuring the second array of each functional block to carry out said second level of logic such that said product terms produced by said first arrays are combined in said second arrays to produce said subfunctions at said output lines, and

configuring said programmable interconnect matrix for carrying out said third level of logic such that said outputs from said functional blocks representing said subfunctions are logically combined in said programmable interconnect matrix to produce said logic function on said output pins.

16. The process of claim 15 wherein said provided programmable logic device includes means for selecting the polarity of signals leading into and out of said programmable interconnect matrix.

17. The process of claim 15 wherein said large subfunction to be split exceeds the number of input terms available to a functional block.

18. The process of claim 15 wherein said large subfunction to be split exceeds the number of product terms available to a functional block.

19. The process of claim 15 wherein splitting a subfunction comprises an OR factorization in which product terms of said subfunction are grouped into subfunctions that are mapped onto output cells.

20. The process of claim 15 wherein splitting a subfunction comprises an AND factorization.

21. The process of claim 20 wherein said AND factorization is carried out by a Boolean factorization procedure.

22. The process of claim 15 wherein assigning each subfunction further comprises splitting at least one of said subfunctions assigned to a functional block into at least two subfunctions, whenever said functional block is assigned subfunctions such that a density measure is less than a predetermined threshold, and splitting subfunctions to use more output cells.

23. A process of programming a programmable logic device for carrying out a specified logic function, the programmable logic device to be programmed being of a type having multiple functional blocks, each functional block having input lines, output lines and successive configurable first and second arrays between said input lines and output lines for carrying out first and second levels of logic, said programmable logic device also having input pins, output pins and a programmable interconnect matrix connected to said input lines and output lines of said functional blocks and to said input pins and output pins of said programmable logic device, said programmable interconnect matrix being configurable by means of programming so as to connect selected input pins of said programmable logic device to selected input lines of said functional blocks and to connect selected output lines of said functional blocks to selected output pins of said programmable logic device for carrying out a third level of logic, said programming process comprising:

assigning subfunctions of a specified logic function to be programmed into said programmable logic device to particular functional blocks using apparatus other than the programmable logic device that has been provided to be programmed, said specified logic function being a multiple output function representable as a plurality of single output subfunctions in sum-of-products form, each subfunction having a set of product terms, the assigning of said subfunctions to particular functional blocks being carried out such that wherever any functional block is initially assigned a set of one or more subfunctions such that a density measure of output lines used by the assigned subfunctions is less than a predetermined threshold, the assigning further includes splitting the subfunctions assigned to that functional block so as to use more output cells,

loading said assigned subfunctions into said particular functional blocks by configuring the first array of each functional block to carry out said first level of logic such that product terms corresponding to said subfunctions are produced by said first arrays from signals on said input lines and by configuring the second array of each functional block to carry out said second level of logic such that product terms produced by said first arrays are combined in said second arrays to produce said subfunctions at said output lines, and

configuring said programmable interconnect matrix for carrying out said third level of logic such that said outputs from said functional blocks representing said subfunctions are logically combined in said programmable interconnect matrix to produce said logic function on said output pins.

24. The process of claim 23 wherein said provided programmable logic device includes means for selecting the polarity of signals leading into and out of said programmable interconnect matrix.