Multi-Core Architecture on FPGA for Large Dictionary String Matching
Qingbo Wang, Viktor K. Prasanna · 2009
FPGA has long been considered an attractive platform for high performance implementations of string matching. However, as the size of pattern dictionaries continues to grow, such large dictionaries can be stored in external DRAM only. The increased memory latency and limited bandwidth pose new challenges to FPGA-based designs, and the lack of spatial and temporal locality in data access also leads to low utilization of memory bandwidth. In this paper, we propose a multi-core architecture on FPGA to address these challenges. We adopt the popular Aho-Corasick (AC-opt) algorithm for our string matching engine. Utilizing the data access feature in this algorithm, we design a specialized BRAM buffer for the cores to exploit a data reuse existing in such applications. Several design optimization techniques are utilized to realize a simple design with high clock rate for the string matching engine. An implementation of a 2-core system with one shared BRAM buffer on a Virtex-5 LX155 achieves up to 3.2 Gbps throughput on a 64 MB state transition table stored in DRAM. Performance of systems with more cores is also evaluated for this architecture, and a throughput of over 5.5 Gbps can be obtained for some application scenarios.