CN117236253B

CN117236253B - FPGA wiring method and device, computer equipment and storage medium

Info

Publication number: CN117236253B
Application number: CN202311492679.6A
Authority: CN
Inventors: 请求不公布姓名
Original assignee: Suzhou Yige Technology Co ltd
Current assignee: Suzhou Yige Technology Co ltd
Priority date: 2023-11-10
Filing date: 2023-11-10
Publication date: 2024-02-02
Anticipated expiration: 2043-11-10
Also published as: CN117236253A

Abstract

The invention relates to the technical field of circuit design, and discloses an FPGA wiring method, an FPGA wiring device, computer equipment and a storage medium, wherein the method comprises the following steps: determining at least one unit connection path between a start logic unit and a corresponding end logic unit; determining a corresponding connection node of the unit connection path; determining node delay and node capacity corresponding to the connection node; determining the shortest path between each initial logic unit and the corresponding termination logic unit based on node delay, and judging whether a connecting node exceeds the corresponding node capacity or not; determining a congestion node and determining the congestion quantity of the congestion node under the condition of existence; according to the congestion quantity, increasing node delay of the corresponding congestion node; and repeatedly determining the shortest path based on the increased node delay until no connected node exceeds the corresponding node capacity. The method can solve the problem of congestion generated in the wiring process under the condition of ensuring shorter critical path delay.

Description

FPGA wiring method and device, computer equipment and storage medium

Technical Field

The invention relates to the technical field of circuit design, in particular to an FPGA wiring method, an FPGA wiring device, computer equipment and a storage medium.

Background

An FPGA (Field Programmable Gate Array, abbreviated as FPGA) is a programmable logic device that can be programmed to implement a specific logic function. And the FPGA wiring refers to connecting logic resources in an FPGA chip to form a circuit. The wiring is an essential link in the enabling process of the FPGA chip, and the core function of the wiring is to combine logic resource information with the result after layout and the connection relation between pins to realize the required logic function.

While wiring, there are often a number of problems faced, such as congestion, delay, etc. Due to limited logic resources or high design complexity, signal line conflict or insufficient logic resources occur during wiring, so that the problem of congestion occurs. In some techniques, to solve the congestion problem, it may be necessary to increase the length of the wiring or introduce more devices, which increases the delay of signal transmission, and also tends to introduce various complex algorithms, etc.

Disclosure of Invention

In view of the above, the invention provides an FPGA wiring method, an FPGA wiring device, a FPGA wiring computer device, and a FPGA storage medium, so as to solve the problem of delay increase while solving the problem of congestion of FPGA wiring in the prior art.

In a first aspect, the present invention provides an FPGA wiring method, the method including:

step S101, determining at least one unit connection path between a starting logic unit and a corresponding ending logic unit, wherein the number of the starting logic unit and the ending logic unit on the FPGA chip is multiple;

step S102, determining corresponding connection nodes of each unit connection path, wherein the connection nodes are used for connection between logic units or connection inside the logic units;

step S103, determining node delay and node capacity corresponding to each connected node;

step S104, determining the shortest path between each initial logic unit and the corresponding termination logic unit based on node delay, and judging whether a connecting node exceeds the corresponding node capacity, wherein the shortest path is a unit connecting path corresponding to the shortest path delay;

step S105, determining a congestion node and determining the congestion quantity of the congestion node under the condition that the existence of the connection node exceeds the corresponding node capacity;

step S106, increasing node delay of the corresponding congestion node according to the congestion quantity;

step S107, repeating the steps S104 to S107 until no connection node exceeds the corresponding node capacity based on the increased node delay.

Meanwhile, the delay problem and the congestion problem are considered, and the shortest path with the shortest delay is determined in an iterative mode, so that the congestion problem generated in the wiring process can be solved under the condition that the delay of a key path is short, the wiring success rate and the wiring quality are improved, the algorithm operation efficiency is improved, and the operation time is shortened.

In an alternative embodiment, determining at least one cell connection path between a starting logical unit and a corresponding ending logical unit includes:

acquiring a unit connection relation between a starting logic unit and a corresponding ending logic unit;

determining a module connection relation between a starting logic module containing the starting logic unit and a termination logic module containing the corresponding termination logic unit according to the unit connection relation between the starting logic unit and the corresponding termination logic unit;

determining at least one module connection path between the initial logic module and the corresponding termination logic module according to the module connection relation between the initial logic module and the corresponding termination logic module;

determining internal connection relations inside all logic units on a module connection path;

and determining a unit connection path according to the internal connection relation and the module connection path.

The adopted step-by-step winding method firstly carries out global wiring and then carries out local wiring, and the problem of winding inside the logic unit is not needed to be considered at the beginning, thereby greatly reducing the time cost and improving the wiring efficiency. The running time of the algorithm and the required maximum memory can be effectively reduced.

In an alternative embodiment, the node delay of the corresponding congested node is increased by the following formula:

wherein,for the increased node delay, n is a variable, and represents an nth connection node; />，/>For starting logical unit->For terminating the logical unit->For maximum delay of all cell connection paths between a starting logic cell and a corresponding ending logic cell, +.>Maximum delay of connection paths of all units on the FPGA chip;，/>for the delay of the connection node +.>For a factor positive with the amount of congestion, +.>The coefficients obtained after the debugging are used.

In an alternative embodiment of the present invention,and->Obtained after the last iteration.

In an alternative embodiment, the connection node is a connection between a pin inside one of the logic units and a pin inside the other logic unit, or a connection between the logic units.

In an alternative embodiment, the path delay is a sum of a node delay corresponding to each connection node on the unit connection path and a delay of each logic unit passing through the unit connection path.

In a second aspect, the present invention provides an FPGA wiring device, the device comprising:

the unit connection path determining module is used for determining at least one unit connection path between the initial logic unit and the corresponding termination logic unit, and the initial logic unit and the termination logic unit on the FPGA chip are multiple;

the connection node determining module is used for determining the connection node corresponding to each unit connection path, wherein the connection node is used for connection between logic units or connection inside the logic units;

the delay determining module is used for determining node delay and node capacity corresponding to each connecting node;

the shortest path determining module is used for determining the shortest path between each initial logic unit and the corresponding termination logic unit based on node delay and judging whether a connecting node exceeds the corresponding node capacity, wherein the shortest path is a unit connecting path corresponding to the shortest path delay;

The congestion determining module is used for determining a congestion node and determining the congestion quantity of the congestion node under the condition that the existence of the connected node exceeds the corresponding node capacity;

the delay increasing module is used for increasing node delay of the corresponding congestion node according to the congestion quantity;

and the iteration module is used for repeatedly determining the shortest path between each starting logic unit and the corresponding termination logic unit based on the increased node delay, and judging whether the connecting node exceeds the corresponding node capacity or not until no connecting node exceeds the corresponding node capacity.

In an alternative embodiment, the unit connection path determining module includes:

the acquisition unit is used for acquiring the unit connection relation between the initial logic unit and the corresponding termination logic unit;

the module connection relation determining unit is used for determining the module connection relation between the initial logic module containing the initial logic unit and the termination logic module containing the corresponding termination logic unit according to the unit connection relation between the initial logic unit and the corresponding termination logic unit;

the module connection path determining unit is used for determining at least one module connection path between the initial logic module and the corresponding termination logic module according to the module connection relation between the initial logic module and the corresponding termination logic module;

The internal connection relation determining unit is used for determining the internal connection relation of all logic units on the module connection path;

and the unit connection path determining unit is used for determining the unit connection path according to the internal connection relation and the module connection path.

In a third aspect, the present invention provides a computer device comprising: the FPGA wiring method comprises a memory and a processor, wherein the memory and the processor are in communication connection, the memory stores computer instructions, and the processor executes the computer instructions, so that the FPGA wiring method of the first aspect or any corresponding implementation mode is executed.

In a fourth aspect, the present invention provides a computer readable storage medium storing computer instructions for causing a computer to execute the FPGA wiring method of the first aspect or any of its corresponding embodiments.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings that are needed in the description of the embodiments or the prior art will be briefly described, and it is obvious that the drawings in the description below are some embodiments of the present invention, and other drawings can be obtained according to the drawings without inventive effort for a person skilled in the art.

FIG. 1 is a flow diagram of an FPGA routing method according to an embodiment of the present invention;

FIG. 2 is a schematic diagram of the structure of an FPGA chip arrangement according to an embodiment of the invention;

FIG. 3 is a schematic diagram of the composition of a logic module according to an embodiment of the present invention;

FIG. 4 is a flow chart of a method included in step S101 according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of a wiring according to an embodiment of the present invention;

FIG. 6 is a schematic diagram of a data selector according to an embodiment of the present invention;

fig. 7 is a schematic structural diagram of an external interface of a network switch according to an embodiment of the present invention;

FIG. 8 is a schematic diagram of a straight line between tiles according to an embodiment of the present invention;

FIG. 9 is an exemplary wiring schematic for shortest path determination in accordance with an embodiment of the present invention;

FIG. 10 is a block diagram of the structure of an FPGA wiring device according to an embodiment of the present invention;

fig. 11 is a schematic diagram of a hardware structure of a computer device according to an embodiment of the present invention.

Detailed Description

For the purpose of making the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the technical solutions of the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention, and it is apparent that the described embodiments are some embodiments of the present invention, but not all embodiments of the present invention. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

