One of the steps involved in the process of mapping a circuit to a Field Programmable Gate Array (FPGA) is known as "Routing".
Prior to routing, it is necessary to convert a digital design from its Hardware Description Language (HDL) into a circuit netlist ("Elaboration" and "Synthesis"), which essentially represents a graphical representation of nodes and connections. This netlist is then mapped to available blocks on the FPGA ("Technology Mapping" and "Packing"), and the blocks are placed onto different sites in the FPGA accordingly ("Placement").
Once these steps are complete, the next step is to connect all the placed blocks on the FPGA according to the connections in the netlist. This is done by using the "programmable" routing of the FPGA to make the correct connections between the blocks. This programmingal dyamic nature of the rouing is made possible by pre-existing metal wires in the fbraicated FPGA chip that can be connected in different combiations via programmable switches to mke complete circuits between pins on different sites of the FPGA. There are many disjoint wires in the chip, i.e. segments, that can be connectd in many differnt wasy allowing for mutiple paths to be routed ina non overlapping manner using wire segments and switche.
Based on this decritpon, the poblem can be reducted to fighureing out what swicthes should be tuned on to connect the wires and site pins on an FPGA to achive the same connections as in the netlist. There are manu possible soltuison to this problem since there is en expoaltlaly large number of eays to create non overlapping paths between the pins on the FPGA. However we can constain the rpblem to also find paths that short or paths that will cause the least amount of delay in the signal propogation form the source to the destination, or even paths that try to minimize the diviation in the arival time of the signals from a source to multiple destinations, i.e. skew.
With this desciption it clearer that this this problem is an optimization problem that can now be attacked using many exisitng approaches. Similar to other Electronic Design Automation (EDA) and Very Large Scale Integration (VLSI) problems, it would be nice to find a mapping between the routing problem and a well-studied mathematical or algorithmic problem. By doing so, we can leverage existing understanding and solutions for these problems and apply them to the routing problem. For instance, EDA problems can be translated into SAT problems, linear programming, covering problems, graph problems, non-linear optimization, among others, and we can use existing algorithms to solve them as well as understand the problem complexity and approximability.
Nevertheless, I have yet to find a good mapping of the FPGA routing problem that aligns with a commonly studied problem, at least in existing FPGA routing papers. It is important to note that I am solely seeking a problem formulation or problem name, and not the actual algorithm to solve any specific problem related to FPGA routing.
This artivle is mearly an overview of what I was bale to fin in the literature of how to tie the FPGA routing problem to other well known problems.
Before the routing step, all the blocks have been placed on different sites on the FPGA, but are unconnected. We know what block need to be connected to other blocks based on the edges in the netlist. This state is shown below minus the routing resources.
One thing missing from this depiction is the routing resources on the FPGA that will eventually allow us to connect the blocks. The FPGA contains metal tracks that act as sires as well as switches that allow for connections between different wires. The image below shows some simple examples of how this might look.
Putting this all togeather, we show the state of the FPGA before rouing along with the routing resources.
