Method for forming a relative placement of components of an integrated circuit using a structural similarity group

• US 6,584,605 B1
• Filed: 04/15/1999
• Issued: 06/24/2003
• 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): Siek, Vuthe
• Application Number:
  US09/293,500
• Time in Patent Office: 1,531 Days
• Field of Search: 716/10, 716/8, 716/9, 716/11, 716/12, 716/13, 716/14, 716/2
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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 forming a relative placement of components of an integrated circuit from a netlist comprising:

taking a netlist representation of components forming all or part of an integrated circuit;

forming groups of components within the netlist which have at least a selected degree of structural similarity between each other;

making a structural similarity group which includes those groups of components identified as having at least the selected degree of structural similarity;

performing an initial relative placement of the groups of components;

reducing wire lengths between components of initial relative placement; and

adding to the relative placement those components from the netlist which were not included in the groups of components.

2. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components which include at least two components.

3. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components which include at least three components.

4. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components which include at least four components.

5. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 10% similarity in bus line and control line connectivity between components of the group.

6. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 20% similarity in bus line and control line connectivity between components of the group.

7. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 33% similarity in bus line and control line connectivity between components of the group.

8. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 50% similarity in bus line and control line connectivity between components of the group.

9. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 66% similarity in bus line and control line connectivity between components of the group.

10. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 75% similarity in bus line and control line connectivity between components of the group.

11. A method according to claim 1 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 80% similarity in bus line and control line connectivity between components of the group.

12. A method according to claim 1 wherein the netlist indicates an order for bus lines in the circuit, the step of performing an initial relative placement of the groups of components includes conserving the order of bus lines indicated in the netlist.

13. A method according to claim 12 further comprising modifying the relative placement of components including conserving the order of bus lines indicated in the netlist.

14. An integrated circuit design tool comprising:

a processor; and

memory coupled to the processor including instructions which when executed by the processor takes a netlist representation of components forming all or part of an integrated circuit and performs the following steps

forming groups of components within the netlist which have at least a selected degree of structural similarity between each other,

making a structural similarity group which includes those groups of components identified as having at least the selected degree of structural similarity,

performing an initial relative placement of the groups of components,

reducing wire lengths between components of initial relative placement, and

adding to the relative placement those components from the netlist which were not included in the groups of components.

15. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components which include at least two components.

16. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components which include at least three components.

17. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components which include at least four components.

18. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 10% similarity in bus line and control line connectivity between components of the group.

19. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 20% similarity in bus line and control line connectivity between components of the group.

20. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 33% similarity in bus line and control line connectivity between components of the group.

21. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 50% similarity in bus line and control line connectivity between components of the group.

22. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 66% similarity in bus line and control line connectivity between components of the group.

23. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 75% similarity in bus line and control line connectivity between components of the group.

24. A design tool according to claim 14 wherein the step of forming groups of components having at least a selected degree of structural similarity between each other includes forming groups of components having at least 80% similarity in bus line and control line connectivity between components of the group.

25. A design tool according to claim 14 wherein the netlist indicates an order for bus lines in the circuit, the step of performing an initial relative placement of the groups of components includes conserving the order of bus lines indicated in the netlist.

26. A design tool according to claim 25 further comprising modifying the relative placement of components including conserving the order of bus lines indicated in the netlist.

27. An article of manufacture comprising a computer readable medium bearing a program code embodied therein for performing a method for forming a structural similarity group from a netlist of an integrated circuit, the method comprising:

taking a netlist representation of components forming all or part of an integrated circuit;

forming groups of components within the netlist which have at least a selected degree of structural similarity between each other;

making a structural similarity group which includes those groups of components identified as having at least the selected degree of structural similarity;

performing an initial relative placement of the groups of components;

reducing wire lengths between components of initial relative placement; and

adding to the relative placement those components from the netlist which were not included in the groups of components.

28. An article of manufacture according to claim 27 wherein the netlist representation includes all of the components forming integrated circuit.

29. An article of manufacture according to claim 27 wherein the netlist representation includes a portion of the components forming integrated circuit.

30. An article of manufacture according to claim 27 wherein each group of components formed includes at least two components.

31. An article of manufacture according to claim 27 wherein each group of components formed includes at least three components.

32. An article of manufacture according to claim 27 wherein each group of components formed includes at least four components.

33. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 10% similarity in bus line and control line connectivity between components of the group.

34. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 20% similarity in bus line and control line connectivity between components of the group.

35. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 25% similarity in bus line and control line connectivity between components of the group.

36. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 33% similarity in bus line and control line connectivity between components of the group.

37. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 50% similarity in bus line and control line connectivity between components of the group.

38. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 66% similarity in bus line and control line connectivity between components of the group.

39. An article of manufacture according to claim 27 wherein the selected degree of structural similarity is at least 75% similarity in bus line and control line connectivity between components of the group.