Multiple level spine routing

• US 8,683,417 B2
• Filed: 11/04/2011
• Issued: 03/25/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:
  US13/289,963
• Publication Number:
  US 20120137264A1
• Time in Patent Office: 872 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

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, at one or more computer systems, information indicative of a specification of a net comprising a plurality of pins;

generating, using the one or more computer systems, a first wire for routing the net;

partitioning, using the one or more computer systems, the plurality of pins into one or more groups of pins based at least in part on a cost function;

for each group of pins of the net, generating, using the one or more computer systems, a second wire that connects to the first wire; and

for each pin of each group of pins of the net, generating using the one or more computer systems, a third wire that connects the pin to its associated second wire.

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 of pins, 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, using the one or more computer systems, the plurality of pins into one or more groups of pins 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 of pins 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, using the one or more computer systems, the plurality of pins into one or more groups of pins 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 plurality of pins;

generate a first wire for routing the net;

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

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

for each pin of each group of pins of the net, generate a third wire that connects the pin to the second wire of its group of pins; 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 of pins, 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 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 is based at least in part on wire lengths.

16. The system of claim 11, wherein partitioning the plurality of pins into one or more groups of pins 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 non-transitory computer readable storage medium and comprising computer instructions for:

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

generating a first wire for routing the net;

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

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

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

20. The computer program product of claim 19, wherein the first wire, the second wire associated with each group of pins, 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 plurality of pins into one or more groups of pins 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.