Method for determining bus line routing for components of an integrated circuit

• US 6,430,734 B1
• Filed: 04/15/1999
• Issued: 08/06/2002
• Est. Priority Date: 04/15/1999
• Status: Expired due to Term

• Current Assignee: Magma Design Automation (Synopsys Incorporated)
• Original Assignee: Sycon Design
• Inventors: Zahar, Sharon
• Primary Examiner(s): PHAN, TRONG Q
• Application Number:
  US09/293,638
• Time in Patent Office: 1,209 Days
• Field of Search: 716/12, 716/13, 716/14
• US Class Current: 716/127
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method for forming a structural similarity group from a netlist for use in performing a relative placement of components of an integrated circuit is described. Also described are a method for forming a relative placement of components of an integrated circuit using a structural similarity group and a method for modifying a relative placement of components of an integrated circuit by analyzing adjacent components for shared resources. In addition, methods for determining bus line routing, control line routing, and cleanup line routing for components of an integrated circuit are described.

Claims

1. A computer implemented method for determining at least part of a bus line routing for each bus line of an integrated circuit, each bus line routing including an initial routing and a cleanup routing, the method comprising:

taking a finalized relative placement of components of the integrated circuit, the placement including routing constraints and at least a first and second port locations associated with each bus line;

determining a routing order for the bus lines based on at least one criterion; and

determining an initial routing for each bus line based on the placement, each initial routing being substantially straight and substantially parallel to a bus line axis, a length of each initial routing based on a distance along the bus line axis between the first and second port locations, a position of each initial routing based on an average distance orthogonal to the bus line axis between at least the first and second port locations, wherein the placement is unaltered.

2. A method according to claim 1 wherein the routing constraints include photolithography limitations.

3. A method according to claim 1 wherein the routing constraints include bus line widths.

4. A method according to claim 1 wherein the routing constraints include bus line spacings.

5. A method according to claim 1 wherein the routing constraints include bus line shielding requirements.

6. A method according to claim 1 wherein determining a routing order includes:

assigning a point scale to each criterion based on an importance of each criterion;

assigning points to each bus line based on the point scale for each criterion;

determining a total number of points assigned to each bus line; and

determining a routing order based on the total number of points.

7. A method according to claim 1 wherein the criterion is a function of the bus line.

8. A method according to claim 1 wherein the criterion is a width of the bus line.

9. A method according to claim 1 wherein the criterion is user-defined.

10. A method according to claim 1 wherein each of the port locations is associated with a first coordinate along the bus line axis and a second coordinate orthogonal to the bus line axis.

11. A method according to claim 1 wherein the length is a difference of the first coordinates associated with the first and second port locations.

12. A method according to claim 1 wherein the position is an average of the second coordinates associated with at least the first and second port locations.

13. A method according to claim 1, further comprising:

determining an alternate position for each initial routing where a blockage is present.

14. A method according to claim 13 wherein determining an alternate position includes:

defining a search region based on at least the first and second port locations; and

selecting a closest available track located within the search region.

15. A method according to claim 14 wherein the search region is a rectangular region having at least two comers defined by the first and second port locations.

16. A method according to claim 1, further comprising:

determining a cleanup routing for each bus line based on the initial routing and the placement, the cleanup routing connecting the initial routing for each bus line to ports associated with each bus line.

17. A method according to claim 16 wherein determining a cleanup routing includes:

determining a length for each cleanup routing based on a distance between the initial routing and the port location; and

determining a position for each cleanup routing based on the initial routing and the port location.

18. A method according to claim 16 wherein determining a cleanup routing includes using the shortest Manhattan length between the initial routing and the port location.

19. A method according to claim 16 wherein determining a cleanup routing is performed by an external router.

20. A method according to claim 16, further comprising:

determining an alternate position for each cleanup routing where a blockage is present.

21. An integrated circuit design tool comprising:

a processor; and

memory coupled to the processor including instructions which when executed by the processor takes a finalized relative placement of components of an integrated circuit, the placement including routing constraints and at least a first and second port locations associated with each bus line, and performs;

determining a routing order for the bus lines based on at least one criterion; and

determining an initial routing for each bus line based on the placement, each initial routing being substantially straight and substantially parallel to a bus line axis, a length of each initial routing based on a distance along the bus line axis between the first and second port locations, a position of each initial routing based on an average distance orthogonal to the bus line axis between at least the first and second port locations, wherein the placement is unaltered.

22. An integrated circuit design tool according to claim 21 wherein the routing constraints include photolithography limitations.

23. An integrated circuit design tool according to claim 21 wherein the routing constraints include bus line widths.

24. An integrated circuit design tool according to claim 21 wherein the routing constraints include bus line spacings.

25. An integrated circuit design tool according to claim 21 wherein the routing constraints include bus line shielding requirements.

26. An integrated circuit design tool according to claim 21 wherein determining a routing order includes:

assigning a point scale to each criterion based on an importance of each criterion;

assigning points to each bus line based on the point scale for each criterion;

determining a total number of points assigned to each bus line; and

