Common issues

The big picture

FPGA tools cookbook
Conclusions

How to Build an Open Source FPGA Toolchain

Sbastien Bourdeauducq

Milkymist RTC
International Conference on Accelerator and Large Experimental
Physics Control Systems

Open Hardware Workshop

October 9th 2011

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
Instead of developing independent tools, you want to talk FPGA
companies into opening their source code.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
Instead of developing independent tools, you want to talk FPGA
companies into opening their source code.

Solution
They won't. Save your breath and start coding.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You think that FPGA companies do not publish the information
needed to write a toolchain and reverse engineering seems
impossible.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You think that FPGA companies do not publish the information
needed to write a toolchain and reverse engineering seems
impossible.

Solution
Find out that FPGA companies do

publish a lot of information

(netlist documentation, raw chip structure including interconnect,

parts of the timing model). Look closer at the secret Xilinx
bitstream format, it is surprisingly
reverse engineer.

Sbastien Bourdeauducq

straightforward and easy

to

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You do not want to work for free for uncooperative FPGA
companies. Reverse engineering seems to be a waste of time as
FPGA chips may quickly become obsolete.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You do not want to work for free for uncooperative FPGA
companies. Reverse engineering seems to be a waste of time as
FPGA chips may quickly become obsolete.

Solution A
Found your own FPGA startup.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You do not want to work for free for uncooperative FPGA
companies. Reverse engineering seems to be a waste of time as
FPGA chips may quickly become obsolete.

Solution A
Found your own FPGA startup.

Solution B
Bite the bullet and consider that a very large part of the toolchain
infrastructure can be

generic

and

portable

to many FPGA families

 and hopefully to an open one someday.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You are afraid of destroying FPGAs while developing your toolchain.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You are afraid of destroying FPGAs while developing your toolchain.

Solution
Risks of damaging modern FPGAs are

overrated

. Did you

know that temporary internal short circuits occur even with

the regular Xilinx ow?
Test rst on
than $10.

cheap

FPGAs, some are easily available for less

No risk, no fun!

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
Building a FPGA toolchain seems impossibly hard and you don't
know where to begin.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
Building a FPGA toolchain seems impossibly hard and you don't
know where to begin.

Solution

Study

in detail how the existing FPGA toolchains work.

Replace the proprietary tools

compatibility
Perfection is unattainable
with them.

one by one

and consider

. Accept being suboptimal in

many cases (like the proprietary toolchain).

Start with a

very crude

toolchain and improve it later.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You know very well how FPGA toolchains work, and it still seems
too large of a task for you.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Common issues

Problem
You know very well how FPGA toolchains work, and it still seems
too large of a task for you.

Solution
Projects like Linux and GNU have been in the same situation. Start

crude, small and modular

, and adopt an

development model.

Sbastien Bourdeauducq

ecient open source

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

The big picture

Synthesis

Packing

Placement
Routing

Bitstream encoding

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Synthesis

module foo(input clk,

input a, input b,
output x);
always @(posedge clk)
x <= a & b;
endmodule

IBUF[a]

LUT2[1000]

IBUF[b]

FD

OBUF[x]

IBUFG[clk]

Synthesis transforms *HDL sources into a graph of primitives.

It is called the netlist and contains no information about the
physical locations of logic and routes on the chip.
Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

A rather transparent process

Xst netlists in proprietary NGC format can be exported to

human-readable EDIF (ngc2edif).
EDIF netlists can be converted back to NGC and used with all
Xilinx tools (edif2ngc).
Verilog and VHDL netlists (instantiating primitives) can be
extracted from NGC les (netgen).
EDIF and NGC netlists can be viewed in PlanAhead.
Most primitives are documented by Xilinx.
Behavioral Verilog models are published for all primitives
(UNISIM).
A synthesizer should not be harder to write than a C compiler.
Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Why packing?

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Packing challenges

Control set restrictions : some signals (clock, reset, clock

enable) are shared between all basic elements (LUTs,
ip-ops) in the slice.
Primitives packed together should be chosen wisely to reduce
routing delays and maximize performance.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Synthesis
Packing
Placement
Routing
Bitstream format

Common issues
The big picture
FPGA tools cookbook
Conclusions

A simple packing algorithm

Split the input list L of unpacked LUT/FFs into lists L1 ...L ,

according to control sets.

While at least one of L1 ...L

1

new slice

is not empty:

Pick a random LUT/FF from a random list

While

1
2

S.

is not full and

Lx

Lx

and pack it in a

is not empty:

Lx , count the number of inputs it has in

common with the LUT/FFs already packed in S .
For each LUT/FF in

Pick the LUT/FF with the most common inputs and pack it
in

S.

(NB: If there are too few common inputs, we may want

to start a new slice instead)

3

Return the graph of interconnected slices.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Placement

The next step is to place the dierent sites (slices, ...) on

suitable locations on the chip.
For Xilinx, the detailed list of sites is available with

xdl -report <chip>

and FPGA Editor.

Try to minimize routing length/delay.

Since we do not know the routing yet, we have to use a
heuristic.
Example: sum of the Manhattan distances between connected
endpoints.

First approach: place sites arbitrarily, then try to improve

incrementally (hillclimbing).

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

The problem with hillclimbing

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Simulated annealing

Allow some moves that

leaving local minima

increase cost

, to be capable of

Progressively reduce the probability of acceptance of

cost-increasing moves.
Analogy with annealing in metallurgy: reduction of crystal
defects by slow cooling.
The parameter that controls the acceptance of cost-increasing
moves is called temperature.

Paccepted

cost

= e T

if

cost > 0, Paccepted = 1

Sbastien Bourdeauducq

otherwise.

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

A simple placement algorithm

Place all sites randomly.

While the solution is not good enough:
Pick a random move and compute its cost variation (i.e.
dierence in the heuristic function to be optimized).
If

Paccepted (cost , T ) > random(0, 1),

accept the move.

Update the temperature T.

For more details, see for example VPR.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Routing overview

Purpose: establish the connections between the placed sites.

One output

pin of a site drives

one or several input

pins.

Chips contain a network of wires and unidirectional switches

called PIPs (Programmable Interconnect Points) can connect
two wires together.
Site I/Os are permanently attached to special pinwires (on
which PIPs are present to continue routing).

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Synthesis
Packing
Placement
Routing
Bitstream format

Common issues
The big picture
FPGA tools cookbook
Conclusions

Understanding the switch network

All PIPs and wires can be listed with

xdl -report -pips <chip>

Very large text output (1GB for medium-small FPGAs).

regular
structures have equivalent
identify all types

Fully expanded description of a quite

architecture.

Many switching

PIP/wire graphs.

Need to

of switching structures present in a

FPGA family:

smaller factored database

faster tool runtime, less memory utilization
enables interconnect timing models to be built

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

A simple routing algorithm

Ps

While P

= pinwire (source ); Pd = pinwires (destinations );

= {Ps }
1

d 6 R :

w in R , for all PIPs p departing from w

destination(p )
/ R and destination(p ) is available:

For all wires

1
2

R = R {destination(p)}
H [destination(p)] = p

For all pinwires d in P :

= {}
1

c = d;
1
2

with

while

c 6= Ps :

L = L {H [c ]}
c = source (H [c ])

Return the set of PIPs to use L.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

Bitstream format

General structure is regular and sparsely documented.

Site conguration encoding:
Straightforward black-box reverse engineering.
Change with FPGA Editor or

xdl,

examine dierence in

output.

Interconnect conguration encoding:

DRC won't let you turn on individual PIPs.
Crack software to remove this restriction (if possible).
Or use set operations to isolate bits (Debit method).

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Synthesis
Packing
Placement
Routing
Bitstream format

PIP to bit mapping

Simple basic rule: each wire is driven by a single multiplexer

controlled by a 1-hot, 2-hot or 3-hot word.

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

ODIN II, ABC

Academic tools for synthesis, open source licenses.

Only target theoretic architectures.

[Link]

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

VPR

Academic tool for packing, placement and routing. Non-free, but

can serve as inspiration.
Only targets theoretic architectures.

[Link]

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

RapidSmith

Academic software similar to FPGA Editor. Open source but

written in Java.
Based on XDL and can be used with real chip and the proprietary
Xilinx bitstream generator.

[Link]

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

Debit

A pioneering attempt at making sense of the Xilinx bitstream

format.

[Link]

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

ReCoBus tools

ReCoBus has made more thorough bitstream format analyses.

Software is non-free, but very interesting publications.

[Link]

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

Leading an open source project

Linus Torvalds's opinions are generally interesting...

[Link]
Linus-Torvalds-s-Lessons-on
-Software-Development-Management/ba-p/440

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

Conclusion

An open source FPGA toolchain is possible, it just needs some work.

These slides online and more:

[Link]
Thank you for your attention!

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain

Common issues
The big picture
FPGA tools cookbook
Conclusions

Resources
Conclusion
Going further

Going further

Physical implementation

Synthesis
High performance LUT
mappers
Resource sharing
Retiming
FSM extraction
Memory extraction
Carry chains (arithmetic,
comparators, ...)
Multiplier blocks

Timing model
Timing-driven routing
Congestion management
Post-placement packing
Analytical global placers
Relative placement
constraints (e.g. carry
chains)
Floorplanning
Partial reconguration

Let's worry about those later...

Sbastien Bourdeauducq

How to Build an Open Source FPGA Toolchain