[Open-graphics] To develop Free FPGA place and route software?
Timothy Normand Miller
theosib at gmail.com
Sun Sep 30 15:59:50 EDT 2007
I've been doing some research in genetic algorithms, particularly
multiobjective ones (MOEAs). It's given me some ideas about how we
could use that and some heuristic techniques in order to develop our
own P&R algorithms. I'd like to bounce those ideas off of people to
see if I'm going in a sensible direction. I want to make sure I don't
reinvent the wrong wheels or go down the wrong bunny trails.
In order to implement a proof-of-concept, we would need to know a lot
about the logic cell and routing resources of common FPGAs, or at
least a toy FPGA architecture that we could scale up once we got the
basic principles down. So, for instance, I would want to be able to
specify to some helper code that I want to place this gate here and
that gate there, and route between them using the K-th best route.
My main idea is to use domain knowledge as much as possible. However,
especially early in the P&R process, lots of choices have to be made
whose effects we cannot predict until we get there. We can use
heuristics to narrow the list of choices. To be able to "back track,"
when we run into a wall, we can backtrack explicitly, but that would
take huge amounts of memory and require lots of work to be redone over
and over. Rather, I would like to employ some GA techniques for
maintaining (smallish) populations of promising partial solutions.
With a blank slate, almost all gates will be completely unconstrained.
Lacking context, they could go into any compatible cell. However,
the fringe gates, connected to I/O pads and macro cells (RAM blocks,
multipliers, etc.) will have some constraints. Identify all of those.
(We'll find some way to deal with the case where the clock period or
routing resources are so slack that we can't do this.) (BTW, here,
I'm taking inspiration from "essentials first" approaches used by
Abductive Inference machines.) For each gate, give it a slot in a
vector. Each logic cell gets a vector. For each gate, fill its slot
in the vector of each logic cell with a value indicating that gate's
fitness for that cell (accounting for worst-case routing, etc.).
Apply a filter to this "image", reducing fitness for all gates in
areas of greater overlap, giving favor to gates who have tighter
constraints. Then apply another filter that zeros any fitness value
below a certain level (50%, maybe?). Now, using this image,
stochastically generate a population of solutions that have these
gates nailed down in random ways. Next, evaluate each one for its
fitness in a number of different categories, particularly the routing
delays for each gate. Throw out any solutions that are strictly
inferior in all terms. Now, for each population member (individual),
repeat this process. Start with the nailed-down gates and find any
new gates that now have constraints that did not exist before.
Lather, rince, repeat.
Note that for fitness, we should not favor "best routes". What want
to do is find "guaranteed sufficient" routes. If we leave slack now,
it will make it easier to place other gates as the algorithm
progresses. The stochastic assignment may subsume this.
Going in that vein, realize that we are not looking for optimal
solutions. This IS an optimization problem, but only up to the
requirements. Anything better is irrelevant. For any good solution,
there should be many many others that are equally good. By the point
where our constraints are SO tight that there's only one solution or
just a few, we're in the domain of trying to actually SOLVE an
NP-complete problem. We don't want to do that. This is the point
where we go as far as we can and then just report the worst paths so
that the designer can manually alter their design to make it easier to
In other words, our near-term goal is to produce functional Free P&R
tools, not blaze trails in the cutting edge of VLSI. (We can do that
Who's interested in doing this? Am I hitting this too soon? With
OGD1 on the horizon, it may be more sensible to focus our attention on
projects that will generate immediate attention through immediately
Timothy Normand Miller
Open Graphics Project
More information about the Open-graphics