The FPGA chip is an essential link in the enabling process during wiring, and the core function of the FPGA chip is to combine logic resource information with the result after layout and the connection method between pins. The link often faces three problems, namely a congestion problem, a delay problem and a running time and memory occupation problem. The congestion problem is caused by the limited logic resources, and the phenomenon is that the connection between the plurality of groups of pins needs to use common hardware winding resources, so that congestion is caused. The delay problem is mainly how to reduce the delay of the critical path (a critical path can be understood as the one with the longest delay in the whole circuit) so as to improve the overall performance. To effectively solve the first two problems, various complex algorithms are often introduced, thereby bringing about a third problem, namely a long run-time problem.

In view of the above, the invention provides a stepwise wiring method based on a kind of FPGA chip hardware structure, which can ensure that wiring links can be efficiently completed under the condition of effectively solving congestion problems and ensuring better time delay. The "wiring" in the present invention is equivalent to the "winding".

According to an embodiment of the present invention, there is provided an FPGA routing method embodiment, it being noted that the steps shown in the flowcharts of the figures may be performed in a computer system such as a set of computer executable instructions, and although a logical order is shown in the flowcharts, in some cases the steps shown or described may be performed in an order different from that shown or described herein.

In this embodiment, an FPGA wiring method is provided, which may be executed by a server, a terminal, or the like, and fig. 1 is a flowchart of the FPGA wiring method according to an embodiment of the present invention, as shown in fig. 1, where the flowchart includes the following steps:

