CN111339727B - Through-hole pillar-aware layer divider with minimized latency and overflow in advanced process - Google Patents

Abstract

The present invention relates to a through-hole column sensing layer distributor that minimizes delay and overflow under an advanced manufacturing process. The through-hole column sensing layer distributor designs a layer distribution scheme according to the following steps: S1) generating an initial solution for subsequent stages; Apply the multi-angle congestion relaxation strategy to evaluate the congestion and then adjust the layer allocation scheme; S2) On the basis of the initial solution, apply the negotiation-based idea to guide the layer allocation; S3) Use the wire network healing algorithm to optimize the maximum delay of the current layer allocation scheme; S4) Sort all the nets according to the delay size and then redistribute them; prioritize the nets with large delays, that is, the timing-critical nets, and use the through-hole column optimization method for the front timing-critical nets, combining through-hole columns and non-default nets ruled lines to further reduce latency, resulting in the final layer allocation scheme. The via post-aware layer distributor can optimize delay and overflow under the premise of considering via congestion, line congestion and coupling effects.

Description

Through-hole pillar-aware layer distributor with minimized latency and overflow in advanced process

technical field

The invention belongs to the technical field of integrated circuit computer-aided design, and in particular relates to a through-hole column sensing layer distributor that minimizes time delay and overflow under an advanced manufacturing process.

Background technique

As one of the important factors affecting chip performance, interconnect latency is an important optimization objective in layer allocation. The network delay mainly includes the line delay and the via delay. However, with the expansion of the circuit scale, the wire resistance and the via resistance increase significantly, which directly leads to the increase of the wire net delay. In advanced processes, the upper layer has a larger line width and line spacing than the lower layer, so the resistance of the upper layer line is smaller. Therefore, assigning timing-critical line segments to the upper layer is beneficial to reduce the delay. However, this method alone is not enough to greatly reduce the delay, so it is necessary to introduce new technologies in the advanced process to further optimize the delay.

As an important technology in advanced manufacturing processes, via pillars can effectively reduce via resistance. Via posts contain a number of conventional vias and come in a variety of forms. Figure 1 shows a type of via post structure. In order to distinguish the effects of via posts and conventional vias on routing resources, the size of the vias and the capacity of the routing cells should be considered. In addition, considering the size of the via and the capacity of the wiring unit is also beneficial to reduce the mismatch between the overall wiring and the detailed wiring.

As another important technology under the advanced process, the application of non-default ruled lines is an important way to reduce line resistance. There are two types of non-default rule lines: parallel lines and wide lines. In the lower layer of the wiring area in the advanced process, due to the limitation of the manufacturing process, the non-default regular lines can only be realized in the form of parallel lines. In other routing layers, non-default regular lines are implemented as wide lines. The line width of a wide line is larger than the default line width and is given in advance.

In addition, there is an upper limit on the routing resources of each routing layer. If too many wires are allocated to upper layers, or if via posts, non-default regular wires are used excessively, routability will deteriorate and wire density will increase. Due to the coupling effect, increased line density will lead to increased coupling capacitance, which in turn will lead to increased latency, which has a negative impact on the timing characteristics of the circuit. Therefore, routing resources, via posts, and non-default ruled lines should be used appropriately.

SUMMARY OF THE INVENTION

The object of the present invention is to provide a via-pillar sensing layer distributor that minimizes delay and overflow under an advanced manufacturing process, and the via-pillar sensing layer distributor can consider via congestion, line congestion and coupling effects under the premise of Optimized for latency and overflow.

In order to achieve the above object, the technical solution adopted in the present invention is: a through-hole column sensing layer distributor that minimizes time delay and overflow under an advanced manufacturing process, and the through-hole column sensing layer distributor performs the layer distribution scheme according to the following steps. Fully automatic design:

S1) Generate an initial solution for subsequent stages; apply a multi-angle congestion relaxation strategy to evaluate congestion and then adjust the layer allocation scheme to reduce overflow while ensuring good timing characteristics;

