University of Cambridge > > Microsoft Research Cambridge, public talks > Building Algorithms for FPGAs

Building Algorithms for FPGAs

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity