UC Riverside

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 Prufer sequence generation hardware for streaming XML document. We match the stream with several Prufer sequence blocks obtained from twig queries.