Dynamic push for topological routing of semiconductor packages

• US 8,006,216 B1
• Filed: 06/06/2008
• Issued: 08/23/2011
• Est. Priority Date: 06/06/2008
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Magma Design Automation (Synopsys Incorporated)
• Inventors: Chen, Guoqiang, Sarto, Egino, Sheth, Kaushik, Liu, Shenghua
• Primary Examiner(s): Lin; Sun J
• Application Number:
  US12/134,849
• Time in Patent Office: 1,173 Days
• Field of Search: 716/126, 716/129, 716/130
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: H01L 23/49838 Geometry or layout
• CPC Class Codes: H01L 2924/00 Indexing scheme for arrangements or methods for connecting or disconnecting semiconductor or solid-state bodies as covered by H01L24/00
• CPC Class Codes: H01L 2924/0002 Not covered by any one of groups H01L24/00, H01L24/00 and H01L2224/00
• CPC Class Codes: H01L 2924/15311 being a ball array, e.g. BGA

Abstract

Techniques are disclosed for performing topologically planar routing of System in Packages (SiPs). A routing graph can be represented by a particle-insertion-based constraint Delaunay triangulation (PCDT) and its dual. A dynamic search routing may be performed using a DS* routing algorithm to determine the shortest path on the dual graph between a start point and an end point. Based on a dynamic pushing technique, net ordering problems may be solved. A first wire can be topologically routed. Dynamic search routing of a second wire may be performed. The first wire may be pushed or detoured in response to the dynamic searching routing of a second wire.

Claims

1. A computer-implemented method for routing topological interconnections for a package, the method comprising:

receiving, using one or more processors associated with one or more computer systems, information associated with a chip;

determining an escape routing of a bump array for the chip, the escape routing indicative of a set of I/Os along a set of escape boundaries;

determining a set of obstructions on a set of package layers;

determining a scale of via staggering pitches on the set of package layers;

for each build-up layer in the set of package layers, from a top layer to a bottom layer;

performing a topologically planar routing of each I/O in the set of I/Os to a location substantially vertical to a center of a corresponding ball, wherein at least a first net is dynamically pushed in response to the topologically planar routing of a second net, and

transferring a stopping point associated with an I/O for a failed net to another build-up layer by stack vias;

assigning vias for one or more successfully routed nets;

analyzing a congestion associated with each build-up layer to generate a congestion map; and

generating, with the one or more processors associated with the one or more computer systems, information indicative of a set of topological interconnections, the congestion map, and a set of fail-routed nets and storing the information in a storage device associated with the one or more computers systems.

2. The method of claim 1, wherein said performing a topologically planar routing of each I/O in the set of I/Os comprises:

distributing a set of particles over the build-up layer to generate a constraint Delaunay triangulation (CDT) graph;

generating a dual of the CDT graph; and

performing a dynamic search routing for each I/O based on the dual of the CDT graph.

3. The method of claim 2 wherein said performing a dynamic search routing for each I/O comprises:

sorting a set of nets on the build-up layer;

sequentially routing each net in response to one or more control parameters;

performing one or more re-route iterations to determine an improvement in a routing wire length; and

distributing cross points on a graph edge for each routed net.

4. The method of claim 3 wherein said sequentially routing each net comprises:

searching the shortest path from a source point to a sink point for a net using a dynamic search technique based on a triangulation plane.

5. The method of claim 4 wherein said sequentially routing each net using a dynamic search technique comprises:

pushing one or more nets blocking a search path associated with the net, the pushed nets being carried to a current searching node;

determining a realized cost and an estimated cost;

determining whether the current searching node is within a threshold to the sink point for the net, wherein the estimated cost is compared to a predefined stopping cost and the number of the pushed nets is compared to a maximal allowed pushing net count; and

if the current searching node is within a threshold to the sink point for the net;

post-processing the pushed nets to eliminate a “

U”

detour happening on a triangle edge or a “

V”

detour happening in a triangle.

6. The method of claim 5, wherein said determining the realized cost comprises:

determining a length of the shortest path from the source point to a dual node of a current searching triangle; and

determining wire widths of the net and the pushed nets.

7. The method of claim 5, wherein said determining the estimated cost comprises:

determining wire widths of the net and the pushed nets; and

determining a geometry distance from a dual node of a current searching triangle to the sink point.

8. The method of claim 3, wherein said performing one or more re-route iterations to determine an improvement in a routing wire length comprises:

re-ordering each net in response to the last routing iteration;

modifying the one or more control parameters in response to the last routing iteration; and

