CN-121984908-A - FPGA signal negotiation distribution method supporting dynamic networking

Abstract

The invention discloses an FPGA signal negotiation distribution method supporting dynamic networking, which comprises the steps of establishing a mapping relation between FPGA nodes and logic nodes, calculating the shortest paths among all FPGA pairs, counting the number of networks on each physical channel, calculating initial TDM ratio and path delay, introducing a relaxation ratio and criticality ranking mechanism, performing iterative wiring optimization based on a dynamic cost function, updating a weight topological graph, identifying physical channels with over-limit TDM ratio and severe congestion, reconstructing physical topology through channel addition, deletion and transfer operation, guiding channel resource distribution based on comprehensive ranking scores of three constraint factors, cooperatively executing PATHFINDER wiring and topology reconstruction processes, and re-performing signal distribution based on a last round of wiring result after topology adjustment each time, and outputting a final wiring path and a reconstructed topological structure.

Inventors

• GUO JINGJING
• Niu Xiaokui
• YANG SUOHANG
• GE YIYAN
• CAI ZHIKUANG

Assignees

• 南京邮电大学

Dates

Publication Date

20260505

Application Date

20260209

Claims (6)

1. 1. An FPGA signal negotiation distribution method supporting dynamic networking is characterized by comprising the following steps: Step one, representing a topological structure of a multi-FPGA platform as an undirected weighted graph, representing a segmented logic netlist as a directed hypergraph, and establishing a mapping relation between FPGA nodes and logic nodes; Step two, initial wiring is carried out based on a Floyd shortest path algorithm, shortest paths among all FPGA pairs are calculated, the number of networks on each physical channel is counted, and initial TDM ratio and path delay are calculated; thirdly, using PATHFINDER to negotiate a wiring method, introducing a relaxation ratio and a critical ranking mechanism, performing iterative wiring optimization based on a dynamic cost function, and updating a weight topological graph; step four, identifying physical channels with excessive TDM ratio and severe congestion, reconstructing physical topology through channel adding, deleting and transferring operations, and guiding channel resource allocation based on comprehensive ranking scores of three types of constraint factors; And fifthly, performing the PATHFINDER wiring and the topology reconstruction process in a coordinated manner, and re-distributing signals based on the last round of wiring result after each topology adjustment, and outputting a final wiring path and a reconstructed topology structure.
2. 2. The method of claim 1, wherein the step one topology modeling method comprises: The method comprises the steps of representing a multi-FPGA platform topological structure as an undirected weighted graph G= (V, E), wherein a vertex set V represents a set of all FPGAs, an edge set E represents a physical connection channel between the FPGAs, the weight w (E) of an edge is defined as the number of nets between the FPGAs, and a logic netlist as a directed hypergraph H= (V, N), wherein the vertex set V is consistent with the topological graph, the hyperedge set N is a set of networks, each net comprises a source end and a plurality of receiving ends, and all endpoints are mapped to different FPGAs.
3. 3. The method of claim 1, wherein the step two of performing the initial routing comprises: Calculating the shortest paths between all FPGA pairs by using Floyd-Warshall algorithm, establishing a distance matrix and a path reconstruction matrix, counting the number of networks passing through each physical channel according to a wiring path, and calculating the TDM ratio according to a formula r qp =|N pq |/w(F p ,F q , wherein |N pq | is the number of networks actually crossing the channel, w (F p ,F q ) is the number of physical channels between node pairs, path delay consists of TDM transmission delay and fixed line delay, and a calculation formula is D (P ij )=∑[α·r qp +beta), wherein alpha is a delay coefficient, and beta is fixed line delay.
4. 4. The method of claim 1, wherein the step three PATHFINDER of negotiating wiring comprises: Introducing a relaxation ratio A ij =D(P ij )/D max , wherein D (P ij ) is a path delay, D max is a global maximum delay, calculating a connection criticality ranking based on the relaxation ratio, determining a wiring priority, defining a cost function as c n =(b n +h n )·p n , wherein b n is a base delay, h n is a historical congestion cost, P n is a current congestion cost, performing path searching in a dynamically updated weight topology graph by using a Dijkstra algorithm, and finally distributing network signals according to weights.
5. 5. The method of claim 1, wherein the method of step four topology reconstruction is: The comprehensive ranking score is calculated by weighting the communication demand score, the TDM congestion score and the critical path participation degree, the weights of the communication demand score, the TDM congestion score and the critical path participation degree are w 1 、w 2 、w 3 respectively, the formula is S=w 1 ·Dnorm+w 2 ·Tnorm+w 3 . Cscore, dnorm is normalized communication demand, tnetwork is normalized TDM congestion degree, cscore is critical path mark, and channel adjustment is required to meet TDM ratio constraint and FPGA IO resource constraint simultaneously.
6. 6. The method of claim 1, wherein the method of step five is cooperatively performed by: And carrying out PATHFINDER wiring iteration and topology optimization circulation alternately, keeping the historical cost and learning state of PATHFINDER after each topology adjustment, initializing a new round of wiring based on the last round of wiring result, and finally outputting the detailed wiring paths and delays of each wire net and outputting the reconstructed physical topology structure.

Description

FPGA signal negotiation distribution method supporting dynamic networking Technical Field The invention belongs to the field of integrated circuits, and particularly relates to an FPGA signal negotiation distribution method supporting dynamic networking. Background With the rapid growth of circuit design scale, hardware simulation platforms have difficulty simulating designs up to billions of gates in size with single or very few FPGAs. Therefore, a large-scale Multi-FPGA system (Multi FPGA SYSTEM, MFS) is widely used for large-scale circuit design implementation. In MFS, a large number of signals need to be passed between FPGAs. Because of the limitation of the hardware structure, not all FPGAs can directly perform interconnection communication, so that a communication path of signals needs to be planned according to the actual hardware interconnection topology, and this process is called system-level wiring. In order to solve the problem of limitation of the number of I/O pins of the FPGA device in the system-level wiring, a Time Division Multiplexing (TDM) technology is widely used to realize efficient communication between different FPGAs. TDM allows multiple channels to share the same channel at different time periods, thereby solving the problem of insufficient wiring channels. Although the TDM technology improves the signal transmission capability of the FPGA prototype system, the system clock frequency is greatly reduced, and the transmission delay among FPGAs is prolonged by a plurality of signals transmitted by the shared channel. In addition, due to the relatively lack of routing resources, portions of the line may bypass the congestion and result in excessively long routing paths, resulting in increased path delays. Current wiring design at the system level is mainly composed of two methods, inter-chip wiring and on-chip wiring. While conventional inter-chip routing is based on integer linear programming and cannot be used for small-scale circuits, the intra-chip routing related method is more focused on TDM ratio distribution, and lacks consideration for inter-chip signal distribution. A good inter-chip routing result directly affects subsequent signal distribution, and thus a routing method that enables collaborative optimization is needed. In summary, the present invention proposes a method for negotiating and distributing FPGA signals supporting dynamic networking to overcome the above-mentioned drawbacks. Disclosure of Invention The invention aims to overcome the defects of the prior art, provides an FPGA signal negotiation distribution method supporting dynamic networking, fully considers the physical topological structure, TDM time sequence constraint and signal connection requirements among FPGAs, and finally reduces signal delay in a collaborative optimization mode by fusing a shortest path algorithm, negotiation wiring and a topology reconstruction mechanism. The method comprises the steps of firstly establishing a graph model of a topology and a logic netlist, constructing an initial wiring scheme through a Floyd algorithm, then introducing PATHFINDER a negotiation wiring mechanism, carrying out iterative optimization based on dynamic cost and critical path analysis, simultaneously combining a topology reconstruction technology, adjusting physical connection resources through three constraint factors, and finally reducing the maximum path delay and improving the wiring quality of a large-scale FPGA system on the premise of meeting various constraints through cooperative optimization of wiring and topology. The invention adopts the following technical scheme for realizing the purposes of the invention: The FPGA signal negotiation distribution method supporting dynamic networking comprises the following steps: Step one, representing a topological structure of a multi-FPGA platform as an undirected weighted graph, representing a segmented logic netlist as a directed hypergraph, and establishing a mapping relation between FPGA nodes and logic nodes; Step two, initial wiring is carried out based on a Floyd shortest path algorithm, shortest paths among all FPGA pairs are calculated, the number of networks on each physical channel is counted, and initial TDM ratio and path delay are calculated; thirdly, using PATHFINDER to negotiate a wiring method, introducing a relaxation ratio and a critical ranking mechanism, performing iterative wiring optimization based on a dynamic cost function, and updating a weight topological graph; step four, identifying physical channels with excessive TDM ratio and severe congestion, reconstructing physical topology through channel adding, deleting and transferring operations, and guiding channel resource allocation based on comprehensive ranking scores of three types of constraint factors; And fifthly, performing the PATHFINDER wiring and the topology reconstruction process in a coordinated manner, and re-distributing signals based on the last round of wiring