Dr. Jens Teubner

"Database Algorithms for Next-Generation Hardware"

The rapid move of the computing industry into the "multi-core era" has obsoleted a number of classical system architecture principles. Parallelism, communication, and system diversity have since become key hardware characteristics. Yet, many database algorithms, including many "hardware-optimized" ones, still suffer from outdated assumptions about their underlying hardware. The actual hardware trends demand much more radical changes in algorithm design.
In my talk, I will illustrate how such changes could look like. I will do so based on two examples that are chosen to cover different database problems and different instances of next-generation hardware. First, I will demonstrate a solution to the "frequent item" problem (a classical data mining task) that can leverage the hardware parallelism inherent to field-programmable gate arrays (FPGAs). This solution achieves a more than four-fold performance advantage over existing techniques, even though the task was found hard to parallelize in the literature. The second example assumes a main-stream multi-core system. I will show how a database join operation can be parallelized to efficiently scale with an arbitrary number of CPU cores in such a system. Compared to a state-of-the-art parallel join algorithm, this results in a more than ten-fold throughput improvement with no indication of any scalability limit.
The presented work has been carried out in the context of my "Avalanche" project at ETH Zurich