Multiple Level Spine Routing

• US 20140033158A1
• Filed: 10/01/2013
• Published: 01/30/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
• Granted Patent: US 9,003,350 B2
• Time in Patent Office: Days
• 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 in accordance with a first cost function, and further in accordance with data associated with the net and the first plurality of routing tracks; 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 selecting, using the one or more computer systems, includes solving a Linear Assignment Problem.

4. The method of claim 1, wherein selecting, using the one or more computer systems, includes solving a Linear Assignment Problem using one or more of the first plurality of routing tracks.

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

6. 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.

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

8. The method of claim 6, wherein the first cost function includes the second cost function.

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

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

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

12. The method of claim 6 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.

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

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

15. The method of claim 12, 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.

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

17. The method of claim 16 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.

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

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

20. 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 in accordance with a first cost function, and further in accordance with data associated with the net and the first plurality of routing tracks; and

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

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

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

23. The system of claim 20, 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.

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

25. The system of claim 23, wherein the first cost function includes the second cost function.

26. The system of claim 23, 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.

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

28. The system of claim 26, 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.

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

30. The system of claim 29, 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.

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

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

33. 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 in accordance with a first cost function, and further in accordance with data associated with the net and the first plurality of routing tracks; and

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

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

35. The non-transitory computer-readable medium of claim 33, 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.

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

37. The non-transitory computer-readable medium of claim 35, 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.

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

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

40. The non-transitory computer-readable medium of claim 39, 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.