CN102194023B - Configuration device and method for preventing congestion - Google Patents

Abstract

The present invention is an anti-congestion configuration device and method for circuit layout. The anti-congestion configuration device includes an analysis module, a definition module and an expansion module. The analysis module is used for analyzing the winding congestion state of the circuit layout to generate analysis results. The defining module is used for defining a congested area and a shared area adjacent to the congested area in the circuit layout according to the analysis result. The electronic component density of the congested area is higher than that of the shared area. The expansion module is used to reconfigure the multiple electronic components in the congested area to the congested area and the shared area.

Description

Anti-congestion configuration device and method

technical field

The present invention is related to circuit layout, in particular, to an anti-congestion arrangement device and method for expanding and distributing the electronic components in the congested area in the circuit layout to the area with a lower density of electronic components nearby, so as to Reduce electronic component density in otherwise difficult-to-wire congested areas, making them wire-routable areas.

Background technique

With the continuous development of electronic technology, various electronic products are becoming thinner and smaller in size, but they have more and more functions. Therefore, a very large number of various electronic components must be arranged in a chip with a relatively small area to meet the actual needs of electronic products.

However, in some circuit layouts, because there are too many electronic components in a certain area, that is, the density of electronic components in this area is too high, it is difficult to perform routing between some electronic components in this area. Failed to pass the design rule checking (design rule checking), resulting in the circuit layout not working properly.

Please refer to FIG. 1A and FIG. 1B . FIG. 1A and FIG. 1B are schematic diagrams illustrating when the density of electronic components in the circuit layout is 75% in the prior art. As shown in FIG. 1A and FIG. 1B, it is obvious that since the electronic components 10 in the circuit layout 1 are not completely closely arranged together, that is, there are still many spaces available for winding between the electronic components 10. , so the circuit layout 1 does not have any congested areas that are difficult to route.

However, the situation obviously changes when the electronic component density of the circuit layout 1 becomes higher. Please refer to FIG. 1C and FIG. 1D . FIG. 1C and FIG. 1D are schematic diagrams illustrating when the density of electronic components in the circuit layout increases to 90% in the prior art. As shown in FIG. 1C and FIG. 1D , since many wiring spaces in the original circuit layout 1 of FIG. 1A have been filled by electronic components 10 ′, there are many congestion areas that are difficult to wire in the circuit layout 1 of FIG. 1C . As shown in FIG. 1D , the congestion status pointers V1 - V3 (at the arrows) represent the vertical congestion area in the circuit layout 1 .

Since the types and numbers of electronic components included in the circuit layout are increasing continuously with the development of technology and the demand of actual use, the congestion phenomenon in the circuit layout is bound to become more serious. However, the traditional solutions to the above problems may cause changes in the relative positional relationship between the electronic components in the circuit layout, so that the circuit layout cannot pass the time constraint, or part of the circuit layout needs to be sacrificed. space, resulting in an additional area penalty in the circuit layout.

Contents of the invention

The object of the present invention is to provide an anti-congestion configuration device and an anti-congestion configuration method, which can avoid additional area loss in circuit layout.

According to one aspect of the present invention, an anti-congestion configuration device is provided, and the anti-congestion configuration device is applied to a circuit layout. The anti-congestion configuration device includes an analysis module, a definition module and an expansion module. The analysis module is used for analyzing the state of winding congestion on the circuit layout to generate an analysis result. The defining module is used for defining a congestion area and a sharing area adjacent to the congestion area in the circuit layout according to the analysis result, wherein the density of electronic components in the congestion area is higher than that of the sharing area. The expansion module is used to reconfigure the multiple electronic components in the congested area to the congested area and the shared area.

Another aspect of the present invention is to provide an anti-congestion configuration method, which is applied in a circuit layout. First, the method performs a winding congestion state analysis on the circuit layout to generate an analysis result; then, the method defines a congestion area and a sharing area adjacent to the congestion area in the circuit layout according to the analysis result, wherein The density of electronic components in the congested area is higher than the density of electronic components in the shared area. Afterwards, the method reconfigures the plurality of electronic components in the congested area to the congested area and the shared area.

