The paper, "Optimality and scalability study of existing placement algorithms," raised a stir when it was delivered last month at the ASP-DAC conference in Japan. Using synthetic benchmarks ranging from 10,000 to 2-million placeable modules, it evaluates three academic placement algorithms along with the commercial QPlace product from Cadence Design Systems Inc.

The results were "quite surprising," said co-author Jason Cong, co-director of the VLSI CAD lab at UCLA. The paper concluded that wire lengths resulting from the placement tools were an average of 1.46 to 2.38 times longer than the optimal solution, and that the wire utilization of the tools deteriorates an additional 4 percent to 25 percent when the size of a design increases by a factor of ten.

If the "optimality gap" in wire length could be closed, Cong said, the benefits would be equivalent to advancing several technology generations. "If you go from aluminum to copper, you get the equivalent of a 30 percent wire length reduction," he said. "If you go through one process of scaling, you get a 30 percent reduction. If we can do this through software optimization, the return on investment is huge."

"There has been a general feeling in the technical community that today's placers and routers are becoming obsolete," said Gary Smith, chief EDA analyst at Gartner Dataquest. "The problem is that there have been so many other technical challenges that they have been put on the back burner."

While looking at placement from the "single perspective" of wire length has some major limitations, Cong's stature in the EDA community gives the paper "instant credibility," Smith said.

"It's surprising to me the results showed there's lots to be gained in terms of improvement, at least for these theoretical examples," said Bill Joyner, director of CAD and test for the Semiconductor Research Corp., which helped fund UCLA's research. "How close these correspond to real examples probably deserves an additional look."

EDA vendors acknowledged that work remains to be done in IC placement. But they said the UCLA paper's synthetic benchmark circuits may not be representative of real-world circuits. And reducing wire length is not nearly as important as improving routability, area and timing, they said.

Chuck Alpert, a member of the technical staff at IBM's research lab in Austin, Texas, also expressed concern about the synthetic benchmarks — some of which are derived from circuits he contributed to the researchers. "The solution space caused by these artificial instances might be very different from the solution space caused by other instances," he said.

Alpert also noted that the examples cited in the UCLA paper don't have pad locations, and he wondered whether results would be the same if they had. "I think, in general, the ideas behind the paper are good, and I believe in the correctness of his [Cong's] assumptions," Alpert said. "I buy into the fact that there's performance on the table. I just don't know if you can quantify something like that."

Quantitative analysis

Cong called the UCLA paper "the first quantitative analysis to study the optimality of placement algorithms." Other studies, he said, have compared placers to each other, but not to an optimal criterion. The reason, to date, has been the difficulty in determining optimum wire length.

That problem was resolved with the synthetic benchmarks, Cong said. "If you give me a [real] circuit, I do not know what the optimal solution is," he said. "However, if I can construct a circuit that looks similar to yours, for that constructed circuit, I know the optimal solution. I can give it to a tool and see how well it does."

That's exactly the approach the UCLA team used to create a series of benchmark examples, using real IBM circuits as a starting point. The benchmarks may be downloaded without charge from a UCLA Web site.

The three academic placers examined by the paper are Dragon, Capo, and mPL. Also studied was QPlace version 5.1.55, as used in Cadence's Silicon Ensemble version 5.3. In general, mPL showed the least divergence from the optimal solution, while Capo showed the most. QPlace's utilization ratio was somewhere in the middle, but it showed the least decrease in quality as designs scaled upwards.

"This is not a negative reflection of the Cadence tool," Cong said. "It compares very well with leading academic placers, which are considered to be leading-edge research."

The researchers did not examine commercial placers from Synopsys, Avanti, Magma or Monterey, but results would "very likely" have been similar, according to Cong. "The [academic] placers we evaluated are considered to be state-of-the-art, and cover most known placement techniques," he said. "It's a good sample of the techniques commonly used in industry."

Not so bad

While voicing respect for Cong, EDA vendors differed with his conclusions. Steven Teig, chief technology officer of Cadence and a well-known placement and routing expert, said the problem identified in the paper may not be much of a problem at all.

"Wire length isn't really the goal of placement," he said. "Commercial placers are trying to make routable chips that work. They need to worry about timing, congestion, and signal integrity — it's not clear they need to worry about wire length at all." Wire length is an issue, he said, only because it "somewhat correlates" with area and congestion.

A second issue is the synthetic benchmarks. "My assessment is that the so-called circuits he [Cong] is generating look very different from real circuits," Teig said.

Nevertheless, "it is certainly reasonable to assume that there are real placement challenges going forward for nanometer design," Teig said. Nanometer-scale designs will call for "floor placement," which will go deeper than floor planning but not all the way to full placement, which will be needed to simultaneously place hundreds of small blocks with standard cells, he said.

"Synopsys has looked at the paper and we are confident that state-of-the-art commercial EDA tools are not leaving wire length on the table to the extent suggested," said a Synopsys spokesman, who declined further comment.

But Steve Sample, vice president of engineering at Monterey Design Systems, had kind words for the paper. "I think it's interesting because [Cong] describes how he prepares the test cases, and does useful comparisons," he said.

"Wire length has a good correlation to routing congestion, so it's important from that point of view," Sample said. "It's important from a timing point of view, because you have to keep things that are timing-critical close to each other. But in itself, it doesn't matter."

Magma Design Automation Inc. has downloaded the benchmark circuits and intends to test them against its own software, said Hamid Savoj, senior vice president of product development at Magma. "I think it is a very interesting paper," he said.

"It definitely seems that the placement tools [Cong] tried are sub-optimal on this set of circuits," Savoj observed. "But these circuits have some unique properties in that the length of every net is optimal. In a real circuit, you can't get every net as short as it can be."

"What we hope is that we can generate a lot of excitement for looking at basic physical design problems," Cong said.

Judging from the attention and controversy generated thus far, the UCLA team has succeeded in that goal.