Jens Teubner
Louis Woods
ABSTRACT
While the performance opportunities of field-programmable gate arrays field (FPGAs)field 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 work we report on an FPGA-based stream processing engine that does not have this limitation. We provide a hardware implementation of XML projection [14] 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 our approach query workload changes can be accommodated fast and with high expressiveness.
- Mehmet Altnel and Michael J. Franklin. Efficient Filtering of XML Documents for Selective Dissemination of Information. In Proc. of the 26th Int'l Conference on Very Large Data Bases (VLDB), Cairo, Egypt, September 2000. Google Scholar
Digital Library
- Véronique Benzaken, Giuseppe Castagna, Dario Colazzo, and Kim Nguyên. Type-Based XML Projection. In Proc. of the 32nd Int'l Conference on Very Large Data Bases (VLDB), Seoul, Korea, September 2006. Google ScholarDigital Library
- Anders Berglund, Scott Boag, Don Chamberlin, Mary F. Fernández, Michael Kay, Jonathan Robie, and Jérôme Siméon. XML Path Language (XPath) 2.0 (Second Edition), December 2010. W3C Recommendation.Google Scholar
- Shekhar Borkar and Andrew A. Chien. The Future of Microprocessors. Communications of the ACM, 54(5):67--77, May 2011. Google ScholarDigital Library
- Robert S. Boyer and J. Strother Moore. A Fast String Searching Algorithm. Communications of the ACM, 20(10):762--772, October 1977. Google ScholarDigital Library
- Beate Commentz-Walter. A String Matching Algorithm Fast on the Average. In Proc. of the 6th Int'l Colloquium on Automata, Languages and Programming (ICALP), Graz, Austria, July 1979. Google ScholarDigital Library
- IBM WebSphere DataPower SOA Appliance. http://www.ibm.com/software/integration/datapower/. Google ScholarDigital Library
- André DeHon. Balancing Interconnect and Computation in a Reconfigurable Computing Array (or, why you don't really want 100% LUT utilization). In Proc. of the Int'l Symposium on Field Programmable Gate Arrays (FPGA), pages 125--134, February 1999. Google ScholarDigital Library
- Yanlei Diao, Mehmet Altnel, Michael J. Franklin, Hao Zhang, and Peter Fischer. Path Sharing and Predicate Evaluation for High-Performance XML Filtering. ACM Transactions on Database Systems (TODS), 28(4):467--516, December 2003. Google ScholarDigital Library
- Peter Fischer and Jens Teubner. MXQuery with Hardware Acceleration. In Proc. of the 28th Int'l Conference on Data Engineering (ICDE), Arlington, VA, USA, April 2012. Google ScholarDigital Library
- Michael Kay. Ten Reasons Why Saxon XQuery is Fast. IEEE Data Eng. Bull., 31(4):65--74, 2008.Google Scholar
- Christoph Koch, Stefanie Scherzinger, and Michael Schmidt. XML Prefiltering as a String Matching Problem. In Proc. of the 24th Int'l Conference on Data Engineering (ICDE), Cancún, Mexico, April 2008. Google ScholarDigital Library
- Ian Kuon and Jonathan Rose. Measuring the Gap Between FPGAs and ASICs. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 26(2), February 2007. Google ScholarDigital Library
- Amélie Marian and Jérôme Siméon. Projecting XML Documents. In Proc. of the 29th Int'l Conference on Very Large Data Bases (VLDB), Berlin, Germany, September 2003. Google ScholarDigital Library
- Roger Moussalli, Mariam Salloum, Walid A. Najjar, and Vassilis J. Tsotras. Accelerating XML Query Matching through Custom Stack Generation on FPGAs. In Proc. of the 5th Int'l Conference on High-Performance Embedded Architectures and Compilers (HiPEAC), pages 141--155, Pisa, Italy, January 2010. Google ScholarDigital Library
- Roger Moussalli, Mariam Salloum, Walid A. Najjar, and Vassilis J. Tsotras. Massively Parallel XML Twig Filtering Using Dynamic Programming on FPGAs. In Proc. of the 27th Int'l Conference on Data Engineering (ICDE), pages 948--959, Hannover, Germany, April 2011. Google ScholarDigital Library
- Rene Mueller, Jens Teubner, and Gustavo Alonso. Data Processing on FPGAs. Proc. of the VLDB Endowment (PVLDB), 2(1), August 2009. Google ScholarDigital Library
- Netezza. http://www.netezza.com/.Google Scholar
- Matthias Nicola and Jasmi John. XML Parsing: A Threat to Database Performance. In Proc. of the 12th Int'l Conference on Information and Knowledge Management (CIKM), pages 175--178, New Orleans, LA, USA, November 2003. Google ScholarDigital Library
- Mohammad Sadoghi, Martin Labrecque, Harsh Singh, Warren Shum, and Hans-Arno Jacobsen. Efficient Event Processing through Reconfigurable Hardware for Algorithmic Trading. Proc. of the VLDB Endowment (PVLDB), 3(2), September 2010. Google ScholarDigital Library
- Mohammad Sadoghi, Harsh Singh, and Hans-Arno Jacobsen. Towards Highly Parallel Event Processing through Reconfigurable Hardware. In Proc. of the 7th Int'l Workshop on Data Management on New Hardware (DaMoN), Athens, Greece, June 2011. Google ScholarDigital Library
- Albrecht R. Schmidt, Florian Waas, Martin L. Kersten, Michael J. Carey, Ioana Manolescu, and Ralph Busse. XMark: A Benchmark for XML Data Management. In Proc. of the 28th Int'l Conference on Very Large Data Bases (VLDB), pages 974--985, Hong Kong, China, August 2002. Google ScholarDigital Library
- Reetinder Sidhu and Viktor Prasanna. Fast Regular Expression Matching Using FPGAs. In IEEE Symp. on Field-Programmable Custom Computing Machines (FCCM), Rohnert Park, CA, USA, 2001. Google ScholarDigital Library
- Jens Teubner and Louis Woods. Snowfall: Hardware Stream Analysis Made Easy. In Proc. of the 14th Conference on Databases in Business, Technology, and Web (BTW), Kaiserslautern, Germany, March 2011.Google Scholar
- Jan van Lunteren. Searching Very Large Routing Tables in Wide Embedded Memory. In Proc. of the IEEE Global Telecommunications Conference (GLOBECOM'01), volume 3, pages 1615--1619, San Antonio, TX, USA, November 2001.Google Scholar
- Jan van Lunteren, Ton Engbersen, Joe Bostian, Bill Carey, and Chris Larsson. XML Accelerator Engine. In Proc. of the 1st Int'l Workshop on High-Performance XML Processing, New York, NY, USA, May 2004.Google Scholar
- Louis Woods, Jens Teubner, and Gustavo Alonso. Complex Event Detection at Wire Speed with FPGAs. Proc. of the VLDB Endowment (PVLDB), 3(1), September 2010. Google ScholarDigital Library
- Xilinx Inc. 7 Series FPGAs Overview, September 2011.Google Scholar
- Yi-Hua E. Yang, Weirong Jiang, and Viktor K. Prasanna. Compact Architecture for High-Throughput Regular Expression Matching on FPGA. In ACM/IEEE Symp. on Architectures for Networking and Communication Systems (ANCS), pages 30--39, San Jose, CA, USA, November 2008. Google ScholarDigital Library
Index Terms
- Skeleton automata for FPGAs: reconfiguring without reconstructing
Recommendations
XLynx—An FPGA-based XML filter for hybrid XQuery processing
Invited papers issueWhile offering unique performance and energy-saving advantages, the use of Field-Programmable Gate Arrays (FPGAs) for database acceleration has demanded major concessions from system designers. Either the programmable chips have been used for very basic ...
Efficient AES implementations on ASICs and FPGAs
AES'04: Proceedings of the 4th international conference on Advanced Encryption StandardIn this article, we present two AES hardware architectures: one for ASICs and one for FPGAs. Both architectures utilize the similarities of encryption and decryption to provide a high throughput using only a relatively small area. The presented ...
Hardware and software infrastructure to implement many-core systems in modern FPGAs
SBCCI '17: Proceedings of the 30th Symposium on Integrated Circuits and Systems Design: Chip on the SandsMany-core systems are increasingly popular in embedded systems due to their high-performance and flexibility to execute different workloads. These many-core systems provide a rich processing fabric but lack the flexibility to accelerate critical ...
Comments