Mapping of programmable logic devices

Abstract

A method for mapping an electronic digital circuit to a Look Up table (LUT) based Programmable Logic Deviceoperates by selecting an unmapped or partially mapped LUT, and identifying a group of circuit elements for mapping on the selected LUT based on the available capacity of the selected LUT and the mapping constraints. The identified circuit elements are mapped onto the selected LUT. The identification of circuit elements and mapping is carried out while taking into consideration the Cascade Logic associated with the selected LUT. The process continues until all circuit elements have been mapped. The group of circuit elements is mapped to the cascade logic prior to mapping on the LUTs. Conversely, the cascade logic is incorporated only after all circuit elements have initially been mapped onto LUTs or some elements remain unmapped after all LUTs have been utilized. The mapping constraints include timing, placement, and size constraints.

1. An improved method for mapping an electronic digital circuit to a Look Up table (LUT) based Programmable Logic Device (PLD) comprising the steps of:
 selecting an unmapped or partially mapped LUT, 
 identifying a group of circuit elements for mapping based on an available capacity of the selected LUT and a plurality of mapping constraints, 
 mapping the group of circuit elements onto the selected LUT, 
 continuing the process of selecting an LUT, forming a group of circuit elements and mapping until all the circuit elements have been mapped, 
 wherein the cascade logic associated with each LUT is also incorporated in the steps of forming the group of circuit elements and the mapping of the group; and 
 wherein the cascade logic is incorporated only after either all circuit elements have initially been mapped onto LUTs or some circuit elements remain unmapped even after all LUTs have been utilized. 
 
     
     
       2. An improved method as claimed in  claim 1  wherein said group of circuit elements are mapped to the cascade logic prior to mapping on the LUTs. 
     
     
       3. An improved method as claimed in  claim 1  wherein the mapping constraints include timing constraints, placement constraints, and size constraints. 
     
     
       4. An improved method as claimed in  claim 1  wherein the mapping on the Cascade logic incorporates one or more of the following constraints depending upon the connectivity of the architecture:
 XOR, XNOR and NOT functions are not mapped on the cascade logic, 
 only one of either the gate mapped onto the cascade logic or its input LUTs have multiple fan-outs, 
 if the output of the cascade logic is a primary output, then the gate mapped onto it is not an ‘AND’ or ‘NOR’ gate, 
 if the mapped gate has multiple fan outs then the outputs are not connected to more than one other gate mapped into a cascade logic element, and 
 if the mapped gate connects to the output of a multi-fan out LUT then the output of the LUT is not, connected to more than one cascade logic element. 
 
     
     
       5. An improved method as claimed in  claim 1  including the verification of one or more of the following conditions at the initial mapping of the cascade logic chain depending upon the connections of the architecture:
 the number of common inputs to the fan-in LUTs of the cascade logic is not greater than the number of inputs of the LUT, 
 the gate mapped onto the cascade logic is not of the type XOR, XNOR or NOT, and 
 only one of either the gates mapped on top the cascade logic or its input LUTs is multi fan. 
 
     
     
       6. An improved system for mapping an electronic digital circuit to a Look up table (LUT) based Programmable Logic Device (PLD) comprising:
 selecting means for selecting an unmapped or partially mapped LUT, 
 grouping means for clustering circuit elements for mapping based on an available capacity of the selected LUT and at least one mapping constraint, 
 mapping means for mapping the group of circuit elements onto the selected LUT, and 
 wherein the grouping means and mapping means include the mapping of cascade logic associated with the selected LUT after mapping of the group of circuit elements onto the LUT. 
 
     
     
       7. A method for mapping circuit elements into a programmable logic device including look-up tables and cascade elements, the method comprising:
 selecting a look-up table; 
 identifying a group of circuit elements to be mapped into the selected look-up table; 
 mapping the identified group of circuit elements into the selected look-up table; determining whether additional circuit elements can be identified and mapped into the look-up table; 
 if the determination is that additional circuit elements can be mapped into the look-up table, mapping the additional circuit elements into the look-up table; 
 if the determination is that additional circuit elements cannot be mapped into the look-up table, determining whether the additional circuit elements can be mapped into a cascade element or elements; 
 if the determination is that the additional circuit elements can be mapped into a cascade element or elements, then mapping the additional circuit elements into the cascade element or elements; 
 if the determination is that the additional circuit elements cannot be mapped into the cascade element or elements, then selecting a new look-up table and mapping the circuit elements into the new look-up table; and 
 repeating the operations of mapping the identified group of circuit elements into the selected look-up table through if the determination is that additional logic cannot be mapped into the cascade element or elements until all circuit elements have been mapped. 
 
     
     
       8. The method of  claim 7  wherein circuit elements are mapped to the cascade logic prior to being mapped into the look-up tables. 
     
     
       9. The method of  claim 7  further comprising:
 identifying the circuit elements to be mapped to the cascade element or elements prior to mapping elements into the look-up tables; 
 mapping all circuit elements into the look-up tables without consideration of the cascade element or elements to generate a mapped list; 
 extracting from the mapped list the circuit elements to be mapped to the cascade element or elements; and 
 mapping the identified circuit elements to the cascade element or elements. 
 
     
     
       10. The method of  claim 7  wherein the operations of mapping the circuit elements are done in accordance with certain mapping constraints such as timing constraints, placement constraints, and size constraints. 
     
     
       11. The method of  claim 7  wherein circuit elements comprise NAND or NOR gates that are mapped to the cascade elements. 
     
     
       12. A method for programming a programmable logic device including look-up tables and cascade elements, the method comprising:
 mapping logic into the look-up tables; 
 mapping logic into the cascade elements; 
 repeating the operations of mapping logic into the look-up tables and mapping logic into the cascade elements until all logic has been mapped into the programmable logic device; 
 identifying logic to be mapped to the cascade elements prior to mapping logic into the look-up tables; 
 mapping all logic into the look-up tables to generate a mapped list; and 
 extracting from the mapped list the logic to be mapped into the cascade elements; and 
 mapping the identified logic to the cascade elements. 
 
     
     
       13. The method of  claim 12  wherein the mapping of logic is done in accordance with certain mapping constraints such as timing constraints, placement constraints, and size constraints. 
     
     
       14. An electronic system for programming a programmable logic device, the programmable logic device including look-up tables and including cascade elements, and the electronic system comprising:
 a selection circuit operable to select look-up tables within the programmable logic device; 
 a logic grouping circuit coupled to the selection circuit and operable to select and group logic as a function of the available capacity of a selected look-up table; and 
 a mapping circuit coupled to the selection and logic grouping circuits and operable to map grouped logic into the selected look-up table and into the cascade elements as a function of the available capacity of the selected look-up table, the cascade logic being mapped after the grouped logic is mapped into the selected look-up table. 
 
     
     
       15. The electronic system of  claim 14 , wherein the programmable logic device comprises a field programmable gate array. 
     
     
       16. The electronic system of  claim 14 , wherein the electronic system comprises a computer system. 
     
     
       17. The electronic system of  claim 14 , wherein the mapping circuit operates to map grouped logic into cascade elements only when a selected look-up table is full and further operates to select a new look-up table when grouped logic cannot be mapped into the currently selected look-up table or the cascade elements. 
     
     
       18. The electronic system of  claim 14  wherein each programmable logic device comprises logic block circuitry, input/output circuitry, and routing channel circuitry. 
     
     
       19. A method implemented by a compiler that includes software and hardware on which the software operates, the method comprising:
 identifying a circuit based on a mapping constraint and an available capacity of a look up table (LUT) of a device;   mapping the identified circuit onto the LUT; and   mapping cascade logic associated with the LUT after the mapping of the circuit onto the LUT.   
     
     
       20. The method as recited in claim 19, wherein the cascade logic is incorporated after each said circuit has been initially been mapped onto one or more said LUTs or one or more said circuits remain unmapped even after each of the LUTs of the device have been utilized. 
     
     
       21. The method as recited in claim 19, wherein the mapping constraint includes a timing constraint, a placement constraint, or a size constraint. 
     
     
       22. The method as recited in claim 19, wherein the mapping of the cascade logic incorporates one or more of the following constraints that are dependent upon connectivity of an architecture:
 XOR, XNOR and NOT functions are not mapped on the cascade logic;   either the gate mapped onto the cascade logic or its input said LUTs have multiple fan-outs, not both;   if the output of the cascade logic is a primary output, then the gate mapped onto it is not an ‘AND’ or ‘NOR’ gate;   if a mapped gate has multiple fan outs then respective outputs are not connected to more than one other gate mapped into a cascade logic element; and   if a mapped gate connects to the output of a multi-fan out LUT then an output of the LUT is not connected to more than one cascade logic element.   
     
     
       23. The method as recited in claim 19, wherein the mapping of the cascade logic includes verifying one or more of the following conditions that are dependent upon connections of an architecture:
 a number of common inputs to a fan-in said LUTs of the cascade logic is not greater than a number of inputs of the LUT;   a gate mapped onto the cascade logic is not of type XOR, XNOR or NOT; and   either the gates mapped on top the cascade logic or its input LUTs is multi fan, not both.   
     
     
       24. The method as recited in claim 19, further comprising clustering elements to form the circuit based on the available capacity of the LUT. 
     
     
       25. The method as recited in claim 19, further comprising:
 determining whether an additional circuit is able to be mapped into the LUT; and   if determination is that the additional circuit is able to be mapped into the LUT, mapping the additional circuit into the LUT.   
     
     
       26. The method as recited in claim 25, further comprising if the determination is that the additional circuit is not able to be mapped into the LUT, determining whether the additional circuits are able to be mapped into cascade logic. 
     
     
       27. The method as recited in claim 26, further comprising if the determination is that the additional circuit is able to mapped into cascade logic, then mapping the additional circuit into the cascade logic. 
     
     
       28. The method as recited in claim 27, further comprising if the determination is that the additional circuit is not able to be mapped into the cascade logic, then selecting a new LUT and mapping the additional circuit into the new LUT. 
     
     
       29. The method as recited in claim 27, wherein the additional circuit is mapped to the cascade logic prior to being mapped into the LUT. 
     
     
       30. The method as recited in claim 27, wherein the additional circuit comprises NAND and NOR gates that are mapped to the cascade logic. 
     
     
       31. A method implemented by a compiler that includes software and hardware on which the software operates, the method comprising:
 selecting at least one look up table (LUT) of a device;   identifying a circuit based on a mapping constraint and an available capacity of the selected LUT; and   mapping the identified circuit onto the selected LUT such that cascade logic associated with the selected LUT is incorporated in mapping the circuit,   wherein the compiler maps the cascade logic after each of said circuits has been initially been mapped onto the LUT or one or more of said circuits remain unmapped even after each of the LUTs of the device have been utilized.   
     
     
       32. The method as recited in claim 31, wherein the mapping constraint includes a timing constraint, a placement constraint, or a size constraint. 
     
     
       33. The method as recited in claim 31, wherein the cascade logic is mapped to follow one or more constraints that are dependent upon connectivity of an architecture as follows:
 XOR, XNOR and NOT functions are not mapped on the cascade logic;   either the gate mapped onto the cascade logic or its input said LUTs have multiple fan-outs, not both;   if the output of the cascade logic is a primary output, then the gate mapped onto it is not an ‘AND’ or ‘NOR’ gate;   if a mapped gate has multiple fan outs then respective outputs are not connected to more than one other gate mapped into a cascade logic element; and   if a mapped gate connects to the output of a multi-fan out LUT then an output of the LUT is not connected to more than one cascade logic element.   
     
     
       34. The method as recited in claim 31, wherein the cascade logic is mapped to follow one or more conditions that are dependent upon connections of an architecture as follows:
 a number of common inputs to a fan-in said LUTs of the cascade logic is not greater than a number of inputs of the LUT;   a gate mapped onto the cascade logic is not of type XOR, XNOR or NOT; and   either the gates mapped on top the cascade logic or its input LUTs is multi fan, not both.   
     
     
       35. The method as recited in claim 31, further comprising clustering elements to form the circuit based on the available capacity of the selected LUT. 
     
     
       36. The method as recited in claim 31, further comprising:
 determining whether an additional circuit is able to be mapped into the selected LUT; and   if the determination is that the additional circuit is able to be mapped into the selected LUT, mapping the additional circuit into the selected LUT.   
     
     
       37. The method as recited in claim 36, further comprising if the determination is that the additional circuit is not able to be mapped into the selected LUT, determining whether the additional circuit is able to be mapped into cascade logic. 
     
     
       38. The method as recited in claim 37, further comprising if the determination is that the additional circuit is able to mapped into the cascade logic, then mapping the additional circuit into the cascade logic. 
     
     
       39. The method as recited in claim 38, further comprising if the determination is that the additional circuit is not able to be mapped into the cascade logic, then selecting a new said LUT and mapping the additional circuit into the new said LUT. 
     
     
       40. A method implemented by a compiler that includes software and hardware on which the software operates, the method comprising:
 selecting, by the compiler, a look up table (LUT) from one or more LUTs of a programmable logic device (PLD);   identifying a circuit based on a mapping constraint and an available capacity of the selected LUT;   mapping the identified circuit onto the selected LUT, and   mapping cascade logic associated with the selected LUT when at least one circuit remains unmapped after each of the one or more LUTs of the PLD have been utilized.   
     
     
       41. The method as recited in claim 40, wherein the mapping constraint includes a timing constraint, a placement constraint, or a size constraint. 
     
     
       42. The method as recited in claim 40, wherein the mapping of the cascade logic incorporates one or more of the following constraints that are dependent upon connectivity of an architecture:
 XOR, XNOR and NOT functions are not mapped on the cascade logic;   either the gate mapped onto the cascade logic or its input said LUTs have multiple fan-outs, not both;   if the output of the cascade logic is a primary output, then the gate mapped onto it is not an ‘AND’ or ‘NOR’ gate;   if a mapped gate has multiple fan outs then respective outputs are not connected to more than one other gate mapped into a cascade logic element; and   if a mapped gate connects to the output of a multi-fan out LUT then an output of the LUT is not connected to more than one cascade logic element.   
     
     
       43. The method as recited in claim 40, wherein the mapping of the cascade logic includes verifying one or more of the following conditions that are dependent upon connections of an architecture:
 a number of common inputs to a fan-in said LUTs of the cascade logic is not greater than a number of inputs of the LUT;   a gate mapped onto the cascade logic is not of type XOR, XNOR or NOT; and   either the gates mapped on top the cascade logic or its input LUTs is multi fan, not both.   
     
     
       44. The method as recited in claim 40, further comprising clustering one or more elements to form the circuit based on the available capacity of the selected LUT. 
     
     
       45. The method as recited in claim 40, further comprising:
 determining whether an additional circuit is able to be mapped into the selected LUT; and   if the determination is that the additional circuit is able to be mapped into the selected LUT, mapping the additional circuit into the selected LUT.   
     
     
       46. The method as recited in claim 45, further comprising if the determination is that the additional circuit is not able to be mapped into the selected LUT, determining whether the additional circuit is able to be mapped into cascade logic. 
     
     
       47. The method as recited in claim 46, further comprising if the determination is that the additional circuit is able to mapped into the cascade logic, then mapping the additional circuit into the cascade logic. 
     
     
       48. The method as recited in claim 47, further comprising if the determination is that the additional circuit is not able to be mapped into the cascade logic, then selecting a new said LUT and mapping the additional circuit into the new said LUT. 
     
     
       49. An apparatus comprising a compiler that includes software and hardware on which the software operates to cause the apparatus to:
 identify a circuit based on a mapping constraint and an available capacity of a look up table (LUT) of a device;   map the identified circuit onto the LUT such that cascade logic of the LUT is incorporated in mapping the circuit,   wherein the compiler maps the cascade logic after each of said circuits has been initially been mapped onto the LUT or one or more of said circuits remain unmapped even after each of the LUTs of the device have been utilized.   
     
     
       50. The apparatus as recited in claim 49, wherein the mapping constraint includes a timing constraint, a placement constraint, or a size constraint. 
     
     
       51. The apparatus as recited in claim 49, wherein the compiler is operable to incorporate one or more of the following constraints that are dependent upon connectivity of an architecture:
 XOR, XNOR and NOT functions are not mapped on the cascade logic;   either the gate mapped onto the cascade logic or its input said LUTs have multiple fan-outs, not both;   if the output of the cascade logic is a primary output, then the gate mapped onto it is not an ‘AND’ or ‘NOR’ gate;   if a mapped gate has multiple fan outs then respective outputs are not connected to more than one other gate mapped into a cascade logic element; and   if a mapped gate connects to the output of a multi-fan out LUT then an output of the LUT is not connected to more than one cascade logic element.   
     
     
       52. The apparatus as recited in claim 49, wherein the compiler is operable to verify one or more of the following conditions that are dependent upon connections of an architecture:
 a number of common inputs to a fan-in said LUTs of the cascade logic is not greater than a number of inputs of the LUT;   a gate mapped onto the cascade logic is not of type XOR, XNOR or NOT; and   either the gates mapped on top the cascade logic or its input LUTs is multi fan, not both.   
     
     
       53. The apparatus as recited in claim 49, wherein the compiler is further configured to cluster elements to form the circuit based on the available capacity of the LUT. 
     
     
       54. The apparatus as recited in claim 49, wherein the compiler is further configured to:
 determine whether an additional circuit is able to be mapped into the LUT; and   if the determination is that the additional circuit is able to be mapped into the LUT, map the additional circuit into the LUT.   
     
     
       55. The apparatus as recited in claim 54, wherein the compiler is further configured such that if the determination is that the additional circuit is not able to be mapped into the LUT, determine whether the additional circuit is able to be mapped into cascade logic. 
     
     
       56. The apparatus as recited in claim 55, wherein the compiler is further configured such that if the determination is that the additional circuit is able to be mapped into the cascade logic, the additional circuit is mapped into the cascade logic. 
     
     
       57. The apparatus as recited in claim 56, wherein the compiler is further configured such that if the determination is that the additional circuit is not able to be mapped into the cascade logic, then a new LUT is selected and the additional circuit is mapped into the new LUT. 
     
     
       58. The apparatus as recited in claim 56, wherein the additional circuit is mapped to the cascade logic prior to being mapped into the LUT. 
     
     
       59. The apparatus as recited in claim 56, wherein the additional circuit includes NAND or NOR gates that are mapped to the cascade logic. 
     
     
       60. The apparatus as recited in claim 49, wherein the compiler includes software and hardware on which the software operates. 
     
     
       61. One or more computer-readable storage devices comprising software that is executable on hardware to:
 select an unmapped or partially mapped look up table (LUT) from one or more LUTs of a programmable logic device (PLD);   more LUTs of a programmable logic device (PLD);   identify a circuit based on a mapping constraint and an available capacity of the selected LUT;   cause the identified circuit to be mapped onto the selected LUT, and   cause cascade logic associated with the selected LUT to be mapped after each said circuit has been mapped onto the LUTs or when at least one circuit remains unmapped after each of the one or more LUTs of the PLD has been utilized.   
     
     
       62. One or more computer-readable storage devices as recited in claim 61, wherein the mapping constraint includes a timing constraint, a placement constraint, or a size constraint. 
     
     
       63. One or more computer-readable storage devices as recited in claim 61, wherein the mapping of the cascade logic incorporates one or more of the following constraints that are dependent upon connectivity of an architecture;
 XOR, XNOR and NOT functions are not mapped on the cascade logic;   either the gate mapped onto the cascade logic or its input said LUTs have multiple fan-outs, not both;   if the output of the cascade logic is a primary output, then the gate mapped onto it is not an ‘AND’ or ‘NOR’ gate;   if a mapped gate has multiple fan outs then respective outputs are not connected to more than one other gate mapped into a cascade logic element; and   if a mapped gate connects to the output of a multi-fan out LUT then an output of the LUT is not connected to more than one cascade logic element.   
     
     
       64. One or more computer-readable storage devices as recited in claim 61, wherein the mapping of the cascade logic includes verifying one or more of the following conditions that are dependent upon connections of an architecture:
 a number of common inputs to a fan-in said LUT of the cascade logic is not greater than a number of inputs of the LUT;   a gate mapped onto the cascade logic is not of type XOR, XNOR or NOT; and   either the gates mapped on top the cascade logic or its input LUTs is multi fan, not both.   
     
     
       65. One or more computer-readable storage devices as recited in claim 61, wherein the software is further configured to cluster elements to form the circuit based on the available capacity of the LUT. 
     
     
       66. One or more computer-readable storage devices as recited in claim 61, wherein the software is further configured to:
 determine whether an additional circuit is able to be mapped into the LUT; and   if the determination is that the additional circuit is able to be mapped into the LUT, map the additional circuit into the LUT.   
     
     
       67. One or more computer-readable storage devices as recited in claim 66, wherein the software is further configured such that if the determination is that the additional circuit is not able to be mapped into the LUT, a determination is made as to whether the additional circuit is able to be mapped into a cascade logic. 
     
     
       68. One or more computer-readable storage devices as recited in claim 67, wherein the software is further configured such that if the determination is that the additional circuit is able to mapped into cascade logic, the additional circuit is mapped into cascade logic. 
     
     
       69. One or more computer-readable storage devices as recited in claim 68, wherein the software is further configured such that if the determination is that the additional circuit is not able to be mapped into cascade logic, then a new LUT is selected and the additional circuit is mapped into the new LUT. 
     
     
       70. One or more computer-readable storage devices as recited in claim 69, wherein the additional circuit is mapped to the cascade logic prior to being mapped into the LUT. 
     
     
       71. One or more computer-readable storage devices as recited in claim 70, wherein the additional circuit includes NAND or NOR gates that are mapped to the cascade logic. 
     
     
       72. One or more computer-readable storage devices as recited in claim 61, wherein the software is a compiler. 
     
     
       73. One or more computer-readable storage devices comprising software that is executable on hardware to:
 decompose a cluster of logic representing a logic function into logic gates;   identify, among the logic gates, one or more logic gates to be mapped to one or more cascade elements;   map the logic gates to one or more look up tables;   extract the identified one or more logic gates; and   map the identified one or more logic gates onto the one or more cascade elements.   
     
     
       74. The one or more computer-readable storage devices as recited in claim 73, wherein the mapping the logic gates to one or more look up tables causes a mapped list to be generated. 
     
     
       75. The one or more computer-readable storage devices as recited in claim 74, wherein the mapped list comprises the identified one or more logic gates configured to be extracted.