Mapping of programmable logic devices

• US 20040133869A1
• Filed: 09/29/2003
• Published: 07/08/2004
• Est. Priority Date: 09/27/2002
• Status: Active Grant

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Inventors: Sharma, Sunil Kumar
• Granted Patent: US 7,124,392 B2
• Time in Patent Office: Days
• US Class Current: 716/16
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

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.

Claims

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 the available capacity of the selected LUT and the mapping constraints,

mapping the group of circuit elements onto the selected LUT, and

continuing the process of selecting an LUT, forming a group of circuit elements and mapping until all the circuit elements have been mapped,

characterized in that, 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.

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 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.

4. An improved method as claimed in claim 1 wherein the mapping constraints include timing constraints, placement constraints, and size constraints.

5. 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.

6. 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.

7. 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 the available capacity of the selected LUT and the mapping constraints,

mapping means for mapping the group of circuit elements onto the selected LUT, and

characterized in that, the grouping means and mapping means include the mapping of cascade logic associated with the selected LUT.

8. 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.

9. The method of claim 8 wherein circuit elements are mapped to the cascade logic prior to being mapped into the look-up tables.

10. The method of claim 8 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.

11. The method of claim 8 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.

12. The method of claim 8 wherein circuit elements comprise NAND or NOR gates that are mapped to the cascade elements.

13. 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; and

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.

14. The method of claim 13 wherein further comprising:

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.

15. The method of claim 13 wherein the mapping of logic is done in accordance with certain mapping constraints such as timing constraints, placement constraints, and size constraints.

16. 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.

17. The electronic system of claim 16 wherein the programmable logic device comprises a field programmable gate array.

18. The electronic system of claim 16 wherein the electronic system comprises a computer system.

19. The electronic system of claim 16 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.

20. The electronic system of claim 16 each programmable logic device comprises logic block circuitry, input/output circuitry, and routing channel circuitry.