For some context, Verilog to Routing (VTR) [1] is a framework for open-source FPGA synthesis, implementation, and FPGA architecture exploration/modeling. The core of VTR is Versatile Place and Route, also known as VPR (a little confusing, VPR is part of VTR). The synthesis part is not really the novel part of VPR since it is mainly done by existing tools including `odin`, `yosys`, and `abc`. The exciting part is VPR.
VPR mainly tackles the problems of packing, placement, and routing. Given any netlist (circuits with gates, other components, and wires), how might one map that circuit to the resources on a specific FPGA architecture (with LUTs, FFs, DSPs, Memory) and also route the design using the FPGA's routing resources? These are typically modeled as optimization problems with many ways to approach them.
For example, placement (putting the circuit elements in your circuits onto a resource on the FPGA at a specific location) is done using a simulated annealing optimizer to minimize "the distance between any two placed elements that are connected in my circuit."
Routing is a bit more complex. Given the graph of all the nodes (routing switches, FPGA element inputs, FPGA element outputs) and edges (physical metal wires on the chip die), one can build a routing graph of the entire system (many implementations model the opposite, where nodes are wires and edges are routing switches). Routing your circuit entails finding non-overlapping subgraphs that connect all the nodes that need to be connected (in your circuit, the output from one gate needs to connect to the input of another gate). I believe VTR uses a variation of the "Pathfinder negotiated congestion algorithm."
Finally, what's nice about VTR is that you can define your own custom FPGA architectures that you want to use in the tool. In this architecture description, I can describe all the elements in my FPGA and how they are all laid out in the FPGA grid and how they connect to each other via routing resources. Useful if you are a startup trying to make and sell your own FPGA with it's own architecture and don't want to write your own EDA tools from scratch.
Digging through the C++ source code for VPR is super interesting as to how these high-level optimizations are solved with various solutions. Since most EDA tools are closed-source, you usually never see this, let alone make contributions and experiment with new ideas.
For me personally, I am fascinated by the EDA algorithms themselves that actually implement the designs and solve these hard, messy optimization problems. I feel like the Hacker News community might find the same aspect interesting.
[1]: "VTR 8: High-performance CAD and Customizable FPGA Architecture Modelling": https://dl.acm.org/doi/10.1145/3388617
Edit / Source: I don't work on VTR directly but I use VTR for my own research, parts of my research are in the same field, and I see the students and PIs who work on VTR at same conferences I go to.
to be blunt: nextpnr is what happens when you look at VPR as prior art and base every design decision around doing the opposite of VPR.
VPR is flexible, true: you can define an architecture description inside an XML file, but I view the VPR XML format to be poorly considered.
- commonly in an FPGA you will have "legality constraints" - for example, a block of LUTs cannot simultaneously be in carry-chain mode and act as LUT RAM. to produce a legal solution, all these constraints must be satisfied. to nextpnr this is [two basic](https://github.com/YosysHQ/nextpnr/blob/master/docs/archapi....) [API calls](https://github.com/YosysHQ/nextpnr/blob/master/docs/archapi....). to vpr, you must [walk the architecture](https://github.com/verilog-to-routing/vtr-verilog-to-routing...) to discover and cache legal placement positions. - VPR often requires significantly more detail about an FPGA than is easy to provide; for example, [how switchboxes are laid out](https://docs.verilogtorouting.org/en/latest/arch/reference/#...), or [routing metal resistance/capacitance](https://docs.verilogtorouting.org/en/latest/arch/reference/#...). to nextpnr, routing is just nodes and edges on a graph.
Further, VPR's algorithms tend not to be designed with performance in mind; simulated annealing as a placement method does not scale well past the tens of thousands of LUTs, which is why nextpnr moved from full simulated annealing to [heterogenous analytic placement](https://ieeexplore.ieee.org/document/6339278), and recently we have been working on a [multi-electrostatic placer](https://dl.acm.org/doi/abs/10.1145/3489517.3530568); both significantly more scalable methods based on using mathematical optimisation methods to place things nearby.