Multiple level spine routing

• US 9,003,350 B2
• Filed: 10/01/2013
• Issued: 04/07/2015
• 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): Rossoshek, Helen
• Application Number:
  US14/043,689
• Publication Number:
  US 20140033158A1
• Time in Patent Office: 553 Days
• Field of Search: 716/122, 716/123, 716/124, 716/129, 716/130, 716/131
• 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 selecting, using one or more computer systems, a first spine routing track from a first multitude of routing tracks in accordance with a first cost function, and further in accordance with data associated with the net and the first multitude of routing tracks. The method further includes generating, using one or more computer systems, a first spine wire on the selected first spine routing track.

Claims

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

selecting, using one or more computer systems, a first spine routing track from a first plurality of routing tracks, wherein the selecting is based on;

data associated with the net,

data associated with the first plurality of spine routing tracks,

a first cost function, and

a solution to a Linear Assignment Problem; and

generating, using one or more computer systems, a first spine wire on the selected first spine routing track.

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 Linear Assignment Problem uses one or more of the first plurality of routing tracks.

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

5. The method of claim 1, wherein selecting, using the one or more computer systems, includes partitioning a plurality of pins associated with the net into one or more groups of pins in accordance with a second cost function.

6. The method of claim 5, wherein the second cost function includes a wire length.

7. The method of claim 5, wherein the first cost function includes the second cost function.

8. The method of claim 5, wherein partitioning, using the one or more computer systems, includes using a position of the selected first spine routing track.

9. The method of claim 5, wherein one of the one or more groups of pins are partitioned on a same side of the selected first spine routing track.

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

11. The method of claim 5 further comprising selecting, using the one or more computer systems, a second spine routing track from a second plurality of routing tracks associated with one of the one or more groups of pins in accordance with a third cost function, and further in accordance with data associated with the second plurality of routing tracks.

12. The method of claim 11, wherein the third cost function includes a wire length.

13. The method of claim 11, wherein selecting, using the one or more computer systems, a second spine routing track includes solving a Linear Assignment Problem.

14. The method of claim 11, wherein selecting, using the one or more computer systems, a second spine routing track includes solving a Linear Assignment Problem using one or more of the second plurality of routing tracks.

15. The method of claim 11 further comprising generating, using the one or more computer systems, a second spine wire on the selected second spine routing track.

16. The method of claim 15 further comprising generating, using the one or more computer systems, a wire from a pin of one of the one or more groups of pins to the second spine wire.

17. The method of claim 11, wherein one or more of the first cost function, the second cost function, and the third cost function are the same.

18. The method of claim 11, wherein the second spine routing track is oriented substantially orthogonal to the first spine routing track.

19. 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;

select a first spine routing track from a first plurality of routing tracks, wherein the selecting is based on;

data associated with the net,

data associated with the first plurality of spine routing tracks,

a first cost function, and

a solution to a Linear Assignment Problem; and

generate a first spine wire on the selected first spine routing track.

20. The system of claim 19, wherein the Linear Assignment Problem uses one or more of the first plurality of routing tracks.

21. The system of claim 19, wherein the first cost function includes a wire length.

22. The system of claim 19, wherein to select the first spine routing track includes partitioning a plurality of pins associated with the net into one or more groups of pins in accordance with a second cost function.

23. The system of claim 22, wherein the second cost function includes a wire length.

24. The system of claim 22, wherein the first cost function includes the second cost function.

25. The system of claim 22, wherein the processor is further configured to select a second spine routing track from a second plurality of routing tracks associated with one of the one or more groups of pins in accordance with a third cost function, and further in accordance with data associated with the second plurality of routing tracks.

26. The system of claim 25, wherein the third cost function includes a wire length.

27. The system of claim 25, wherein to select a second spine routing track includes solving a Linear Assignment Problem using one or more of the second plurality of routing tracks.

28. The system of claim 25, wherein the processor is further configured to generate a second spine wire on the selected second spine routing track.

29. The system of claim 28, wherein the processor is further configured to generate a wire from a pin of one of the one or more groups of pins to the second spine wire.

30. The system of claim 25, wherein one or more of the first cost function, the second cost function, and the third cost function are the same.

31. The system of claim 25, wherein the second spine routing track is oriented substantially orthogonal to the first spine routing track.

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

code for selecting, using one or more computer systems, a first spine routing track from a first plurality of routing tracks, wherein the selecting is based on;

data associated with the net,

data associated with the first plurality of spine routing tracks,

a cost function, and

a solution to a Linear Assignment Problem; and

code for generating, using one or more computer systems, a first spine wire on the selected first spine routing track.

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

34. The non-transitory computer-readable medium of claim 32, wherein the code for selecting includes code for partitioning a plurality of pins associated with the net into one or more groups of pins in accordance with a second cost function.

35. The non-transitory computer-readable medium of claim 34, wherein the second cost function includes a wire length.

36. The non-transitory computer-readable medium of claim 34, further comprising code for selecting a second spine routing track from a second plurality of routing tracks associated with one of the one or more groups of pins in accordance with a third cost function, and further in accordance with data associated with the second plurality of routing tracks.

37. The non-transitory computer-readable medium of claim 36, wherein the third cost function includes a wire length.

38. The non-transitory computer-readable medium of claim 36, further comprising code for generating a second spine wire on the selected second spine routing track.

39. The non-transitory computer-readable medium of claim 38, further comprising code for generating a wire from a pin of one of the one or more groups of pins to the second spine wire.