This app demonstrates the well-known FPGA routing algorithm: PathFinder algorithm. Every channel, logic block, and I/O pin is regarded as a node and the FPGA board is regarded as a graph.
PathFinder algorithm is a negotiated congestion algorithm in which the cost of each node varies according to the number of nets using the current node.
The cost of using node is calculated by
Cn = (bn + hn) * pn
where bn is the base cost of using n, hn is related to the history of congestion on n during previous iterations of the global router, and pn is related to the number of other signals presently using node n
Cn = Aij*dn + (1-Aij)*cn
Aij is the slack ratio which calculated by Aij = Dij/Dmax
Dij is the longest path containing the source-destination pair, and Dmax is the maximum delay over all paths
To Use the App
First load a config file (sample is given in the GitHub page), then control the animation using the “VCR” buttons and check-boxes.
If you are interested, here is the source code
Reference
Betz,Vaughn; Rose,Jonathan; Marquardt,Alexander. Architecture and CAD for Deep-Submicron FPGAs. Kulwer Academic Publishers, 1999. Print
McMurchie, C. Ebeling, “PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs,” IEEE FPGA 95’ Proceedings of the Third International ACM Symposium on Field-Programmable Gate Arrays, 1995
Shen, G. Luo “Corolla: GPU-Accelerated FPGA Routing Based on Subgraph Dynamic Expansion,” FPGA’17 Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Pages 105-114, 2017