# Research on an Intelligent Test Method for Interconnect Resources in an FPGA
## 4 Intelligent Routing Method  
The purpose of the FPGA test configuration is to find the path through which a test stimulus signal passes. Using the modeling process described above, we converted the physical connection relationships in the FPGA interconnect resources into vertex-edge relationships in a mathematical graph. Intelligent wiring is the process of finding a test path. To satisfy the considerations of high test efficiency and low test cost, we need to search for the longest wiring path in the mathematical graph. In this study, an improved depth-first algorithm was used as the intelligent wiring method, with the goal of reaching the leaf node of the searched structure. The traversal process of the depth-first algorithm starts at an unvisited vertex as the starting vertex and walks along the edges of the current vertex to another unvisited vertex. When there are no unvisited vertices, we return to the previous vertex and continue to explore other vertices until all vertices have been visited. This algorithm is simple to execute, but its search strategy is incomplete and has some randomness, which may prevent it from producing the optimal solution. Additionally, in a directed graph, when traversing child nodes, it is necessary to backtrack to the parent node, which may require multiple traversals, thus affecting the traversal efficiency. Furthermore, when processing a large number of data, duplicate paths may also exist. Therefore, this study improves the depth-first algorithm to improve the efficiency of intelligent wiring. The improved algorithm uses memorization during the graph traversal process to record the visited vertices and maintain the longest path value for each vertex. When a previously visited vertex is encountered, the current path is compared with the previously saved longest path value, and the larger value is taken as the new longest path. This improved depth-first algorithm not only reduces the occurrence of duplicate paths but also effectively avoids backtracking in the directed graphs, thereby improving both traversal efficiency and the accuracy of finding the longest wiring path. The algorithm used in this article retains the recursive idea in the depth-first algorithm. When modeling and parameterizing each point, the out-degree (the number of outgoing edges from a vertex) and the traversal flags are added to the original graph dictionary. In the same type of FPGA, the out-degree of each point may be different, but we set it to 1 for all points. When using this improved depth-first algorithm to find the next traversal point, we choose a point with a higher probability of being routable based on a probability model. If the current state is denoted as s and the next state is denoted as s', at a certain moment in time when the state is s, the probability of transitioning to the subsequent state s' after taking action a is:  
\[\mathrm{P}^{a}_{ss^{\prime}}=\mathrm{P}[\mathrm{s}(\mathrm{t}+1)=\mathrm{s}^{ \prime}|\mathrm{s}(\mathrm{t})=\mathrm{s},\mathrm{A}(\mathrm{t})=\mathrm{a}] \tag{1}\]  
In this model, s represents a point in a mathematical graph, s' represents the adjacent points connected to that point, and action a represents the edges connecting them. In practice, there can be multiple s' corresponding to a given s, meaning that the current state can be connected to many other states. We estimate the probability P by utilizing historical trajectory configurations and employing the maximum likelihood estimation method. The probability P is defined as follows:  
\[\mathrm{P}^{a}_{ss^{\prime}}=\frac{\#\text{Selectable path in any state}}{\#\text{ Selectable path to all states S'}} \tag{2}\]  
where i represents the number of available paths in the current state, that is, the out-degree W of the current point.