[HN Gopher] Verilog to Routing
___________________________________________________________________
Verilog to Routing
Author : stefanpie
Score : 82 points
Date : 2023-09-25 15:59 UTC (1 days ago)
(HTM) web link (verilogtorouting.org)
(TXT) w3m dump (verilogtorouting.org)
| tboerstad wrote:
| The animations at the bottom are really fascinating. I wonder if
| it's some kind of simulated annealing algorithm(s)?
| stefanpie wrote:
| That is correct, VPR's placement is done using simulated
| annealing.
|
| See section 8 of this paper
| (https://dl.acm.org/doi/pdf/10.1145/3388617), the originals VPR
| paper
| (https://link.springer.com/chapter/10.1007/3-540-63465-7_226),
| and the source code (https://github.com/verilog-to-routing/vtr-
| verilog-to-routing...) for more details.
| stefanpie wrote:
| 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.
| ZirconiumX wrote:
| full disclosure: I work for YosysHQ, who have an alternative
| open-source place-and-route program -
| [nextpnr](https://github.com/YosysHQ/nextpnr/) - and YosysHQ
| presently has [a grant](https://activities.esa.int/4000141380)
| from ESA on improving nextpnr.
|
| 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 ba
| sic](https://github.com/YosysHQ/nextpnr/blob/master/docs/archap
| i....) [API calls](https://github.com/YosysHQ/nextpnr/blob/mast
| er/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](http
| s://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.
| stefanpie wrote:
| Awesome, thank you for the details and looking froward to the
| work with more funding! I have yet to look into the details
| of nextpnr and this is a great set of of resources for me to
| get started. I am working on some "deep learning for FPGA
| implementation" projects and it would be neat to see if I can
| plug nextpnr into my work. I think (from my point of view),
| VTR is more of a generic architecture exploration tool /
| academic tool with a more top down approach hence the arch
| def files and so on.
| mathisfun123 wrote:
| > full disclosure: I work for YosysHQ
|
| let me take this opportunity to ask a question about
| something that makes absolutely zero sense to me: why did
| yosys insist on sticking with tcl over some more modern/well-
| known/familiar scripting language? yes everyone has their
| favorite tcl scripts for vivado or intel or whatever but none
| of them are transferrable to yosys irrespective of that fact
| that yosys supports tcl.
|
| further more, why is yosys itself basically scripting of ABC
| and nextpnr and etc _using cpp_ instead of again using just
| some reasonable scripting language to connect the pieces?
|
| > multi-electrostatic placer
|
| um why? dreamplace exists?
| https://github.com/limbo018/DREAMPlace
| musicale wrote:
| There are some things I like about tcl (and Tk) but I can't
| imagine choosing a scripting language other than python
| today.
| AshamedCaptain wrote:
| > yes everyone has their favorite tcl scripts for vivado or
| intel or whatever but none of them are transferrable to
| yosys irrespective of that fact that yosys supports tcl.
|
| But still it is much easier to have one Tcl script with
| conditionals targeting all the tools than a myriad scripts
| in various language-of-the-week. Tcl is just good enough,
| and extremely "well known".
| stefanpie wrote:
| I think there is a big difference between published
| academic tools that work on a specific benchmark format
| versus an academic tool that has been integrated into a
| robust EDA toolflow. Also, note that dreamplace is simply
| accelerated electrostatic placement tool using deep
| learning frameworks to take advantage of GPUs.
| Electrostatic placement is not a new concept and is not
| specific to dreamplace.
| msapaydin wrote:
| Does this support Xilinx pynq?
| duck2 wrote:
| This kind of stuff requires access to the complete
| architectural parameters of the device, so adding support for
| even a single device family is a huge reverse-engineering^W
| documentation effort.
|
| See f4pga.readthedocs.io which consolidates pretty much
| everyone's efforts into a distribution, but supports only 4
| device families: iCE40 and ECP5 from Lattice, some 7-series
| devices from Xilinx and EOS-S3 from QuickLogic.
|
| For internal testing, VPR has "Stratix IV-like" and most
| recently "Stratix 10-like" architecture files but these don't
| try to "document" the whole thing, they just want a close
| enough approximation to a modern device to evaluate the tool
| better.
| ZirconiumX wrote:
| I should point out that even the F4PGA page
| [admits](https://f4pga.readthedocs.io/en/latest/how.html)
| that ECP5 and iCE40 support is done through nextpnr, rather
| than VPR.
|
| (actually nextpnr has slowly-maturing support for Lattice
| MachXO{2,3}, Intel Cyclone V and Gowin parts too)
| mathisfun123 wrote:
| support isn't even in the vernacular with these kinds of
| tools:
|
| https://docs.verilogtorouting.org/en/latest/vtr/cad_flow/#vt.
| ..
|
| the question of pynq support is addressed/implicated in
| several places (timing/delay maps, tech mapping, bitstream
| generation).
|
| the short of it: this shit is proprietary/encumbered beyond
| belief.
|
| the medium of it: there are OSS flows that can generate
| bitstreams for pynqs (depending on the actual FPGA part) but
| they are not at all supported by AMD (formerly Xilinx) and
| rely on rev-eng work. the problem is while burning a
| bitstream is important, it's not the only thing you need to
| make OSS worthwhile. in particular you need the timing/delay
| maps and as far as i know, those are all shipped encrypted
| with vivado (and the cracks haven't been released).
___________________________________________________________________
(page generated 2023-09-26 23:01 UTC)