CN113987995A

CN113987995A - Wiring scheme determination method and device, electronic equipment and storage medium

Info

Publication number: CN113987995A
Application number: CN202111259891.9A
Authority: CN
Inventors: 唐洁群
Original assignee: Shenzhen Hongxin Micro Nano Technology Co ltd
Current assignee: Shenzhen Hongxin Micro Nano Technology Co ltd
Priority date: 2021-10-28
Filing date: 2021-10-28
Publication date: 2022-01-28

Abstract

The application provides a wiring scheme determination method, a wiring scheme determination device, electronic equipment and a storage medium, and relates to the technical field of integrated circuit wiring. Firstly, obtaining data to be wired, wherein the data to be wired comprises a plurality of wiring objects and configuration files, each wiring object comprises position information, each wiring object is synchronously pushed according to unit length until the wiring object is overlapped with another wiring object or exceeds the range of the configuration files, each pushing scheme is used as an alternative scheme, a target scheme is selected from the alternative schemes according to a control strategy in the configuration files, two overlapped wiring objects in the target scheme are combined into a new wiring object, and the step of pushing each wiring object according to the unit length is repeatedly executed until a wiring end point is determined so as to determine the wiring scheme, wherein the wiring scheme comprises the wiring end point and a wiring path. The wiring scheme can be rapidly determined, and the effect of better balance is achieved.

Description

Wiring scheme determination method and device, electronic equipment and storage medium

Technical Field

The present application relates to the field of integrated circuit wiring technologies, and in particular, to a method and an apparatus for determining a wiring scheme, an electronic device, and a storage medium.

Background

The routing is an important ring in the back-end design of integrated circuits, and the task of the routing is to connect all equivalent nodes in the chip through metal interconnection lines. Given the node position and the connection relationship, the routing algorithm needs to determine the topology structure and the specific routing line segment of the network on the premise of satisfying certain constraint conditions (such as design rules and routing resources), and pursue optimization objectives (such as minimizing the total line length and maximizing the timing slack) on the basis of routing. For multi-pin networks, routing algorithms typically add some additional intermediate nodes, which are typically placed to increase the common routing section of the nets, thereby reducing the total net length.

With more complex design, the layout of the blocking blocks and the macro cells further extrudes wiring resources, and the difficulty in finding a proper balance position to place the middle node is further increased.

In conclusion, the prior art has the problem that the wiring scheme is difficult to determine.

Disclosure of Invention

The application aims to provide a wiring scheme determining method, a wiring scheme determining device, electronic equipment and a storage medium, so as to solve the problem that the wiring scheme is difficult to determine in the prior art.

In order to achieve the above purpose, the embodiments of the present application employ the following technical solutions:

in a first aspect, an embodiment of the present application provides a method for determining a routing scheme, where the method includes:

the method comprises the steps of obtaining data to be wired, wherein the data to be wired comprises a plurality of wiring objects and configuration files, and each wiring object comprises position information;

synchronously advancing each wiring object by unit length until the wiring object is overlapped with another wiring object or exceeds the range of the configuration file, and taking each advancing scheme as an alternative scheme;

selecting a target scheme from the alternative schemes according to the control strategy in the configuration file, and combining the overlapped wiring objects in the target scheme into a new wiring object;

and repeating the step of advancing each wiring object by unit length until a wiring end point is determined so as to determine a wiring scheme, wherein the wiring scheme comprises the wiring end point and a wiring path.

Alternatively, the step of advancing by unit length for each wiring object includes:

advancing each of the routing objects in a unit length in a transverse direction and a longitudinal direction;

the step of taking each propulsion option as an alternative comprises:

the solution of advancing in the transverse direction is taken as a first alternative and the solution of advancing in the longitudinal direction is taken as a second alternative.

Optionally, after the step of merging the overlapped routing objects in the target solution into a new routing object, the method further includes:

deleting the overlapped wiring object pairs in the target scheme;

the step of determining the wiring end point comprises the following steps:

and when the number of the remaining wiring objects is one, using the position information of the remaining wiring objects as the position information of the wiring end point.

advancing the position of the wiring object by one unit length in the transverse direction and the longitudinal direction by using the position of the wiring object as a starting position, and using the advanced position as a base position;

and when the base point position is not overlapped with the advanced base point position of any other wiring object and is not beyond the range of the configuration file, taking the base point position as a starting point position, and advancing by one unit length along the transverse direction and the longitudinal direction until the base point position is overlapped with another wiring object or exceeds the range of the configuration file.

