1. Introduction
As the technology node enters into the nanometer era, the concept of yield-driven design becomes increasingly important for modern chip designs[1-7]. Any via failure in an interconnect caused by electromigration, thermal stress and random defects has become one of the most important difficulties[8-11]. Without violating any design for manufacturability (DFM) design rules and to improve via reliability, a redundant via (RV) provides an alternative path. Therefore, redundant via insertion has become one of the well-known and highly recommended methods to improve the via reliability.
In general, redundant via insertion is performed in a post-routing stage[12-26]. The first work of the RV insertion in the detailed maze routing was proposed by Xu et al.[14]. Lee et al.[15] formulated the RV insertion problem as a maximum independent set (MIS) problem in the post-routing stage; however, the MIS-based method is an NP-complete problem, it would take much execution time to complete it. For a higher insertion rate, Chen et al.[16] formulated the RV insertion problem as one or more bipartite matching problems, but the optimality can be guaranteed only when the design is grid-based and involves up to three routing layers. The other method was proposed by Chang et al.[17], who introduced a novel via pattern, rectangle via (REV) for dead vias, which has the same function as the traditional double via (DV) and has lower resistance than that of a single via (SV), but they have not presented a new insertion method. The now available methods are proposed based on the assumption that the timing delay of each net does not alter before and after RV insertion. However, inserting the RV may change the original circuit design. So the yield and circuit function might be altered during the RV insertion[14-20]. Luo et al.[25] considered the timing issue, but the insertion algorithm cannot guarantee whether the circuit timing is degraded or not after the insertion. Pan et al.[26] and Yan et al.[27] developed an insertion approach considering the timing constraints. However, the objects were only confined to DV rather than the varying length RV.
In this paper, considering the timing constraints, a new RV insertion method is proposed to solve the RV insertion task from the global perspective. Moreover, we deduce the process to compute the distance between a RV and the corresponding single via, we also put forward an improved redundant via type, which is defined as long length via (LLV). Then, a new weighted model to determine the insertion order is proposed. According to the technology requirements, the DV structure has priority over REV's and LLV's, while the REV structure has priority over LLV's. The experimental results show that our proposed insertion approach not only can effectively insert the redundant via, but also properly control the circuit timing delays to guarantee the demands in circuit function and circuit yield.
2. Timing driven redundant via insertion method
In this section, the problem of the timing delays for RV insertion is demonstrated. Then we introduce the process to compute varying lengths for RV insertion under the timing constraints. We conclude this part with the RV insertion method.
2.1 Timing constraints model and process to compute varying length
Redundant via insertion is a highly recommended method to improve via reliability. However, the RV occupies more routing resources than a normal SV does for grid-based routing methods; redundant via insertion might change the circuit timing delay and then alter the circuit function. It is necessary to guarantee the timing delay between nets during redundant via insertion for DFM requirement.
Figure 1 shows the layout patterns and required resources of SV, DV, REV and LLV. Here, it is assumed that the width of the via and minimum spacing between two nets are
According to the connection between nets and the single via, the structures of redundant vias can be categarized into two different shapes. The L-shape, (this structure looks like the letter 'L') in which a single via only connects two net segments. The T-shape, (this structure looks like the letter 'T') in which a single via connects more than two net segments.
The methods to calculate the timing delay for different RV types are different; the particular models for different RV types are shown in Ref. [26]. Considering the limit of the size of paper, we introduce the detailed computing processes in the following typical model, which can effectively give expression to the calculation process. In order to accurately calculate the Elmore timing delay, we transform the redundant via to the equivalent acyclic RC circuits. Then, we can obtain the redundant via structure under the timing constraints and its insertion site by analyzing the change of timing delay. The redundant via insertion should meet the timing delay conditions (
As shown in Fig. 2, we can easily find that the via provides the connection of nets between two adjacent metal layers and this template is on-track type Ⅰ in an L-shape RV. Assume that
τLon1=Rso[c1(L1−x)+(2cvLv+c1x+c2x)+c2L2+Csi]+r1(L1−x)[c1(L1−x)2+(2cvLv+c1x+c2x)+c2L2+Csi]+(r1x+rvLv)(r2x+rvLv)(r1x+rvLv)+(r2x+rvLv)×(cvLv+c1x2+c2x2+c2Lv+Csi)+r2L2(c2L22+csi). |
(1) |
The redundant via insertion should meet the timing conditions. The timing constraint is
τLon1⩽τLo. |
(2) |
By plugging
x21+(3cvLv2cw−rvLv2rw−L1+L22−Rsorw+Csi2cw)x1+(rvLvL22rw−cvLvL1cw−cvLvRsorwcw+rvLvCsi2rwcw)⩾0. |
(3) |
Moreover, by calculating the quadratic Eq. (3), the
x1∈(−∞,−B1−√B21−4C12]∪[−B1+√B21−4C12,+∞), |
(4) |
where
B1=3cvLv2cw−rvLv2rw−L1+L22−Rsorw+Csi2cw, |
(5) |
C1=rvLvL22rw−cvLvL1cw−cvLvRsorwcw+rvLvCsi2rwcw. |
(6) |
According to this model above, we can work out the other templates'
2.2 Redundant via insertion method
Based on the definition above, we can assign a weight
w=η(αA+βB+γC), |
(7) |
where
According to the technology requirements, the DV structure has priority over REV's and LLV's, and the REV structure has priority over LLV's. When this RV has a DV structure to the corresponding SV, the value of
Based on the weighted model above, we propose a modified timing constraint RV insertion method. The insertion steps are shown as follows.
Step 1. Analyze the timing delay and find the
Step 2. Choose a via
Step 3. Insert this RV
Step 4. Recalculate the
After finishing the steps above, we have completed the inserting process to all single vias that can be inserted by RV under critical area and timing constraints.
3. Experimental results
This method has been implemented in the C++ programming language on a dual core 2.1-GHz PC with 4-GB memory. Four tested circuits have been applied to test the via insertion in the proposed method. The four circuits are adder, subtracter, multipliers and divider, respectively, all of which are 4-bit. As shown in Table 1, the circuit scales are gradually increasing. The four layouts, which correspond to the circuits above, have been changed into the multi-layer plane figure and are of a Caltech intermediate form (CIF) file format. We can obtain the position of via and nets in the layout; the vias layer and corresponding two metal layers can be extracted by analyzing the plane figure. Then, we can implement the following experiments. Since on-track RVs costs less routing resource and have better electrical properties than off-track RV's, we choose
![]() |
We have classified experiments into three groups to illustrate the effectiveness of our method. The circuits' major and relevant information is listed in Table 1. In those tables, for each test circuit, "test circuit" represents the circuit name, and "single vias" indicates the number of single vias. "R. L." gives the number of routing layers. "Nets" shows the number of nets. "W. L. (mm)" shows the length of interlinked wires. "Ins. RV" shows the number of the new inserted vias. "
![]() |
As shown in Table 3, this experimental group shows the results by using the insertion method under the timing constraints. The insertion rate is 88.79%. In Table 4, we have completed the RV insertion with the proposed method in Ref. [26]. The total insertion rate is 85.38%, and the incremental yield is 0.049% to 1.979% compared to the original circuit. In Tables 2 and 3, it is easily found that the insertion rate and the yield have a lower rate, but it ensures the delay characteristic to satisfy the demand in circuit design. From Tables 3 and 4, we can see that our method can get a higher insertion rate and yield than in Ref. [26]. In Ref. [26], the insertion problem is solved by a timing-driven minimum weighted matching algorithm, but the objects were only confined to DV rather than the varying length RV and the insertion problem might fall into local optimum. It can be found that the presentation of varying length RV leads to increase the RV insertion rate compared to the existing methods, and the insertion method completes the RV insertion task from the global perspective, so it can increase the possibility of RV insertion and the timing-driven method can guarantee the circuit timing and function. Therefore, our method can improve the redundant via insertion rate and assure the circuit function simultaneously.
![]() |
![]() |
4. Conclusion
Redundant via (RV) insertion is highly recommended for improving the via reliability. At the same time, inserting a RV adjacent to a single via can alter circuit timing delay. In this paper, we consider the post-routing RV insertion problem under the timing constraints. Besides, we introduce a model to compute varying length and present an improved RV insertion method from the global perspective. The experimental results show that the proposed method can effectively insert the RV and, compared to the no constraints driven method, the proposed constraints driven method has a good control of the circuit timing delays to guarantee the demands in circuit function and circuit yield. Therefore, this paper has great significance in improving the via reliability. This model could be further applied to the other layout optimization process.