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 route. 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 later.) 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 practical products. -- Timothy Normand Miller http://www.cse.ohio-state.edu/~millerti Open Graphics Project _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
