Pathfinder Algorithm composed of two parts: a signal router, which routes one signal at a time using a shortest-path algorithm, and a global router, which calls the signal router to route all signals, adjusting the resource costs in order to achieve a complete routing. The signal router uses a breadth-first search to find the shortest path given a congestion cost and delay for each routing resource. The global router dynamically adjusts the congestion penalty of each routing resource based on the demands signals place on that resource. During the first iteration of the global router there is no cost for sharing routing resources and individual routing resources may be used by more than one signal. However, during subsequent iterations the penalty is gradually increased so that signals in effect negotiate for resources. Signals may use shared resources that are in high demand if all alternative routes utilize resources in even higher demand; other signals will tend to spread out and use resources in lower demand. The global router reroutes signals using the signal router until no more resources are shared. The use of a cost function that gradually increases the penalty for sharing is a significant departure from Nair’s algorithm, which assigns a cost of infinity to resources whose capacity is exceeded.
Realization of algorithm based on .place and .net files from "FPGA Place-and-Route Challenge" from University of Toronto. To visualize routing used OpenGL. To read more: docs or here
In Linux
Run ./build.sh
Required:
cmake
libxmu-dev libxi-dev
freeglut3 freeglut3-dev
In Windows Use CMake application to create MVS project and then compile
./PATHFINDER .place-file .net-file Fvp Fvh Iterations-count