step S101, determining at least one unit connection path between a start logic unit and a corresponding end logic unit, wherein the number of the start logic unit and the number of the end logic unit on the FPGA chip are multiple. FPGA chips often consist of a series of regularly arranged logic modules (also known as tiles by those skilled in the art), as shown in fig. 2. Each logic module includes a logic unit, which may be a Switch Hub (a Switch Hub on an FPGA is a component used for internal connection and communication of an FPGA chip, and is generally used for connecting different logic modules or external interfaces in the FPGA to implement data transmission and communication. The network switch is mainly internally composed of a series of multiplexers, i.e. data selectors. In this embodiment, the network switch, the logic resource, and the like may be referred to as a logic unit, and are shown with reference to fig. 3.

Referring to fig. 4, in some alternative embodiments, step S101, determining at least one cell connection path between a start logical unit and a corresponding end logical unit includes:

in step S1011, the cell connection relationship between the start logical unit and the corresponding end logical unit is obtained.

Specifically, the enabling process from user design to FPGA chip mainly comprises: five links of analysis and optimization, synthesis, layout, wiring and bit stream generation. The FPGA chip includes a plurality of tiles, each of which is composed of a series of simple logic resources and mainly includes hardware units such as LUT (Look up Table), FF (Flip-Flop), etc., in this embodiment, each of the tiles is referred to as a logic module, and the hardware units included in each of the tiles are referred to as logic units.

After the integration, the user design is converted into a logic unit with equivalent logic function on the FPGA chip and the unit connection relation thereof. For example, a user design implements a 1bit addition a+b function, which can be implemented with a LUT on an FPGA chip. After confirming the logic units equivalent to the logic functions of the user design, i.e. to confirm which position on the FPGA chip each logic unit should be placed on, the position confirmation of each logic unit goes into the link of wiring. The wiring link then confirms how the pins should be connected based on the location of each logic cell and the pins of the logic cells in the layout link. It should be emphasized that after the layout link is finished, only one logic unit H1 and one logic unit H2 are known to have a connection relationship, and how to connect specifically needs to be implemented by the wiring link.

Further, when it is known that the connection relationship exists between the logic unit H1 and the logic unit H2, one of the logic units may be regarded as a start logic unit, the other logic unit to be connected may be regarded as a corresponding end logic unit, for example, the logic unit H1 may be regarded as a start logic unit, and the logic unit H2 may be regarded as an end logic unit. The unit connection relationship between the start logic unit and the corresponding end logic unit in this embodiment only indicates that there is a connection relationship between the start logic unit and the corresponding end logic unit.

Step S1012, determining a module connection relationship between the start logic module including the start logic unit and the end logic module including the corresponding end logic unit according to the unit connection relationship between the start logic unit and the corresponding end logic unit.

As described above, each logic module includes a logic unit, and after knowing the layout link, that is, knowing the unit connection relationship between the start logic unit and the corresponding end logic unit, it can be determined that the connection relationship, that is, the module connection relationship, also necessarily exists between the start logic module including the start logic unit and the end logic module including the corresponding end logic unit.

The wiring will be described more particularly below, and reference may be made to fig. 5. Assuming the layout, it is known that one output of LUT3 in the start logic cell will become one input of LUT2 in the end logic cell, i.e., the cell connection relationship is known. That is to say, it is determined that LUT3 is placed at the position of the start logic module Tile3, and LUT2 is placed at the position of the end logic unit Tile2, that is, the module connection relationship is known.

Step S1013, determining at least one module connection path between the start logic module and the corresponding termination logic module according to the module connection relationship between the start logic module and the corresponding termination logic module.

After knowing that there must be a connection relationship between the starting logical module and the corresponding ending logical module, determining a connection path between the starting logical module and the corresponding ending logical module begins. Still referring to fig. 5, an example is shown in which one output of LUT3 becomes one input of LUT 2. How the network switch inside the logic unit is configured may enable the connection of the output of LUT3 to the input of the corresponding LUT 2.

Fig. 5 shows two possible connection paths, first the output of LUT3 would correspond to one output port of Tile3 and input to the network switch of Tile4, at which time two connection paths are selectable. Firstly, a signal can be transmitted from the Tile4 to the Tile5 from a connection line between the network exchanger of the Tile4 and the network exchanger of the Tile5, then transmitted to the Tile2 from a straight connection line between the Tile5 and the Tile2, and finally transmitted to the LUT2 of the Tile 2; another path is from Tile4 to Tile1 to Tile2 and finally to LUT 2.

After determining the positions and unit connection relations of all logic units, implementing all connection relations based on hardware winding resources is the main work of a wiring link. Referring to fig. 5, the winding resources are the connection between the network switches, the connection between the logic resources and the network switches, the direct connection between the network switches between the Tile and the Tile, and the direct connection between the logic resources and the network switches.

For wiring, in some technologies, a logic resource or a network switch included in a logic unit is often taken as an object, and in fig. 5, for example, LUT3 and LUT2 are taken as objects, and whether a feasible connection path exists is directly determined globally. The wiring method is low in efficiency, easy to make mistakes, easy to increase delay, and poor in operation quality.

In the embodiment of the present invention, a step-by-step winding method is adopted, specifically, firstly, the connection relationship between the initial logic unit and the final logic unit is determined according to the layout, then, the connection relationship between the modules of Tile and Tile is determined, for example, in fig. 5, the connection relationship between LUT3 and LUT2 is known, and one output of LUT3 is connected to one input of LUT2, then, it can be determined that at least one connection relationship exists between the logic resource specific output of Tile3 and the network switch of Tile2, and finally, the connection relationship inside the network switch is determined.

That is, the step-by-step winding method employed in the embodiment of the present invention. This has the advantage that the problem of wiring inside the logic cell is not considered at the beginning, thereby greatly reducing the time cost. The reason for this advantage can be expressed in a simple mathematical way. Assume that the time complexity of an algorithm is O (n ² ) Where n is the number of nodes involved, n=a+b. Then the time required for the conventional wiring concept is (a+b) ² According to the wiring concept in this embodiment, the required time is a ² +b ² ≤(a+b) ² . The step division is performed, so that the information processed at the same time is reduced, and the internal is reducedAnd (5) storing consumption.

Still taking fig. 5 as an example, based on the layout result (including the connection relationship between the pins of the logic units), the connection relationship between each logic unit (LUT, FF, etc.) is first entered into a connection relationship abstract link, and then the connection relationship between the logic units (logic modules) is first converted into a connection relationship between the tiles, and then global wiring is first performed, that is, a module connection path between the tiles is confirmed, as shown in fig. 5, the module connection path between the Tile3 and the Tile2 may be Tile3-Tile4-Tile1-Tile2, or may be Tile3-Tile4-Tile5-Tile2, that is, the module connection path is determined from the global angle.

In step S1014, internal connection relationships among all the logic units on the module connection path are determined. After the global wiring is completed, local wiring is performed, that is, the internal wiring mode of the logic unit is confirmed.

The logic unit structure inside the Tile can be shown in fig. 3, where the Tile may include a network switch and logic resources, where the logic resources include a series of physical devices for FPGA such as LUT, FF, DSP (Digital Signal Processing, meaning digital signal processing). The network switch is mainly composed of a series of multiplexers, namely data selectors, and the structure of the data selectors can be shown in fig. 6. Taking the most basic data selector as an example, the data selector has three input signals and one output signal, wherein the input signals are respectively I0, I1 and S signals, if S is 1, the output signals O and I0 are consistent, and if S is 0, the output signals O and I1 are consistent.

While a network switch has a series of interfaces in four directions, the external interfaces of the network switch can be seen with reference to fig. 7, with four interfaces in each direction. The one-to-one connection relationship between interfaces can be realized through the configuration of the data selector inside the network switch. For example, the signal inputted from C0 may be outputted from A0, or the signal inputted from C0 may be outputted from A0, A1, B0 at the same time.

As shown in fig. 5, if the module connection paths of Tile3-Tile4-Tile1-Tile2 are selected, it is necessary to confirm the wiring patterns inside the logic cells of Tile4, tile1, tile2, i.e., the wiring patterns inside the network switch, i.e., the internal connection relationships, respectively, and the wiring inside the network switch is essentially realized by adjusting the control signals of the data selector inside the network switch.

Step S1015, determining a unit connection path according to the internal connection relationship and the module connection path. That is, after determining the wiring patterns inside the logic units and the connection paths between each logic module and each logic module on the module connection paths, the unit connection paths starting from the internal pins of the starting logic units and ending the internal pins of the logic units can be determined. That is, the cell connection path includes a connection between logic cells, and a connection between logic modules when there are logic cells between the logic modules. After the local wiring is finished, judging whether the wiring result is successful, namely whether congestion exists in the wiring result, if the wiring is successful, outputting a winding result, and if not, judging that the wiring is failed.

In this embodiment, the adopted step-by-step winding method is to perform global wiring first and then local wiring, so that the problem of winding inside the logic unit is not considered at the beginning, thereby greatly reducing the time cost and improving the wiring efficiency. The running time of the algorithm and the required maximum memory can be effectively reduced.

Step S102, determining that each unit connection path corresponds to a connection node, wherein the connection node is used for connection between logic units or connection inside the logic units.

After the unit connection paths are determined by adopting the step-by-step winding method, connection nodes on the unit connection paths also need to be determined. That is, the wiring problem is abstracted into known nodes (layout information) and corresponding relations (connection relations between pins) between the nodes, a solution is found on the FPGA chip, a path formed by edges is provided between all nodes having the corresponding relations by connecting the nodes, and no intersection exists between the paths (two edges in the obtained solution cannot overlap), so that the delay of a critical path (the path with the longest delay in all paths) is as small as possible.

In some alternative embodiments, the connection node is a connection between a pin inside one of the logic units and a pin inside the other logic unit, or a connection between the logic units.

In this embodiment, when there is a straight line between the pins of the logic unit between the tiles, the straight line may be regarded as a connection node, or a line inside the logic unit may be regarded as a connection node. When global wiring is performed, a connection line between tiles can be regarded as a connection node, and when local wiring is performed, a connection line inside a logic unit can be regarded as a connection node. That is, the unit connection path includes connection nodes inside the logic units and connection nodes between the logic units in one of the logic modules and the logic units in the other logic module.

Step S103, determining node delay and node capacity corresponding to each connected node. When signals are transmitted on the line, that is, when signals are transmitted from the input pin to the output pin, it takes a certain time, which is node delay in this embodiment, and the node delay includes driving time of the signals. It should be noted that, in addition to the delay of the connection, there is also a delay of each hardware structure itself when in operation.

The hardware structure of the FPGA chip according to this embodiment may be shown in fig. 2, where a series of connection lines exist between the Tile and the Tile, and the connection lines represented by the thick solid lines are more than one. Three solid dots replace the other Tile in that direction. In addition, the wires between the tiles are not just adjacent, and reference is made to fig. 8. Fig. 8 illustrates that, taking Tile0 in fig. 2 as an example, a portion of the direct connection line existing on the right side of Tile0, that is, the line connecting Tile and Tile, it can be seen that the direct connection line exists between Tile0 and Tile1, between Tile0 and Tile2, and between Tile0 and Tile 3. Of course, taking Tile0 as an example, the direct connection line does not necessarily exist only on the right side, but may also exist above, below and on the left side of Tile 0.

The distance spanned between the straight lines can be represented by a step length, for example, the step length of the straight line between Tile0 and Tile1 is 1, and the step length between Tile0 and Tile3 is 3. The step sizes of the existing straight lines may also contain not only 1, 2, 3, but also 4, 5, 6, etc. The number of the straight lines between every two tiles with the straight lines is determined, for example, 3 straight lines exist between Tile0 and Tile 1.

Regarding the node capacity, as described above, there is a series of wires between the tiles, and more than one wire between the tiles is often used, and a fixed signal amount can be transmitted by one wire, in this embodiment, the signal amount can be the node capacity.

Step S104, determining the shortest path between each initial logic unit and the corresponding termination logic unit based on the node delay, and judging whether the connected node exceeds the corresponding node capacity, wherein the shortest path is the unit connection path corresponding to the shortest path delay.

In some alternative embodiments, the path delay is the sum of the node delay corresponding to each connection node on the cell connection path and the delay of each logical cell passing through the cell connection path.

Referring to fig. 9, an example is illustrated: assume that the initial connection node inside the initial logical unit includes S ₁ 、S ₂ 、S ₃ Initial connection node S ₁ The corresponding termination connection node is D ₁ Initial connection node S ₂ The corresponding termination connection node is D ₂ Initial connection node S ₃ The corresponding termination connection node is D ₃ . Then look for S respectively ₁ To D ₁ 、S ₂ To D ₂ 、S ₃ To D ₄ The path with the shortest delay. Assuming that the delays of the intermediate connection nodes A, B, C are all 1, the delays of the initial connection node to the intermediate connection node or the intermediate connection node to the terminating connection node are as shown in connection with fig. 9, then S ₁ -B-D ₁ 、S ₂ -B-D ₂ 、S ₃ -B-D ₃ The path delays of (a) are 3, S ₁ -B-D ₁ 、S ₂ -B-D ₂ 、S ₃ -B-D ₃ All are shortest paths.

Further, it is determined whether the connection nodes exceed the corresponding node capacities, and it is assumed that the node capacity of each connection node is 1, i.e., only one path can be passed. And the paths of the three initial connection nodes and the corresponding termination connection nodes all select to pass through the intermediate connection node B, so that the intermediate connection node B exceeds the corresponding node capacity at the moment, and congestion occurs.

Step S105, when the presence of the connection node exceeds the corresponding node capacity, determining a congestion node, and determining the congestion amount of the congestion node.

For instance, taking the above example as an example, if the intermediate connection node B exceeds the corresponding node capacity 1, the intermediate connection node B is a congested node, and the congestion amount is 2, i.e. the passing amount minus the node capacity.

And step S106, increasing the node delay of the corresponding congestion node according to the congestion quantity.

And when the first round of initial connection nodes and the corresponding termination connection nodes are congested after being traversed, entering a second round of iteration, and calculating node delay of the congested nodes again according to the number of the congested nodes because the congestion phenomenon occurs in the previous round and the congestion is 2 in the second round of iteration process, namely increasing the node delay of the congested nodes.

Step S107, repeating the steps S104 to S107 until no connection node exceeds the corresponding node capacity based on the increased node delay. That is, according to the increased node delay, the shortest path between the initial connection node in each initial logic unit and the termination connection node in the corresponding termination logic unit is determined again, and whether the connection node exceeds the corresponding node capacity is determined again until no connection node exceeds the corresponding node capacity, and then the wiring is successful, so that the final wiring path is determined.

By way of example, taking the above example as an example, if the congestion amount is 2, the delay of connecting node bs can be recalculated, referring to the formula ，/>Set to 1, & gt>1, let->The value of (a) is changed from 0 to 3, the delay of the connecting node B is changed to 4, and the path S ₁ -B-D ₁ The path delay of (2) is 6, which is found if S is selected ₁ -A-D ₁ The path delay of the path becomes 5, then S ₁ Path S is not selected in order to go to D1 ₁ -B-D ₁ Will select the path S ₁ -A-D ₁ 。S ₃ To D ₃ There is also another possible path S ₃ -C-D ₃ But the path delay of this path is 7.S is S ₂ To D ₂ There is only a single path and therefore its path remains unchanged. There are two paths through the node B at this time, with a capacity of 1 and a congestion amount of 1. A third iteration is then entered, at which time h _n The value of (2) is changed from 3 to 4.5.S is S ₃ -B-D ₃ The path delay of (a) becomes 7.5, S ₃ To D ₃ Will select S with less path delay ₃ -C-D ₃ So far no congestion exists.

In this embodiment, there are two iteration conditions, one is to determine whether there is no congestion, that is, there is no connection node exceeding the corresponding node capacity, if yes, the wiring is successful, and the wiring result is output; another condition is to determine if a specified iteration round is reached, if congestion is reached and still present, the routing fails.

In the embodiment, the delay problem and the congestion problem are considered at the same time, and the shortest path with the shortest delay is determined in an iterative mode, so that the congestion problem generated in the wiring process can be solved at the same time under the condition that the delay of a key path is short, the wiring success rate and the wiring quality are improved, the algorithm operation efficiency is improved, and the operation time is reduced.

In some alternative embodiments, the node delay of the corresponding congested node is increased by the following formula:

wherein,for the increased node delay, n is a variable, and represents an nth connection node; />，/>For the start logic unit, j is the end logic unit, < ->For maximum delay of all cell connection paths between a starting logic cell and a corresponding ending logic cell, +.>Maximum delay of connection paths of all units on the FPGA chip;，/>for the delay of the connection node +.>For a factor positive with the amount of congestion, +.>The coefficients obtained after the debugging are used. Wherein (1)>May be a multiple of the amount of congestion, such as 1.5 times, etc., a +.>Can be obtained for early experimental debugging, such as 1.1 and the like.

In some of the alternative embodiments of the present invention,and->Obtained after the last iteration.

Each connection node has a fixed delay, in this embodiment referred to as d, and each hardware pin has a known fixed delay, and the critical path is the path with the longest delay. Regarding the above calculation formula, the node delay after the additionIs valued between 0 and 1 +.>Controlled, when the start connection node in the start logic unit +.>When the termination connection node j in the termination logic unit is on the critical path, the termination logic unit is in the form of a block >. Thereby ensuring that the delay of the connecting node is only related to the delay itself, but not to +.>Irrespective, it is thereby ensured that the selected path does not cause serious damage to the delay of the critical path.

In addition, when a path is not on the critical path,can have an impact on the delay of the connected node. In the most extreme case, assume +.>Then->. The essence is that a node is continuously increased when the node is continuously in a congestion conditionSo that when a path is selected, other nodes can be favored over the node at all, thereby eliminating congestion. Therefore, the method for calculating the node delay after the increase in the embodiment can solve the congestion problem according to iteration under the condition that the key path delay is ensured to be short.

It should be noted that, when the initial connection node in one initial logic unit has a plurality of termination connection nodes in the termination logic unit, the connection between the initial connection node and the termination connection node is not necessarily found, and the connection between the initial connection node and the termination connection node may also be found from any node passing through the paths of the initial connection node and other termination connection nodes, so as to reduce the difficulty of searching.

In this embodiment, based on the hardware structure of the FPGA chip, a distributed winding method is adopted, and global winding is performed first, and then local winding is performed. The method can effectively improve the algorithm dispatching operation efficiency, reduce the operation time, and the longer operation time is always a big pain point of the FPGA wiring. Meanwhile, the embodiment also provides an algorithm for global winding and local winding, which considers the delay problem and the congestion problem at the same time, and displays the algorithm in a calculation method for increasing node delay, so that the congestion problem generated in the winding process can be solved under the condition of ensuring the critical path delay, and the winding success rate and the winding quality are improved.

The embodiment also provides an FPGA wiring device, which is used to implement the foregoing embodiments and preferred embodiments, and is not described in detail. As used below, the term "module" may be a combination of software and/or hardware that implements a predetermined function. While the means described in the following embodiments are preferably implemented in software, implementation in hardware, or a combination of software and hardware, is also possible and contemplated.

The present embodiment provides an FPGA wiring device, as shown in fig. 10, including:

the unit connection path determining module 1001 is configured to determine at least one unit connection path between a start logic unit and a corresponding end logic unit, where the start logic unit and the end logic unit on the FPGA chip are multiple;

a connection node determining module 1002, configured to determine that each unit connection path corresponds to a connection node, where the connection node is used for connection between logic units or for connection inside the logic units;

a delay determining module 1003, configured to determine a node delay and a node capacity corresponding to each connection node;

the shortest path determining module 1004 is configured to determine, based on the node delay, a shortest path between each start logic unit and a corresponding termination logic unit, and determine whether a connection node exceeds a corresponding node capacity, where the shortest path is a unit connection path corresponding to a shortest path delay;

a congestion determining module 1005, configured to determine a congestion node and determine a congestion amount of the congestion node when the presence of a connection node exceeds a corresponding node capacity;

a delay increasing module 1006, configured to increase node delay of a corresponding congestion node according to the congestion amount;

And an iteration module 1007, configured to repeatedly determine, based on the increased node delay, a shortest path between each start logic unit and a corresponding termination logic unit, and determine whether a connection node exceeds a corresponding node capacity until no connection node exceeds the corresponding node capacity.

In some alternative embodiments, the unit connection path determination module 1001 includes:

The FPGA wiring means in this embodiment is presented in the form of functional units, where the units refer to ASIC circuits, processors and memories executing one or more software or firmware programs, and/or other devices that can provide the functionality described above.

Further functional descriptions of the above respective modules and units are the same as those of the above corresponding embodiments, and are not repeated here.

The embodiment of the invention also provides computer equipment, which is provided with the FPGA wiring device shown in the figure 10.

Referring to fig. 11, fig. 11 is a schematic structural diagram of a computer device according to an alternative embodiment of the present invention, as shown in fig. 11, the computer device includes: one or more processors 111, memory 112, and interfaces for connecting the components, including high-speed interfaces and low-speed interfaces. The various components are communicatively coupled to each other using different buses and may be mounted on a common motherboard or in other manners as desired. The processor may process instructions executing within the computer device, including instructions stored in or on memory to display graphical information of the GUI on an external input/output device, such as a display device coupled to the interface. In some alternative embodiments, multiple processors and/or multiple buses may be used, if desired, along with multiple memories and multiple memories. Also, multiple computer devices may be connected, each providing a portion of the necessary operations (e.g., as a server array, a set of blade servers, or a multiprocessor system). One processor 111 is illustrated in fig. 11.

The processor 111 may be a central processor, a network processor, or a combination thereof. The processor 111 may further include a hardware chip, among others. The hardware chip may be an application specific integrated circuit, a programmable logic device, or a combination thereof. The programmable logic device may be a complex programmable logic device, a field programmable gate array, a general-purpose array logic, or any combination thereof.

Wherein the memory 112 stores instructions executable by the at least one processor 111 to cause the at least one processor 111 to perform the methods shown in implementing the above embodiments.

Memory 112 may include a storage program area that may store an operating system, at least one application program required for functionality, and a storage data area; the storage data area may store data created from the use of the computer device of the presentation of a sort of applet landing page, and the like. In addition, memory 112 may include high-speed random access memory, and may also include non-transitory memory, such as at least one magnetic disk storage device, flash memory device, or other non-transitory solid-state storage device. In some alternative embodiments, memory 112 may optionally include memory located remotely from processor 111, which may be connected to the computer device via a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof.

Memory 112 may include volatile memory, such as random access memory; the memory may also include non-volatile memory, such as flash memory, hard disk, or solid state disk; memory 112 may also include a combination of the above types of memory.

The computer device also includes a communication interface 113 for the computer device to communicate with other devices or communication networks.

The embodiments of the present invention also provide a computer readable storage medium, and the method according to the embodiments of the present invention described above may be implemented in hardware, firmware, or as a computer code which may be recorded on a storage medium, or as original stored in a remote storage medium or a non-transitory machine readable storage medium downloaded through a network and to be stored in a local storage medium, so that the method described herein may be stored on such software process on a storage medium using a general purpose computer, a special purpose processor, or programmable or special purpose hardware. The storage medium can be a magnetic disk, an optical disk, a read-only memory, a random access memory, a flash memory, a hard disk, a solid state disk or the like; further, the storage medium may also comprise a combination of memories of the kind described above. It will be appreciated that a computer, processor, microprocessor controller or programmable hardware includes a storage element that can store or receive software or computer code that, when accessed and executed by the computer, processor or hardware, implements the methods illustrated by the above embodiments.

Although embodiments of the present invention have been described in connection with the accompanying drawings, various modifications and variations may be made by those skilled in the art without departing from the spirit and scope of the invention, and such modifications and variations fall within the scope of the invention as defined by the appended claims.

Claims

1. An FPGA wiring method, the method comprising:

step S101, determining at least one unit connection path between a starting logic unit and a corresponding ending logic unit, wherein the number of the starting logic unit and the number of the ending logic unit on an FPGA chip are multiple;

step S103, determining node delay and node capacity corresponding to each connection node;

step S104, determining the shortest path between each initial logic unit and the corresponding termination logic unit based on the node delay, and judging whether the connected node exceeds the corresponding node capacity, wherein the shortest path is the unit connection path corresponding to the shortest path delay;

Step S105, determining a congestion node and determining the congestion quantity of the congestion node under the condition that the connection node exceeds the corresponding node capacity;

step S107, repeating the steps S104 to S107 until no connected node exceeds the corresponding node capacity based on the increased node delay;

the determining at least one cell connection path between the start logic cell and the corresponding end logic cell includes:

Determining internal connection relations among all logic units on the module connection path;

determining the unit connection path according to the internal connection relationship and the module connection path;

increasing node delay of the corresponding congestion node by the following formula:

wherein,for the increased node delay, n is a variable, and represents the nth connecting node; />I is the start logic unit, j is the stop logic unit,/is the stop logic unit>For the maximum delay of all cell connection paths between the starting logic cell and the corresponding terminating logic cell,/->Maximum delay of connection paths of all units on the FPGA chip; />，/>For the delay of the connection node, +.>For a factor positive with said congestion amount, +.>The coefficients obtained after the debugging are used.

2. The method of claim 1, wherein the step of determining the position of the substrate comprises,and->Obtained after the last iteration.

3. The method of claim 1, wherein the connection node is a connection between a pin inside one of the logic cells and a pin inside the other logic cell, or a connection between logic cell interiors.

4. The method of claim 1, wherein the path delay is a sum of the node delay corresponding to each of the connection nodes on the cell connection path and the delay of each of the logic cells passing through the cell connection path.

5. An FPGA wiring device, the device comprising:

the unit connection path determining module is used for determining at least one unit connection path between a starting logic unit and a corresponding termination logic unit, and the starting logic unit and the termination logic unit on the FPGA chip are multiple;

the connection node determining module is used for determining a connection node corresponding to each unit connection path, wherein the connection node is used for connection between logic units or connection inside the logic units;

the shortest path determining module is used for determining the shortest path between each starting logic unit and the corresponding ending logic unit based on the node delay, and judging whether the connecting node exceeds the corresponding node capacity, wherein the shortest path is the unit connecting path corresponding to the shortest path delay;

the congestion determining module is used for determining a congestion node and determining the congestion quantity of the congestion node under the condition that the connecting node exceeds the corresponding node capacity;

the iteration module is used for repeatedly determining the shortest path between each starting logic unit and the corresponding ending logic unit based on the increased node delay, and judging whether the connecting node exceeds the corresponding node capacity or not until the connecting node does not exceed the corresponding node capacity;

6. The apparatus of claim 5, wherein the unit connection path determination module comprises:

A module connection path determining unit, configured to determine at least one module connection path between the starting logic module and the corresponding termination logic module according to a module connection relationship between the starting logic module and the corresponding termination logic module;

an internal connection relation determining unit, configured to determine internal connection relations inside all logic units on the module connection path;

7. A computer device, comprising:

a memory and a processor, said memory and said processor being communicatively coupled to each other, said memory having stored therein computer instructions, said processor executing the FPGA routing method of any of claims 1-4 by executing said computer instructions.

8. A computer-readable storage medium storing computer instructions for causing the computer to perform the FPGA routing method of any of claims 1-4.