Open source FPGA place and route


FPGA 'programming' has some commercial parallels to compiling traditional programming languages.
Early on C compilers tended to be vendor-proprietary, CPU architecture specific tools, often expensive and sometimes poor in quality.
Gnu C compiler was (IMO) a mindset-changing product. Eventually CPU manufacturers realised that rather than spend millions on making compilers for their proprietary chips, they could spend a lot less and add a backend to the existing, open-source GCC. Everyone wins.

FPGAs, whilst a slightly different problem, are in the same place that C compilers were. Each of the major FPGA vendors (Xilinx, Altera, Actel/Microsemi etc) provide their own proprietary toolsets to program their own FPGAs. The primary reason they do this is fear of someone pinching their technology. However as the CPU manufacturers found, open source helped them more than any perceived hindrance. Rather than discuss the philosophical issues, we look at the outcomes. Each vendor provides their own toolsets, some of which work with large commercial EDA vendors' products. Each toolset and the programming inputs to those toolsets have their own flavours so whilst VHDL and Verilog are nominally standardised there are lots of practical differences (eg specifying I/O PINs).
There are occasional gestures towards standardisation but only so far that vendors don't feel they are losing vendor lockin.

The Challenge - Open source FPGA toolchain

Why bother?

Well that's a good question but people have been climbing mountains for thousands of years just because they're there. If you don't see the point, that's fine :-)
Beyond that the promise of reconfigurable computing (simply put - dynamically changeable (sub)-circuits) seems to have led to renewed interest in this area. Whilst vendors are starting to support this, doing so requires them to expose more of their FPGA internals than they'd like and demand is probably still quite low in the mainstream. It's easy to change and FPGAs configuration, just load a new bitstream, but doing so is akin to rebooting a computer and selecting a different operating system - it works fine for occasional changes but is a bit clunky for rapid/partial changes.
One thing that makes the effort less worthwhile for many is that the main FGPA vendors provide their toolsets for free (albeit in a somewhat limited form). Having free (although not open source) tools removes the incentive to make one's own.
A professional FPPA engineer with product deadlines wouldn't even consider open source FPGA toolsets in the foreseeable future - and that would be the right decision.

Is it doable?

Possibly, maybe, yes but .... the problem is hard for three broad reasons
  1. the problem of packing, placing and routing efficiently is hard.
  2. each series of FPGAs tends to have a different architecture so there's a lot of effort in adapting a tool to a specific product (much more so than a CPU instruction set)
  3. FPGA vendors keep the innermost details of their FPGAs secret. Reverse engineering these details can be very hard and is 'needless effort'.

Where is the open-source world up to in this problem?

Good question. It's probably fair to say effort is very fragmented and divides into two camps:
  1. Academic research into Place and Route type problems. Tools such as VPR, ROAD etc attempt to solve the problem with imaginary FPGA archiectures. There are occasional attempts to port this work to specific FGPA chipsets (eg VPR on Virtex).
  2. Lower key attempts to manually wire up circuits on specific FPGA architectures. Some examples include:

If you want to go looking for other projects (and some history) keywords include: JBits, JHDL, PyHDL

Many projects have fallen by the wayside because the problem is hard and can't easily be solved by one person or else because the projects have come up against vendor walls (technical and/or legal).

More recently some potentially useful academic driven frameworks have popped up: Torc and OpenPR. Torc provides a generic framework for FPGA programming housekeeping (managing netlists, packing etc). It appears to cover place and route as well but does not yet provide much in the way of solutions there.

The FPGA Process

This needs a pretty diagram but for now the traditional approach is:
HDL -(Synthesis)-> netlist -(Mapping and Packing)-> netlist (maybe) -(Place and Route)-> Bitstream.

Note the following process is performed by all FGPA toolsets, however the steps are theoretical and not always differentiated at a user level. For example some tools might define "Synthesis" to include Mapping and Packing. These steps ignore the ancillary data and other steps such as timing evaluation.

  • Synthesis is the process of converting a high level circuit description (often RTL) into a set of interconnected logic primitives (gates) that can be implemented on a real FPGA (as opposed to Simululation only code for example).
  • Mapping converts generic logic primitives into device specific resources (eg LUTs, MUXes, BRAMs etc)
  • Packing seeks to group and optimise small pieces of logic (closely related in space? logic) to find the best use of FPGA resources (which typically have several Muxes, FlipFlops and Registers in a single FGPA cell).
  • Placement is like high level packing - it decides where to locate each piece of packed logic in the overall FPGA architecture taking into account I/O pin placement, timing constraints and area constraints. Poor placement can lead to unroutable designs and non-functioning circuits (timing constraints violations)
  • Routing implementing the netlists that connected the placed resources. Limited interconnect resources can make routing impossible. The problem is computationally difficult and can involve lots of ripping up and re-routing to find a workable (if not optimal) solution. In some ways the problem is similar to "PCB routing on Veroboard" where the tracks are pre-existent.

Examples of traditional HDLs are VHDL and Verilog.
Examples of netlist formats include EDIF and BLIF.

The steps above are not always performed as a simple one pass process. If the routing step fails it might require us to loop back to redo some of the placement and even the packing step could be reviewed. For example pieces of logic may become co-located and thus benefit from being packed together as a result of placement decisions.

Which HDL ?

Those who program FPGAs professionally probably need a good knowledge of both VHDL and Verilog. If you're just starting out - some free advice - pick Verilog. Such statements can start wars but I think it fair to say Verilog was designed by one or two guys. It's fairly clean, succinct and whilst it has limitations by the time you reach them you'll probably be a professional in the area. VHDL on the other hand was designed by a committee (need I go on) is a lot more verbose and just harder to get right at least for newcomers if not professionals too. It's not just my opinion, I originally thought I should start with VHDL but a number of studies have come to the same conclusion.
Traditional HDLs are not however the be all and end all. They serve a purpose but are not the final point in the evolutionary chain. Some higher-level HDLs have evolved such as SystemVerilog and SystemC amongst others which try and abstract away some of the low=level knowledge required that makes writing complex systems more of a challenge in traditional HDLs. I have not yet played with these systems, SystemC looks interesting but I've been told SystemVerilog is a bit of a dogs breakfast of features - YMMV.

HDL systems are available from vendors and third parties. If however you're looking for open source solutions you need to decide whether you want VHDL or Verilog. I think Verilog tools are more common probably because Verilog is a less complex language. Device whether you want simulation and/or synthesis.
There are several Open Source simulators around with varying benefits (eg performance) - eg GHDL, Icarus Verilog, Verilator, Veriwell etc.
For synthesis though the options become much more limited as synthesis is generally NOT device independent in practice. The only Open Source Verilog tool capable of any form of synthesis is, AFAIK, Icarus Verilog and even then only to a limited degree.

My Project

First of all I should point out I'm not trying to solve the world's FPGA problems, I just want to learn more about FPGAs (the hard way) by trying to put together an end-to-end toolchain for one specific FGPA product (whilst trying to keep things generic where possible).

I chose the Atmel AT40K FPGA architecture for this project. Now this is more-or-less a dead duck in the FPGA world. It's older, lower capacity technology sold by Atmel who have not really demonstrated any interest in promoting or improving the product line or toolsets.
So why did I choose this ? Well I happen to have a development board in my junk box and, more importantly (given development boards can be had for under $100 these days) I know probably 95% of the internal configuration information - so I know enough to program it.
Incidentally Atmel also have version of the FPGA with an AVR micro included which could actually make this product line quite popular in open-source communities should Atmel decide to see wisdom and get on board. Either that or they just kill it off..

Building upon the work of some others I've progressed the reverse engineering of the AT40K FPGA to the point where I can program resources in it as I want.
I use many programming languages, language selection usually depends on the problem domain, but when free to choose I find python far more productive and elegant than most.
I use Icarus Verilog for simulation and synthesis. If you want to try synthesis (produce an EDIF file) you currently need verilog-0.8.* as the verilog-0.9.* tree as broken (and temporarily removed synthesis - hopefully it will be put back at some point in the future)


At the moment I can do the following:
  • Decode AT40k bitstreams, output ASCII configuration information and an SVG floorplan map of FPGA resources.
  • Python API to create EDIF files and parse them back in (it's not full EDIF, just a practical FPGA subset)
  • Simple demo to create an AT40K bitstream that flashes a LED on the development board.
In progress (Dec 2012)
  • Map LPM EDIF to AT40K architecture specific
  • Low level At40k specific library to create AT40k bitstreams
  • Implement A* pathfinder search algorithm to place and route netlists.

Related information:

If enough people are interested I'll release the code repo, but it needs a bit of cleaning up first...
Email me: kim @ domain_name

  • + : A leading plus sign indicates that this word must be present in every object returned.
  • - : A leading minus sign indicates that this word must not be present in any row returned.
  • By default (when neither plus nor minus is specified) the word is optional, but the object that contain it will be rated higher.
  • < > : These two operators are used to change a word's contribution to the relevance value that is assigned to a row.
  • ( ) : Parentheses are used to group words into subexpressions.
  • ~ : A leading tilde acts as a negation operator, causing the word's contribution to the object relevance to be negative. It's useful for marking noise words. An object that contains such a word will be rated lower than others, but will not be excluded altogether, as it would be with the - operator.
  • * : An asterisk is the truncation operator. Unlike the other operators, it should be appended to the word, not prepended.
  • " : The phrase, that is enclosed in double quotes ", matches only objects that contain this phrase literally, as it was typed.


Related Sites