A Reconfigurable Pattern Matching Hardware Implementation Using On-Chip Ram-Based FSM

摘要

The use of synthesizable reconfigurable IP cores has increasingly become a trend in System on Chip (SOC) designs. Such domain-special cores are being used for their flexibility and powerful functionality. The market introduction of multi-featured platform FPGAs equipped with on-chip memory and embedded processor blocks has further extended the possibility of utilizing dynamic reconfiguration to improve overall system adaptability to meet varying product requirements. A dynamically reconfigurable Finite State Machine (FSM) can be implemented using on-chip memory and an embedded processor. Since FSMs are the vital part of sequential hardware designs, the reconfiguration can be achieved in all designs containing FSMs.In this thesis, a FSM-based reconfigurable hardware implementation is presented. The embedded soft-core processor is used for orchestrating the run-time reconfiguration. The FSM is implemented using an on-chip memory. The hardware can be reconfigured on-the-fly by only altering the memory content. The use of a processor for reconfiguration enables SOC designers to utilize both software and hardware capability to achieve reconfiguration. This scheme of reconfigurable hardware implementation is independent of the placement and routing of the hardware on the FPGA. To demonstrate the feasibility of the proposed approach, the Knuth-Morris-Pratt (KMP) algorithm was implemented. A unique way of using memory-based FSM to reconfigure and speed up the KMP search algorithm has been introduced. With the proposed technique, the system can reconfigure itself based on a new incoming pattern and perform a pattern search on a given text without involving a host processor.Data extracted from test cases shows that the proposed approach made the maximum achievable frequency of the design independent of the pattern length. The number of clock cycles required to match the pattern in the worst case is equal to the pattern length plus the text length (O (m+n)).