determining a routing order based on the total number of points.

27. An integrated circuit design tool according to claim 21 wherein the criterion is a function of the bus line.

28. An integrated circuit design tool according to claim 21 wherein the criterion is a width of the bus line.

29. An integrated circuit design tool according to claim 21 wherein the criterion is user-defined.

30. An integrated circuit design tool according to claim 21 wherein each of the port locations is associated with a first coordinate along the bus line axis and a second coordinate orthogonal to the bus line axis.

31. An integrated circuit design tool according to claim 21 wherein the length is a difference of the first coordinates associated with the first and second port locations.

32. An integrated circuit design tool according to claim 21 wherein the position is an average of the second coordinates associated with at least the first and second port locations.

33. An integrated circuit design tool according to claim 21, further comprising:

determining an alternate position for each initial routing where a blockage is present.

34. An integrated circuit design tool according to claim 33 wherein determining an alternate position includes:

defining a search region based on at least the first and second port locations; and

selecting a closest available track located within the search region.

35. An integrated circuit design tool according to claim 34 wherein the search region is a rectangular region having at least two corners defined by the first and second port locations.

36. An integrated circuit design tool according to claim 21, further comprising:

determining a cleanup routing for each bus line based on the initial routing and the placement, the cleanup routing connecting the initial routing for each bus line to ports associated with each bus line.

37. An integrated circuit design tool according to claim 36 wherein determining a cleanup routing includes:

determining a length for each cleanup routing based on a distance between the initial routing and the port location; and

determining a position for each cleanup routing based on the initial routing and the port location.

38. An integrated circuit design tool according to claim 36 wherein determining a cleanup routing includes using the shortest Manhattan length between the initial routing and the port location.

39. An integrated circuit design tool according to claim 36 wherein determining a cleanup routing is performed by an external router.

40. An integrated circuit design tool according to claim 36, further comprising:

determining an alternate position for each cleanup routing where a blockage is present.

41. An article of manufacture comprising a computer readable medium bearing a program code embodied therein for performing a method for determining at least part of a bus line routing for each bus line of an integrated circuit, each bus line routing including an initial routing and a cleanup routing, the method comprising:

taking a finalized relative placement of components of the integrated circuit, the placement including routing constraints and at least a first and second port locations associated with each bus line;

determining a routing order for the bus lines based on at least one criterion; and

determining an initial routing for each bus line based on the placement, each initial routing being substantially straight and substantially parallel to a bus line axis, a length of each initial routing based on a distance along the bus line axis between the first and second port locations, a position of each initial routing based on an average distance orthogonal to the bus line axis between at least the first and second port locations, wherein the placement is unaltered.

42. An article of manufacture according to claim 41 wherein the routing constraints include photolithography limitations.

43. An article of manufacture according to claim 41 wherein the routing constraints include bus line widths.

44. An article of manufacture according to claim 41 wherein the routing constraints include bus line spacings.

45. An article of manufacture according to claim 41 wherein the routing constraints include bus line shielding requirements.

46. An article of manufacture according to claim 41 wherein determining a routing order includes:

assigning a point scale to each criterion based on an importance of each criterion;

assigning points to each bus line based on the point scale for each criterion;

determining a total number of points assigned to each bus line; and

determining a routing order based on the total number of points.

47. An article of manufacture according to claim 41 wherein the criterion is a function of the bus line.

48. An article of manufacture according to claim 41 wherein the criterion is a width of the bus line.

49. An article of manufacture according to claim 41 wherein the criterion is user-defined.

50. An article of manufacture according to claim 41 wherein each of the port locations is associated with a first coordinate along the bus line axis and a second coordinate orthogonal to the bus line axis.

51. An article of manufacture according to claim 41 wherein the length is a difference of the first coordinates associated with the first and second port locations.

52. An article of manufacture according to claim 41 wherein the position is an average of the second coordinates associated with at least the first and second port locations.

53. An article of manufacture according to claim 41, further comprising:

determining an alternate position for each initial routing where a blockage is present.

54. An article of manufacture according to claim 53 wherein determining an alternate position includes:

defining a search region based on at least the first and second port locations; and

selecting a closest available track located within the search region.

55. An article of manufacture according to claim 54 wherein the search region is a rectangular region having at least two corners defined by the first and second port locations.

56. An article of manufacture according to claim 41, further comprising:

determining a cleanup routing for each bus line based on the initial routing and the placement, the cleanup routing connecting the initial routing for each bus line to ports associated with each bus line.

57. An article of manufacture according to claim 56 wherein determining a cleanup routing includes:

determining a length for each cleanup routing based on a distance between the initial routing and the port location; and

determining a position for each cleanup routing based on the initial routing and the port location.

58. An article of manufacture according to claim 56 wherein determining a cleanup routing includes using the shortest Manhattan length between the initial routing and the port location.

59. An article of manufacture according to claim 56 wherein determining a cleanup routing is performed by an external router.

60. An article of manufacture according to claim 56, further comprising:

determining an alternate position for each cleanup routing where a blockage is present.