COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Acceleration of streaming applications on FPGAs from high level constructs
by Mitra, Abhishek, Ph.D., University of California, Riverside, 2008, 192; 3341851
Abstract (Summary)

Field Programmable Gate Arrays (FPGA) based Reconfigurable Computing hardware are programmed with specialized Hardware Description Language (HDL). FPGAs are increasingly being made available as co-processors on high-performance computation systems. The generation of HDL from high-level software languages is way too complex for a human developer to handle in a reasonable amount of time due to incompatibilities in the execution paradigm between a traditional CPU and on an FPGA. This error prone process manifests itself as the main impediment to a wider use of reconfigurable platforms in high-performance computing. Compilation frameworks are thus a valuable tool for translating traditional high-level software constructs to HDL for implementation on FPGAs.

This dissertation details how we leverage FPGAs for accelerating PERL Compatible Regular Expressions (PCRE), SNORT Intrusion Detection System (IDS), Common Processing Functions, and XML Filtering, by compiling high-level software language to HDL.

In this dissertation, we detail the implementation of a tool that translates PCRE code into hardware that is mapped to an FPGA. Our compiler generates VHDL code corresponding to the opcodes generated from regular expressions. We have tuned our hardware implementation to utilize an NFA based regular expression engine using greedy quantifiers in much the same way as the software based PCRE engine does.

The SNORT IDS system, incorporates the software based PCRE engine for regular expression matching on the payload. We benchmark the performance of regular expression based rules from SNORT IDS using software only execution on a multi-processor system. We demonstrate the case when 30% or more number of network packets trigger regular expression matching, the software based IDS cannot maintain 10 Gbps throughout, and thus requires hardware acceleration.

Using our PCRE to HDL compilation system, we implement regular expressions from the SNORT ruleset on to the FPGA. These rulesets are organized into one of 16 banks on the FPGA and all operate in parallel. We have implemented more than two hundred PCRE engines based on a plethora of SNORT IDS regular expression rules. These were mapped to the Xilinx Virtex-4 LX200 FPGA on the SGI RASC RC 100 Blade connected to the SGI ALTIX 4700 supercomputing system as a testbed. We obtain an interface throughput of 12.9 GBits/s and a speedup of 353X over software based PCRE execution. We also show that it is possible to scale down the processing related power consumption of an IDS by two orders of magnitude using an FPGA.

In this dissertation we describe software tools as well as an IDS architecture that leverages reprogrammability of FPGA hardware. Our software tools for Configurable System on a Chip (CSoCs) generates the communication interface between the software running on the CPU and a tightly coupled IP core based co-processing system. Our tool generates hardware wrappers for the IP Cores that makes them look like a C function invocation in the source code. We also use our tool to support partial reconfiguration: the same wrapper is used for a multitude of IP Cores and the user selects the core to be invoked in the program.

We also demonstrate an adaptable regular expression based IDS using Virtex-4 LX 200 FPGAs that have been floor-planned for partial reconfiguration. Our novel design allows partial reprogramming across 16 banks of regular expression rule-sets. We implement 448 different regular expressions on two FPGAs and perform multiple partial and full reconfigurations. We measure the throughout of the integrated Field Programmable Gate Array (FPGA) and multiprocessor SGI Altix system with varying number of reconfigurations per minute. The adaptive IDS can provide better than 10 Gbps throughput even with 32 partial reconfigurations per minute.

In this dissertation we demonstrate a four step approach that converts user profiles expressed as XPath queries into HDL, suitable for implementation on FPGA. We convert XPaths to PCRE, cluster them by their common prefixes, compile the PCRE to HDL and finally synthesize and implement them on FPGA. This hardware is usable for XML filtering in pub-sub applications. Our benchmarks reveal orders of magnitude improvement in running time while running XML filtering on FPGA, when compared to the state of the art software based XML filtering systems.

Finally, in this dissertation we demonstrate a FPGA based implementation of Prüfer sequence generation hardware for streaming XML document. We match the stream with several Pr¨ufer sequence blocks obtained from twig queries.

Indexing (document details)
Advisor: Najjar, Walid A.
Commitee: Bhuyan, Laxmi N., Tsotras, Vassilis J.
School: University of California, Riverside
Department: Computer Science
School Location: United States -- California
Source: DAI-B 69/12, Dissertation Abstracts International
Subjects: Electrical engineering, Computer science
Keywords: Acceleration, Architecture, FPGAs, Publish/subscribe, Regular expression, XML
Publication Number: 3341851
ISBN: 978-0-549-97920-3
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy