Verilog to Routing
verilogtorouting.org
verilogtorouting.org
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.
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.
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
1.1. It is not "just scripting ABC", but ignoring that. I assume it's because Claire just liked C++. She was historically an embedded/hardware engineer. A lot of them like C++. But I can't read anyone's mind. The project is like, probably 15 years old now (the initial Git checkins from 2013 aren't even full replications of the real history, to my knowledge, which go further back into an ancient SVN server.) What would you have suggested using in 2010? Python with zero static typing and pip?
2. Because actually owning the code you write and ship to your users is a nice and good thing. Dreamplace is a DL-reinforced placer. It's an academic project. Having rode that bull (shipping academic code to production users and then having to rework it again and again), realistically, I'd probably reimplement Dreamplace directly into the codebase if I wanted to ship features to users. No offense but this isn't a SaaS service where the sausage machine is hidden; and most RTL engineers, nor I, want to install some giant annoying shitware ML stack into a python virtualenv to run Nextpnr. Just to be clear, if yosys uses some magical ML reinforcement learning, or doesn't, I don't care. It would be great if it did and it got a bajillion % higher QoR. But I don't want actually using the thing to be a giant pain in the ass.
Most open source software engineering isn't about being Super Epic. It's about meeting users where they are at and handling basic engineering constraints around the project. EDA is no different.
I'm not downplaying the fact that yosys is a logic synthesizer - it's valuable and it's the only one of its kind. But that doesn't change the fact that many of the steps are just piping ABC or nextpnr or whatever and doing it using cpp. See https://github.com/search?q=repo%3AYosysHQ%2Fyosys%20ScriptP.... And like I know this not tangentially but because I tried use yosys but not all of yosys and it was impossible to decompose it.
> No offense but this isn't a SaaS service where the sausage machine is hidden; and most RTL engineers, nor I, want to install some giant annoying shitware ML stack into a python virtualenv to run Nextpnr. Just to be clear, if yosys uses some magical ML reinforcement learning, or doesn't, I don't care. It would be great if it did and it got a bajillion % higher QoR. But I don't want actually using the thing to be a giant pain in the ass.
I'm with you on every instance of this trueism except here, where runtime of the tool is not just important it's absolutely critical for DSE.
> Most open source software engineering isn't about being Super Epic
Again I agree with you in every other instance except here - just like LLVM and gcc can't be just oss, they need to be nuclear weapons grade software in order to have won mindshare (and investment) away from commercial compilers so does yosys.
So you can take me to task for being naive and arrogant but the reality is that the decisions made by yosys prevent further serious investment by anyone that's not playing with toys.
> 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.
First: PYosys exists as Python bindings for Yosys, so you can in fact use a more modern scripting language for this.
Second: even if the Tcl scripts are not transferrable, a lot of our users do still have Tcl experience, and that transfers if nothing else.
But personally? For a lot of tasks you don't need a scripting language. If you want to turn a set of Verilog files into a JSON to pass to nextpnr-ecp5, that's `yosys -p "synth_ecp5 -abc9 -top top -json design.json" *.v` and there is neither Tcl nor Python involved here.
> 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?
Yosys is not simply some scripting around ABC: you need to parse input files, store this in an intermediate representation (RTLIL), elaborate and monomorphise the input structure, perform optimisation and logic minimisation on it; you need to map large structures like memories, hard multipliers and carry chains (ABC can't do that), legalise flop types and only then can you pass the logic to ABC. Once you get that logic from ABC, you need to turn it into cells that tooling recognises.
That the "script passes" we have that most front-end users use are so simple is because the complex logic is packed into neat passes to call.
> > multi-electrostatic placer
> um why? dreamplace exists? https://github.com/limbo018/DREAMPlace
We're aware of DREAMPlace, however: DREAMPlace itself is for ASIC applications, so you'd want to use DREAMPlaceFPGA instead, which is...limited to a simplified Xilinx architecture or whatever partial FPGA Interchange Format support they have. We consider speed a feature, and having to deserialise the target device and netlist into FPGA Interchange Format in the hopes that DREAMPlaceFPGA can understand it is...not fast.
So instead we're working on our own multi-electrostatic placer which can more tightly integrate with nextpnr than something using DREAMPlace[FPGA] could.
Obviously it'd be off-topic to try to discuss your particular needs and use-cases of Yosys here, so feel free to email me at lofty@yosyshq.com.
Indeed I opted to go with vivado instead of yosys (so i'm not an expert) but you're being a little disingenuous; there are absolutely places where yosys is explicitly, manifestly, being used as a scripting harness - you literally have ScriptPass
https://github.com/YosysHQ/yosys/blob/076c5ceb714bc8f20136a8...
and it is indeed used extensively for all of the flows:
https://github.com/search?q=repo%3AYosysHQ%2Fyosys%20ScriptP...
and so in particular, wanting to do synthesis for Xilinx, I was stuck basically commenting various lines in SynthXilinxPass::script
https://github.com/YosysHQ/yosys/blob/076c5ceb714bc8f20136a8...
to experiment with various flows. Now maybe you have/had a better way to do this but I couldn't find it.
Yes, those flows use ScriptPass, because for the most part they are scripts. If they were written in Tcl, then Yosys would need to depend on a Tcl interpreter, and equivalently a Python interpreter for Python. By just using C++ for these scripts which usually only developers need to modify, Yosys does not need to depend on either.
But anyway, if I was going to mess about with the flow that much, I'd start by running `help synth_xilinx`, which outputs a list of all the commands that it calls (more or less; it can't model control flow like a proper language can), and then that can be edited into what I need it to do.
this isn't a bugbear - how should i, a user of yosys, that disagrees with the yosys devs about how the xilinx flow should work, proceed?
> By just using C++ for these scripts which usually only developers need to modify, Yosys does not need to depend on either.
you really don't understand how sequence of parameterized steps and compiled binary don't go together at all? see my first question.
> (more or less; it can't model control flow like a proper language can), and then that can be edited into what I need it to do.
again you're being disingenuous - the help message is right there in that file plain as day for everyone to see and the actual steps in the flows are also plain as day and there is an enormous gap in what can be adjusted and exists.
i feel like i'm taking crazy pills here - there's a reason why scripting interfaces are exposed at all right? i.e., tcl. because users need to be able to disagree/decompose/parameterize etc. and these example flows in yosys are frozen in stone (binary) instead of written as scripts that can be adjusted by users.
There is a scripting engine in yosys called yosys script. It doesn't support logic but if you just want to run some commands it works fine.
There is also some basic TCL script support in yosys but I have never used it. So I can't really comment how well it works.
In addition a pass doesn't have to be inside the yosys tree for it to work. You can load any module at runtime. Sure this is not as quick to do then having a full scripting interface but you can be up and running within a few minutes.
Nothing forces you to use C++ scripting here; Yosys has a shell that you can enter commands in, and it takes via `-s` a file of commands; a script.
That the default scripts are written in C++ to not need dependencies does not mean you also need to write your scripts in C++.
I don't know why you're explaining this to me (I've made contributions to dreamplace). my point is why reinvent a very well-functioning wheel?
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".
Python is a "language of the week"? While absolutely no one uses tcl except EDA.
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.
(actually nextpnr has slowly-maturing support for Lattice MachXO{2,3}, Intel Cyclone V and Gowin parts too)
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).