Multiple level spine routing

• US 8,959,473 B2
• Filed: 11/04/2011
• Issued: 02/17/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:
  US13/289,965
• Publication Number:
  US 20120137265A1
• Time in Patent Office: 1,201 Days
• Field of Search: 716/122, 716/126, 716/129, 716/130, 716/131, 716/132, 716/136
• US Class Current: 716/126
• 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 plurality of nets and a specification of a set of routing tracks available for main spines, a main spine routing track is assigned to each of the plurality of nets based at least in part on a cost function and main spine wires are generated on the assigned main spine routing tracks for each of the plurality of nets.

Claims

1. A method for routing a plurality of nets, comprising:

receiving, at one or more computer systems, information indicative of a specification of a plurality of nets;

receiving, at the one or more computer systems, a specification of a first set of routing tracks, wherein each of the routing tracks of the specification is assignable for a main spine wire of one of the nets;

based on the received information of the nets, the received specification of the first set of routing tracks, and a cost function, assigning, using the one or more computer systems, one of the assignable routing tracks to each of the nets, wherein the assigning of the assignable routing tracks to each of the nets is based on a solution to a Linear Assignment Problem; and

generating, using the one or more computer systems, a main spine wire for each of the nets, wherein the generated main spine wire for each particular net is placed in the routing track assigned for the particular net.

2. The method of claim 1, wherein the plurality of nets comprises an integrated circuit.

3. The method of claim 1, wherein assigning, the assignable routing tracks to each of the nets is based on a solution to a Linear Assignment Problem in which one or more of the first set of routing tracks are considered for each net.

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

5. The method of claim 1, wherein the cost function comprises a first cost function and wherein assigning the assignable routing tracks to each of the nets comprises partitioning pins associated with each net into one or more groups based at least in part on a second cost function.

6. The method of claim 5, wherein the second cost function is based at least in part on wire lengths.

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

8. The method of claim 5, wherein partitioning, using the one or more computer systems, pins associated with each net into one or more groups is based at least in part on a position of the main spine routing track assigned to that net.

9. The method of claim 5, wherein pins of each group are located on a same side of a main spine of a corresponding net.

10. The method of claim 5, wherein partitioning, using the one or more computer systems, pins associated with each 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.

11. The method of claim 5, further comprising;

receiving, at the one or more computer systems, information indicative of a specification of a second set of routing tracks selectable for second level spines; and

assigning, using the one or more computer systems, a second level spine routing track from the second set of routing tracks to each group of each net based at least in part on a third cost function.

12. The method of claim 11, wherein the third cost function is based at least in part on wire lengths.

13. The method of claim 11, wherein assigning, using the one or more computer systems, a second level spine routing track to each group of each net based at least in part on a third cost function is based on a solution to a Linear Assignment Problem.

14. The method of claim 11, wherein assigning, using the one or more computer systems, a second level spine routing track to each group of each net based at least in part on a third cost function is based on a solution to a Linear Assignment Problem in which one or more of the second set of routing tracks are considered for each group.

15. The method of claim 11, further comprising generating, using the one or more computer systems, second level spine wires on the assigned second level spine routing tracks for each group.

16. The method of claim 15, further comprising generating, using the one or more computer systems, a wire between each pin of each group and a second level spine wire associated with that group.

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 level spine routing tracks are oriented substantially orthogonal to the main spine routing tracks.

19. A system for routing a plurality of nets, comprising:

a processor configured to;

receive a specification of a plurality of nets;

receive a specification of a first set of routing tracks, wherein each of the routing tracks of the specification is assignable for a main spine wire of one of the nets;

based on the received information of the nets, the received specification of the first set of routing tracks, and a cost function, assign of the assignable routing tracks to each of the nets based on a solution to a Linear Assignment Problem; and

generate a main spine wire for each of the nets, wherein the generated main spine wire for each particular net is placed in the routing track assigned to the particular net; and

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

20. The system of claim 19, wherein assigning one of the assignable routing tracks to each of the nets is based on a solution to a Linear Assignment Problem in which one or more of the first set of routing tracks are considered for each net.

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

22. The system of claim 19, wherein the cost function comprises a first cost function and wherein to assigning one of the assignable routing tracks to each of the nets comprises partitioning pins associated with each net into one or more groups based at least in part on a second cost function.

23. The system of claim 22, wherein the second cost function is based at least in part on wire lengths.

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

25. The system of claim 22, wherein the processor is further configured to receive a specification of a second set of routing tracks selectable for second level spines and assign a second level spine routing track to each group of each net based at least in part on a third cost function.

26. The system of claim 25, wherein the third cost function is based at least in part on wire lengths.

27. The system of claim 25, wherein to assign a second level spine routing track to each group of each net based at least in part on a third cost function is based on a solution to a Linear Assignment Problem in which one or more of the second set of routing tracks are considered for each group.

28. The system of claim 25, wherein the processor is further configured to generate second level spine wires on the assigned second level spine routing tracks for each group.

29. The system of claim 25, wherein the processor is further configured to generate a wire between each pin of each group and a second level spine wire associated with that group.

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 level spine routing tracks are oriented substantially orthogonal to the main spine routing tracks.

32. A computer program product for routing a plurality of nets, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving a specification of a plurality of nets;

receiving a specification of a first set of routing tracks, wherein each of the routing tracks of the specification is assignable for a main spine wire of one of the nets;

based on the received information of the nets, the received specification of the first set of routing tracks, and a cost function, assigning one of the assignable routing tracks to each of the nets based on a solution to a Linear Assignment Problem; and

generating a main spine wire for each of the nets, wherein the generated main spine wire for each particular net is placed in the routing track assigned to the particular net.

33. The computer program product embodied in the non-transitory computer readable storage medium of claim 32, wherein the cost function is based at least in part on wire lengths.

34. The computer program product embodied in the non-transitory computer readable storage medium of claim 32, wherein the cost function comprises a first cost function and wherein assigning one of the assignable routing tracks to each of the nets comprises partitioning pins associated with each net into one or more groups based at least in part on a second cost function.

35. The computer program product embodied in the non-transitory computer readable storage medium of claim 34, wherein the second cost function is based at least in part on wire lengths.

36. The computer program product embodied in the non-transitory computer readable storage medium of claim 34, further comprising computer instructions for receiving a specification of a second set of routing tracks selectable for second level spines and assigning a second level spine routing track to each group of each net based at least in part on a third cost function.

37. The computer program product embodied in the non-transitory computer readable storage medium of claim 36, wherein the third cost function is based at least in part on wire lengths.

38. The computer program product embodied in the non-transitory computer readable storage medium of claim 37, further comprising computer instructions for generating second level spine wires on the assigned second level spine routing tracks for each group.

39. The computer program product embodied in the non-transitory computer readable storage medium of claim 37, further comprising computer instructions for generating a wire between each pin of each group and a second level spine wire associated with that group.