Optionally, the configuration file further includes routing information, and after the step of synchronously advancing each routing object by unit length until overlapping another routing object or exceeding the range of the configuration file, and taking each advancing scheme as an alternative, the method further includes:

and when the alternative scheme does not contain the target scheme, replacing the wiring mode information according to the configuration file until the target scheme is determined.

Optionally, the control policy in the configuration file includes:

when the number of the overlapping pairs is the same, selecting the alternative scheme with the shortest path as a target scheme; or

When the path lengths are the same, selecting the alternative scheme with the largest number of the overlapped pairs as a target scheme; or

Selecting an alternative scheme of the minimum value of the path length/the overlap logarithm as a target scheme; or

And selecting an alternative scheme of the minimum value of the number of the care-of/the overlap pair as a target scheme.

Optionally, the configuration file comprises routing boundary locations and obstacle locations, and the step of advancing each routing object by unit length synchronously until overlapping another routing object or beyond the range of the configuration file comprises:

and synchronously advancing each wiring object by unit length until the boundary position or the barrier position is reached.

In a second aspect, an embodiment of the present application further provides a routing scheme determining apparatus, where the apparatus includes:

the device comprises an information acquisition unit, a data processing unit and a data processing unit, wherein the information acquisition unit is used for acquiring data to be wired, the data to be wired comprises a plurality of wiring objects and configuration files, and each wiring object comprises position information;

the data processing unit is used for synchronously advancing each wiring object according to the unit length until the wiring object overlaps another wiring object or exceeds the range of the configuration file, and each advancing scheme is taken as an alternative scheme;

the data processing unit is further used for selecting a target scheme from the alternative schemes according to the control strategy in the configuration file and merging the overlapped wiring objects in the target scheme into a new wiring object;

and the data processing unit is further used for repeatedly executing the step of advancing each wiring object by the unit length until the wiring end point is determined so as to determine the wiring scheme, wherein the wiring scheme comprises the wiring end point and the wiring path.

In a third aspect, an embodiment of the present application further provides an electronic device, including: a memory for storing one or more programs; a processor; the one or more programs, when executed by the processor, implement the wiring scheme determination method described above.

In a fourth aspect, the present application further provides a computer-readable storage medium, on which a computer program is stored, and the computer program, when executed by a processor, implements the wiring scheme determination method described above.

Compared with the prior art, the method has the following beneficial effects:

the embodiment of the application provides a wiring scheme determining method, a wiring scheme determining device, electronic equipment and a storage medium. On the one hand, the wiring scheme can be determined quickly according to the wiring object and the configuration file. On the other hand, the method adopts a heuristic propulsion mode of carrying out a wiring scheme on each wiring object, so that the wiring objects can realize horizontal and vertical balanced winding, better balance is realized, and subsequent time sequence optimization and convergence are facilitated.

In order to make the aforementioned objects, features and advantages of the present application more comprehensible, preferred embodiments accompanied with figures are described in detail below.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present application, the drawings that are required to be used in the embodiments will be briefly described below, it should be understood that the following drawings only illustrate some embodiments of the present application and therefore should not be considered as limiting the scope, and it will be apparent to those skilled in the art that other related drawings can be obtained from the drawings without inventive effort.

Fig. 1 is a schematic block diagram of an electronic device according to an embodiment of the present disclosure.

Fig. 2 is a schematic flow chart of a method for determining a wiring scheme according to an embodiment of the present application.

Fig. 3 is a schematic flowchart of a wiring scheme determination apparatus according to an embodiment of the present application.

In the figure:

100-an electronic device; 101-a processor; 102-a memory; 103-a communication interface; 200-a wiring scheme determination means; 210-an information acquisition unit; 220-data processing unit.

Detailed Description

In order to make the objects, technical solutions and advantages of the embodiments of the present application clearer, the technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application, and it is obvious that the described embodiments are some embodiments of the present application, but not all embodiments. The components of the embodiments of the present application, generally described and illustrated in the figures herein, can be arranged and designed in a wide variety of different configurations.

Thus, the following detailed description of the embodiments of the present application, presented in the accompanying drawings, is not intended to limit the scope of the claimed application, but is merely representative of selected embodiments of the application. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present application.