re-routing each net based on the re-ordering and the modified control parameters.

9. The method of claim 8, wherein said re-ordering each net comprises:

determining an estimate for a realized wire length for each net;

sorting each net in a decreasing order of an estimated realized wire length; and

modifying an ordering of one or more nets in response to a pushing order of the pushed nets.

10. The method of claim 8, wherein said re-routing each net based on the re-ordering and the modified control parameters comprises:

deleting a net path on a current build-up layer; and

routing the net based on the modified control parameters.

11. The method of claim 1, wherein said assigning vias for one or more successfully routed nets comprises:

determining via positions along a straight line from a stopping point to a corresponding ball center based on the scale of via staggering pitches.

12. The method of claim 1, wherein said analyzing a congestion associated with each build-up layer to generate a congestion map comprises:

analyzing edge congestion on a set of triangle edges; and

analyzing area congestion in a set of triangles.

13. A computer-implemented method for routing topological interconnections for a package, the method comprising:

receiving, using one or more processors associated with one or more computer systems, information associated with a build-up layer of the package;

generating a constraint Delaunay graph and a corresponding dual constraint Delaunay graph for the build-up layer;

determining a routing order associated with a set of nets for the build-up layer to generate a first set of ordered nets;

determining a set of routing control parameters;

performing a dynamic search routing using the dual constraint Delaunay graph and the set of routing control parameters to determine a topological planar routing for each net in the first set of ordered nets, wherein at least one net in the first set of ordered nets detours another net in the first set of ordered nets; and

generating, with the one or more processors associated with the one or more computer system, information indicative of the topological planar routing for each net in the first set of ordered nets and storing the information in a storage device associated with the one or more computers systems.

14. The method of claim 13 further comprising:

re-sorting the nets in the first set of ordered nets to generate a second set of ordered nets;

modifying the set of routing control parameters in response to the nets; and

performing a dynamic search routing using the dual constraint Delaunay graph and the modified set of routing control parameters to determine a topological planar routing for each net in the second set of ordered nets, wherein at least one net in the second set of ordered nets detours another net in the second set of ordered nets.

15. The method of claim 13 further comprising:

determining a cost associated with a topological planar routing for each net in the first set of ordered nets; and

pushing the at least one net in the first set of ordered nets when the cost fails to exceed a pre-determined threshold.

16. The method of claim 13 further comprising:

determining a congestion associated with a topological planar routing for each net in the first set of ordered nets; and

pushing the at least one net in the first set of ordered nets when the congestion satisfies a pre-determined tolerance.

17. The method of claim 13 further comprising:

modifying the at least one net subsequent to being pushed to reduce a length of the at least one net.

18. A non-transitory computer readable medium configured to store a set of code modules which when executed by a processor of a computer system become operational with the processor for routing topological interconnections of a package, the non-transitory computer readable medium comprising:

code for receiving information associated with a chip;

code for determining an escape routing of a bump array for the chip, the escape routing indicative of a set of I/Os along a set of escape boundaries;

code for determining a set of obstructions on a set of package layers;

code for determining a scale of via staggering pitches on the set of package layers;

code for, for each build-up layer in the set of package layers, from a top layer to a bottom layer;

performing a topologically planar routing of each I/O in the set of I/Os to a location substantially vertical to a center of a corresponding ball, wherein at least a first net is dynamically pushed in response to the topologically planar routing of a second net, and

transferring a stopping point associated with an I/O for a failed net to another build-up layer by stack vias;

code for assigning vias for one or more successfully routed nets;

code for analyzing a congestion associated with each build-up layer to generate a congestion map; and

code for generating information indicative of a set of topological interconnections, the congestion map, and a set of fail-routed nets.

19. The non-transitory computer readable medium of claim 18, wherein said code for performing a topologically planar routing of each I/O in the set of I/Os comprises:

code for distributing a set of particles over the build-up layer to generate a constraint Delaunay triangulation (CDT) graph;

code for generating a dual of the CDT graph; and

code for performing a dynamic search routing for each I/O based on the dual of the CDT graph.

20. The non-transitory computer readable medium of claim 19, wherein said code for performing a dynamic search routing for each I/O comprises:

code for sorting a set of nets on a build-up layer;

code for sequentially routing each net in response to one or more control parameters;

code for performing one or more re-route iterations to determine an improvement in a routing wire length; and

code for distributing cross points on a graph edge for each routed net.

21. The non-transitory computer readable medium of claim 20, wherein said code for sequentially routing each net comprises:

code for searching the shortest path from a source point to a sink point for a net using a dynamic search technique based on a triangulation plane.

