MULTIPLE LEVEL SPINE ROUTING

• US 20120137264A1
• Filed: 11/04/2011
• Published: 05/31/2012
• Est. Priority Date: 11/29/2010
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: SpringSoft, Inc. (Synopsys Incorporated)
• Inventors: Chang, Fong-Yuan, Chen, Sheng-Hsiung, Chuang, Wei-Shun, Chang, Hsian-Ho, Rau, Ruey-Shi
• Granted Patent: US 8,683,417 B2
• Time in Patent Office: Days
• US Class Current: 716/131
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Multiple level spine routing is disclosed. In some embodiments, in response to receiving a specification of a net comprising a set of pins, a first wire for routing the net is generated, the set of pins comprising the net is partitioned into one or more groups based at least in part on a cost function, a second wire that connects to the first wire is generated for each group of the net, and a third wire that connects each pin to the second wire of its group is generated for each pin of each group of the net.

Claims

1. A method for routing a net, comprising:

receiving a specification of a net comprising a set of pins;

generating a first wire for routing the net;

partitioning the set of pins comprising the net into one or more groups based at least in part on a cost function;

for each group of the net, generating a second wire that connects to the first wire; and

for each pin of each group of the net, generating a third wire that connects the pin to the second wire of its group.

2. The method recited in claim 1, wherein the net is part of an integrated circuit.

3. The method recited in claim 1, wherein the first wire, the second wire associated with each group, and the third wire associated with each pin are used to route the net.

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

5. The method recited in claim 1, wherein partitioning the set of pins comprising the net into one or more groups is based at least in part on a position of the first wire.

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

7. The method recited in claim 1, wherein the cost function is based at least in part on wire lengths.

8. The method recited in claim 1, wherein partitioning the set of pins comprising the net into one or more groups comprises partitioning based at least in part on a k-means clustering algorithm or a k-median clustering algorithm.

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

10. The method recited in claim 1, wherein the first wire and the second wire are oriented substantially orthogonally.

11. A system for routing a net, comprising:

a processor configured to;

receive a specification of a net comprising a set of pins;

generate a first wire for routing the net;

partition the set of pins comprising the net into one or more groups based at least in part on a cost function;

for each group of the net, generate a second wire that connects to the first wire; and

for each pin of each group of the net, generate a third wire that connects the pin to the second wire of its group; and

a memory coupled to the processor and configured to provide the processor with instructions.

12. The system of claim 11, wherein the first wire, the second wire associated with each group, and the third wire associated with each pin are used to route 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 set of pins comprising the net into one or more groups is based at least in part on a position of the first wire.

15. The system of claim 11, wherein the cost function is based at least in part on wire lengths.

16. The system of claim 11, wherein partitioning the set of pins comprising the net into one or more groups comprises partitioning based at least in part on a k-means clustering algorithm or a k-median clustering algorithm.

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

18. The system of claim 11, wherein the first wire and the second wire are oriented substantially orthogonally.

19. A computer program product for routing a net, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

receiving a specification of a net comprising a set of pins;

generating a first wire for routing the net;

partitioning the set of pins comprising the net into one or more groups based at least in part on a cost function;

for each group of the net, generating a second wire that connects to the first wire; and

for each pin of each group of the net, generating a third wire that connects the pin to the second wire of its group.

20. The computer program product of claim 19, wherein the first wire, the second wire associated with each group, and the third wire associated with each pin are used to route the net.

21. The computer program product of claim 19, wherein the first wire comprises a main spine of the net.

22. The computer program product of claim 19, wherein partitioning the set of pins comprising the net into one or more groups is based at least in part on a position of the first wire.

23. The computer program product of claim 19, wherein the cost function is based at least in part on wire lengths.

24. The computer program product of claim 19, wherein the second wire comprises a second level spine of the net.

25. The computer program product of claim 19, wherein the first wire and the second wire are oriented substantially orthogonally.