A Dynamically Reconfigurable Equi-Joiner on FPGA

As the increase of clock frequencies has slowed, special purpose hardware circuits are becoming increasingly important to accelerate the performance of computing systems. In this context, FPGAs offer advantages over hard-coded ASICs, since FPGAs allow us to use the entire chip to implement optimized algorithms for specific inputs by reconfiguring the circuits at runtime. For example, relational database systems are typically implemented with multiple algorithms for each relational algebraic operation and the one that is expected to process a given query most quickly can be selected as needed. However, previous research on FPGA acceleration for databases has not paid much attention to such algorithm selection. This paper describes an FPGA equi-joiner that switches between two equi-join algorithms, a hash join and a sort-merge join, to fully allocate the FPGA's resources to one algorithm at a time. Our implementation of each algorithm takes advantage of the fact that it can use most of the hardware resources on an FPGA to maximize the size of a key component, a hash table for the hash join and a sort-merge tree for the sort-merge join, which is critical for the join performance. Our experimental results have shown that a simple mathematical model can be used to estimate the execution time of each algorithm for a given data size to select the algorithm appropriately.

By: Takanori Ueda, Megumi Ito, and Moriyoshi Ohara

Published in: RT0969 in 2015


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .