Abstract:
Disclosed is an improved method, system, and mechanism for using and constructing a minimum spanning tree. In one approach, each iteration of the process for constructing a minimum spanning tree calculates at most two additional point-pairs for nearest neighbors of points previously added to the tree. These additional point-pairs are appended to a list of point pairs, and the point-pair having the shortest distance is selected and added to the minimum spanning tree. Any metric can be employed to determine nearest neighbors, including Euclidean or Manhattan metrics. An advantage is that not all point-pairs need to be examined, greatly increasing speed and efficiency. Since every point-pair does not have to be examined, a preprocessing step is not required to reduce the number of point-pairs being considered. The resultant minimum spanning tree can be used to facilitate the routing process for an integrated circuit.

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
     This application is a Divisional of U.S. Non-Provisional application Ser. No. 10/342,640, filed Jan. 14, 2003, and is fully incorporated herein by reference for all purposes. 
    
    
     COPYRIGHT NOTICE 
     A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files and records, but otherwise reserves all other copyright rights. 
     BACKGROUND 
     The invention relates to a method and mechanism for using and implementing a minimum spanning tree. A minimum spanning tree is the shortest tree that connects a set of points in space. A Euclidean minimum spanning tree is the shortest tree in which the distance between a pair of points is the Euclidean distance. 
     Numerous advantages in many fields can be achieved by being able to efficiently construct a minimum spanning tree. For example, consider the process for designing an integrated circuit (“IC”). An IC is a small electronic device typically formed from semiconductor material. Each IC contains a large number of electronic components, e.g., transistors, that are wired together to form a self-contained circuit device. The components and wiring on the IC are materialized as a set of geometric shapes that are “placed and routed” on the chip material. During placement, the location and positioning of each geometric shape corresponding to an IC component are identified on the IC layers. During routing, a set of routes are identified to tie together the geometric shapes for the electronic components. 
     Constructing a minimum spanning tree is particularly useful with respect to the routing step. The minimum spanning tree provides a projection of the shortest connectivity that can be achieved between the components on the IC chip. This projection of the shortest connectivity can be used to develop a general mapping for how the chip should be routed, or even as the initial routing plan for the chip. 
     To explain approaches for constructing a minimum spanning tree, a useful term to describe is the “cut”, which is a subset of the points. A point-pair crosses the cut if one point is in the cut and the second point is outside the cut. Typically, the cut is a set of vertices that are currently connected in a partially-constructed minimum spanning tree, and the point-pair of interest is a point-pair that crosses the cut that are nearest to each other. The efficiency and speed for determining a minimum spanning tree is highly dependant upon the number of point-pairs to be considered. 
     Examples of known approaches for constructing a minimum spanning tree are the Prim, Kruskal and Sollin approaches, each of which calls for enumeration for all of the point-pairs involving vertex v that cross the cut formed by T′. In the Kruskal approach, the point-pairs are sorted and are considered in order. In the Prim and Sollin approaches, point-pairs are calculated for every point in the tree against every other point, and the point-pair having the shortest distance is added to the tree. These actions repeat until all points are added to the tree. In effect, all point-pairs must be enumerated at every stage of the process to determine the next point/vertex to add to the tree. A significant drawback to these approaches is that since an advanced IC chip may potentially contain a large number of points (components) to route together, requiring enumeration of every point-pair in the layout to form a minimum spanning tree could be prohibitively expensive. 
     A preprocessing step can be performed to specify a subset of the point-pairs to consider for the traditional approaches. However, such preprocessing steps are complicated to implement and may consume considerable time and computing resources. 
     SUMMARY 
     The present invention provides an improved method, a system, a computer program product comprising a computer usable storage medium storing the executable code which, when executed by a computer, causes the computer to perform the improved method, and a mechanism for using and constructing a minimum spanning tree. In one embodiment, each iteration of the process for constructing a minimum spanning tree calculates at most two additional point-pairs for nearest neighbors of points previously added to the tree. These additional point-pairs are appended to a list of point pairs, and the point-pair having the shortest distance is selected and added to the minimum spanning tree. Any metric can be employed to determine nearest neighbors, including Euclidean or Manhattan metrics. Embodiments of the invention have an advantage that not all point-pairs need to be examined, greatly increasing speed and efficiency. Since every point-pair does not have to be examined, a preprocessing step is not required to reduce the number of point-pairs being considered. The resultant minimum spanning tree can be used to facilitate the routing process for an integrated circuit. 
     Other and additional objects, features, and advantages of the invention are described in the detailed description, figures, and claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a flowchart of an embodiment of a process for constructing a minimum spanning tree. 
         FIGS. 2-11  show an illustrated example of a process for constructing a minimum spanning tree according to an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     The present invention provides an improved method, system, and mechanism for using and constructing a minimum spanning tree. 
       FIG. 1  shows a flowchart of an embodiment of the invention. Assume that T refers to the partially built minimum spanning tree. Initially, T contains a single vertex s ( 104 ). The single vertex s can be any point selected from the available set of points V. A point is not necessarily a zero-dimensional object; it could be any geometric object. The available set of points V refers to the set of points, components, or geometric objects/shapes for which it is desirable to construct a minimum spanning tree and/or to route together. A point-pair list L is maintained to track a set of point-pairs that may be added to the tree T. Any suitable data structure may be employed to maintain the tree T or list L. 
     At  106 , the nearest neighbor point in V to vertex s is identified. This action identifies the point that is the closest distance to the vertex s. If the “point” is actually a geometric shape, then the closest location(s) on the geometric shape to the neighbor(s) can be considered when determining the closest distance. The point-pair list L is modified to contain a single point-pair consisting of vertex s and its nearest neighbor in V. For a Euclidean minimum spanning tree, this action identifies the point having the Euclidean closest distance to vertex s. The invention is not limited to the Euclidean metric. Other nearest-neighbor approaches are available for additional metrics, such the Manhattan metric used for IC routing. Any suitable approach for determining a nearest neighbor can be employed in  106 , such as the approach for performing a nearest neighbor determination disclosed in co-pending U.S. application Ser. No. 10/342,768, which is now U.S. Pat. No. 6,981,235 and is entitled “Nearest Neighbor Mechanism”, filed on even date herewith, which is hereby incorporated by reference in its entirety. 
     At  108 , the identified point-pair is added to the minimum spanning tree T. If the initial point-pair was added to point-pair list L, then it is removed from L at this time. In an alternate embodiment, the initial point-pair is not added to L and therefore is not deleted at this time. 
     A determination is then made whether there are any additional points in V that are not yet in T ( 110 ). If there are no more points, then the entire tree has been constructed and the process ends. If there are additional points, then the process continues to  112 . 
     At  112 , the nearest neighbor determination is performed for each of the points for the point-pair most recently added to T. Nearest neighbors are selected from those points that are not yet in tree T. The identified point-pairs are stored in the point-pair list L. At  114 , the process selects (u,v), the shortest point-pair path stored in a point-pair list L. 
     At  116 , a determination is made whether the shortest point-pair path in list L forms a loop with existing points in tree T. This determination can be made by identifying whether both points in the point-pair are already in T. If so, then the shortest point-pair is removed from L ( 120 ). Another nearest neighbor calculation is performed to identify a replacement point-pair for the removed point-pair in L ( 122 ). Specifically, if (u,v) is in a loop, then a nearest neighbor of u that is not currently in T is found, say w, and (u,w) replaces (u,v). The process then returns to  114 . If the shortest point-pair (u,v) loop in L does not form a loop, then it is added to minimum spanning tree T. The point-pair is then removed from list L. In other words, if (u,v) crosses the cut, then add (u,v) to the tree T to form tree T′. The process then adds the nearest neighbor of u in (V−T′) to the point-pair list, and adds the nearest neighbor of v in (V−T′) to the point-pair list. The process then returns back to  110 , and loops until all points in V have been added to the tree T. 
     The following describes pseudo code for implementing an embodiment of the invention, where “NN( )” refers to the selected nearest-neighbor calculation:
         1. Let T={s}, L={(s, NN(s, V−T))}   2. while (T!=V)   3. (u,v)=remove shortest pair from L   4. if u and v are in the same connected component of T   5. L=L U{(u, NN(u, V−T))}   6. else   7. T=T U{v}   8. L=L U {(u, NN(u, V−T))} U {(v, NN(v, V−T)}       

     In this example pseudo code, line  1  initializes the partially constructed tree and the point-pair list L, as described in  104 - 106  of  FIG. 1 . Line  2  begins a loop which ends when all of the points have been added to the tree. Line  3  removes the shortest pair from the point-pair list L. Line  4  checks to see whether this point-pair induces a cycle in T. If so, then line  5  is performed. Otherwise, lines  7  and  8  are performed. If line  5  is performed, then the nearest neighbor list is updated. In the point-pair, it is assumed that the first point is in T. Then u and its nearest neighbor with respect to the current cut are added to the point-pair list. If step  7  and  8  are run, the tree is updated, and two pairs are added to the list L. These pairs are the nearest neighbors of u and v with respect to the current cut. 
     It is noted that in this approach, at most only two nearest neighbor calculations are performed for each iteration of the loop. This is in contrast to the prior approaches in which all point-pairs are processed for each additional point-pair to add to the tree. If vertex v is already in the tree, then the nearest neighbor of u that crosses the cut is found. Otherwise, vertex v is added to the tree, and the nearest neighbor of v that crosses the cut must be found as well. 
     ILLUSTRATIVE EXAMPLE 
       FIGS. 2-11  provide an illustrative example of an embodiment of the process for determining a minimum spanning tree when applying the method shown in  FIG. 1 . This example will pictorially show and explain the process of adding point-pairs to the minimum spanning tree. In these figures, the path for a point-pair added to the minimum spanning tree T will be shown with a solid connecting line and the path for a point-pair added to the point-pair list L will be shown with a dashed connecting line. As this example is described, the relevant process actions from  FIG. 1  are identified for the sake of exposition. 
       FIG. 2  shows an initial set of points (objects) A, B, C, D, and E. Initially, there are no points in the minimum tree. Assume that point A is selected as the initial Vertex ( 104 ). Further assume that the nearest neighbor to point A is point B ( 106 ). The initial point-pair A-B is added to the tree ( 108 ). The action of adding the point-pair A-B to the tree is pictorially illustrated by the modified set of points shown in  FIG. 3 . This figure displays a path  202  corresponding to the point-pair A-B added to the minimum spanning tree. 
     The next action is to determine whether there are any additional points that are not yet in the tree ( 110 ). At this time, only points A and B have been added to the tree. Points C, D, and E have not yet been added to the minimum spanning tree. Therefore, the process will continue. 
     Referring to  FIG. 4 , an identification is made of the nearest neighbor for each of the points in the point-pair most recently added to the tree ( 112 ). Here, the point-pair most recently added to the tree was A-B. Therefore, the nearest neighbor for each of point A and point B are identified. Assume that point C is the nearest neighbor to point B and that point E is the nearest neighbor to point A. Therefore, point-pairs B-C and A-E are added to the point-pair list. This is pictorially illustrated in  FIG. 4  by the dashed path  204  for point-pair B-C and the dashed path  206  for point-pair A-E. 
     Referring to  FIG. 5 , the next action is to identify which point-pair in the point-pair list has the shortest distance ( 114 ). Assume that the point-pair B-C has a shorter distance than point-pair A-E. A determination is made whether the path  204  for point-pair B-C forms a loop with an existing point in the minimum spanning tree ( 116 ). Here, it can be seen that it does not, since point C is not yet in the tree. Therefore, point-pair B-C is added to the minimum spanning tree ( 118 ). This is pictorially shown in  FIG. 5  by changing path  204  from a dashed line to a solid line. 
     Once again, a determination is made whether there are any additional points that are not yet in the tree ( 110 ). At this time, points A, B, and C have been added to the minimum spanning tree. Points D and E have not yet been added to the tree. Therefore, the process will continue. 
     Referring to  FIG. 6 , identification is made of the nearest neighbor for each of the points in the point-pair most recently added to the tree ( 112 ). Here, the point-pair most recently added to the tree was B-C. Therefore, the nearest neighbor for each of points B and C are identified. 
     Assume that point D is the nearest neighbor to point B. Therefore, point-pair B-D is added to the point-pair list as pictorially shown in  FIG. 6  by the dashed path  208  between B and D. 
     Assume that point D is the nearest neighbor to point C (for points not yet in the tree). Therefore, point-pair C-D is added to the point-pair list. This is pictorially illustrated in  FIG. 6  by the dashed path  212  between points C and D. 
     It is noted that the point-pair (A-E) previously placed in point-pair list still remains in that list. The new point-pairs added to the point-pair list (C-D and B-D) append to the contents of the list rather than replacing the existing list. Thus, the point-pair list now includes A-E, C-D, and B-D. In this manner, the point-pair information previously identified for prior iterations of the nearest neighbor calculations do not need to be re-calculated for points not added to the minimum spanning tree. Instead, that information is retained and is used to determine the next point-pair set that is added to the minimum spanning tree. 
     This highlights a significant advantage of the present approach. Since the previous point-pair information is retained, each iteration of the process only needs to perform the nearest neighbor calculations for two points—for the two points of the point-pair most recently added to the minimum spanning tree. This is sufficient to maintain information about the nearest neighbor point-pair for every point in the tree, regardless of the number of points already existing in the tree. 
     Referring to  FIG. 7 , the next action is to identify which point-pair in the point-pair list has the shortest distance ( 114 ). Assume that the point-pair C-D has a shorter distance than point-pairs A-E and B-D. A determination is made whether the path  212  for point-pair C-D forms a loop with an existing point in the minimum spanning tree ( 116 ). Here, it can be seen that it does not, since point D is not yet in the tree. Therefore, point-pair C-D is added to the minimum spanning tree ( 118 ). This is pictorially shown in  FIG. 7  by changing path  212  from a dashed line to a solid line. 
     A determination is again made whether there are any additional points that are not yet in the tree ( 110 ). At this time, points A, B, C, and D have been added to the minimum spanning tree. However, point E has not yet been added to the tree. Therefore, the process continues. 
     Referring to  FIG. 8 , identification is made of the nearest neighbor for each of the points in the point-pair most recently added to the tree ( 112 ). Here, the point-pair most recently added to the tree was C-D. Therefore, the nearest neighbor for each of points C and D are identified. Assume that point E is the nearest neighbor not yet in the tree to point D and that point E is also the nearest neighbor to point C. Therefore, point-pairs C-E and D-E are appended to the point-pair list. This is pictorially illustrated in  FIG. 8  by the dashed path  214  for point-pair D-E and the dashed path  216  for point-pair C-E. 
     With reference to  FIG. 9 , the next action is to identify which point-pair in the point-pair list has the shortest distance ( 114 ). Assume that path  208  for point-pair B-D has a shorter distance than paths  206 ,  214 , and  216  for point pairs A-E, D-E, and C-E, respectively. A determination is made whether the path  208  for point-pair A-C forms a loop with an existing point in the minimum spanning tree ( 116 ). Here, it can be seen that it does, since all the points in point-pair B-D are already in the minimum spanning tree. Therefore, point-pair B-D is not added to the tree; instead, this point-pair is removed from the point-pair list ( 120 ). In one embodiment, this point-pair is removed from further eligibility for being selected by the nearest neighbor calculations. This is pictorially shown in  FIG. 9  by removal of the path  208  between point B and point D. 
     A replacement point-pair can be identified for the particular point associated with the removed point-pair. Here, another nearest neighbor calculation is performed for point B, since removed point-pair B-D was identified based upon the nearest neighbor calculation previously performed for point B. Assume that point E is the nearest neighbor to point B, subject to the previous point-pair (B-D) and any other points in the tree being removed from eligibility. Therefore, point-pair B-E is added to the existing point-pair list. This is pictorially illustrated in  FIG. 10  by the dashed path  215  between points B and E. 
     The next action is to determine which point-pair in the point-pair list has the shortest distance ( 114 ). Assume that the path  214  for point-pair D-E has a shorter distance than the paths  206 ,  215 , and  216  for point-pairs A-E, B-E, or C-E, respectively. A determination is made whether the path  214  for point-pair D-E forms a loop with an existing point in the minimum spanning tree ( 116 ). Here, it can be seen that it does not, since point E is not yet in the tree. Therefore, point-pair D-E is added to the minimum spanning tree ( 118 ). This is pictorially shown in  FIG. 10  by portraying path  214  as a solid line (from the dashed line in  FIG. 9 ). 
     A determination is made whether there are any additional points that are not yet in the tree ( 110 ). At this time, points A, B, C, D, and E have all been added to the minimum spanning tree. There are no further points to add to the tree. Therefore, the minimum spanning tree for the set of points {A, B, C, D, E} has been fully constructed.  FIG. 11  displays the final form of the minimum spanning tree for this example with paths  202 ,  204 ,  212 , and  214  showing the point-pairs in the tree. 
     This minimum spanning tree can be used for a number of practical applications. For example, the tree provides a projection and/or a visualization of shortest connectivity and routing between the points. This connectivity can be used to develop a plan for routing the IC or as an initial estimate/plan for routing the chip. It can form the basis of further estimates for the placement process, such as determining whether the placement can be successfully routed and whether circuit timing constraints can be met. 
     In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. For example, the above-described process flows are described with reference to a particular ordering of process actions. However, the exact ordering or content of the described process actions may be changed without affecting the scope or operation of the invention. In addition, points may refer to geometric objects such as sets of rectangles, polygons, and circles. The Euclidean metric may be generalized to any metric. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense.