Patoma was described in a paper given at the recent 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 floor planning and mixed-size placement have become a very important problem for design planning, physical prototyping and physical implementation in nanometer-IC designs," Cong told EE Times.

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

Compared with Parquet-2, an academic floor planner 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 floor plan 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) floor planning, which is employed when blocks are soft. Another is a row-oriented block packing (ROB) heuristic, for floor-planning combinations of fixed- and variable-dimension blocks. ZDS and ROB are probably responsible for Patoma's wire-length improvement, said Magma's Riepe.

Patoma was developed in a year's time, with funding support from Semiconductor Research Corp. UCLA has a patent pending on the research. Cong said there was no direct support from EDA companies.