FPGA Pathfinder Algorithm

About Algorithm

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

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

How to build

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

Usage

./PATHFINDER .place-file .net-file Fvp Fvh Iterations-count