Compared with the prior art, the beneficial technical effect of the present invention is that the anti-congestion arrangement device and method of the present invention expand and distribute the electronic components originally only arranged in the congested area to the congested area and its vicinity with lower electronic components Density sharing area, so as to reduce the originally high density of electronic components in the congested area, so that the congested area can be changed from an area that is difficult to wire to an area that can be wound, and the density of electronic components in the congested area and the shared area becomes relatively average. More importantly, after being processed by the anti-congestion configuration device and method of the present invention, the relative positional relationship between all electronic components of the circuit layout remains unchanged, so that the circuit layout can still pass the time limit, and for the As far as the circuit layout is concerned, there will be no additional area loss in order to eliminate the congested area.

Description of drawings

The advantages and spirit of the present invention can be further understood through the following detailed description of the preferred embodiments of the present invention in conjunction with the accompanying drawings, wherein:

FIG. 1A and FIG. 1B are schematic diagrams illustrating a circuit layout in the prior art when the density of electronic components is 75%.

FIG. 1C and FIG. 1D are schematic diagrams illustrating a circuit layout in the prior art when the density of electronic components is 90%.

FIG. 2 is a functional block diagram illustrating an anti-congestion configuration device according to a first embodiment of the present invention.

FIG. 3A is a schematic diagram illustrating that the definition module defines a congested area and a shared area in a circuit layout according to an analysis result.

3B and FIGS. 4A-4C are schematic diagrams illustrating the movement of electronic components from the original position O to T in the circuit layout.

5A to 5C illustrate the processing method when the position of the electronic components after being moved through the expansion module is just located in the high electronic component density area.

6A and 6B are schematic diagrams illustrating that the expansion module only moves the combined elements in the circuit layout while the sequential elements remain fixed.

7A and 7B are schematic diagrams illustrating that the expansion module only moves one of the electronic component modules in the circuit layout.

FIG. 8 is a flowchart illustrating a congestion prevention configuration method according to a second embodiment of the present invention.

Detailed ways

The first embodiment according to the present invention is an anti-congestion configuration device. In this embodiment, the anti-congestion configuration device is applied to a circuit layout, and the circuit layout includes a plurality of electronic components. The type and number of these electronic components and the coupling relationship between the electronic components are not limited, and it depends on actual needs.

Please refer to FIG. 2 . FIG. 2 is a functional block diagram illustrating an anti-congestion configuration device applied to the circuit layout. As shown in FIG. 2 , the anti-congestion configuration device 2 includes an analysis module 20 , a definition module 22 , an extension module 24 and a setting module 26 . Wherein, the analysis module 20 is coupled to the definition module 22 ; the definition module 22 and the setting module 26 are respectively coupled to the extension module 24 . Next, each module and its function of the anti-congestion configuration device 2 will be introduced respectively.

In this embodiment, the main function of the analysis module 20 is to perform a winding congestion state analysis on the circuit layout, and generate an analysis result accordingly. In fact, the analysis module 20 can analyze whether the density of electronic components in each area of the circuit layout is higher than a default value, so as to generate an analysis result about the state of winding congestion in each area of the circuit layout at that time, for example , the analysis results may be similar to those shown in the foregoing FIGS. 1A-1D , but not limited thereto.

Next, the definition module 22 can define a congested area with a relatively high density of electronic components and a shared area adjacent to the congested area with a relatively low density of electronic components in the circuit layout according to the analysis result obtained by the analysis module 20 . Afterwards, the expansion module 24 can reconfigure the electronic components originally located in the congested area, so that the electronic components can expand outward and be distributed in the congested area and the shared area.

For example, as shown in FIG. 3A , it is assumed that the analysis result obtained by the analysis module 20 is that the density of electronic components in the region 30 in the circuit layout 3 is too high. The area 30 is defined as a congested area, and areas 31 and 32 near the congested area 30 in the circuit layout 3 are further defined as a first sharing area and a second sharing area. Wherein, the first sharing area 31 is closer to the congested area 30 , and the second sharing area 32 is located outside the first sharing area 31 .

