On 1/29/08, Terry Hancock <[EMAIL PROTECTED]> wrote: > > Undocumented and proprietary yes, but probably really not that hard > > to figure out. Writing a good synthesizer and dealing with the > > NP-complete problem that is P&R are what are difficult about this. > > Okay, it's a hard problem, but isn't it a *solved* hard problem?
There are no direct solutions to NP-complete problems. And this is demonstrated by the fact that everyone's P&R algorithm sucks in some way or another. We can apply knowledge, randomization, hill-climbing, and other kinds of search to the problem, but there will always be limits to how well we can do. For FOSS, a major obstacle is that the problem isn't interesting enough to enough people, and the results aren't glitzy enough. > Is the > floorplanning algorithm for an FPGA really all that different from the > ones used for PCB-layout? It's completely different. Yes, there are superficial similarities and certainly some deep ones, but the problems are defined in radically different ways. I went into this for one of the interview questions. > Doesn't gEDA or some other project have such > code? Or failing that, at least developers with experience with the > concepts and AI methods used to do it? AI methods are used. > > I was talking with someone who had worked for Lattice, I think, who > > had some good ideas about how to go about this. Sadly, we're both > > too busy to work on it, and finding some people to do the coding for > > us isn't likely to happen. > > Well, if you (or someone) could factor out the problem into the > proprietary interface and the abstract P&R problem, write a spec for > what the P&R system should take as input and what it should produce as > output, that would seem to be the challenging part from a programmer's > perspective. We could start with a simple toy FPGA architecture and target that, keeping in mind that the solution has to be very general so that we can map it to real FPGAs. > If you present programmers with an abstract problem to solve, they're > going to be a lot more likely to help than if you start with "first you > have to buy an FPGA..." Certainly. Like I say, toy FPGA architecture. Something easy to understand and simulate. > This is the flip-side of something Lourens Veen was talking about: > > > If you give a programmer a buggy editor as well as its source, she > > will fix the editor. If you give a hardware developer a buggy > > schematic capture tool, he will find something else to work on. > > You're in the same quandary if the programmer needs specialized hardware > to test her software. Agreed. > If, on the other hand, you can minimize the hardware layer, so that the > complex task happens entirely in a separately-testable piece of > software, then you've got something more feasible. For the initial stage, we can reduce it to zero. But moreover, we can probably develop a simulation of a real FPGA. Within some reasonable degree of precision, we can model all of the gate and wire timings. > I suspect it would also have other uses. As a trivial example, > self-documentation tools could produce *readable* UML diagrams from > code. (HappyDoc could generate UML diagrams from code, but the result is > a kind of rats nest -- you have to spend some time manually moving > things around to make it readable afterwards). I tried to do some diagramming with Umbrello. I couldn't get it to let me describe the architecture in a way that made sense from a hardware perspective. > Anyway, this could be at about the level of a university semester > project, IMHO. Pieces of it could be. A better FPGA P&R algorithm could be a Ph.D. dissertation. -- 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)
