Monterey, Calif. -- Anyone who thinks FPGA synthesis is a solved problem will get a rude awakening at the FPGA 2006 conference here this week. That's when an eminent CAD researcher will show that current synthesis tools may produce circuits that are 70 to 500 times larger than the known optimal solutions in synthetic benchmarks.

Professor Jason Cong, who chairs the computer science department at the University of California at Los Angeles, and his student Kirill Minkovich will present a paper titled "Optimality study of logic synthesis for LUT-based FPGAs," describing how UCLA generated lookup-table-based circuits with known optimal solutions and then compared those solutions with real results from two academic synthesis programs and two commercial tools.

"It was surprising to see the big gap, even though we have worked in this area for over two decades," Cong said. "It indicates that it's definitely worthwhile to look into this topic further. I hope the industry will have more investments [here]."

While the paper shows that FPGA-mapping algorithms can produce close to optimal results, logic optimization--another part of the synthesis process--is a different story. Here, the paper notes, "the best industrial and academic FPGA synthesis flows are around 70 times larger in terms of area on average, and in some cases as much as 500 times larger" than the known optimal solutions in the benchmarks.

Still, Cong quickly noted, the results don't mean commercial synthesis tools are that far off in real designs. "We show a 70x gap in this type of [benchmark] circuit, but that doesn't mean you have 70x in every type of circuit," he said. "Nevertheless, it shows that existing tools and methodologies leave a lot of room on the table."

Representatives of FPGA synthesis providers generally welcomed the research, but cautioned that Cong's synthetic benchmarks are not fully representative of real-world designs. Real FPGAs contain far more than replicated LUTs, they noted, and gate-level logic optimization is just one small part of the RTL-to-silicon design flow.

Cong, who published a similar paper on the optimality of IC placement in 2003, has a strong reputation in the EDA community. In addition to university research, Cong founded APlus Design Technologies, an FPGA physical synthesis company bought by Magma Design Automation Inc. in 2003.

"Jason is one of our top academics," said Gary Smith, chief EDA analyst at Gartner Dataquest. "His research has led to breakthroughs in design technology, and he is one of the leading experts in FPGA design. With credentials like that, his 70- to 500-times claim is not something we can dismiss out of hand."

Time for research
As Cong notes in his paper, many researchers have considered FPGA synthesis to be a solved problem, so relatively few papers have taken a look at it in recent years. In fact, the UCLA study was undertaken when paper co-author Minkovich wanted to pursue some research in FPGA mapping, and Cong was unsure whether such work was actually needed.

It won't be the first time that Cong has shaken up the design automation community. In 2003, Cong published a conference paper that stated that current IC placement algorithms leave so much excess wire that chip designs are essentially several technology generations behind where they could be. That paper, he said, resulted in numerous citations and helped inspire a new round of academic research that reduced the "optimality gap" in IC placement to around 20 percent.

Cong said it's a lot harder to come up with "known optimal" benchmarks for synthesis than placement, given the many transformations that logic networks go through. But FPGAs have one advantage, he said: their reliance on four- and five-input LUTs. Thus, the UCLA researchers only had to come up with known optimal benchmarks for one type of cell.