It is worth noting that the shapes of the congestion area 30, the first sharing area 31 and the second sharing area 32 in this embodiment are all circular, but in practical applications, the congestion area and the sharing area of the circuit layout are formed by a long The aspect ratio factor is determined, so the user can change the shape of the congestion area and the sharing area by setting different aspect ratio factors, such as square, rectangle or ellipse, without certain restrictions. In addition, the number of the congested area and the shared area of the circuit layout 3 defined by the definition module 22 may also depend on the actual analysis result of the analysis module 20 , and there is no certain limitation.

As shown in FIG. 3A , the congestion area 30 , the first sharing area 31 and the second sharing area 32 of the circuit layout 3 form concentric circles from inside to outside with C(c _x , _cy ) as the center, wherein the radius of the congestion area 30 is cr, the radius of the first sharing area 31 is psr, the radius of the second sharing area 32 is ssr, and ssr>psr>cr. Assuming that the original position of an electronic component in circuit layout 3 is O(o _x , o _y ), oc_diff is the distance from O(o _x , o _y ) to C(c _x , cy ₎ , x_diff is the horizontal component of oc_diff, y_diff is the vertical component of oc_diff.

As shown in FIG. 3B , if the original position O( _ox , o _y ) of the electronic component is located in the congested area 30 , it moves to T(t _x , _ty ) via the expansion module 24 . The moved position T(t _x , _ty ) of the electronic component will be limited within the congested area 30 and the first shared area 31, and the coordinates (t _x , _ty ) of the moved position T can be passed The following equations 1 to 3 are obtained:

sca_fac=psr/cr (Equation 1)

t _x =c _x +(x_diff*sca_fac) (equation 2)

t _y =c _y +(y_diff*sca_fac) (Equation 3)

Wherein, the expansion ratio sca_fac described in Equation 1 is the ratio of the radius psr of the first sharing area 31 to the radius cr of the congestion area 30, that is, the expansion ratio sca_fac is the distance from the center point C of the congestion area 30 to the boundary of the congestion area 30 The ratio of the distance from the center point C of the congested area 30 to the boundary of the first sharing area 31 , but not limited thereto.

For example, as shown in FIG. 4A and FIG. 4B , assuming that cr=10, psr=20, and ssr=100, the boundaries (that is, the circumference) of the congestion area 30, the first sharing area 31, and the second sharing area 32 are respectively B1, B2 and B3, if the electronic components before moving are respectively located in the positions C(0, 0), D(5, 0) and E(10, 0) in the congestion area 30, then according to the above equations 1 and 2 That is to say, the positions of the moved electronic components are C'(0,0), D'(10,0) and E'(20,0).

That is to say, the expansion module 24 will redistribute each electronic component in the congested region 30 according to a value related to a psr/cr ratio (that is, the radius psr of the first sharing region 31 divided by the radius cr of the congested region 30 ). It is arranged within the range of the congested area 30 and the first sharing area 31, thereby increasing the distance between the electronic components and making the distribution of the electronic components relatively loose, so the density of the electronic components in the congested area 30 can naturally be greatly increased. reduce.

Similarly, if the original position O(o _x , o _y ) of the electronic component is located in the first sharing area 31 or the second sharing area 32, the position T(t _x , t _y ) will be limited within the scope of the second sharing area 32. The coordinate position (t _x , _ty ) of point T can be obtained by the following equations 4~6:

sca_fac＝psr+((oc_diff-cr)*(ssr-psr)/(ssr-cr)) (equation 4)

t _x =c _x +(x_diff*sca_fac/oc_diff) (equation 5)

t _y =c _y +(y_diff*sca_fac/oc_diff) (Equation 6)

Wherein, the expansion ratio sca_fac described in equation 4 is the distance from the center point C of the congestion area 30 to the boundary B3 of the second sharing area 32 (that is, the radius ssr of the second sharing area 32), the center point of the congestion area 30 The distance from C to the boundary B2 of the first sharing area 31 (i.e. the radius psr of the first sharing area 31), the distance from the central point C of the congestion area 30 to the boundary B1 of the congestion area 30 (i.e. the radius cr of the congestion area 30 ) and the distance from the center point C of the congestion area 30 to the original position O of the electronic component. More specifically, the expansion ratio sca_fac described in Equation 4 is related to the ratio of the second sharing area 32 to the entire first sharing area 31 and the second sharing area 32 , but it is not limited thereto.

As shown in Fig. 4A and Fig. 4C, if the electronic components before moving are located in positions E(10, 0), F(15, 0), G(20, 0), H(50, 0) and I(100, 0), then according to the above equations 4 to 6, the positions of the moved electronic components can be obtained as E′(20,0), F′(24.44,0 ), G′ (28.88, 0), H′ (55.56, 0) and I′ (100, 0), all located in the second sharing area 32 .

That is to say, after the electronic components originally located in the first sharing area 31 or the second sharing area 32 are moved through the expansion module 24, the expansion module 24 will expand each electronic component according to a value related to the ratio of sca_fac/oc_diff. The distance between the components makes the electronic components originally located in the first sharing area 31 move to the second sharing area 32 with a larger range, so as to avoid the electronic components moving from the congested area 30 to the first sharing area 31 from causing the original electronic components Therefore, the density of electronic components in the first shared region 31 with lower density is greatly increased.

Please refer to FIG. 5A to FIG. 5C . FIG. 5A to FIG. 5C illustrate the processing method when the position of the electronic component is just located in the high electronic component density area after being moved through the expansion module. As shown in Figure 5A, suppose the central rectangle is the congested area CR, the outer rectangle is the sharing area SR, O(0,0) is the origin, the original position of the electronic components is at P(1,1), and the oblique area is is the high electronic component density region HDR located in the sharing region SR.

As shown in FIG. 5B, since the calculated position of the electronic component after moving is N1 (3, 2), unfortunately it is located in the high electronic component density area HDR. If the expansion module 24 really moves the electronic component to N1 (3, 2), on the contrary, it increases the density of electronic components in the HDR area, so this movement is not feasible. In view of this, the present invention proposes a solution, which is to find several alternative moving points through Manhattan distance calculation. According to the calculation method of Manhattan distance, the distance between two points is the sum of the absolute wheelbases of the two points on the standard coordinates.

As shown in Figure 5C, due to the Manhattan distance between the originally obtained N1(3,2) and the original position P(1,1)=(3-1)+(2-1)=3, it can be calculated according to P(1 , 1) Obtain the alternative moving points N2(1,4), N3(2,3) and N4(4,1) different from N1(3,2) with a distance of 3 from Manhattan. Since these alternative moving points N2(1,4), N3(2,3) and N4(4,1) are not located in the high electronic component density region HDR, the expansion module 24 can move the electronic components to N2(1 , 4), N3 (2, 3) or N4 (4, 1), and will not increase the density of electronic components in the HDR area.

In practical applications, the user does not necessarily want to move all the electronic components in the congested area CR outward through the expansion module 24 , that is, the user may only want to move some of the electronic components. At this point, the user can set which electronic components among all the electronic components originally located in the congestion region CR need to be reconfigured and which electronic components remain fixed through the setting module 26 .

For example, as shown in Figure 6A, assume that there are multiple combination cells (combination cells) c (such as OR gates (ORgate) and NAND gates (NAND gate)) and multiple sequential cells (sequential cells) s (such as trigger The flip-flop, latch and clock gate are all located in the congestion region CR of the circuit layout, in order to maintain the clock of the insertion delay of the circuit layout Therefore, the user can set only the combination element c to be moved through the setting module 26, and the expansion module 24 will only move the combination element c outward according to this setting, as for all sequential elements The position of s remains fixed.

In addition, as shown in FIG. 7A , assuming that the circuit layout contains a total of three types of electronic component modules, only the distribution of the electronic component module CM is in a congested state that is difficult to wire, and the other two electronic component modules AM and BM are in a congested state. Coilable state. At this time, the user can set only the electronic component module CM to be moved through the setting module 26, and the expansion module 24 will only move the electronic component module CM outward according to this setting, as for other types of electronic component modules AM and BM The position will remain fixed.

The second specific embodiment according to the present invention is an anti-congestion configuration method. In this embodiment, the anti-congestion configuration method is applied to a circuit layout, and the circuit layout includes a plurality of electronic components. Please refer to FIG. 8 , which is a flow chart illustrating the anti-congestion configuration method.

As shown in FIG. 8 , firstly, the method executes step S10 , analyzing the state of winding congestion on the circuit layout to generate an analysis result. Next, the method executes step S11 , defining a congested area and a shared area adjacent to the congested area in the circuit layout according to the analysis result. In fact, the shapes of the congestion area and the sharing area are determined by an aspect ratio factor, so their shapes can be circular, oval, square, rectangular or other shapes depending on the aspect ratio factor, and There are no certain restrictions.

In this embodiment, the sharing area includes a first sharing area and a second sharing area, with the congested area as the center, the congested area, the first sharing area and the second sharing area in sequence from inside to outside , but not limited to this.

Then, the method executes step S12 to set the electronic components that are originally located in the congested area and need to be reconfigured. Finally, the method executes step S13 to reconfigure the electronic components such that the electronic components expand outward and are distributed in the congested area and the shared area. It should be noted that after the step S13 of reconfiguring these electronic components, the relative positional relationship between all the electronic components of the circuit layout remains unchanged.

For example, electronic components originally located at a first location within the congested area may be moved outwards to a second location within the congested area or the first shared area according to a value associated with a first expansion ratio, The second position can be calculated according to the central point of the congested area, the first position and the value related to the first expansion ratio. In practical applications, the value related to the first expansion ratio is related to the distance from the center point of the congestion area to the boundary of the congestion area and the distance from the center point of the congestion area to the boundary of the first sharing area, but This is not the limit. As for the calculation method of the second position, reference may be made to the above-mentioned equations 1-3, which will not be repeated here.

In addition, in the sharing area, the electronic components originally located in a third position in the first sharing area can also be reconfigured according to a value related to a second expansion ratio, and then moved outward to the second sharing area. A fourth location within the zone is limited to the second sharing zone, wherein the fourth location is calculated based on the center point of the congested area, the third location, and the value associated with the second expansion ratio. In fact, the value related to the second expansion ratio is the distance from the center point of the congested area to the border of the second sharing area, the distance from the center point of the congested area to the border of the first sharing area, the congested The distance from the central point of the area to the boundary of the congested area and the distance from the central point of the congested area to the third location are related, but not limited thereto. As for the calculation method of the fourth position, reference may be made to the aforementioned equations 4-6, which will not be repeated here.

Compared with the prior art, the anti-congestion arrangement device and method according to the present invention expand and distribute the electronic components that were originally only arranged in the congested area to the congested area and its nearby sharing areas with lower electronic component density, In order to reduce the originally high density of electronic components in the congested area, the congested area can be changed from an area that is difficult to wire into an area that can be routed, and the density of electronic components in the congested area and the sharing area becomes more even. More importantly, after being processed by the anti-congestion configuration device and method of the present invention, the relative positional relationship between all electronic components of the circuit layout remains unchanged, so that the circuit layout can still pass the time limit, and for As far as the circuit layout is concerned, there will not be any additional area loss.

Through the above detailed description of the preferred embodiments, it is hoped that the characteristics and spirit of the present invention can be described more clearly, and the scope of the present invention is not limited by the preferred embodiments disclosed above. On the contrary, the intention is to cover various changes and equivalent arrangements within the scope of the claimed patent scope of the present invention.

Claims (12)

1. A configuration device for preventing congestion, applied to a circuit layout, characterized in that the configuration device for preventing congestion comprises: An analysis module, coupled to the circuit layout, is used to perform a winding congestion state analysis on the circuit layout to generate an analysis result; a definition module, coupled to the analysis module, for defining a congested region and a shared region adjacent to the congested region in the circuit layout according to the analysis result, wherein the density of electronic components in the congested region is higher than that of the shared region electronic component density; and an expansion module, coupled to the definition module and the circuit layout, for relocating a plurality of electronic components in the congested area to the congested area and the shared area; a setting module, coupled to the expansion module, for setting the electronic components that need to be reconfigured among the electronic components originally located in the congested area; Wherein, the sharing area includes a first sharing area and a second sharing area, with the congested area as the center, the congested area, the first sharing area and the second sharing area in sequence from the inside to the outside; And wherein the expansion module moves the electronic components at a first location in the congestion area outward to a second location in the congestion area or the first sharing area according to a first expansion ratio, and the second location is based on The central point of the congestion area, the first position and the first expansion ratio are calculated, and the relative positional relationship between the electronic components remains unchanged after reconfiguration of the expansion module. 2. The anti-congestion configuration device according to claim 1, characterized in that, the expansion module expands and distributes the electronic components in the congested area outward and reconfigures the congested area and its vicinity to have lower electronic components. The share area of device density is used to reduce the originally high density of electronic devices in the congested area. 3. The configuration device for preventing congestion according to claim 2, wherein when the density of electronic components in the congested area is reduced to a default value, the congested area can pass the analysis of the winding congestion status of the analysis module and further become a coilable area. 4. The anti-congestion configuration device according to claim 1, wherein the first expansion ratio is related to the distance from the center point of the congested area to the boundary of the congested area and the distance from the central point of the congested area to the second A distance from the boundary of the shared area. 5. The anti-congestion configuration device according to claim 1, characterized in that, the expansion module can also move the electronic components at a third position in the first sharing area to the outside according to a second expansion ratio. 2. A fourth position in the sharing area, and the fourth position is calculated according to the central point of the congestion area, the third position and the second expansion ratio. 6. The configuration device for preventing congestion according to claim 5, wherein the second expansion ratio is related to the distance from the center point of the congestion area to the boundary of the second sharing area, the distance from the center point of the congestion area to The distance from the boundary of the first sharing area, the distance from the central point of the congested area to the boundary of the congested area, and the distance from the central point of the congested area to the third location. 7. An anti-congestion configuration method for a circuit layout, characterized in that it comprises the following steps: performing a winding congestion state analysis on the circuit layout to generate an analysis result; defining a congested area and a shared area adjacent to the congested area in the circuit layout according to the analysis result, wherein the electronic component density of the congested area is higher than that of the shared area; and Setting electronic components that need to be reconfigured among the electronic components in the congested area; relocating electronic components in the congested area to the congested area and the shared area; Wherein the sharing area includes a first sharing area and a second sharing area, with the congested area as the center, the congested area, the first sharing area and the second sharing area in sequence from the inside to the outside; and wherein electronic components at a first location within the congestion area are moved outwards to a second location within the congestion area or the first sharing area according to a first expansion ratio, and the second location is based on the The central point of the congestion area, the first position and the first expansion ratio are calculated, and the relative positional relationship between these electronic components remains unchanged after reconfiguration. 8. The anti-congestion configuration method according to claim 7, characterized in that, in the step of relocating the electronic components, the electronic components originally located in the congested area are relocated to the congested area by expanding their distribution outwards and the shared area with lower electronic component density nearby, so as to reduce the originally higher electronic component density of the congested area. 9. The anti-congestion configuration method according to claim 8, wherein when the density of electronic components in the congested area is reduced to a default value, the congested area can pass the analysis of the winding congestion state of the analysis module and further become a coilable area. 10. The anti-congestion configuration method according to claim 7, wherein the first expansion ratio is related to the distance from the center point of the congested area to the boundary of the congested area and the distance from the center point of the congested area to the second A distance from the boundary of the shared area. 11. The anti-congestion configuration method according to claim 7, wherein the electronic components at a third position in the first sharing area can also be moved outwards to the second sharing area according to a second expansion ratio A fourth position within the congested area, and the fourth position is calculated according to the central point of the congested area, the third position and the second expansion ratio. 12. The anti-congestion configuration method according to claim 11, wherein the second expansion ratio is related to the distance from the center point of the congestion area to the boundary of the second sharing area, the distance from the center point of the congestion area to The distance from the boundary of the first sharing area, the distance from the central point of the congested area to the boundary of the congested area, and the distance from the central point of the congested area to the third location.