22. The non-transitory computer readable medium of claim 20, wherein said code for performing one or more re-route iterations to determine an improvement in a routing wire length comprises:

code for re-ordering each net in response to the last routing iteration;

code for modifying the one or more control parameters in response to the last routing iteration; and

code for re-routing each net based on the re-ordering and the modified control parameters.

23. The non-transitory computer readable medium of claim 22, wherein said code for re-ordering each net comprises:

code for determining an estimate for a realized wire length for each net;

code for sorting each net in a decreasing order of an estimated realized wire length; and

code for modifying an ordering of one or more nets in response to a pushing order of pushed nets.

24. A non-transitory computer readable medium configured to store a set of code modules which when executed by a processor of a computer system become operational with the processor for routing topological interconnections of a package, the non-transitory computer readable medium comprising:

code for receiving information associated with a build-up layer of the package;

code for generating a constraint Delaunay graph and a corresponding dual constraint Delaunay graph for the build-up layer;

code for determining a routing order associated with a set of nets for the build-up layer to generate a first set of ordered nets;

code for determining a set of routing control parameters; and

code for performing a dynamic search routing using the dual constraint Delaunay graph and the set of routing control parameters to determine topological planar routing for each net in the first set of ordered nets, wherein at least one net in the first set of ordered nets detours another net in the first set of ordered nets.

25. A system for routing topological interconnections of a package, the system comprising:

a processor; and

a memory coupled to the processor, the memory configured to store a set of instructions which when executed by the processor cause the processor to;

receive information associated with a chip;

determine an escape routing of a bump array for the chip, the escape routing indicative of a set of I/Os along a set of escape boundaries;

determine a set of obstructions on a set of package layers;

determine a scale of via staggering pitches on the set of package layers;

for each build-up layer in the set of package layers, from a top layer to a bottom layer;

perform a topologically planar routing of each I/O in the set of I/Os to a location substantially vertical to a center of a corresponding ball, wherein at least a first net is dynamically pushed in response to the topologically planar routing of a second net, and

transfer a stopping point associated with an I/O for a failed net to another build-up layer by stack vias;

assign vias for one or more successfully routed nets;

analyze a congestion associated with each build-up layer to generate a congestion map; and

generate information indicative of a set of topological interconnections, the congestion map, and a set of fail-routed nets.

26. The system of claim 25, wherein to perform a topologically planar routing of each I/O in the set of I/Os the processor is further caused to:

distribute a set of particles over a build-up layer to generate a constraint Delaunay triangulation (CDT) graph;

generate a dual of the CDT graph; and

perform a dynamic search routing for each I/O based on the dual of the CDT graph.

27. The system of claim 26, wherein to perform a dynamic search routing for each I/O the processor is further caused to:

sort a set of nets on the build-up layer;

sequentially route each net in response to one or more control parameters;

perform one or more re-route iterations to determine an improvement in a routing wire length; and

distribute cross points on a graph edge for each routed net.

28. The system of claim 27, wherein to sequentially route each net the processor is further caused to:

search the shortest path from a source point to a sink point for a net using a dynamic search technique based on a triangulation plane.

29. The system of claim 27, wherein to perform one or more re-route iterations to determine an improvement in a routing wire length the processor is further caused to:

re-order each net in response to the last routing iteration;

modify the one or more routing control parameters in response to the last routing iteration; and

re-route each net based on the re-ordering and the modified control parameters.

30. The system of claim 29, wherein to re-order each net the processor is further caused to:

determine an estimate for a realized wire length for each net;

sort each net in a decreasing order of an estimated realized wire length; and

modify an ordering of one or more nets in response to a pushing order of pushed nets.

31. The system of claim 29, wherein to re-route each net based on the re-ordering and the modified control parameters the processor is further caused to:

delete a net path on a current build-up layer; and

route the net based on the modified control parameters.

32. A system for routing topological interconnections of a package, the system comprising:

a processor; and

a memory coupled to the processor, the memory configured to store a set of instructions which when executed by the processor cause the processor to;

receive information associated with a build-up layer of the package;

generate a constraint Delaunay graph and a corresponding dual constraint Delaunay graph for the build-up layer;

determine a routing order associated with a set of nets for the build-up layer to generate a first set of ordered nets;

determine a set of routing control parameters; and

perform a dynamic search routing using the dual constraint Delaunay graph and the set of routing control parameters to determine a topological planar routing for each net in the first set of ordered nets, wherein at least one net in the first set of ordered nets detours another net in the first set of ordered nets.