Improving FPGA Performance for Arithmetic Circuits

Date: 
Tuesday, February 26, 2008 - 10:25am


Philip Brisk
Post Doc in the Processor Architecture Laboratory at EPFL, the Swiss Federal Institute of Technology, Lausanne
DATE: Thursday, Feb 28th
TIME: 3:30 to 4:30
PLACE: CS Conference Room (HFH 1132)

ABSTRACT:
The performance gap between FPGAs and ASICs is exacerbated for arithmetic dominated circuits, compared to control-dominated circuits and finite state machines. One important arithmetic operation for which FPGA performance is lacking is multi-input addition, which occurs in the context of parallel multipliers, video coding, FIR filters, and wireless communications; moreover, multi-input addition can be exposed by a set of well-defined arithmetic transformations, applicable to fairly general classes of arithmetic circuits. It is well-known from computer arithmetic that a compressor tree (e.g., a Wallace or Dadda Tree) is the ideal circuit to implement multi-operand addition; however, due to the peculiar structure of FPGA logic blocks, it has long been thought that trees of carry-propagate adders outperform compressor trees on FPGAs. This talk will summarize nearly 2 years of research at EPFL on efficiently accelerating multi-input addition on FPGAs. Our solutions include: (1) the first software mapping techniques to synthesize a compressor tree on an FPGA that outperforms adder trees; (2) incremental hardware modifications to FPGA logic blocks to make them more amenable to compressor trees; and (3) the Field Programmable Counter Array (FPCA), a programmable compressor tree that can be included in an FPGA or coarse-grained reconfigurable device as a hard IP core. These three approaches respectively yield increasing performance for arithmetic circuits, with increasing hardware complexity. Ideally, one of the two harware-based approaches will be selected for inclusion in the next-generation of high-performance FPGAs.

BIOGRAPHY:
Philip Brisk receive his B.S., M.S., and Ph.D. degrees from UCLA, all in Computer Science, in 2002, 2003, and 2006 respectively. Since 2006, he has been a postdoctoral researchers in the Processor Architecture Laboratory at EPFL, the Swiss Federal Institute of Technology, Lausanne. His research interests include FPGA architecture and mapping algorithms, extensible processor architecture and customization, compilers, and hardware synthesis.