Multiple level spine routing
View Patent ↗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.
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, information indicative of a specification of a first set of routing tracks selectable for main spines;
assigning, using the one or more computer systems, a main spine routing track from the first set of routing tracks to each of the plurality of nets based at least in part on a cost function; and
generating, using the one or more computer systems, main spine wires on the assigned main spine routing tracks for each of the plurality of nets.
2. The method of claim 1 , wherein the plurality of nets comprises an integrated circuit.
3. The method of claim 1 , wherein assigning, using the one or more computer systems, a main spine routing track to each of the plurality of nets based at least in part on a cost function is based on a solution to a Linear Assignment Problem.
4. The method of claim 1 , wherein assigning, using the one or more computer systems, a main spine routing track to each of the plurality of nets based at least in part on a cost function 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.
5. The method of claim 1 , wherein the cost function is based at least in part on wire lengths.
6. The method of claim 1 , wherein the cost function comprises a first cost function and wherein assigning, using the one or more computer systems, a main spine routing track to each of the plurality of nets comprises partitioning pins associated with each net into one or more groups based at least in part on a second cost function.
7. The method of claim 6 , wherein the second cost function is based at least in part on wire lengths.
8. The method of claim 6 , wherein the first cost function comprises the second cost function.
9. The method of claim 6 , 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.
10. The method of claim 6 , wherein pins of each group are located on a same side of a main spine of a corresponding net.
11. The method of claim 6 , 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.
12. The method of claim 6 , 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.
13. The method of claim 12 , wherein the third cost function is based at least in part on wire lengths.
14. The method of claim 12 , 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.
15. The method of claim 12 , 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.
16. The method of claim 12 , 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.
17. The method of claim 16 , 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.
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 level spine routing tracks are oriented substantially orthogonal to the main spine routing tracks.
20. 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 selectable for main spines;
assign a main spine routing track from the first set of routing tracks to each of the plurality of nets based at least in part on a cost function; and
generate main spine wires on the assigned main spine routing tracks for each of the plurality of nets; and
a memory coupled to the processor and configured to provide the processor with instructions.
21. The system of claim 20 , wherein to assign a main spine routing track to each of the plurality of nets based at least in part on a cost function 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.
22. The system of claim 20 , wherein the cost function is based at least in part on wire lengths.
23. The system of claim 20 , wherein the cost function comprises a first cost function and wherein to assign a main spine routing track to each of the plurality of nets comprises partitioning pins associated with each net into one or more groups based at least in part on a second cost function.
24. The system of claim 23 , wherein the second cost function is based at least in part on wire lengths.
25. The system of claim 23 , wherein the first cost function comprises the second cost function.
26. The system of claim 23 , 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.
27. The system of claim 26 , wherein the third cost function is based at least in part on wire lengths.
28. The system of claim 26 , 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.
29. The system of claim 26 , wherein the processor is further configured to generate second level spine wires on the assigned second level spine routing tracks for each group.
30. The system of claim 26 , 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.
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 level spine routing tracks are oriented substantially orthogonal to the main spine routing tracks.
33. 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 selectable for main spines;
assigning a main spine routing track from the first set of routing tracks to each of the plurality of nets based at least in part on a cost function; and
generating main spine wires on the assigned main spine routing tracks for each of the plurality of nets.
34. The computer program product embodied in the non-transitory computer readable storage medium of claim 33 , wherein the cost function is based at least in part on wire lengths.
35. The computer program product embodied in the non-transitory computer readable storage medium of claim 33 , wherein the cost function comprises a first cost function and wherein assigning a main spine routing track to each of the plurality of nets comprises partitioning pins associated with each net into one or more groups based at least in part on a second cost function.
36. The computer program product embodied in the non-transitory computer readable storage medium of claim 35 , wherein the second cost function is based at least in part on wire lengths.
37. The computer program product embodied in the non-transitory computer readable storage medium of claim 35 , 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.
38. The computer program product embodied in the non-transitory computer readable storage medium of claim 37 , wherein the third cost function is based at least in part on wire lengths.
39. The computer program product embodied in the non-transitory computer readable storage medium of claim 38 , further comprising computer instructions for generating second level spine wires on the assigned second level spine routing tracks for each group.
40. The computer program product embodied in the non-transitory computer readable storage medium of claim 38 , further comprising computer instructions for generating a wire between each pin of each group and a second level spine wire associated with that group.