It should be noted that: like reference numbers and letters refer to like items in the following figures, and thus, once an item is defined in one figure, it need not be further defined and explained in subsequent figures. Meanwhile, in the description of the present application, the terms "first", "second", and the like are used only for distinguishing the description, and are not to be construed as indicating or implying relative importance.

Some embodiments of the present application will be described in detail below with reference to the accompanying drawings. The embodiments described below and the features of the embodiments can be combined with each other without conflict.

As described in the background, there is a problem in the prior art that the wiring scheme is difficult to determine. For example, some special routing tasks, such as clock tree routing, place additional demands on the balance of the network based on the common routing problem. One clock wiring problem involves one root node (root, i.e., end point) and s-1 clock receiver points (sinks), and requires that the delay difference between the time signal from the root node and all receiver points be as small as possible. One clock tree with zero delay skew is called zero-skew tree. Usually, the winding algorithm estimates the delay according to the length of the line, and determines the position of the middle node from top to bottom or from bottom to top to construct a clock tree.

The routing algorithm determines not only the location, length of the routing, but also the metal layer in which the wire segment is located. Usually, only traces in the same direction (transverse or longitudinal) are placed on one metal layer, and adjacent non-equidirectional trace segments are connected by through holes. Considering the inconsistency of the electrical parameters of different metal layers, the time delay estimated based on the line length often has deviation from the actual situation, and the deviation is often difficult to accurately estimate due to the disturbance of the conditions such as environment, process and the like. With the increasing frequency of clock signals and the increasing popularity of multi-mode multi-angle analysis, skew poses more and more serious challenges to timing convergence. Meanwhile, as the design becomes more complex, the layout of the blocking blocks and the macro cells further extrudes the wiring resources, and the difficulty in finding a proper balance position to place the middle node is further increased.

In view of the above, the present application provides a method for determining a routing scheme, which determines routing schemes of all routing objects by advancing routing objects according to unit length in synchronization.

It should be noted that, the wiring scheme determination method provided in the present application is applied to an electronic device, and referring to fig. 1, the electronic device 100 may include a memory 102, a processor 101, and a communication interface 103, where the memory 102, the processor 101, and the communication interface 103 are directly or indirectly electrically connected to each other to implement data transmission or interaction. For example, the components may be electrically connected to each other via one or more communication buses or signal lines.

The memory 102 may be used to store software programs and modules, such as program instructions or modules corresponding to the positioning apparatus provided in the embodiment of the present application, and the processor 101 executes the software programs and modules stored in the memory 102 to execute various functional applications and data processing, thereby executing the steps of the positioning method provided in the embodiment of the present application. The communication interface 103 may be used for communicating signaling or data with other node devices.

The Memory 102 may be, but is not limited to, a Random Access Memory (RAM) 102, a Read Only Memory (ROM) 102, a Programmable Read Only Memory (PROM) 102, an Erasable Read Only Memory (EPROM) 102, an Electrically Erasable Programmable Read Only Memory (EEPROM) 102, and the like.

