Design is all about getting from where you are to where you want to be. Only you’re not quite sure how you’re going to get there. In fact, you may not even know exactly where you’re going to end up. It’s almost like being Neil Armstrong or, perhaps better yet, Lewis and Clark. Maybe even the early vanguard crossing the land bridge at what is today’s Bering Strait.

If you think about some of the early explorers, it’s not like they mapped out where they were going, entered it in their GPS, and waited for instructions. “Turn left at the big giant humongous floating collection of plastic trash.” They basically took off somewhere, perhaps thinking they knew where they were going. Like India. <snort>. Or they were sure there was a watery way to the West Coast, where uptight Pilgrims could go to catch a cool buzz and some tasty waves, and they followed their noses in an attempt to sleuth it out.

This kind of discovery is almost like a random walk thing. You sail your boat up the coast and poke in here and there to see what’s up. With luck, you come back out without any new hardware having been hurled at you by locals annoyed at your peremptorily declaring their land to be yours. (How do you say “WTF??” in Iroquois?)

This is far from an ideal form of exploration. If you could, you’d go up into space, map everything out, and then chart a route from here to there. Of course, whether King George would have funded a space program is a matter for conjecture.

Imperfect though it be, the random walk process has, over time, given us a good picture of what’s where – with the world’s space programs having brought an unimaginable level of accuracy to our maps. We can still go exploring, but we can now do so with the assurance that here there be no dragons.

It would be nice if we had such a map for designing ICs as well. But the problem is, the landscape keeps changing with each new process node. It’s as if plate tectonics and volcanism were operating on the scale of our lifetimes. Our maps would never be of use since they’d always be out of date. So every time we went someplace new, we’d have to explore again how to get there. And the random walk thing just kinda gets old after a while. You keep turning the ship into this bay and that, hoping that you eventually converge on your destination. Think of it as road trip closure.

And every EDA company has a major goal to accelerate closure. Which means eliminating loops through the system. It’s like trying to get to a barbecue in deepest darkest suburban Silicon Valley. Talk about your exploration nightmare. You can smell the tri-tip, so you know you’re close. You drive in one road, follow it around, and you know you’re on the right track because, as you get closer, the more subtle scent of shrimp wafting off the barbie delights your nose.

And you start to hear the music, and you make one more turn – and you find that you’re stuck in a cul de sac. And not the right one. So you have to go back out and try a different turn somewhere.

And you repeat the process. Hopefully you are able to converge on a steaming primal plate of smoked meats with a side of carbs and a token veggie before the rest of the party has pickled itself in PBR and you’re left to fend for yourself, dipping stale bread into suspicious-looking spinach dip. Think of it as missing the barbecue window. Not good.

Cadence recently announced a new digital flow that attempts to eliminate this back-out-and-loop-through-again thing entirely. They don’t guarantee zero loops, but the fact that they can say it’s possible with a straight face is something.

One of the main contributors to what they do relates to floorplan exploration early on. For a long time, floorplanning has been divorced from the rest of the design process. The tools and engines that were used to decide which floorplans were best were different from those used in actual implementation, so you were kind of guessing, even if in an educated manner. Hopefully the guess was good; if not, you ended up looping back to try something different.

Over the last couple years, floorplanning tools have started leveraging the same power and timing engines as the full-up design tools did, improving the accuracy of the floorplans and reducing somewhat the need for design iterations. But it has still been a manual exploration process.

Manual exploration is a slow affair. The fact that we know all of the coasts of all of the continents so well is not because Magellan manually checked them all out to find the best route; this knowledge represents the accumulated result of countless exploration sorties, far more than any one individual could do. And we know Magellan’s name only because he was the lucky dude that stumbled upon a way to make it all the way around the world.

What would be really nice would be a way to explore far more of the landscape than is possible manually. And this is what Cadence is trying to do with their Auto Floorplan Synthesis, a recently-announced addition to their Encounter system. They use a genetic algorithm that builds floorplans on an unconstrained basis, tests them against the constraints using the implementation power and timing engines, and then swaps DNA between the best floorplans in an attempt to get them even better.

Using such a methodology, here’s how we’d get to our elusive backyard barbecue. We’d deploy five cars going five different ways. They’d each pick random turns to make, and, at a certain point, they’d all call each other and compare notes. Those who could no longer smell the meat would be called back to try something different. Those whose stomachs were growling thanks to the olfactory promise of smoky fatty goodness would share their more useful moves, and everyone would try a different combination of the more promising turns, until someone would finally ring up the others and, between slugs of cheap lager, remark on how good the potato salad is.

It’s not quite so simple in the floorplanning world because the decision on what constitutes the best option isn’t as straightforward as deciding whether the beer is cold and the ribs have a perfect smoke ring. So the tool ranks the floorplans, along with their implications, and the designer makes the call on which of them to trash or implement. The algorithm is apparently very fast and lends itself well to multicore for even faster implementation. They also have a data abstraction model that cuts the amount of data to be manipulated by 100x, further speeding things up.

Had Ferdinand and Isabella had this, they might have dispatched the Nina, Pinta, and Santa Maria in three different directions instead of sending them all to the same (unknown) place. Of course, once one of them finally found their way to the corn on the cob, there would have been no way to let the others know. Except perhaps for a postcard… “Pulque is delicious, wish you were here.”

Link:  Cadence Encounter