Building Algorithms for FPGAs

Add to your list(s) Download to your calendar using vCal

• Rene Mueller - ETHZ
• Thursday 15 April 2010, 10:00-11:00
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

Abstract: Field-programmable gate arrays (FPGAs) can provide performance advantages with a lower resource consumption (e.g., energy) than conventional CPUs. Unfortunately, algorithms that work quite well on traditional CPUs cannot be simply ported to FPG As. In this talk I will illustrate using an algorithm from data mining (Frequent Item Problem) that naïvely porting an algorithm to FPG As does not immediately result in an improvement. Performance gains can only be obtained after taking the underlying FPGA computation model into consideration and adapting the algorithm.

The frequent item problem is to identify the most frequent items present in a data stream. It represents an important problem that is often found in data mining. We will look at three design alternatives, each one of them exploiting different FPGA features. The first design is a one-to-one mapping of the Space-Saving algorithm (shown to be the best approach in software), built on special features of FPG As: content-addressable memory and dual-ported BRAM . The second implementation exploits the parallelism of the FPG As but unfortunately does not scale well to larger instances. This is finally solved in the third design which applies a pipelining strategy, resulting in significant improvements in performance.

On low-cost FPGA hardware, the fastest of our designs can outperform the best known result in software by a factor four. Moreover, and unlike in software approaches where performance is directly related to the skew in the data, the high throughput is independent of the skew of the input distribution. This additional property is a direct result of the redesign of the algorithm for FPG As. Having learned about the importance of pipelining we developed “Handshake Join”, our window-based stream join operator. In the talk I will briefly present “Handshake Join” and show that the techniques can be reapplied in software, leading to good scalability behaviour in multi-core systems too.

Biography: Rene Mueller is a PhD candidate at the Computer Science Department of ETH Zurich. He is advised by Prof. Gustavo Alonso. After an undergraduate degree in electrical engineering, Rene Mueller obtained a MSc in computer science from ETH Zurich. His area of research is stream processing and hardware acceleration for databases. In his previous work, he developed SwissQM, a virtual machine-based query processing platform for wireless sensor networks. Currently, he is working on automated compilation of continuous streaming queries into digital hardware circuits for FPG As. His research interests further include hardware acceleration for databases using GPUs and the Cell B.E. processor.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.