The processor 101 may be an integrated circuit chip having signal processing capabilities. The Processor 101 may be a general-purpose Processor 101, including a Central Processing Unit (CPU) 101, a Network Processor 101 (NP), and the like; but may also be a Digital Signal processor 101 (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other Programmable logic device, discrete Gate or transistor logic device, discrete hardware components.

It will be appreciated that the configuration shown in FIG. 1 is merely illustrative and that electronic device 100 may include more or fewer components than shown in FIG. 1 or have a different configuration than shown in FIG. 1. The components shown in fig. 1 may be implemented in hardware, software, or a combination thereof.

The following exemplifies a wiring scheme determination method provided in the present application:

as an alternative implementation manner, referring to fig. 2, the method for determining a routing scheme provided by the present application includes:

s102, obtaining data to be wired, wherein the data to be wired comprises a plurality of wiring objects and configuration files, and each wiring object comprises position information.

S104, synchronously advancing each wiring object according to the unit length until the wiring object overlaps another wiring object or exceeds the range of the configuration file, and taking each advancing scheme as an alternative scheme.

S106, selecting a target scheme from the alternative schemes according to the control strategy in the configuration file, and combining the wiring objects overlapped in the target scheme into a new wiring object.

And S108, repeatedly executing the step of advancing each wiring object according to the unit length until the wiring end point is determined so as to determine the wiring scheme, wherein the wiring scheme comprises the wiring end point and the wiring path.

The implementation mode of the method adopts horizontal and vertical balance type winding to realize synchronous propelling according to unit length, and the wire net is composed of a series of wiring sections with the same length and the same direction. Because the wiring segments with the same direction can be arranged on the same metal layer, the time lag caused by the non-uniformity of the electrical parameters of the metal wiring layers can be better controlled in an actual chip. The method is particularly beneficial to the optimization and convergence of time sequence in the multi-mode multi-angle analysis.

It should be noted that the routing object provided in the present application means the starting points of a plurality of routes, for example, in a circuit board of 10 × 10 size, points to be routed include points a (0,0), B (0,1), C (1,1), and D (1,0), and then points A, B, C and D are both routing objects, and each routing object has corresponding position information, and the present application represents the position information of the routing object in a coordinate manner. When the position information is located, the coordinate axis may be set as needed, for example, the center position of the circuit board may be used as the origin of the coordinate axis, or the end point of the circuit board may be used as the origin of the coordinate axis, which is not limited herein.

The configuration file may include data preset by the system and data set by the user, for example, the data preset by the system may include the size of the circuit board, the position and size of the obstacle, the wiring layer where the circuit board is located, and the like. The circuit board generally includes a plurality of layers, each layer of wiring layer can be wired separately, and each layer of wiring layer has a certain size, and a wiring area cannot exceed the area.

The data set by the user includes the form of the routing, for example, the routing adopts a linear routing or a non-linear routing, and the non-linear routing includes whether to use a turn-back line segment, whether to use a fold line to update a routing scheme, whether to accept an unbalanced routing scheme, and the like.

Of course, in some implementations, the preset data and the data set by the user may also be set separately, that is, the configuration file only contains the relevant parameters set by the user, and the preset data is stored in other databases.

After the routing data is acquired, each routing object may be synchronously advanced by unit length until it overlaps another routing object or is out of range of the configuration file, with each advancement being an alternative.

For example, if the routing object includes X (0,0) and routing cash-in Y (2,0), then when X (0,0) advances one unit length to the right and Y (2,0) advances one unit length to the left in synchronization, then object X and object Y can both advance to the position of (1,0) and overlap at this position, which may be an alternative.

It can be understood that, after the advancing manner, a plurality of alternatives can be obtained, then an optimal scheme is determined from the alternatives as a target scheme according to a selection policy given by the configuration file, and one or more wiring object pairs in the target scheme are merged into a new wiring object. The pair of routing objects described in the present application refers to two routing objects that can be overlapped by advancing, for example, if the object X and the object Y can both be overlapped by advancing to the position of (1,0), the object X and the object Y form a routing object pair.

It should be further noted that, as an implementation manner, the control policy in the configuration file includes, but is not limited to:

the first method comprises the following steps: and when the number of the overlapped pairs is the same, selecting the alternative scheme with the shortest path as the target scheme.

And the second method comprises the following steps: and when the path lengths are the same, selecting the alternative with the largest number of overlapped pairs as the target scheme.

And the third is that: and selecting the alternative scheme of the minimum value of the path length/overlap logarithm as the target scheme.

And fourthly: and selecting an alternative scheme of the minimum value of the number of the care-of/the overlap pair as a target scheme.

For example, there is an overlapping point between the routing object X and the routing object Y during the advancing, and in this alternative, the advancing is twice; there is also an overlapping point between the routing object X and the routing object Z in the advancing process, and in this alternative, the advancing is performed three times, and assuming that the shortest path is used as the selection policy, when determining the target solution, the candidate including the routing object X and the routing object Y will be used as the target solution, so as to make the determined path of the new routing object shortest. And then repeatedly executing the step of advancing each wiring object by unit length until the wiring scheme is determined.

As one implementation, the step of S104 includes:

and S1041, advancing each wiring object along the transverse direction and the longitudinal direction according to the unit length.

The step of taking each propulsion option as an alternative comprises:

s1042, the scheme of advancing in the transverse direction is taken as a first alternative, and the scheme of advancing in the longitudinal direction is taken as a second alternative.

It is to be understood that the lateral advancement, as described herein, can refer to leftward or rightward advancement and the longitudinal advancement can refer to upward or downward advancement. By taking all the schemes of transverse propulsion as a first alternative and all the schemes of longitudinal propulsion as a second alternative, the data can be classified, and the target scheme can be determined conveniently.

In an optional implementation manner, after the step of merging two routing objects in the target solution into a new routing object, the method further includes:

deleting two wiring objects in the target scheme;

the step of determining the wiring end point comprises the following steps:

when the number of the remaining wiring objects is one, the position information of the remaining wiring objects is used as the position information of the wiring end point.

In other words, when determining the routing scheme, the routing scheme is actually determined in a round-by-round iteration manner, and with each round of iteration, the number of routing objects will be reduced until the number of routing objects is reduced to 1, and at this time, the position of the routing object is the position of the midpoint of the routing. And determining a wiring scheme, wherein the wiring scheme comprises a wiring end point and a wiring path.

For example, when the routing objects include A, B, C and D, after the first round of determination of the target scheme, a new routing object E is determined by the object a and the object B, wherein the lengths of the routing object E to the routing object a and the routing object B are consistent; a new wiring object F is determined by the object C and the object D, wherein the lengths of the wiring object F to the wiring object C and the wiring object D are consistent. Then after the first iteration, new wiring objects E and F are obtained, and the system also automatically deletes the original wiring objects A, B, C and D, the number of the wiring objects is changed from 4 to 2, and then the next iteration is performed, i.e. the target scheme is continuously determined according to the new wiring objects E and F, and new wiring objects G are obtained, and the wiring objects E and F are deleted. At this time, if only G remains in the wiring object, the position information of G is used as the position information of the wiring end point, and the position information is integrated with the route of the wiring process to form the final wiring plan.

On this basis, after the step of S102, the method further includes:

s103, judging whether the number of the wiring objects is more than one, and if so, executing the step of advancing each wiring object synchronously according to the unit length. If not, exiting.

In other words, in each iteration process of the target scheme, the system judges whether the number of the wiring objects is more than one, and determines whether to obtain the wiring end point according to the number of the wiring objects.

As one implementation, the step of S104 includes:

s1043, using the position of the wiring object as a starting position, advancing by a unit length along the transverse direction and the longitudinal direction, and using the advanced position as a base position;

s1044, when the base point position does not overlap with the advanced base point position of any of the other routing objects and does not exceed the range of the profile, advancing the base point position by one unit length in the transverse direction and the longitudinal direction with the base point position as the starting point position until overlapping with another routing object or exceeding the range of the profile.

Taking the position of the wiring object as a starting point, advancing the wiring object to the periphery, taking transverse advancing as an example, two alternatives of advancing one unit length to the right and one unit length to the left can be achieved, and if the requirement is not met at the moment, continuing advancing; when advancing forward, as an alternative to advancing to the right, one may advance further to the right or longitudinally (up or down) until overlapping another routing object or beyond the scope of the profile.

For example, taking the wiring object a (0,0) as an example, one unit length is advanced to the right, the base point position after the advancement is (1,0), and when the wiring object is not overlapped with other wiring objects after the first advancement, the second advancement is required, and at this time, the wiring object is advanced upward, downward and rightward respectively based on the base point position (1,0), and new base point positions (1,1), (2,0) (1, -1) are obtained respectively, and the process is repeated until the wiring objects are overlapped or exceed the range of the configuration file.

In one implementation, when an alternative in which two wiring objects overlap occurs during the advancing process, the flow of continuing the advancing is ended, because the present application takes the shortest route as the target solution, and once an alternative in which two wiring objects overlap occurs, even if the advancing is resumed and a solution in which the wiring objects overlap occurs again, the road length thereof increases accordingly due to the increase in the advancing times, in other words, the alternative in which two wiring objects overlap earliest is finally selected as the target solution. Therefore, in order to reduce the amount of computation of the system, when an alternative in which two wiring objects overlap occurs, the flow of continuing the advancement is ended.

In addition, the configuration file provided by the application can comprise wiring boundary positions and obstacle positions, and the step of advancing each wiring object by unit length synchronously until the wiring object overlaps another wiring object or exceeds the range of the configuration file comprises the following steps:

each routing object is synchronously advanced by unit length until a boundary position or an obstacle position is reached.

For example, if (1,0) is in the obstacle position, if the wiring object is advanced by one unit length and reaches (1,0) at this time, this indicates that the present advancement has entered the obstacle position, and if the present advancement is not legal.

As an alternative implementation, when the configuration file further includes the wiring manner information, for example, a user-defined wiring manner. After the steps of synchronously advancing each routing object by unit length until overlapping another routing object or out of range of a configuration file, and taking each advancement scheme as an alternative, the method further comprises:

When a plan that the wiring objects can be overlapped is not determined in a certain advancing process, the target plan cannot be determined in the transverse direction or the longitudinal direction, and at this time, the wiring mode needs to be replaced, for example, a fold line wiring mode is added, an oblique line wiring mode is added, and the like.

It should be noted that, as an implementation manner, the electronic device provided in the present application may include a plurality of databases for storing different data. The databases include, for example, a wiring resource database, a wiring object database, a wiring flow configuration file, an alternative wiring scheme database, and a scheduled wiring scheme database, wherein,

the routing resource database contains layout information of the integrated circuit design, including the size of the design, the location, size of the obstacles, the routing layers to which it belongs, and the like.

The wiring object database contains all the wiring objects for which the wiring scheme is not determined. Each routing object includes its initial location and possibly accepted routing schemes that start from the same initial location, traverse a series of routing segments of the same routing layer and of the same length, and reach different end points.

The database of determined wiring plans contains all of the determined wiring plans, represented as a series of nets with different end points.

The wiring flow configuration file is generated according to the setting of a user. The settings include whether to use the foldback line segment, whether to use the polyline to update the wiring scheme, and whether to accept an unbalanced wiring scheme. And generating a flow for updating the alternative scheme database according to the setting.

The alternative routing scheme database is initialized by the routing object database, and the possible routing schemes of the routing objects in the routing object database are updated according to the routing flow configuration file. And advancing all wiring schemes of the wiring object at different wiring layers, advancing one unit at a time, communicating with the wiring resource database, and inquiring whether the advancing is legal (if the end point of the wiring object enters a barrier area or exceeds a design area, the advancing is illegal). When the end point of one or more pairs of wiring objects with wiring schemes reaches the same position, or the inquiry finds that the progress causes all possible wiring schemes of a certain wiring object to be illegal, the updating is stopped. If one or more pairs of routing objects for which routing solutions can be merged (i.e., the endpoints arrive at the same location) appear in at least one of the alternative routing solution databases in an update, the routing object database and the determined routing solution database may be updated with the alternative routing solution database. And if the two alternative wiring scheme databases both meet the updating condition, selecting one of the two alternative wiring scheme databases according to a certain strategy. For the wiring object pair merged by the wiring scheme in the selected alternative scheme database, fixing the corresponding wiring scheme, adding the wiring scheme into the fixed wiring scheme database, deleting the original object from the wiring object database, and constructing a new wiring object by taking the terminal merging position as an initial position to be added into the wiring object database; for routing objects that fail to merge, their solutions in the routing object database are updated with the possible routing solutions in the alternative routing solution database. And if the two alternative solution databases do not meet the updating condition, the alternative wiring solution database is reinitialized, and a new wiring means is selected for updating according to the wiring flow configuration file.

The following description will exemplify layout information of a design obtained after layout is completed, in which a routing area is a 10 × 10 square area, the origin of a coordinate system is located at the center of the square, there are four clock receiving points to be routed, the four points are routing objects, and are located at (-2,3), (2,3), (-2, -3), (4, -3), respectively, and there is no obstacle, i.e., layout can be performed in the square area.

Firstly, carrying out global initialization action, initializing a wiring object database according to the position information of the four clock receiving points, wherein after initialization, 4 objects and initial positions thereof exist in the database, and no wiring scheme which is possibly accepted exists; initializing a wiring resource database, wherein only wiring region information exists because of no barrier; according to the user setting: the method comprises the following steps of obtaining a corresponding wiring flow configuration file without using a turn-back line segment, using a fold line and receiving an unbalanced wiring scheme: the attempt is made using straight line segments (by default) and then using broken line segments (by default), if an unsuccessful, unbalanced routing scheme is acceptable. And copying the current wiring object database to initialize the alternative wiring scheme database.

After global initialization, the routing object database contains four objects at this time, so a first iteration is started, the alternative scheme database is updated by using the straight line segments according to the process configuration file, and the routing objects in the routing object database and routing scheme information which may be accepted by the routing objects are copied to update the alternative routing scheme database.

Updating the alternative database: suppose the alternatives database updates alternatives at the horizontal routing level and the alternatives database updates alternatives at the vertical routing level. The updating process of the alternative database is described by taking the updating of the wiring object with the initial position of (-2,3) in the alternative database as an example:

therefore, there is no wiring scheme that can be accepted by the wiring object, and thus, there are two wiring schemes [ (-2,3), (-2-, 3) ] and [ (-2,3), (-2+, 3) ] proceeding from the initial position to the left and right directions, respectively.

After two advances, the endpoints of the two alternatives reached (-4, 3) and (0,3), respectively. At this time, the route object whose initial position is (2,3) also has the end point of one route plan reaching the (0,3) position, and thus the update of the alternative database is completed.

The two wiring schemes for the wiring object in the alternative database are [ (-2,3), (-2, 3-) ] and [ (-2,3), (-2,3+), respectively. After the three times of progress, the end point of one wiring scheme reaches (-2,0), meanwhile, the wiring objects with the initial positions of (-2, -3) also have the end point of one wiring scheme reaching the position, the combinable wiring objects exist, and the updating is finished.

Determining whether the scheme is accepted or not: at this point, both alternative databases satisfy the update condition, and each has a pair of routing objects that can be merged. And one of the alternative databases is advanced by a smaller number of steps than the other alternative database, so that the alternative database with a smaller number of steps is selected.

After determining the target propulsion scheme, updating the wiring object database and the determined wiring scheme database, deleting the original object for the merged wiring object pair, adding a new object and saving the wiring scheme: deleting the wiring objects with initial positions of (-2,3) and (2,3) from the wiring object database, and adding the wiring objects with initial positions of (0, 3); corresponding wiring schemes [ (-2,3), (0,3) ] and [ (2,3), (0,3) ] are added to the determined wiring scheme database.

For the routing objects which cannot be merged, updating the routing scheme of the routing objects: taking an object with an initial position of (-2, -3) as an example, when the object does not have any wiring scheme within the wiring resource database, the object within the updated wiring object database contains two wiring schemes [ (-2, -3), (0, -3) ] and [ (-2, -3), (-4, -3) ].

After the first iteration is finished, the wiring object database contains three wiring objects, the ending condition is not met, and a new iteration is started. The main flow is not different from the first iteration, and the second updating of the alternative scheme database is illustrated by taking a wiring object with an initial position of (-2, -3) in the alternative scheme database as an example.

After initialization the object has two wiring schemes: [ (-2, -3), (0, -3) ] and [ (-2, -3), (-4, -3) ], the alternative database advances the wiring scheme at the vertical wiring level starting from the end of the existing wiring scheme, so two wiring schemes will expand to four [ (-2, -3), (0, -3), (0, -3+) ], [ (-2, -3), (0, -3), (0, -3-) ], [ (-2, -3), (-4, -3), (-4, -3+), [ (-2, -3), (-4, -3), (-4, -3-) ].

After the three steps are advanced, the end point of one wiring scheme reaches (0,0) and is [ (-2, -3), (0, -3), (0,0) ], the end point of the other wiring object is merged, and the updating is finished.

The iterative alternative wiring scheme database in the current round also has a pair of combinable wiring line object pairs, only 1 step needs to be advanced, the cost is lower, and therefore alternative wiring scheme data are accepted.

After the second iteration, the wiring object library comprises two objects, and two wiring schemes are newly added into the determined wiring scheme database: [ (-2, -3), (0, -3), (1, -3) ] and [ (4, -3), (2, -3), (1, -3) ].

After the third iteration, the determined routing scheme database is added with [ (1, -3), (1,0) ], [ (0,3), (1,3), (1,0) ], and the routing resource database only has one object with the initial position of (1,0), and the procedure is ended.

The invention updates the two alternative wiring scheme databases, performs heuristic promotion on the alternative wiring schemes of the wiring object in different wiring layers, and selects whether to accept the heuristic and which alternative scheme according to a certain strategy, thereby realizing the horizontal and vertical balanced winding. Compared with the existing winding algorithm, the transverse and longitudinal balanced wiring provided by the application has better balance. In some special winding tasks, such as clock tree wiring, the balance is improved, so that subsequent timing optimization and convergence are facilitated, and great significance is achieved.

And, a series of possibly accepted wiring schemes are constructed for each wiring object. For a certain routing object, all the starting points of the routing schemes are the same, and the routing objects pass through a series of line segments which are positioned in the same routing layer and have the same length from the same starting point to reach different end points. For the routing object database or the alternative routing scheme database at a certain moment, paths traced back from all global end points to corresponding initial clock receiving points are all composed of routing line segments which are located in the same routing layer and have the same length, and the effect is better.

Based on the foregoing implementation, please refer to fig. 3, the present application provides a wiring scheme determining apparatus 200, including:

the information obtaining unit 210 is configured to obtain data to be wired, where the data to be wired includes a plurality of wiring objects and configuration files, and each wiring object includes location information.

It is understood that the above S102 may be performed by the information acquisition unit 210.

And the data processing unit 220 is used for synchronously advancing each wiring object by unit length until the wiring object overlaps another wiring object or exceeds the range of the configuration file, and taking each advancing scheme as an alternative scheme.

It is understood that the above S104 may be performed by the data processing unit 220.

And the data processing unit 220 is further configured to determine, from the alternatives, a scheme in which the paths of the two routing objects are shortest as a target scheme, and merge the two routing objects in the target scheme into a new routing object.

It is understood that the above S106 may be performed by the data processing unit 220.

The data processing unit 220 is further configured to repeatedly perform the step of advancing by unit length for each wiring object until the wiring scheme is determined.

It is understood that the above S108 may be performed by the data processing unit 220.

It is to be understood that the steps of the method described above may correspond to one functional module to execute the corresponding steps, which are not described herein again.

To sum up, the embodiment of the present application provides a wiring scheme determination method, an apparatus, an electronic device, and a storage medium, where data to be wired is first obtained, where the data to be wired includes a plurality of wiring objects and a configuration file, and each wiring object includes location information, each wiring object is synchronously advanced according to a unit length until the wiring object overlaps with another wiring object or exceeds a range of the configuration file, each advanced scheme is used as an alternative scheme, a target scheme is selected from the alternative schemes according to a control policy in the configuration file, two wiring objects overlapped in the target scheme are merged into a new wiring object, and the step of advancing each wiring object according to the unit length is repeatedly performed until a wiring end point is determined, so as to determine the wiring scheme, where the wiring scheme includes a wiring end point and a wiring path. On the one hand, the wiring scheme can be determined quickly according to the wiring object and the configuration file. On the other hand, the method adopts a heuristic propulsion mode of carrying out a wiring scheme on each wiring object, so that the wiring objects can realize horizontal and vertical balanced winding, better balance is realized, and subsequent time sequence optimization and convergence are facilitated.

The above description is only a preferred embodiment of the present application and is not intended to limit the present application, and various modifications and changes may be made by those skilled in the art. Any modification, equivalent replacement, improvement and the like made within the spirit and principle of the present application shall be included in the protection scope of the present application.

It will be evident to those skilled in the art that the present application is not limited to the details of the foregoing illustrative embodiments, and that the present application may be embodied in other specific forms without departing from the spirit or essential attributes thereof. The present embodiments are therefore to be considered in all respects as illustrative and not restrictive, the scope of the application being indicated by the appended claims rather than by the foregoing description, and all changes which come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein. Any reference sign in a claim should not be construed as limiting the claim concerned.

Claims

1. A wiring scheme determination method, characterized in that the method comprises:

2. The wiring scheme determination method according to claim 1, wherein the step of advancing by unit length for each wiring object comprises:

the step of taking each propulsion option as an alternative comprises:

3. The routing scheme determination method of claim 1 wherein, after the step of merging overlapping routing objects in the target scheme into a new routing object, the method further comprises:

deleting the overlapped wiring object pairs in the target scheme;

the step of determining the wiring end point comprises the following steps:

4. The wiring scheme determination method according to claim 1, wherein the step of advancing by unit length for each wiring object comprises:

5. The wiring scheme determination method according to claim 1, wherein the configuration file further includes wiring manner information, and after the step of advancing each wiring object by unit length synchronously until overlapping another wiring object or out of the range of the configuration file, and taking each advancing scheme as an alternative, the method further comprises:

6. The wiring scheme determination method of claim 1, wherein the control policy in the configuration file comprises:

7. The routing scheme determination method of claim 1 wherein the configuration file includes routing boundary locations and obstacle locations, the step of advancing each routing object in synchronization by unit length until overlapping another routing object or out of range of the configuration file comprising:

8. A wiring scheme determination apparatus, characterized in that the apparatus comprises:

9. An electronic device, comprising:

a memory for storing one or more programs;

a processor;

the one or more programs, when executed by the processor, implement the wiring scheme determination method of any of claims 1-7.

10. A computer-readable storage medium, on which a computer program is stored, which, when being executed by a processor, carries out the wiring scheme determination method according to any one of claims 1 to 7.