Global Sources
EE Times-Asia
Stay in touch with EE Times Asia
EE Times-Asia > EDA/IP

IC floorplanning moves ahead with Patoma

Posted: 16 Mar 2005 ?? ?Print Version ?Bookmark and Share

Keywords:ic floorplanning? design? wire length? placement? prototyping?

A new approach to IC floorplanning is said to reduce wire length while running orders of magnitude faster than previous solutions. If it can be applied successfully on a commercial level, the Patoma algorithm developed at UCLA could help usher in a new generation of IC design-planning and placement tools.

Patoma was described in a paper given at the ASP-DAC conference in Shanghai, China by noted EDA Researcher Jason Cong, professor of computer science at UCLA. Authored by Cong, Michael Romesis and Joseph Shinnerl, the paper was titled "Fast Floorplanning by Look-ahead Enabled Recursive Bipartitioning."

"We consider this a fairly significant development because large-scale floorplanning and mixed-size placement have become a very important problem for design planning, physical prototyping and physical implementation in nanometer-IC designs," Cong said.

Cong said the Patoma algorithm could be applied to commercial design-planning tools and IC placement tools. The improved wire length, he said, can reduce routing congestion and help improve performance, density and power. The faster runtimes will reduce the overall design time and allow more design iterations.

Compared with Parquet-2, an academic floorplanner based on simulated annealing, Patoma claims to run 37 to 824 times faster in benchmarks, while providing a 10 to 20 percent reduction in average wire length. It has not been compared with commercial EDA products.

"This is a good paper with some nice results," said Michael Riepe, member of consulting staff at Magma Design Automation Inc. "Algorithms such as Patoma would probably be applicable to commercial hierarchical chip-planning and prototyping products."

Patoma claims to floorplan any combination of fixed- and variable-shape blocks, given a fixed outline area and a wire-length objective. It constructs legal layouts for every partition block at every level of a top-down hierarchy, eliminating "post hoc" legalization, the UCLA paper states.

"Rather than optimize first and legalize afterward, Patoma legalizes first and then optimizes in a way that always allows it to recover some legal configuration before terminating," said Shinnerl, an assistant researcher at UCLA.

Patoma also claims two new techniques. One is a wire-length-aware, zero-dead-space (ZDS) floorplanning, which is employed when blocks are soft. Another is a row-oriented block packing (ROB) heuristic for floorplanning combinations of fixed- and variable-dimension blocks. ZDS and ROB are probably responsible for Patoma's wire-length improvement, said Magma's Riepe.

- Richard Goering

EE Times

Article Comments - IC floorplanning moves ahead with Pa...
*? You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.

Back to Top