Skeleton Automata for FPGAs: Reconfiguring without Reconstructing

May 3, 2012
Louis Woods | ETH Zurich

While the performance opportunities of field-programmable gate arrays (FPGAs) for high-volume query processing are well-known, system makers still have to compromise between desired query expressiveness and high compilation effort. The cost of the latter is the primary limitation in building efficient FPGA/CPU hybrids. In this talk I will present an FPGA-based stream processing engine that does not have this limitation. It provides a hardware implementation of XML projection that can be reconfigured in less than a micro-second, yet supports a rich and expressive dialect of XPath. By performing XML projection in the network, we can fully leverage its filtering effect and improve XQuery performance by several factors. These improvements are made possible by a new design approach for FPGA acceleration, called skeleton automata. Skeleton automata separate the structure of finite-state automata from their semantics. Since individual queries only affect the latter, with this approach query workload changes can be accommodated fast and with high expressiveness.

Speaker Details

Louis Woods is a third year PhD student in the Systems Group at ETH Zurich. His research interests include FPGAs in the context of modern databases, parallel algorithms, stream processing, and pattern matching. Louis received both his B.S. and M.S. degree in Computer Science from ETH Zurich in 2008 and 2009, respectively. In 2011 he was an intern in the Embedded Systems Group at MSR in Redmond.