FPGA placement performs poorly: ICCAD

Timing-driven placement algorithms for FPGAs can be as much as 50 percent away from optimal results, according to a paper given at the International Conference on Computer-Aided Design (ICCAD). But the paper found that Xilinx’s commercial placement tool does much better.

Entitled “Optimality and stability study of timing-driven placement algorithms,” the paper was authored by Jason Cong, professor at the University of California at Los Angeles (UCLA), and other UCLA researchers. It’s a follow-on to a controversial paper given at the ASP-DAC conference in Japan in January 2003, where Cong and his colleagues reported that academic and commercial placement algorithms leave excessive wire length on the table.

Wire length, however, is not the only objective for IC placement, so the ICCAD paper looks at the role of placement in performance optimization. It examines two widely-used FPGA timing-driven placement algorithms. One is VPR, based on simulated annealing, and the other is Path, an enhancement to VPR that takes path sharing into account. Finally, it examines Xilinx’ PAR placement engine.

“The highlight is that modern timing-driven placers may perform poorly on certain architectures,” said Cong. “They can be 50 percent away from optimal in the worst case and 30 percent away on average.”

“The positive news is that the Xilinx placer did quite well on their Virtex architectures,” Cong said.

To evaluate the placers, Cong’s team constructed a set of timing-optimal benchmarks. Much of the paper is devoted to showing how this was done. The ASP-DAC paper also used synthetic benchmarks, and approach that raised some questions about how close they are to real circuits.

The ICCAD paper showed that, for FPGAs with a single longest path, the delay produced by VPR and Path was 10 to 18 percent longer than the optimal on average, and from 34 to 53 percent longer in the worst case. With more than five longest paths, delay was 23 percent to 35 percent longer than optimal on average, and from 41 percent to 48 percent longer in the worst case. Path, however, performed better than VPR.

Then the researchers tested the Xilinx PAR placer on a set of 17 synthetic circuits constructed from Microelectronics Center of North Carolina (MCNC) benchmarks. On the average, the delay generated by PAR was only 8.3 percent worse than optimal for solutions without routing, and 4.1 percent worse after routing. In a few cases, PAR did even better than the constructed optimal solutions.

“The results seem to suggest that timing-driven placement algorithms, both net-based and path-based, have room for improvement,” the paper concluded.

– Richard Goering

EE Times