S2) On the basis of the initial solution, apply the guidance layer assignment based on the negotiation idea;

S3) Use the line network healing algorithm to optimize the maximum delay of the current layer allocation scheme; in this process, non-default rule lines can be used; and, using the segment distinction method, assign values to segments according to the distance between the segment and the signal source to distinguish the time sequence Timing critical segments and timing non-critical segments in critical nets;

S4) Sort and redistribute all the nets according to the size of the delay; give priority to the nets with a large delay, that is, the timing-critical nets. Non-default rule lines to further reduce latency, resulting in the final layer allocation scheme.

Further, in the step S1, the specific method of applying the multi-angle congestion relaxation strategy to evaluate the congestion is:

The multi-angle congestion relaxation strategy considers the relationship between objects occupying routing resources and routing regions that provide routing resources from multiple perspectives. Routing resources can be occupied by lines, vias and obstacles. Considering these factors, the congestion cost function is defined as follows:

cong(s)=cong(o)+cong(v)+cong(w)

where s represents a line segment; o, v, and w represent obstacles, vias, and lines, respectively; segment congestion cost cong(s) includes obstacle congestion cost cong(o), via congestion cost cong(v), and line Congestion cost cong(w); if s is a through hole, v means the through hole and cong(w) is 0; if s is a line segment, then w means the line segment and cong(v) is 0; e and g respectively Represents the edge and wiring unit that the line segment s passes through; tc(e) and tc(g) represent the edge capacity of e and the area capacity of g respectively; dc(e _o ), dc(e _v ) and dc(e _w ) denote the number of tracks in e occupied by obstacles, vias, and lines, respectively; dc(g _o ), dc(g _v ), and dc(g _w ) denote the areas of g occupied by obstacles, vias, and lines, respectively ;of(e _w ) is the additional congestion cost when line overflow occurs; h _e is the historical cost, which is calculated as follows:

和

分别表示e的第i次历史代价和第i+1次历史代价；ρ是定义的参数。in

and

Represent the i-th historical cost and the i+1-th historical cost of e, respectively; ρ is a defined parameter.

Further, in the step S2, the specific method of applying layer allocation based on the negotiation idea is as follows: if the currently allocated segment is allocated to an edge with no remaining available number of wiring tracks, the cost of using the edge is increased to reduce the cost of using the edge. Directs subsequently allocated segments to avoid using this edge.

Further, in the step S3, the wire net healing algorithm guides the timing non-critical wire net to release the wiring resources shared with the timing critical wire net, so as to provide more space and flexibility for the redistribution of the timing critical wire net, and then Decrease maximum delay.

Further, in the step S4, the through-hole column optimization method is used to combine the through-hole column and the non-default regular line, and when combining the through-hole column and the non-default regular line, the type of the through-hole column and the type of the line are considered, The type of via post depends on the type of wire that the via post is connected to. Since parallel lines occupy two routing tracks and wide lines occupy three routing traces, the setting method of via post type is as follows: one connects parallel lines and the default rule A via post for a line is a 2×1 type; a via post that connects two pairs of parallel lines is a 2×2 type; a via post that connects a wide line and the default regular line is a 3×1 type; The via post of the parallel line is 3×2 type; a via post connecting two wide lines is 3×3 type; if a via post is connected to the default regular line, the via post is converted into a regular via; If a via post is not connected to a line on a layer, the type of via post depends on the default rule line for that layer; for via segments directly connected to the signal source of timing-critical nets, use 2× 2 types of through hole posts.

Compared with the prior art, the present invention has the following beneficial effects: it proposes a via post sensing layer distributor that minimizes delay and overflow under an advanced process considering via size and coupling effect, the via post sensing The layer allocator takes into account via congestion, line congestion and coupling effects through a congestion relaxation strategy that reduces overflow, a net healing algorithm that optimizes maximum delay, and a via pillar optimization method that effectively combines via pillars and non-default regular lines. Under the premise of optimizing delay and overflow, it has strong practicability and broad application prospects.

Description of drawings

FIG. 1 is a schematic diagram of a conventional through-hole column structure.

FIG. 2 is a comparison diagram of a non-default ruled line and a default ruled line in an embodiment of the present invention.

FIG. 3 is a schematic diagram of a conventional through hole model in an embodiment of the present invention.

FIG. 4 is a schematic diagram of wiring resources occupied by through holes, lines and obstacles in an embodiment of the present invention.

FIG. 5 is a schematic diagram of various types of through-hole pillars in an embodiment of the present invention.

FIG. 6 is a schematic diagram of a layer allocation scheme optimized by adopting a wire net healing algorithm in an embodiment of the present invention.

FIG. 7 is an implementation flow chart of the layer allocation scheme design performed by the through-hole column sensing layer allocator according to an embodiment of the present invention.

Detailed ways

The present invention will be further described in detail below with reference to the accompanying drawings and specific embodiments.

Non-default rule lines:

Non-default rule lines have line weights that differ from the default line weights. Specifically, the default line widths are different for different wiring layers. The default line weight of the upper layer is usually larger than the default line weight of the lower layer. The comparison between the non-default rule line and the default rule line is shown in Figure 2. In Figure 2(a), two pins are connected using parallel lines and default rule lines, respectively, where the default rule lines occupy one routing track and the parallel lines occupy two routing tracks. In Figure 2(b), two pins are connected using a wide line and a default rule line, where the default rule line occupies one routing track and the wide line occupies three routing tracks. Compared with the default rule line, although the non-default rule line occupies more routing resources, the non-default rule line can reduce the line resistance and optimize the delay.

Through hole post:

A via post contains multiple regular vias. The horizontal projection of a regular via is a rectangle. The length and width of the rectangle are determined by the line width and spacing of two lines on different layers connected to the via, as shown in FIG. 3 . If a regular via has no line connected to the via on a certain layer, the length or width of the horizontal projection of the regular via depends on the default line width and spacing of the layer.

Compared to conventional vias, via posts have lower resistance and higher capacitance. Therefore, the rational application of through-hole pillars can reduce the delay, otherwise it may increase the delay. For example, for a wire mesh, using the through-hole column technology only for the downstream through-hole section will lead to an increase in the delay of each upstream section, and eventually lead to an increase in the delay of the wire mesh. Additionally, via posts may take up more routing resources than conventional vias, which can worsen circuit congestion. Therefore, via posts should be used reasonably to ensure good routability while optimizing latency.

Cabling Congestion:

In the overall routing, the routing area includes routing units and edges. In order to reduce the mismatch between the overall wiring and the detailed wiring, the present invention not only considers the edge capacity, line width and spacing, but also considers the area of the wiring unit and the size of the through hole. Specifically, the area of a wiring unit is determined by the length and width of the wiring unit, and the capacity of a side is determined by the number of tracks included in the side. As shown in Figure 4, the routing unit area and routing tracks can be occupied by vias and wires of the wire mesh, as well as by obstacles. The uppermost track in Figure 4 cannot be used by other nets because it is occupied by through holes, and is called an unavailable track.

If the area occupancy of the wiring unit by the wire net and the obstacle is larger than the area capacity of the wiring unit, the area of the wiring unit will overflow. Edge overflow occurs when nets and obstacles occupy a track that is greater than the track capacity for that edge. The calculation of routing unit g overflow of(g) and edge e overflow of(e) is as follows:

where u(g) and c(g) represent the current area usage and capacity of g, respectively. u(e) and c(e) denote the current track usage and capacity of e, respectively. The area overflow and edge overflow of the routing unit can be attributed to the occupation of routing resources by vias and the occupation of routing resources by wires.

The present invention provides a through-hole column sensing layer distributor that minimizes delay and overflow under an advanced manufacturing process considering through-hole size and coupling effect. As shown in FIG. 7 , the through-hole column sensing layer distributor is as follows: Perform fully automatic design of layer assignments:

S1) Generate an initial solution for subsequent stages; apply a multi-angle congestion relaxation strategy to evaluate congestion and then adjust the layer allocation scheme to reduce overflow while ensuring good timing characteristics.

Multi-angle congestion relaxation strategy:

The present invention adopts a multi-angle congestion relaxation strategy to optimize congestion and improve routability. In order to reduce the degree of mismatch between overall routing and detailed routing, the multi-angle congestion relaxation strategy considers the interrelationship between objects occupying routing resources and routing areas providing routing resources from multiple perspectives. Specifically, the routing resources of the routing area include the area of the edge track and the routing unit, and these routing resources can be occupied by lines, vias and obstacles. Taking these factors into consideration, the congestion cost function is defined as follows:

cong(s)=cong(o)+cong(v)+cong(w)

where s represents a line segment; o, v, and w represent obstacles, vias, and lines, respectively; segment congestion cost cong(s) includes obstacle congestion cost cong(o), via congestion cost cong(v), and line Congestion cost cong(w); if s is a through hole, v means the through hole and cong(w) is 0; if s is a line segment, then w means the line segment and cong(v) is 0; e and g respectively Represents the edge and wiring unit that the line segment s passes through; tc(e) and tc(g) represent the edge capacity of e and the area capacity of g respectively; dc(e _o ), dc(e _v ) and dc(e _w ) denote the number of tracks in e occupied by obstacles, vias, and lines, respectively; dc(g _o ), dc(g _v ), and dc(g _w ) denote the areas of g occupied by obstacles, vias, and lines, respectively ;of(e _w ) is the additional congestion cost when line overflow occurs; h _e is the historical cost, which is calculated as follows:

和

分别表示e的第i次历史代价和第i+1次历史代价；ρ是用户定义的参数，在本发明中设置为0.05。in

and

respectively represent the i-th historical cost and the i+1-th historical cost of e; ρ is a user-defined parameter, which is set to 0.05 in the present invention.

The multi-angle congestion relaxation strategy can optimize the congestion in the routing area to reduce the overflow caused by lines and vias, while ensuring good timing characteristics. This strategy quantifies the pros and cons of each alternative as a cost by conducting a more detailed analysis of the alternatives. If the scheme is better, the corresponding cost of the scheme is low, and if the scheme is inferior, the corresponding cost of the scheme is high. Finally, the low-cost scheme is selected to guide the layer assignment.

S2) On the basis of the initial solution, apply the negotiation-based idea to guide layer assignment. The specific method is as follows: if the currently allocated segment is allocated to an edge with no remaining available routing tracks, the cost of using the edge is increased to guide subsequent allocated segments to avoid using the edge.

S3) Use the wire net healing algorithm to optimize the maximum delay of the current layer allocation scheme; in this process, non-default rule lines can be used; and, in order to distinguish the timing critical segment and the timing non-critical segment in the timing critical wire net, use the segment Distinguishing method, assign a value to the segment according to the distance between the segment and the signal source. Segments close to the signal source are timing critical segments and are assigned larger values; segments farther from the signal source are timing non-critical segments and are assigned smaller values. In this way, the timing critical segment and the timing non-critical segment in the timing critical net are distinguished.

Wire net healing algorithm:

The maximum delay is an important factor affecting the performance of the chip. Therefore, the present invention proposes a wire net healing algorithm to reduce the maximum delay. The net healing algorithm guides the timing non-critical nets to release the routing resources shared with the timing critical nets, provides more space and flexibility for the redistribution of the timing critical nets, and reduces the maximum delay.

