'Unbelievable' paper cites 90X IC placement speedup

PHOENIX, Ariz. — An IC placement paper described as "unbelievable" by conference organizers — yet credible, because its results can be duplicated — is the talk of this week's International Symposium on Physical Design (ISPD '04) here. The paper, which describes a placement technique that's 97 times faster than a well-known academic placer, could have a profound impact on IC CAD tools.

Part of the irony is the paper's relatively humble origins. It outlines research done for a master's degree thesis at Iowa State University in Ames, Iowa. Natarajan Viswanathan, the former student who presented the paper, wasn't able to get funding to pursue PhD work and is now a CAD engineer at Micron Technology.

The paper describes FastPlace, a flat quadratic placer for large standard cell designs. Benchmarks have shown that it's 13 times faster than the Capo 8.8 placer and 97 times faster than Dragon 2.2.3, with average wirelengths just 1.0 percent and 1.6 percent higher, respectively. Of these two academic placers, Capo is probably closest to commercial IC placement tools in terms of speed.

"It's a remarkable paper that nobody believed," said Chuck Alpert, ISPD '04 chair and research staff member at IBM's Austin Research Laboratory. From the start, he said, the paper was either destined for rejection or for "best paper" status. After reviewers found the results could be verified and replicated, it received the latter.

"FastPlace is an order of magnitude faster than anything seen before," Alpert said. He described it as a "real productivity enhancer" that should have an impact on commercial tools, even though it's currently lacking a few features, such as an ability to handle large blocks.

"It seems unbelievable you can get a 90-fold performance gain with no penalty," said Patrick Groeneveld, ISPD technical program chair and professor at the Technical University of Eindhoven, Holland. Groeneveld, an advisor to Magma Design Automation, noted that commercial placement tools are congestion-driven as opposed to wire length driven like Dragon and Capo. But the techniques described in the paper can be used in the commercial EDA world, he said.

"It's important to have the best placement algorithms for circuit design," Viswanathan said as he presented the paper. "There seems to be significant room for improvement."

Viswanathan developed FastPlace under the direction of Chris Chong-Nuen Chu, assistant professor of electrical and computer engineering at Iowa State University. Viswanathan noted that Chu proposed the idea and was involved in every phase of the project.

FastPlace is based on three techniques, Viswanathan said. First is a "cell shifting" technique to remove cell overlap from the quadratic solution. Second is an iterative local refinement technique that reduces wire length. Third is a hybrid net model that combines traditional "clique" and "star" net models, reducing the number of non-zero entries in the connectivity matrix.

The first stage of FastPlace is an iterative procedure that alternates between global optimization and cell shifting. During cell shifting, the placement region is divided into equal sized bins and the utilization of each bin is determined. Standard cells are shifted around the placement region based on this information.

A second stage refines the placement with iterative local refinement. Here, Viswanathan said, FastPlace looks at cells one by one, and considers moving cells based on wire length and cell density. The final stage of FastPlace is detailed placement, which consists of legalizing the current placement by assigning cells to pre-defined rows and removing any overlap.

Viswanathan tested FastPlace using an IBM benchmark suite described at ISPD in 2002. The suite includes 18 circuits. Tests were run on a 750MHz Sun Sparc2 machine.

ISPD '04, which showcases advancements in IC physical design, runs April 19-21.