Apparatus and Methods for Congestion Estimation and Optimization for Computer-Aided Design Software

• US 20080059931A1
• Filed: 08/29/2006
• Published: 03/06/2008
• Est. Priority Date: 08/29/2006
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Peters, Jason, Padalia, Ketan, Ludwin, Adrian
• Granted Patent: US 7,681,165 B2
• Time in Patent Office: Days
• US Class Current: 716/9
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method of performing placement of resources in a computer-aided design (CAD) tool includes performing a first congestion analysis, proposing a placement move, and evaluating the placement move. The method further includes incrementally updating information used for performing another congestion analysis.

Claims

1. A method of performing placement of resources in a computer-aided design (CAD) tool, the method comprising:

performing a first congestion analysis;

proposing a placement move;

evaluating the placement move; and

incrementally updating information used for performing a second congestion analysis.

2. The method according to claim 1, wherein evaluating the placement move comprises evaluating a congestion cost for a net based on a bounding box of the net.

3. The method according to claim 2, wherein the congestion cost for the net comprises an average congestion information of its bounding box.

4. The method according to claim 3, wherein the average congestion information is structured efficiently to minimize calculations.

5. The method according to claim 1, wherein the information used for performing the second congestion analysis is minimized.

6. The method according to claim 1, further comprising selectively performing congestion optimization based on congestion levels.

7. The method according to claim 6, wherein performing congestion optimization further comprises determining respective congestion levels of a set of rectangular regions.

8. The method according to claim 1, wherein evaluating the placement move comprises calculating respective bounding box changes of a set of nets.

9. The method according to claim 8, wherein evaluating the placement move further comprises calculating an average congestion cost for each net in the set of nets.

10. The method according to claim 8, wherein calculating an average congestion cost for each net in the set of nets comprises performing directionally weighted averaging.

11. The method according to claim 1, wherein evaluating the placement move comprises calculating a change in a terminal count within a set of regions.

12. The method according to claim 1, wherein proposing the placement move comprises by using information from the first congestion analysis to propose a move that reduces average congestion.

13. A system for performing placement of resources in a computer-aided design (CAD) tool, the system comprising:

a computer, configured to;

perform a first congestion analysis;

propose a placement move;

evaluate the placement move; and

incrementally update information used for performing a second congestion analysis.

14. The system according to claim 13, wherein the computer is further configured to evaluate the placement move by evaluating a congestion cost for a net based on a bounding box of the net.

15. The system according to claim 14, wherein the congestion cost for the net comprises an average congestion of its bounding box.

16. The system according to claim 15, wherein the average congestion information is structured efficiently to minimize calculations.

17. The system according to claim 13, wherein the computer is further configured to minimize information used for performing the second congestion analysis.

18. The system according to claim 13, further comprising configuring the computer to selectively perform congestion optimization based on congestion levels.

19. The system according to claim 18, wherein the computer is configured to perform congestion optimization by determining respective congestion levels of a set of rectangular regions.

20. The system according to claim 13, wherein the computer is further configured to evaluate the placement move by calculating respective bounding box changes of a set of nets.

21. The system according to claim 20, wherein the computer is further configured to evaluate the placement move by calculating an average congestion cost for each net in the set of nets.

22. The system according to claim 20, wherein the computer is further configured to calculate an average congestion cost for each net in the set of nets by performing directionally weighted averaging.

23. The system according to claim 13, wherein the computer is further configured to evaluate the placement move by calculating a change in a terminal count within a set of regions.

24. The system according to claim 13, wherein the computer is further configured to propose the placement move by using information from the first congestion analysis to propose a move that reduces average congestion.

25. A computer program product, comprising:

a computer application adapted for processing by a computer to perform

placement of resources in a computer-aided design (CAD) tool, the

computer application configured to cause the computer to;

perform a first congestion analysis;

propose a placement move;

evaluate the placement move; and

incrementally update information used for performing a second congestion analysis.

26. The computer program product according to claim 25, wherein the computer application is further configured to cause the computer to evaluate the placement move by evaluating a congestion cost for a net based on a bounding box of the net.

27. The computer program product according to claim 26, wherein the congestion cost for the net comprises an average congestion of its bounding box.

28. The computer program product according to claim 25, wherein the computer application is further configured to cause the computer to minimize information used for performing the second congestion analysis.

29. The computer program product according to claim 25, wherein the computer application is further configured to cause the computer to selectively perform congestion optimization based on congestion levels.

30. The computer program product according to claim 29, wherein the computer application is configured to cause the computer to perform congestion optimization by determining respective congestion levels of a set of rectangular regions.

31. The computer program product according to claim 25, wherein the computer application is further configured to cause the computer to evaluate the placement move by calculating respective bounding box changes of a set of nets.

32. The computer program product according to claim 31, wherein the computer application is further configured to cause the computer to evaluate the placement move by calculating an average congestion cost for each net in the set of nets.

33. The computer program product according to claim 31, wherein the computer application is further configured to cause the computer to calculate an average congestion cost for each net in the set of nets by performing directionally weighted averaging.

34. The computer program product according to claim 25, wherein the computer application is further configured to cause the computer to evaluate the placement move by calculating a change in a terminal count within a set of regions.

35. The computer program product according to claim 25, wherein the computer application is further configured to cause the computer to propose the placement move by using information from the first congestion analysis to propose a move that reduces average congestion.