# Research on an Intelligent Test Method for Interconnect Resources in an FPGA
## 3 Building a Test Model  
The focus of modeling is to construct mathematical graph models of the interconnect resources within the FPGAs. In Section 2, we learned that metal interconnect lines are divided into different types of fold lines based on the number of switch matrices they traverse. By observing the driver relationship of the metal interconnect lines in different series of FPGAs, we found that different types of metal interconnect lines exist in different FPGAs, and their drive mapping relationships also differ. Sections of the same type of metal interconnect line and its corresponding port within the same series of FPGAs are grouped together as an X-fold line layer. Thus, a mapping relationship between different fold line layers exists. By treating each fold line layer as a point on a mathematical graph and the directional driver relationship as edges in the graph, we can abstractly convert the interconnect resources of an FPGA into a directed graph. For example, in Figure 4, the different fold line layers can be interpreted as being self-driven; single layers and double layers or single layers and hex layers can drive each other; double layers can drive long layers; hex layers and long-line layers can drive hex layers; and single layers can drive long layers. Figure 4: Schematic diagram of line layer driver. Within each fold line layer, the points on the switch matrix ports, metal interconnect lines, and programmable interconnect lines within the interconnect resources of the FPGA can be treated as points and edges on a mathematical graph. Given the properties of the metal interconnect lines starting at the BEG port and ending at the END port, and the programmable interconnect lines starting at the END port and ending at the BEG port, they can be abstracted into a mathematical graph: G\(<\)V,E\(>\). This is demonstrated in Figure 5, where the solid lines represent the driver relationship of the metal line segments, and the dotted lines represent the driver relationship of the programmable interconnect lines. The graph G\(<\)V,E\(>\) can be divided into two subsets, V\({}_{\text{BEG}}\) and V\({}_{\text{END}}\), where V\({}_{\text{BEG}}\)\(\cap\) V\({}_{\text{END}}\) = \(\emptyset\) and V\({}_{\text{BEG}}\)\(\cup\) V\({}_{\text{END}}\) = V. All edge endpoints in graph G belong to either V\({}_{\text{BEG}}\) or V\({}_{\text{END}}\), and graph G satisfies the definition of a bipartite graph. In this study, we analyze the interconnect relationships of the FPGA's underlying layers by converting them into a bipartite graph. As the connection from the BEG port to the END port is unique and certain, we need to find similar mapping relationships from the END port to the BEG port that form the maximum path during the configuration. The metal interconnect line, M, is a subset of the edges in graph G (excluding the loops), where any two edges in M do not have common vertices. M is a match for graph G, and it represents the maximum number of edges contained in M, saturating all vertices in graph G. Therefore, the metal interconnect line M is a perfect match (maximum match) for graph G. When searching for the maximum path in one configuration, we are also searching for the longest alternating path in graph G.  
As the connectivity of the metal interconnect lines is certain, to reduce the search information in the graph model during the actual processing, we treat a metal interconnect line from the BEG port to the END port as a single point on the mathematical graph. We also consider the programmable interconnect lines between the connecting metal interconnect lines as edges in the mathematical graph, as shown in Figure 6a, which represents the actual connection information of the ports, wires, and PIPs in the FPGA interconnect resources. Figure 6b shows the point-edge information that has been batch processed for ease of the wire routing searches. Figure 5: Abstract schematic diagram of interconnecting lines. Figure 6: Schematic diagram of a switch matrix model.