BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Building Algorithms for FPGAs - Rene Mueller - ETHZ
DTSTART:20100415T090000Z
DTEND:20100415T100000Z
UID:TALK24371@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:*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 FPGAs. In this talk I will il
 lustrate using an algorithm from data mining (Frequent Item Problem) that 
 naïvely porting an algorithm to FPGAs does not immediately result in an i
 mprovement. Performance gains can only be obtained after taking the underl
 ying FPGA computation model into consideration and adapting the algorithm.
 \n\nThe frequent item problem is to identify the most frequent items prese
 nt in a data stream. It represents an important problem that is often foun
 d 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 so
 ftware)\, built on special features of FPGAs:\ncontent-addressable memory 
 and dual-ported BRAM. The second implementation exploits the parallelism o
 f the FPGAs but unfortunately does not scale well to larger instances. Thi
 s is finally solved in the third design which applies a pipelining strateg
 y\, resulting in significant improvements in performance. \n\nOn low-cost 
 FPGA hardware\, the fastest of our designs can outperform the best known r
 esult in software by a factor four. Moreover\, and unlike in software appr
 oaches where performance is directly related to the skew in the data\, the
  high throughput is independent of the skew of the input distribution. Thi
 s additional property is a direct result of the redesign of the algorithm 
 for FPGAs. Having learned about the importance of pipelining we developed 
 "Handshake Join"\, our window-based stream join operator. In the talk I wi
 ll briefly present "Handshake Join" and show that the techniques can be re
 applied in software\, leading to good scalability behaviour in multi-core 
 systems too. \n\n*Biography:* Rene Mueller is a PhD candidate at the Compu
 ter Science Department of ETH Zurich. He is advised by Prof. Gustavo Alons
 o. After an undergraduate degree in electrical engineering\, Rene Mueller 
 obtained a MSc in computer science from ETH Zurich. His area of research i
 s stream processing and hardware acceleration for databases. In his previo
 us work\, he developed SwissQM\, a virtual machine-based query processing 
 platform for wireless sensor networks.\nCurrently\, he is working on autom
 ated compilation of continuous streaming queries into digital hardware cir
 cuits for FPGAs. His research interests further include hardware accelerat
 ion for databases using GPUs and the Cell B.E. processor. \n
LOCATION:Small public lecture room\, Microsoft Research Ltd\, 7 J J Thomso
 n Avenue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR