FPGA Acceleration for the Frequent Item Problem
Publication Details
Title
FPGA Acceleration for the Frequent Item Problem
Authors
Jens Teubner, René Müller, and Gustavo Alonso
Published
Proceedings 26th Int'l Conference on Data Engineering (ICDE), Long Beach, CA, USA, March 2010.
Download
paper (PDF), presentation slides (PDF)
Abstract
Field-programmable gate arrays (FPGAs) can provide performance advantages with a lower resource consumption (e.g., energy) than conventional CPUs. In this paper, we show how to employ FPGAs to provide an efficient and high-performance solution for the frequent item problem.
We discuss three design alternatives, each one of them exploiting different FPGA features, and we provide an exhaustive evaluation of their performance characteristics. 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 FPGAs: content-addressable memory and dual-ported BRAM. The two other implementations exploit the flexibility of digital circuits to implement parallel lookups and pipelining strategies, resulting in significant improvements in performance. On low-cost FPGA hardware, the fastest of our designs can process 80 million items per second―three times as much as the best known result. Moreover, and unlike in software approaches where performance is directly related to the skew factor of the Zipf distribution, the high throughput is independent of the skew of the distribution of the input. In the paper we discuss as well several design trade-offs that are relevant when implementing database functionality on FPGAs. In particular, we look at resource consumption and the levels of data and task parallelism of three different designs.
Publication Log
October 2009
camera-ready for ICDE 2010
June 2009
submission to ICDE 2010 (accepted as full paper)
- submission (PDF)
- reviews (results: accept, accept, accept)