Multiple level spine routing

• US 8,782,588 B2
• Filed: 10/01/2013
• Issued: 07/15/2014
• Est. Priority Date: 11/29/2010
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated, Synopsys Taiwan Co., Ltd. (Synopsys Incorporated)
• Inventors: Chang, Fong-Yuan, Chuang, Wei-Shun, Chen, Sheng-Hsiung, Chang, Hsian-Ho, Rau, Ruey-Shi
• Primary Examiner(s): Kik, Phallaka
• Application Number:
  US14/043,619
• Publication Number:
  US 20140033157A1
• Time in Patent Office: 287 Days
• Field of Search: 716/131, 716/129, 716/130, 716/122, 716/123, 716/124
• US Class Current: 716/131
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A computer implemented method for routing a net includes generating, using one or more computer systems, a first wire associated with the net in accordance with data associated with the net including a multitude of pins and partitioning, using the one or more computer systems, the multitude of pins into at least a first group of pins in accordance with a first cost function. The method further includes connecting, using the one or more computer systems, a second wire associated with the first group of pins to the first wire, and connecting, using the one or more computer systems, a third wire from a pin of the first group of pins to the second wire.

Claims

1. A computer implemented method for routing a net, comprising:

generating, using one or more computer systems, a first wire associated with the net in accordance with data associated with the net including a plurality of pins when the one or more computer systems are invoked to route the net;

partitioning, using the one or more computer systems, the plurality of pins into at least a first group of pins in accordance with a first cost function;

connecting, using the one or more computer systems, a second wire associated with the first group of pins to the first wire; and

connecting, using the one or more computer systems, a third wire from a pin of the first group of pins to the second wire.

2. The method of claim 1, wherein the net is a net of an integrated circuit design.

3. The method of claim 1, wherein the first wire, the second wire, and the third wire route a portion of the net.

4. The method of claim 1, wherein the first wire includes a main spine of the net.

5. The method of claim 1, wherein partitioning, using the one or more computer systems, includes using a position of the first wire.

6. The method of claim 1, wherein the first group of pins are located on a same side of the first wire.

7. The method of claim 1, wherein the cost function includes a wire length.

8. The method of claim 1, wherein partitioning, using the one or more computer systems, includes partitioning in accordance with a k-means clustering algorithm or a k-median clustering algorithm.

9. The method of claim 1, wherein the second wire comprises a second level spine of the net.

10. The method of claim 1, wherein the first wire is oriented substantially orthogonal to the second wire.

11. A system for routing a net, comprising:

a processor, and

a memory storing a set of instructions which when executed by the processor configures the processor to;

generate a first wire associated with the net in accordance with data associated with the net including a plurality of pins when the system is invoked to route the net;

partition the plurality of pins into at least a first group of pins in accordance with a first cost function;

connect a second wire associated with the first group of pins to the first wire; and

connect a third wire from a pin of the first group of pins to the second wire.

12. The system of claim 11, wherein the first wire, the second wire, and the third wire are used to route a portion of the net.

13. The system of claim 11, wherein the first wire comprises a main spine of the net.

14. The system of claim 11, wherein partitioning the plurality of pins into one or more groups of pins is based at least in part on a position of the first wire.

15. The system of claim 11, wherein the cost function includes a wire length.

16. The system of claim 11, wherein partitioning includes partitioning in accordance with on a k-means clustering algorithm or a k-median clustering algorithm.

17. The system of claim 11, wherein the second wire includes a second level spine of the net.

18. The system of claim 11, wherein the first wire is oriented substantially orthogonal to the second wire.

19. A non-transitory computer-readable medium storing computer-executable code for routing a net, the non-transitory computer-readable medium comprising:

code for generating a first wire associated with the net in accordance with data associated with the net including a plurality of pins when the non-transitory computer-readable medium is invoked to route the net;

code for partitioning the plurality of pins into at least a first group of pins in accordance with a first cost function;

code for connecting a second wire associated with the first group of pins to the first wire; and

code for connecting a third wire from a pin of the first group of pins to the second wire.

20. The non-transitory computer-readable medium of claim 19, wherein the first wire, the second wire, and the third wire route a portion of the net.

21. The non-transitory computer-readable medium of claim 19, wherein the first wire includes a main spine of the net.

22. The non-transitory computer-readable medium of claim 19, wherein partitioning includes using a position of the first wire.

23. The non-transitory computer-readable medium of claim 19, wherein the cost function includes a wire length.

24. The non-transitory computer-readable medium of claim 19, wherein the second wire includes a second level spine of the net.

25. The non-transitory computer-readable medium of claim 19, wherein the first wire is oriented substantially orthogonal to the second wire.