Pin reordering during placement of circuit designs

• US 7,058,915 B1
• Filed: 09/30/2003
• Issued: 06/06/2006
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Singh, Amit, Chaudhary, Kamal
• Primary Examiner(s): Lin, Sun James
• Application Number:
  US10/676,445
• Time in Patent Office: 980 Days
• Field of Search: 716/10, 716/6
• US Class Current: 716/113
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method (400) of placing a circuit design can include the steps of identifying topological levels of a circuit design representation (415) and determining an arrival time for each input signal to a look up table within a circuit design representation (420). The propagation delay associated with each pin of the look up table can be identified (420) such that the input signals of the look up table can be ordered according to the arrival times of each input signal and the propagation delay of each pin of the look up table (435). The method can continue processing each look up table of an identified topological level (440) as well as each topological level of the circuit design representation (455).

Claims

1. A method of placing a circuit design comprising a component having input signals with asymmetric delays, the method comprising steps of:

first identifying topological levels of the circuit design;

determining an arrival time for each input signal of a plurality of input signals to the component;

identifying a propagation delay associated with each input port of a plurality of input ports of the component; and

ordering the plurality of input signals of the component according to arrival times associated with the plurality of input signals and propagation delays associated with the plurality of input ports of the component.

2. The method of claim 1, further comprising repeating said determining, said identifying, and said ordering steps for each component within one of said identified topological levels.

3. The method of claim 2, further comprising iteratively performing said repeating step for each of said identified topological levels of the circuit design.

4. The method of claim 3, wherein the identified topological levels are processed in hierarchical order.

5. The method of claim 4, further comprising updating timing information for the circuit design after ordering input signals of each component of an identified topological level.

6. The method of claim 1, said ordering step further comprising a step of matching input signals having an earlier arrival time with input ports of the component having longer propagation delays.

7. The method of claim 6, wherein said matching step matches a first input signal having the earliest arrival time with a first input port of the component having the longest propagation delay, and a second input signal having the latest arrival time with an input port of the component having the shortest propagation delay.

8. The method of claim 1, said ordering step comprising:

sorting input signals according to an arrival time at the component;

sorting input ports of the component according to propagation delay; and

matching said sorted input signals having an earlier arrival time with said sorted input ports having longer propagation delays.

9. The method of claim 8, wherein said matching step matches an input signal having the earliest arrival time with an input port of the component having the longest propagation delay, and an input signal having the latest arrival time with an input port of the component having the shortest propagation delay.

10. The method of claim 1 wherein the component is a look-up table (LUT).

11. A system for placing a circuit design comprising:

means for first identifying topological levels of the circuit design;

means for determining an arrival time for each input signal to a component within a circuit design representation;

means for identifying propagation delay associated with each pin of the component; and

means for ordering input signals of the component according to the arrival time of each input signal and the propagation delay of each pin of the component; and

means for causing said means for determining said means for identifying, and said means for ordering to operate on each component within an identified topological level.

12. The system of claim 11, wherein the component is a look up table.

13. The system of claim 11, further comprising means for iteratively processing each of identified topological levels of the circuit design representation, wherein said means for iteratively processing processes the topological levels in hierarchical order.

14. The system of claim 13, further comprising means for updating timing information for the circuit design representation after ordering input signals of each component of an identified topological level.

15. The system of claim 11, said means for ordering further comprising means for matching input signals having an earlier arrival time with pins of the component having longer propagation delays.

16. The system of claim 15, wherein said means for matching matches an input signal having the earliest arrival time with a pin of the component having the longest propagation delay, and an input signal having the latest arrival time with a pin of the component having the shortest propagation delay.

17. The system of claim 11, said means for ordering further comprising:

means for sorting input signals according to an arrival time at the component;

means for sorting pins of the component according to propagation delay; and

means for matching input signals having an earlier arrival time with pins of the component having longer propagation delays.

18. The system of claim 17, wherein said means for matching matches an input signal having the earliest arrival time with a pin of the component having the longest propagation delay, and an input signal having the latest arrival time with a pin of the component having the shortest propagation delay.

19. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform steps of:

determining an arrival time for each input signal to a look up table within a circuit design representation;

identifying propagation delay associated with each pin of the look up table; and

ordering input signals of the look up table according to the arrival time of each input signal and the propagation delay of each pin of the look up table.

20. The computer program of claim 19, further causing the machine to perform a step of first identifying topological levels of the circuit design representation.

21. The computer program of claim 20, further causing the machine to perform a step of repeating said determining, said identifying, and said ordering steps for each look up table within an identified topological level.

22. The computer program of claim 21, further causing the machine to perform a step of iteratively performing said repeating step for each identified topological level of the circuit design representation.

23. The computer program of claim 22, wherein the identified topological levels are processed in hierarchical order.

24. The computer program of claim 23, further causing the machine to perform a step of updating timing information for the circuit design representation after ordering input signals of each look up table of an identified topological level.

25. The computer program of claim 19, wherein said ordering step further comprising a step of matching input signals having an earlier arrival time with pins of the lookup table having longer propagation delays.

26. The computer program of claim 25, wherein said matching step matches an input signal having an earliest arrival time with a pin of the look up table having a longest propagation delay, and an input signal having a latest arrival time with a pin of the look up table having a shortest propagation delay.

27. The computer program of claim 19, wherein said ordering step comprising:

sorting input signals according to an arrival time at the look up table;

sorting pins of the look up table according to propagation delay; and

matching input signals having an earlier arrival time with pins of the look up table having longer propagation delays.

28. The computer program of claim 27, wherein said matching step matches an input signal having earliest arrival time with a pin of the lookup table having the longest propagation delay, and the input signal having the latest arrival time with a pin of the lookup table having the shortest propagation delay.