Figure 6 gives an example for explaining the wire mesh healing algorithm. n ₁ is a timing non-critical net, and n ₂ is the maximum delay net. The layer assignment order is n ₁ , n ₂ . Fig. 6(a) is a 2D wiring scheme of n ₁ and n _2. It can be seen from Fig. 6(a) that n ₁ and n ₂ compete with each other for routing resources. In the 3D wiring area, the capacity of each side is 1, and the line resistance of the upper layer is smaller than that of the lower layer. In order to reduce the maximum delay, the maximum delay net should have priority to use routing resources. The original layer assignment scheme for n ₁ and n ₂ is shown in Fig. 6(b) before using the wire mesh cure algorithm. Figure 6(c) shows the 3D wiring scheme of n ₁ and n ₂ when using the net healing algorithm. Under the guidance of the net healing algorithm, the layer allocation scheme of n ₂ is adjusted to the layer allocation scheme shown in Figure 6 (c). In order to ensure good routability, the layer allocation scheme of n ₁ is adjusted to the layer allocation scheme shown in Fig. 6(d). Figure 6(d) presents the final layer assignment scheme for n ₁ and n ₂ after using the wire mesh healing algorithm.

S4) Sort and redistribute all the nets according to the size of the delay; preferentially process the nets with a large delay, that is, the critical timing nets, and use the key nets in the front (the first 5% in this embodiment) at the same time. The via pillar optimization method combines via pillars and non-default ruled lines to further reduce latency, resulting in a final layer assignment scheme with good timing characteristics and routability.

Through-hole pillar optimization method:

In order to improve the quality of the layer allocation scheme, the present invention reasonably uses via posts to reduce the net delay without causing congestion deterioration. Specifically, in order to fully consider the wire net delay, congestion, wire type and timing critical segment, the via post optimization method of the present invention reasonably combines via posts and non-default regular lines.

Due to the large number of nets involved in layer assignment, the use of via posts for each net is not only unnecessary but also causes routability degradation. The delay of the timing critical net is one of the important factors affecting the performance of the chip, and the wire length of the timing critical net is usually very large. Therefore, if the via post is used downstream of the timing critical net, the downstream capacitance of each upstream segment of the timing critical net will increase, which in turn leads to increased net delay. Therefore, via pillars should be used for timing critical sections in timing critical nets close to signal sources to effectively reduce latency.

In order to avoid congestion deterioration, the present invention fully considers the type of the via post and the type of the line when combining the via post and the non-default ruled line, and the type of the via post depends on the type of the wire connected to the via post. Specifically, since parallel lines occupy two routing tracks and wide lines occupy three routing tracks, the via post types are set as follows:

As shown in Figure 5(a), a via post connecting parallel lines and default rule lines is 2×1 type; as shown in Figure 5(b), a via post connecting two pairs of parallel lines is 2×2 type; as shown in Figure 5(c), a via post connecting a wide line and a default regular line is a 3×1 type; as shown in Figure 5(d), a via post connecting a wide line and a parallel line is 3×2 type. As shown in Figure 5(e), a via post connecting two wide lines is a 3×3 type; in addition, if a via post is connected to the default regular line, the via post is transformed into a via post as shown in Figure 3 regular vias; if a via post is not connected to a line on a layer, the type of via post depends on the default rule line for that layer; in addition, considering the direct connection to the signal source of the timing-critical net The downstream capacitance of the via segment is large, and in order to properly coordinate timing and routability, the present invention uses a 2×2 type via post for this via segment.

The above are the preferred embodiments of the present invention, all changes made according to the technical solutions of the present invention, when the resulting functional effects do not exceed the scope of the technical solutions of the present invention, belong to the protection scope of the present invention.

Claims (4)

1. A through hole column sensing layer distribution method for minimizing time delay and overflow under an advanced process is characterized in that the through hole column sensing layer distribution method carries out full-automatic design of a layer distribution scheme according to the following steps:

