Efficient method for mapping a logic design on field programmable gate arrays

• US 7,676,782 B2
• Filed: 12/27/2005
• Issued: 03/09/2010
• Est. Priority Date: 12/29/2004
• Status: Expired due to Fees

• Current Assignee: Sicronic Remote KG LLC (Intellectual Ventures LLC)
• Original Assignee: Sicronic Remote KG LLC (Intellectual Ventures LLC)
• Inventors: Samanta, Dhabalendu, Agarwal, Viren
• Primary Examiner(s): ROSSOSHEK, YELENA
• Application Number:
  US11/319,015
• Publication Number:
  US 20060190906A1
• Time in Patent Office: 1,533 Days
• Field of Search: 716/10, 716/11, 716/16, 703/19, 326/398, 326/39, 326/41, 257/678
• US Class Current: 716/138
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

An efficient method for mapping a logic design on Field Programmable Gate Arrays involves a determination of the minimum required square grid of FPGA logic blocks for mapping the design, providing a compensation factor on the minimum square grids, selecting the maximum value among the compensated square grids for reducing the mapping time; and implementing a legalization adjustment to ensure mapping of said compensated design.

Claims

1. A computer-implemented method for determining value of required Silicon area on a Field Programmable Gate Array (FPGA) to map a logic design, the method comprising:

determining a required Silicon area for logic blocks in the logic design by calculating the square root of the number of logic blocks in the logic design;

determining a required Silicon area for input and output cells in the logic design by dividing the number of input and output blocks in the logic design by two;

determining a required Silicon area for macros in the logic design by selecting the highest value of a maximum height or a maximum width of the macros in the logic design;

adjusting said determined required Silicon area for logic blocks, for input and output cells, and for macros in order to reduce an amount of time it will take to map the logic design onto the FPGA; and

selecting the highest value of said adjusted required Silicon area for logic blocks, said adjusted Silicon area for input and output cells, and said adjusted Silicon area for macros as the value of required Silicon area; and

mapping the logic design using the selected value of required Silicon area.

2. The method as recited in claim 1, further comprising readjusting said value of required Silicon area by:

determining a legalization value for macros by executing a legalization algorithm to find the minimum amount of silicon required to place all of the macros in the logic design without legalization;

determining a readjusted value for input and output cells by selecting the lesser of the adjusted Silicon area for input and output cells and the size of the FPGA; and

selecting the highest of the value of required Silicon area, the legalization value for macros, and the readjusted value for input and output cells, as the readjusted value of required Silicon area.

3. The method as recited in claim 1, wherein the value of required Silicon area is less than the FPGA'"'"'s area.

4. The method as recited in claim 1, wherein adjusting said determined required Silicon area for logic blocks comprises multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3.

5. The method as recited in claim 1, wherein adjusting said determined required Silicon area for input and output cells comprises multiplying said determined required Silicon area for input and output cells by a value of 1.2.

6. The method as recited in claim 1, wherein adjusting said determined required Silicon area for macros comprises multiplying said determined required Silicon area for macros by a value of 1.2.

7. The method as recited in claim 1, wherein adjusting said determined required Silicon area for logic blocks comprises multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3, wherein adjusting said determined required Silicon area for input and output cells comprises multiplying said determined required Silicon area for input and output cells by a value of 1.2, and wherein adjusting said determined required Silicon area for macros comprises multiplying said determined required Silicon area for macros by a value of 1.2.

8. The method as recited in claim 1, wherein adjusting said determined required Silicon area for logic blocks comprises multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3, wherein adjusting said determined required Silicon area for input and output cells comprises multiplying said determined required Silicon area for input and output cells by a value of 1.2, and wherein adjusting said determined required Silicon area for macros comprises multiplying said determined required Silicon area for macros by a value of 1.

9. A system for determining a value of required Silicon area on a Field Programmable Gate Array (FPGA) to map a logic design, the system comprising:

means for determining a required Silicon area for logic blocks in the logic design by calculating the square root of the number of logic blocks in the logic design;

means for determining a required Silicon area for input and output cells in the logic design by dividing the number of input and output blocks in the logic design by two;

