Abstract:
A method for designing wiring topology for electromigration avoidance, which is composed of multiple sources, multiple sinks and multiple wires, is disclosed. The steps of said method to get an optimal topology includes: 1. calculating the length of all the wires to choose one of the wires with the shortest length as a feasible wire, 2. deciding a capacity of the feasible wire, 3. deciding the capacities of the other wire according to the capacity of the feasible wire, a flow of the source of the feasible wire and a flow of the sink of the feasible wire, 4. comparing the length of the other wires to select another feasible wire, 5. repeating said steps until finding all feasible wires for constructing a feasible topology, 6. creating a flow network according to the feasible topology, 7. iteratively checking if a negative cycle exists in the flow network and removing it until no more negative cycles.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    (1) Field of the Invention 
         [0002]    The invention relates to a method for designing wiring topology and a fabrication method of integrate circuit including said method, and especially relates to a method for designing optimal wiring topology applied for electromigration avoidance in the integrate circuit. 
         [0003]    (2) Description of the Prior Art 
         [0004]    For the shrinking feature size and multiple functions of the chip, the components and the designed wires thereof disposed on the chip are more complex, so the size of the wires should be shrunk. Therefore, as the long term usage of the chip or the current density of the wire exceeding the process limitation, a mass of atoms inside of the metal wire are forced to migrate along the direction of the current, and the gradual transport eventually causes the void and the hillock formed on the wire. Said phenomenon is referred to as electromigration (EM), and the electromigration causes a permanent failure, such as open circuit or short circuit. For example, the failure of the chip is triggered when the hillock of the wire contacting with the neighbor. 
         [0005]    The conventional method for EM avoidance essentially relies on the following two techniques: one is an accurate EM simulator for increasing the reliability; the other is a good wiring topology for EM avoidance. 
         [0006]    The first technique is that the chip is analyzed by an accurate EM simulator at post routing for diminishing the EM risk. The narrow wire routed on the chip is widened according to the current density of the wire. However, the conventional EM fixing is applied at post-layout, which may consume tremendous routing resources and induce a large amount of layout change. 
         [0007]    The second technique is that the good wiring topology considering EM is applied to a router, which may immune EM with much fewer routing resources. One of the conventional method for designing wiring topology is based on the Delaunay triangulation (DT) algorithm to calculate the feasible solution of the wire in advance of EM avoidance. 
         [0008]    The DT-based method is described as below. First of all, the connected graph is constructed by the Delaunay triangulation algorithm so that each of all the source currents is connected with each of all the sink currents. Secondly, a source or a sink at the DT boundary is selected as the starting point, and the starting point is connected to the nearest neighbor in DT. Considering the two possible current directions of the connection wire, the starting point is then greedily connected to the nearest neighbor with the feasible solution and the width of the wire is determined accordingly. Another point at the DT boundary is selected to obtain the better result. Said process is repeated and, finally, the resulting tree is formed by the method for designing wiring topology with the DT-based method. 
         [0009]    However, the tree edge is able be provided only from DT edges; thus, if the solution must include a non-DT edge, the wiring topology fails. 
         [0010]    Consequently, how to find the optimal wiring topology to avoid electromigration and to save the routing resource is an important issue. 
       SUMMARY OF THE INVENTION 
       [0011]    Accordingly, the objective of the invention is to provide a method for designing wiring topology applied for electromigration avoidance. 
         [0012]    In one aspect, the invention provides a method for designing wiring topology, applied for selecting an optimal wiring topology for electromigration avoidance among a plurality of wiring topologies on a chip set. Wherein each of the wiring topologies has a plurality of sources, a plurality of sinks and a plurality of wires, each of the wires is directly connected between one of the sources and one of the sinks, each of the sources provides a source current, each of the sinks receives a sink current, and an effective current flows from one of the sources into one of the sinks through each of the wires. 
         [0013]    The steps of the method includes: calculating the lengths of all the wires to choose the minimum among the wires as a feasible wire; deciding a capacity of the feasible wire, wherein the capacity is the maximum of the effective current through the feasible wire; deciding the capacity of each of the other wires according to the capacity, the source current and the sink current of the feasible wire; comparing the length of the other wires to choose another feasible wire; repeating said steps until finding all feasible wires to construct a feasible wiring topology; creating a flow network according to the feasible wiring topology; executing an algorithm to iteratively check if a negative cycle existing in the flow network; and removing the negative cycle if existing in the flow network to obtain the optimal wiring topology. Wherein the feasible wiring topology is defined as the optimal wiring topology if no more the negative cycle existing in the flow network. 
         [0014]    In an embodiment, further including: replacing the feasible wire with a ladder-type wire by one end of the feasible wire connected by a horizontal wire and another end of feasible wire connected by a vertical wire, wherein the horizontal wire is perpendicular to the vertical wire. 
         [0015]    In an embodiment, an obstacle is disposed on the chip set, and the obstacle is bypassed by one of the wires, so the steps of the method comprises: adding a routing length to the length of the wire bypassing the obstacle. 
         [0016]    In an embodiment, the chip set has at least two routing layers stacked, and the length of the wire passing the two routing layers has a minimal distance between the two routing layers. 
         [0017]    In another aspect, the invention provides a fabrication method of integrate circuit including the method for designing wiring topology, wherein the method for designing wiring topology is utilized before the routing stage. 
         [0018]    In the other aspect, the invention provides a fabrication method of integrate circuit including the method for designing wiring topology, wherein the method for designing wiring topology is utilized after the routing stage to apply for local modification. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0019]      FIG. 1  is a chart showing the method for designing wiring topology. 
           [0020]      FIG. 2  is a schematic view of the feasible wiring topology on the chip set with single routing layer. 
           [0021]      FIG. 3  is a schematic view of the flow network. 
           [0022]      FIG. 4  is a schematic view of the residual graph of the flow network. 
           [0023]      FIG. 5  is a schematic view of the residual graph with removing the negative cycle. 
           [0024]      FIG. 6  is a schematic view of the optimal flow network. 
           [0025]      FIG. 7  is a schematic view of the optimal wiring topology on the chip set with single routing layer. 
           [0026]      FIG. 8  is a schematic view of the conversion between the optimal wiring topology and the optimal rectilinear routing. 
           [0027]      FIG. 9  is a schematic view of the optimal rectilinear routing on the chip set with single routing layer. 
           [0028]      FIG. 10  is a schematic view of the optimal wiring topology on the chip set with single routing layer considering the obstacle. 
           [0029]      FIG. 10A  is a schematic view of the optimal rectilinear routing on the chip set with single routing layer considering the obstacle. 
           [0030]      FIG. 11  is a schematic view of the optimal wiring topology on the chip set with multiple routing layers. 
           [0031]      FIG. 11A  is a schematic view of the optimal rectilinear routing on the chip set with multiple routing layers. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0032]    In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. In this regard, directional terminology, such as “top,” “bottom,” “front,” “back,” etc., is used with reference to the orientation of the Figure(s) being described. The components of the present invention can be positioned in a number of different orientations. As such, the directional terminology is used for purposes of illustration and is in no way limiting. On the other hand, the drawings are only schematic and the sizes of components may be exaggerated for clarity. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention. Also, it is to be understood that the phraseology and terminology used herein are for the purpose of description and should not be regarded as limiting. The use of “including,” “comprising,” or “having” and variations thereof herein is meant to encompass the items listed thereafter and equivalents thereof as well as additional items. Unless limited otherwise, the terms “connected,” “coupled,” and “mounted” and variations thereof herein are used broadly and encompass direct and indirect connections, couplings, and mountings. Similarly, the terms “facing,” “faces” and variations thereof herein are used broadly and encompass direct and indirect facing, and “adjacent to” and variations thereof herein are used broadly and encompass directly and indirectly “adjacent to”. Therefore, the description of “A” component facing “B” component herein may contain the situations that “A” component facing “B” component directly or one or more additional components is between “A” component and “B” component. Also, the description of “a” component “adjacent to” “B” component herein may contain the situations that “A” component is directly “adjacent to” “B” component or one or more additional components is between “A” component and “B” component. Accordingly, the drawings and descriptions will be regarded as illustrative in nature and not as restrictive. 
         [0033]    The present invention provides a method for designing wiring topology for electromigration avoidance and a fabrication method of integrate circuit including said method, applied on a chip set. The method for designing wiring topology is utilized before the routing stage, where the routing stage in the fabrication method of integrate circuit is applied for the components electrically connected with each other on the chip set. In other words, the method for designing wiring topology with considering the electromigration avoidance is able to find an optimal wiring topology for decreasing the routing resources when the designed wiring stage of the chip set without routing. Therefore, the method for designing wiring topology is able to be utilized after the routing stage to apply for local modification for keeping electromigration off in the integrate circuit. 
         [0034]    For executing the method for designing wiring topology to avoid electromigration, a computer is utilized in the present invention to run a wiring topology designed software. The wiring topology designed software provides a flow network to simulate the wiring topology. The hardware in the method for designing wiring topology is described as below. The computer has an input unit, an operating unit, a storage unit and an output unit. The input unit is a keyboard or a handwriting input device. The operation unit is a central processing unit (CPU). The storage unit is a hardware electrically connected to the input unit, the operating unit and the output unit. The wiring topology designed software is installed in the hardware. The output unit is a display or a printer. 
         [0035]    Refer to  FIG. 1  for a chart showing the method for designing wiring topology. The steps of the method are described as below. 
         [0036]    Step( 100 ): input the positions and the source currents of the sources (x si , y si , f si ), the positions and the sink currents of the sinks (x tj , y tj , f tj ), a minimal wiring length w min , a maximal wiring length w max  and a maximum tolerable current density J max  by an user of the wiring topology designed software via the input unit. Wherein the wiring topology has a plurality of sources, a plurality of sinks and a plurality of wires, each of the wires is straightly connected between one of the sources and one of the sinks, and an effective current flows from one of the sources into one of the sinks through each of the wires. 
         [0037]    Step( 101 ): calculate the length of all the wires to choose the minimum among all the wires as a feasible wire, which has a minimal length of all the wires, via the operating unit. 
         [0038]    Step( 102 ): decide a capacity of the feasible wire, and an effective current of each feasible wire smaller than or equal to the corresponding capacity. In other words, the capacity is the maximum of the effective current through the feasible wire. Wherein the minimum min(f si , f tj ) of the source current f si  and the sink current f y  is selected as the capacity of the feasible wire. 
         [0039]    Step( 103 ): decide the capacity of each of the other wires except for the chosen feasible wire according to the capacity, the source current and the sink current of the feasible wire. 
         [0040]    Step( 104 ): compare the length of the other wires to choose the minimum among the other wires as another feasible wire, which has a secondary minimal length of all the wires, and back to step(S 102 ). Therefore, judge if the capacity of each of the other wires is zero. When the capacity of one of the other wires is zero, said wire should not be added more capacity up, so said wire is unable to be as the feasible wire. 
         [0041]    Step( 105 ): repeat said step(S 102 ) to step(S 104 ) until find all feasible wires to construct a feasible wiring topology. Wherein a current density of each of the feasible wires is smaller than or equal to the maximum tolerable current density J max . 
         [0042]    Step( 106 ): create a flow network according to the feasible wiring topology. 
         [0043]    Step( 107 ): execute an algorithm to iteratively check if a negative cycle existing in the flow network. Yes for going to the step(S 108 ); no for going to the step(S 109 ). Wherein said algorithm is a negative cycle detection algorithm. 
         [0044]    Step( 108 ): remove the negative cycle if existing in the flow network to obtain the optimal wiring topology and go to the step(S 110 ). 
         [0045]    Step( 109 ): define the feasible wiring topology as the optimal wiring topology. 
         [0046]    Step( 110 ): modify the over extension or the under extension for the width of the feasible wires in the optimal wiring topology in accordance with the minimal wiring length w min  and the maximal wiring length w max . 
         [0047]    Finally, replace the feasible wire with a ladder-type wire by one end of the feasible wire connected by a horizontal wire and another end of the feasible wire connected by a vertical wire. Wherein the horizontal wire is perpendicular to the vertical wire. The below steps is illustrated that the method for designing wiring topology is applied for finding an optimal wiring topology on the chip set in advance of the designed wiring stage. The optimal wiring topology connected all the sources and the sinks is formed as an optimal rectilinear routing S+T, so that the current is able to flow through each wire and to satisfy the Kirchhoff&#39;s current conservation law. 
         [0048]    Step 1: given a set S={s 1 , s 2 , . . . , s m } of m sources, a set T={t 1 , t 2 , . . . , t n } of n sinks, each source i is associated with its flow characterized source current f si  and each sink j is associated with its flow characterized sink current f si . 
         [0049]    In an embodiment, a single routing layer of the chip set  100  having three sources and four sinks is illustrated with  FIG. 2 . The data of the sources S={s 1 , s 2 , s 3 } and the data of the sinks T={t 1 , t 2 , t 3 , t 4 } are tabulated. The wire and its capacity between the sources S={s 1 , s 2 , s 3 } and the sinks T={t 1 , t 2 , t 3 , t 4 } are shown as Table 1 to Table 7. Wherein each lattice (L, C) represents each connection having the length L of the wire and the capacity C. 
         [0050]    1. Calculate the length of all the wires to choose the minimum among all the wires as a feasible wire and decide a capacity of the feasible wire. Wherein the minimum min(f si , f tj ) among the source current f si  and the sink current f tj  is selected as the capacity of the feasible wire. 
         [0051]    As Table 1 showing, the connection (5,2) is selected as the feasible wire, and the former represents the length of the feasible wire and the latter represents the capacity of the feasible wire. Because the sources s 3  of the feasible wire has the source current f si =+9 and the sink t 3  of the feasible wire has the sink current f si =−2, the capacity of the feasible wire is min(|f si |, |f tj |)=2. Said feasible wire is the wire between the source s 3  and the sink t 3  as shown in  FIG. 2 . Wherein the source current, provided by the source, is represented by the positive signs “+”, and the source current, received by the sink, is represented by the negative signs “−”. 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 1 . . . 
               
             
          
           
               
                 S/T 
                 t 1 (−8) 
                 t 2 (−4) 
                 t 3 (−2) 
                 t 4 (−5) 
               
               
                   
               
               
                 s 1 (+7) 
                 (7, 7) 
                 (13, 4) 
                 (18, 2) 
                 (13, 5) 
               
               
                 s 2 (+3) 
                 (7, 3) 
                 (11, 3) 
                 (6, 2) 
                 (7, 3) 
               
               
                 s 3 (+9) 
                 (12, 8) 
                 (8, 4) 
                 (5, 2) * 
                 (10, 5) 
               
               
                   
               
               
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0052]    2. Decide the capacity of each of the other wires except for the chosen feasible wire according to the capacity, min(|f si |, |f tj |)=2, of the connection (5,2), the source current f si =+9 of the source s 3  and the sink current f tj =−2 of the sink t 3 . As shown in Table 2, the capacity of the connection between the source s 1  and the sink t 3  is zero, the capacity of the connection between the source s 2  and the sink t 3  is zero, the capacity of the connection between the source s 3  and the sink t 1  is 7 unit, and the capacity of the connection between the source s 3  and the sink t 2  is 4 unit. Therefore, the source s 3  provides the current of 2 unit to the sink t 3 , so the source current f si  of the source s 3  is varied from 9 unit to 2 unit. The sink t 3  receives the current of 2 unit from the source s 3 , so the sink current f tj  is varied from 2 unit to zero. 
         [0053]    Compare the length of the other wires to choose the minimum among the other wires as another feasible wire, which has a secondary minimal length of all the wires, so the connection (7,3) is selected, which represents the wire between the source s 2  and the sink t 4  in  FIG. 2 . When the capacity of one of the other wires is zero, said wire is unfeasible, so said wire is unable to be as the feasible wire. 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 2 . . . 
               
             
          
           
               
                 S/T 
                 t 1 (−8) 
                 t 2 (−4) 
                 t 3 (0) 
                 t 4 (−5) 
               
               
                   
               
               
                 s 1 (+7) 
                 (7, 7) 
                 (13, 4) 
                 (18, 0) 
                 (13, 5) 
               
               
                 s 2 (+3) 
                 (7, 3) 
                 (11, 3) 
                 (6, 0) 
                 (7, 3) * 
               
               
                 s 3 (+7) 
                 (12, 7) 
                 (8, 4) 
                 (5, 2) * 
                 (10, 5) 
               
               
                   
               
               
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0054]    3. Decide the capacity of each of the other wires except for the chosen feasible wires according to the capacity, min(|f si |, |f tj |)=3, of the connection (7,3), the source current f si =+3 of the source s 2  and the sink current f tj =−5 of the sink t 4 . As shown in Table 3, the capacity of the connection between the source s 1  and the sink t 4  is 2 unit, the capacity of the connection between the source s 2  and the sink t 1  is zero, the capacity of the connection between the source s 2  and the sink t 2  is zero, and the capacity of the connection between the source s 3  and the sink t 4  is 2 unit. Therefore, the source s 2  provides the current of 3 unit to the sink t 4 , so the source current f si  of the source s 2  is varied from 3 unit to zero. The sink t 4  receives the current of 3 unit from the source s 2 , so the sink current is varied from 5 unit to 2 unit. 
         [0055]    Compare the length of the other wires, and the connection (7,7) is selected as another feasible wire, which represents the wire between the source s 1  and the sink t 1  in  FIG. 2 . 
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 3 . . . 
               
             
          
           
               
                   
                 S/T 
                 t 1 (−8) 
                 t 2 (−4) 
                 t 3 (0) 
                 t 4 (−2) 
               
               
                   
                   
               
               
                   
                 s 1 (+7) 
                 (7, 7) * 
                 (13, 4) 
                 (18, 0) 
                 (13, 2) 
               
               
                   
                 s 2 (0) 
                 (7, 0) 
                 (11, 0) 
                 (6, 0) 
                 (7, 3) * 
               
               
                   
                 s 3 (+7) 
                 (12, 7) 
                 (8, 4) 
                 (5, 2) * 
                 (10, 2) 
               
               
                   
                   
               
               
                   
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0056]    4. Decide the capacity of each of the other wires except for the chosen feasible wires according to the capacity, min(|f si |, |f tj |)=7, of the connection (7,7), the source current f si =+7 of the source s 1  and the sink current f tj =−8 of the sink t 1 . As shown in Table 4, the capacity of the connection between the source s 1  and the sink t 2  is zero, the capacity of the connection between the source s 1  and the sink t 3  is zero, the capacity of the connection between the source s 1  and the sink t 4  is zero, the capacity of the connection between the source s 2  and the sink t 1  is zero, and the capacity of the connection between the source s 3  and the sink t 1  is 1 unit. Therefore, the source s 1  provides the current of 7 unit to the sink t 1 , so the source current f si  of the source s 1  is varied from 7 unit to zero. The sink t 1  receives the current of 7 unit from the source s 1 , so the sink current f tj  is varied from 8 unit to 1 unit. 
         [0057]    Compare the length of the other wires, and the connection (8,4) is selected as another feasible wire, which represents the wire between the source s 3  and the sink t 2  in  FIG. 2 . 
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 4 . . . 
               
             
          
           
               
                   
                 S/T 
                 t 1 (−1) 
                 t 2 (−4) 
                 t 3 (0) 
                 t 4 (−2) 
               
               
                   
                   
               
               
                   
                 s 1 (0) 
                 (7, 7) * 
                 (13, 0) 
                 (18, 0) 
                 (13, 0) 
               
               
                   
                 s 2 (0) 
                 (7, 0) 
                 (11, 0) 
                 (6, 0) 
                 (7, 3) * 
               
               
                   
                 s 3 (+7) 
                 (12, 1) 
                 (8, 4) * 
                 (5, 2) * 
                 (10, 2) 
               
               
                   
                   
               
               
                   
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0058]    5. Decide the capacity of each of the other wires except for the chosen feasible wires according to the capacity, min(|f si |, |f tj |)=4, of the connection (8,4), the source current f si =+7 of the source s 3  and the sink current f tj =−4 of the sink t 2 . As shown in Table 5, the capacity of the connection between the source s 3  and the sink t 1  is 1 unit, and the capacity of the connection between the source s 3  and the sink t 4  is 2 unit. Therefore, the source s 3  provides the current of 4 unit to the sink t 2 , so the source current f si  of the source s 3  is varied from 7 unit to 3 unit. The sink t 2  receives the current of 7 unit from the source s 1 , so the sink current f tj  is varied from 4 unit to zero. 
         [0059]    Compare the length of the other wires, and the connection (10,2) is selected as another feasible wire, which represents the wire between the source s 3  and the sink t 4  in  FIG. 2 . 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                 TABLE 5 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 5 . . . 
               
             
          
           
               
                 S/T 
                 t 1 (−1) 
                 t 2 (0) 
                 t 3 (0) 
                 t 4 (−2) 
               
               
                   
               
               
                 s 1 (0) 
                 (7, 7) * 
                 (13, 0) 
                 (18, 0) 
                 (13, 0) 
               
               
                 s 2 (0) 
                 (7, 0) 
                 (11, 0) 
                 (6, 0) 
                 (7, 3) * 
               
               
                 s 3 (+3) 
                 (12, 1) 
                 (8, 4) * 
                 (5, 2) * 
                 (10, 2) * 
               
               
                   
               
               
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0060]    6. Decide the capacity of each of the other wires except for the chosen feasible wires according to the capacity, min(|f si |, |f tj |)=2, of the connection (10,2), the source current f si =+3 of the source s 3  and the sink current f tj =−2 of the sink t 4 . As shown in Table 6, the capacity of the connection between the source s 3  and the sink t 1  is 1 unit. Therefore, the source s 3  provides the current of 2 unit to the sink t 4 , so the source current f si  of the source s 3  is varied from 3 unit to 1 unit. The sink t 2  receives the current of 2 unit from the source s 1 , so the sink current f tj  is varied from 2 unit to zero. 
         [0061]    Compare the length of the other wires, and the connection (12,1) is selected as another feasible wire, which represents the wire between the source s 3  and the sink t 1  in  FIG. 2 . 
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 6 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 6 . . . 
               
             
          
           
               
                   
                 S/T 
                 t 1 (−1) 
                 t 2 (0) 
                 t 3 (0) 
                 t 4 (0) 
               
               
                   
                   
               
               
                   
                 s 1 (0) 
                 (7, 7) * 
                 (13, 0) 
                 (18, 0) 
                 (13, 0) 
               
               
                   
                 s 2 (0) 
                 (7, 0) 
                 (11, 0) 
                 (6, 0) 
                 (7, 3) * 
               
               
                   
                 s 3 (+1) 
                 (12, 1) * 
                 (8, 4) * 
                 (5, 2) * 
                 (10, 2) * 
               
               
                   
                   
               
               
                   
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0062]    7. For the capacity of each of the other wires except for the chosen feasible wires being zero, end the steps of finding the feasible wire. All the feasible wires are selected as shown in Table 7 and  FIG. 2 , where the connection (7,7) represents the wire between the source s 1  and the sink t 1 , the connection (7,3) represents the wire between the source s 2  and the sink t 4 , the connection (12,1) represents the wire between the source s 3  and the sink t 1 , the connection (8,4) represents the wire between the source s 3  and the sink t 2 , the connection (5,2) represents the wire between the source s 3  and the sink t 3 , and the connection (10,2) represents the wire between the source s 3  and the sink t 4 . 
         [0063]    Link all the feasible wires with each other to construct a feasible wiring topology. Wherein a current density of each feasible wire is smaller than or equal to the maximum tolerable current density J max , so the current flows through each feasible wire for assuredly avoiding electromigration. 
         [0000]    
       
         
               
             
               
               
               
               
               
             
           
               
                 TABLE 7 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the step 7 . . . 
               
             
          
           
               
                 S/T 
                 t 1 (0) 
                 t 2 (0) 
                 t 3 (0) 
                 t 4 (0) 
               
               
                   
               
               
                 s 1 (0) 
                 (7 , 7)* 
                 (13, 0) 
                 (18, 0) 
                 (13, 0) 
               
               
                 s 2 (0) 
                 (7, 0) 
                 (11, 0) 
                 (6, 0) 
                 (7, 3) * 
               
               
                 s 3 (0) 
                 (12, 1) * 
                 (8, 4) * 
                 (5, 2) * 
                 (10, 2) * 
               
               
                   
               
               
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0064]    Step 2: create a flow network as shown in  FIG. 3  according to the feasible wiring topology, which includes the length, the source current, the sink current and the capacity of each feasible wire between the source and the sink. 
         [0065]    Each source current and each sink current are represented by the vertexes. (l i,j , f i,j , c i,j ) represents a directed edge (s i , t j ) from s i  to t j  for each pair of the source and the sink, where l i,j  represents the length of the wire between the source s i  and the sink t j , f i,j  represents the effective current from the source s i  to the sink t j , c i,j  represents the capacity, and the capacity is smaller than or equal to the effective current f i,j , c i,j =min(f si , f tj ). In addition, two dummy vertices, representing the super source s s  and the super sink t t , are added. One edge from the super source s s  to each distinct source s i  is the total flow associated with (0, f si , f si ), while one edge from each distinct sink t j  to the super sink t t  is the total flow current associated with (0, f tj , f tj ). In addition, one edge (s s , t t ) is also added associated with (0, f ss , f ss )=(0,19,19), where f ss  is the total flow from the super source to the super sink. Wherein the solid edge between the source s i  and the sink t j  represents the feasible wire, and the dashed edge represents the other wires. 
         [0066]    Step 3: execute an algorithm to iteratively check if a negative cycle existing in the flow network. Wherein said algorithm is a negative cycle detection algorithm. 
         [0067]    Firstly, create a residual graph based on said flow network as shown in  FIG. 4 . Define (l′ i,j , f′ i,j , c′ i,j ) as the residual state of the residual length, the residual flow, and the residual capacity. For each edge (s i , t j ) between source s i  and sink t j  with the flow f i,j  and the wirelength l i,j  in the flow network, two directional edges are constructed in the corresponding residual graph as follows. 
         [0068]    1. A forward edge (s i , t j ) has a residual wirelength l′ i,j =+l i,j  and a residual capacity c′ i,j =c i,j −f i,j , 0≦f′ i,j ≦c i,j −f i,j . 
         [0069]    2. A backward edge (t j , s i ) has a residual wirelength l′ i,j =−l i,j  and a residual capacity c′ i,j =−f i,j , −f i,j ≦f′ i,j ≦0. 
         [0070]    Wherein the wirelength and the capacity thereof, represented by the positive signs “+”, are on the forward edge and the residual flow are provided by the source; the wirelength and the capacity thereof, represented by the negative signs “−”, are on the backward edge and the residual flow are received by the sink. 
         [0071]    Secondly, check if the negative cycle existing in the residual graph. A negative cycle C N ={s i , t j , . . . , s i } is a cycle that starts and ends at the same source and has a negative sum of wirelength L C  on its constituent edges. As shown in  FIG. 5 , the solid edges represents the negative cycle of the residual graph. The negative cycle C N ={s 1 , t 1 , s 2 , t 2 , s 1 } is a cycle that starts from the source s 1  to the sink t 1 , then to the source s 2  and the sink t 1 , and ends at the source s 1 . The negative sum of wirelength L C  is 7+(−12)+10+(−7)=−2. 
         [0072]    Finally, judge if the negative sum of wirelength L C  is zero. If the negative sum of wirelength L C  is zero, the negative exists in the residual graph and go to Step 4; else if, the negative dose not exist in the residual graph, and the feasible wiring topology is defined as an optimal wiring topology for effectively saving the routing sources and go to Step 5. 
         [0073]    Step 4: remove the negative cycle if existing in the flow network. Refer to  FIG. 6  for a schematic view of the optimal flow network, which showing the flow network removed the negative cycle, obtained from  FIG. 3 . The steps of removing the negative cycle are described as below with Table 8. 
         [0074]    Firstly, one unit of the effective current flowing from the source s 3  to the sink t 1  is changed to be injected from the source s 2  along the direction of the negative cycle, so the capacity of the feasible wire between the source s 2  and the sink t 4  is varied to be 2 unit and the capacity of the feasible wire between the source s 3  and the sink t 4  is varied to be 3 unit. Secondly, an optimal wiring topology is obtained on the chip set  100  as shown in  FIG. 7 . If the width of one of the feasible wires in the optimal wiring topology is smaller than the minimal wiring length w min , the width of said wire is modified to be the minimal wiring length w min ; if the width of said wire is lager than the maximal wiring length w max , said wire is altered by multiple wires so that the width of said wire is modified to be the suitable width in accordance with the minimal wiring length w min  and the maximal wiring length w max . 
         [0000]    
       
         
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 8 
               
             
             
               
                   
               
               
                 The length and the capacity of the wire in the optimal 
               
               
                 wiring topology. 
               
             
          
           
               
                   
                 S/T 
                 t 1 (−8) 
                 t 2 (−4) 
                 t 3 (−2) 
                 t 4 (−5) 
               
               
                   
                   
               
               
                   
                 s 1 (+7) 
                 (7, 7) * 
                 (13, 0) 
                 (18, 0) 
                 (13, 0) 
               
               
                   
                 s 2 (+3) 
                 (7, 1) * 
                 (11, 0) 
                 (6, 0) 
                 (7, 2) * 
               
               
                   
                 s 3 (+9) 
                 (12, 0) 
                 (8, 4) * 
                 (5, 2) * 
                 (10, 3) * 
               
               
                   
                   
               
               
                   
                 * (the length of the feasible wire, the capacity of the feasibke wire) 
               
             
          
         
       
     
         [0075]    Step 5: finally, replace the feasible wire with a ladder-type wire by one end of the feasible wire connected by a horizontal wire and another end of the feasible wire connected by a vertical wire as shown in  FIG. 8 . In other words, the optimal wiring topology is conversed by rectilinearization to form an optimal rectilinear routing as shown in  FIG. 9 . Wherein the solid line represents the wire and the number of the arrow near the solid line represents the effective current of the wire. 
         [0076]    In an preferred embodiment, a plurality of obstacles O are disposed on the chip set  100  as shown in  FIG. 10 . The feasible wires between the source S={s 1 , s 2 , s 3 } and the sink T={t 1 , t 2 , t 3 , t 4 } are selected with considering the obstacles. However, the wire is straightly connected between the source and the sink so that the wirelength is added by the obstacle. The length of the wire bypassing the obstacle is added a routing length, where the routing length is a difference between the length of the wire bypassing the obstacle and the length of said wire straightly connecting the source and the sink. Calculate the length added the routing length up to obtain all the feasible wire. The length of the feasible wire between the source s 1  and the sink t 1  is 9 unit and the capacity thereof is 7 unit. The length of the feasible wire between the source s 2  and the sink t 3  is 6 unit and the capacity thereof is 2 unit. The length of the feasible wire between the source s 2  and the sink t 4  is 7 unit and the capacity thereof is 3 unit. The length of the feasible wire between the source s 3  and the sink t 2  is 10 unit and the capacity thereof is 4 unit. The length of the feasible wire between the source s 3  and the sink t 4  is 10 unit and the capacity thereof is 5 unit. 
         [0077]    Link all the feasible wires with each other to construct a feasible wiring topology. Finally, the optimal wiring topology is conversed by rectilinearization to form an optimal rectilinear routing as shown in  FIG. 10A . 
         [0078]    In an preferred embodiment, the chip set  101  has at least three routing layers  101   a ,  101   b  and  101   c  stacked as shown in  FIG. 11 . The length of the wire passing those routing layers has a minimal distance between the routing layers with considering the routing layers  101   a ,  101   b  and  101   c . The feasible wires between the source p 1 (x 1 , y 1 , z 1 ) and the sink p 2 (x 2 , y 2 , z 2 ) are selected to construct a feasible wiring topology. Finally, the optimal wiring topology is conversed by rectilinearization to form an optimal rectilinear routing as shown in  FIG. 11A   
         [0079]    Above all, the present invention is utilized after the routing stage to apply for local modification for avoiding electromigration in the fabrication method of integrate circuit. Therefore, the present invention is utilized to design an optimal wiring topology on the chip set before the routing stage for decreasing the routing resources. 
         [0080]    The present invention is utilized by the applicable products such as the analog design, the mixed signal design and the reliability-driven design automation tool, and the applicable industries such as IC design house, IC design service company, IC design tool vendor and IC design foundry. 
         [0081]    The foregoing description of the preferred embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form or to exemplary embodiments disclosed. Accordingly, the foregoing description should be regarded as illustrative rather than restrictive. Obviously, many modifications and variations will be apparent to practitioners skilled in this art. The embodiments are chosen and described in order to best explain the principles of the invention and its best mode practical application, thereby to enable persons skilled in the art to understand the invention for various embodiments and with various modifications as are suited to the particular use or implementation contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents in which all terms are meant in their broadest reasonable sense unless otherwise indicated. Therefore, the term “the invention”, “the present invention” or the like is not necessary limited the claim scope to a specific embodiment, and the reference to particularly preferred exemplary embodiments of the invention does not imply a limitation on the invention, and no such limitation is to be inferred. The invention is limited only by the spirit and scope of the appended claims. The abstract of the disclosure is provided to comply with the rules requiring an abstract, which will allow a searcher to quickly ascertain the subject matter of the technical disclosure of any patent issued from this disclosure. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. Any advantages and benefits described may not apply to all embodiments of the invention. It should be appreciated that variations may be made in the embodiments described by persons skilled in the art without departing from the scope of the present invention as defined by the following claims. Moreover, no element and component in the present disclosure is intended to be dedicated to the public regardless of whether the element or component is explicitly recited in the following claims.