s1) generating an initial solution for the subsequent stage; a multi-angle congestion relaxation strategy is applied to evaluate congestion so as to adjust a layer distribution scheme, and overflow is reduced while good time sequence characteristics are guaranteed;

s2), on the basis of the initial solution, applying negotiation-based idea guiding layer distribution;

s3) optimizing the maximum time delay of the current layer distribution scheme by adopting a net healing algorithm; in this process, a non-default ruled line is used; and a segment distinguishing method is adopted, and the segments are assigned with values according to the distance between the segments and the signal source so as to distinguish a time sequence key segment and a time sequence non-key segment in the time sequence key line network;

s4) sorting all the nets according to the time delay and then redistributing the nets; the time delay large-time-delay line network is processed preferentially, meanwhile, a through hole column optimization method is used for the previous time sequence key line network, and the time delay is further reduced by combining the through hole column and the non-default regular line, so that a final layer distribution scheme is generated;

in step S1, the specific method for evaluating congestion by applying the multi-angle congestion relaxation strategy is as follows:

the multi-angle congestion relaxation strategy considers the correlation between an object occupying wiring resources and a wiring area providing the wiring resources from multiple angles, and specifically comprises the following steps: the routing resources of the routing area comprise side tracks and the area of routing units, the routing resources can be occupied by lines, through holes and obstacles, and the factors are comprehensively considered, and a congestion cost function is defined as follows:

cong(s)＝cong(o)+cong(v)+cong(w)

whereins represents a segment of a line; o, v and w represent obstacles, vias and lines, respectively; segment congestion costs cong(s) include barrier congestion costs cong (o), via congestion costs cong (v), and line congestion costs cong (w); if s is a via, v represents the via and conv (w) is 0; if s is a segment, w represents the segment and cong (v) is 0; e and g respectively represent the edge and the wiring unit through which the line segment s passes; tc (e) and tc (g) respectively represent the side capacity of e and the area capacity of g; dc (e)_o)、dc(e_v) And dc (e)_w) Respectively representing the number of tracks in e occupied by the barrier, via and line; dc (g)_o)、dc(g_v) And dc (g)_w) Respectively representing the area of g occupied by the barrier, via and line; of (e)_w) Is an additional congestion penalty when a line overflow occurs; h is_eIs a historical cost, and the calculation mode is as follows:

wherein

And

respectively representing the ith history cost and the (i + 1) th history cost of e; ρ is a defined parameter.

2. The method as claimed in claim 1, wherein the step S2 is implemented by using a specific method for guiding layer allocation based on negotiation idea as follows: if a currently allocated segment is allocated to an edge with no remaining available routing tracks, the cost of using that edge is increased to direct subsequently allocated segments to avoid using that edge.

3. The method as claimed in claim 1, wherein in step S3, the net healing algorithm directs the timing non-critical nets to free the routing resources shared with the timing critical nets, so as to provide more space and flexibility for re-allocating the timing critical nets and further reduce the maximum delay.

4. The method of claim 1, wherein in step S4, via pillars and non-default regular lines are combined by using a via pillar optimization method, and when combining via pillars and non-default regular lines, the types of via pillars and the types of lines are considered, the types of via pillars depend on the type of lines connected to the via pillars, and since parallel lines occupy two routing tracks and wide lines occupy three routing tracks, the via pillar types are set as follows: one via post connecting the parallel lines and the default ruled lines is of the 2 x 1 type; a via post connecting the two pairs of parallel lines is of the 2 x 2 type; a via post connecting the wide line and the default ruled line is of type 3 x 1; a via post connecting the wide lines and the parallel lines is of the 3 x 2 type; a via post connecting the two wide lines is of the 3 x 3 type; if one through hole pillar is connected with the default rule line, the through hole pillar is changed into a conventional through hole; if a via post is not connected to a line on a layer, the type of the via post depends on the default ruled line of the layer; for the via segment directly connected to the signal source of the timing critical net, a 2 × 2 type via post is used.

Images