means for determining a required Silicon area for macros in the logic design by selecting the highest value of a maximum height or a maximum width of the macros in the logic design;

means for adjusting said determined required Silicon area for logic blocks, for input and output cells, and for macros in order to reduce an amount of time it will take to map the logic design onto the FPGA; and

means for selecting the highest value of said adjusted required Silicon area for logic blocks, said adjusted Silicon area for input and output cells, and said adjusted Silicon area for macros as the value of required Silicon area.

10. The system as recited in claim 9, further comprising readjusting said value of required Silicon area by:

means for determining a legalization value for macros by executing a legalization algorithm to find the minimum amount of silicon required to place all of the macros in the logic design without legalization;

means for determining a readjusted value for input and output cells by selecting the lesser of the adjusted Silicon area for input and output cells and the size of the FPGA; and

means for selecting the highest of the value of required Silicon area, the legalization value for macros, and the readjusted value for input and output cells, as the readjusted value of required Silicon area.

11. The system as recited in claim 9, wherein the value of required Silicon area is less than the FPGA'"'"'s area.

12. The system as recited in claim 9, wherein adjusting said determined required Silicon area for logic blocks comprises means for multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3.

13. The system as recited in claim 9, wherein adjusting said determined required Silicon area for input and output cells comprises means for multiplying said determined required Silicon area for input and output cells by a value of 1.2.

14. The system as recited in claim 9, wherein adjusting said determined required Silicon area for macros comprises means for multiplying said determined required Silicon area for macros by a value of 1.2.

15. The system as recited in claim 9, wherein adjusting said determined required Silicon area for logic blocks comprises means for multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3, wherein adjusting said determined required Silicon area for input and output cells comprises multiplying said determined required Silicon area for input and output cells by a value of 1.2, and wherein adjusting said determined required Silicon area for macros comprises multiplying said determined required Silicon area for macros by a value of 1.2.

16. A mapping system configured to:

determine a required Silicon area for logic blocks in the logic design by calculating the square root of the number of logic blocks in the logic design;

determine a required Silicon area for input and output cells in the logic design by dividing the number of input and output blocks in the logic design by two;

determine a required Silicon area for macros in the logic design by selecting the highest value of a maximum height or a maximum width of the macros in the logic design;

adjust said determined required Silicon area for logic blocks, for input and output cells, and for macros in order to reduce an amount of time it will take to map the logic design onto the FPGA; and

select the highest value of said adjusted required Silicon area for logic blocks, said adjusted Silicon area for input and output cells, and said adjusted Silicon area for macros as a value of required Silicon area.

17. The mapping system as recited in claim 16, further comprising readjusting said value of required Silicon area by:

determining a legalization value for macros by executing a legalization algorithm to find the minimum amount of silicon required to place all of the macros in the logic design without legalization;

determining a readjusted value for input and output cells by selecting the lesser of the adjusted Silicon area for input and output cells and the size of the FPGA; and

selecting the highest of the value of required Silicon area, the legalization value for macros, and the readjusted value for input and output cells, as the readjusted value of required Silicon area.

18. The mapping system as recited in claim 16, wherein the value of required Silicon area is less than the FPGA'"'"'s area.

19. The mapping system as recited in claim 16, wherein adjusting said determined required Silicon area for logic blocks comprises multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3.

20. The mapping system as recited in claim 16, wherein adjusting said determined required Silicon area for input and output cells comprises multiplying said determined required Silicon area for input and output cells by a value of 1.2.

21. The mapping system as recited in claim 16, wherein adjusting said determined required Silicon area for macros comprises multiplying said determined required Silicon area for macros by a value of 1.2.

22. The mapping system as recited in claim 16, wherein adjusting said determined required Silicon area for logic blocks comprises multiplying said determined required Silicon area for logic blocks by a value between 1.5 and 3, wherein adjusting said determined required Silicon area for input and output cells comprises multiplying said determined required Silicon area for input and output cells by a value of 1.2, and wherein adjusting said determined required Silicon area for macros comprises multiplying said determined required Silicon area for macros by a value of 1.2.