Research On Hardware Acceleration For String Pattern Matching

With the development of Internet and Information technology, fast string pattern matching is essential to implementing network content detection, IP address lookup in routers, Internet security and many other desirable services in networks. Recently, some researches focus on how to implement fast and efficient string pattern matching. Along with the improvement of hardware process and the development of FPGA technology, a larger number of studies on how to implement fast string pattern matching with parallel hardware structures have emerged. Different studies and design make great differences between speed, area, cost and flexibility. But in practical application, these implementations can always play key roles in some dedicated field.In this paper, we propose a research of design application specific instruction processor (ASIP) to achieve accelerated string pattern matching purposes. ASIP is a king of special processor designed for specific applications. Making tradeoffs between speed, area, cost and flexibility, the designers customize ASIP to meet the demand of many design goals. So ASIP is becoming more and more popular in embedded applications.ASIP is always specially designed and optimized base on the custom application. The design process is often started from the local, application-based analysis and demand analysis, for which the laws and handling characteristics are summarized and responded. And, design of ASIP should be highly integrated. The compiler should also be designed with the processor for convenient development and easily acceptance by embedded engineers.The research of this paper mainly includeâ‘ Analysis the rule of regular expressions (RE) and Backus-Naur Form's (BNF) syntax.RE and BNF are both syntax for describing the pattern of string matching. REs are a context-independent syntax that can represent a wide variety of character sets and character set orderings, where these character sets are interpreted according to the current locale. Augmented BNF (ABNF) is a modified version of Backus-Naur Form. It balances compactness and simplicity, with reasonable representational power and has been popular among many Internet specifications. Firstly we analysis the rule of RE, ABNF and the law of how they are used for description of string pattern and data structure. Then we define the main functions of modules for our ASIP.â‘¡Define instruction set of string pattern matching processorWe define a set of instructions based on the characteristic of RE and ABNF. This Instruction set include a set of basic instructions and a set of special instructions. The basic instruction set guarantee the processor have the general processing capability and the special instruction set is defined based on the rules of grammar patterns and good at describing the string model rules. By using the special instructions, the code for string pattern matching can be more brief and efficient.â‘¢Research on architecture design of string pattern matching processor and management of memory access.String pattern matching Algorithms implemented on General purpose processors mostly comprised of comparison, judgement, order cycle and branches which cause the processor frequently access to the memory, leading to pipeline bubble and Cache missing, and poor performance of GPP. In order to achieve much greater acceleration on string pattern matching, the design of ASIP should address there problems and give find the solutions. The key modules of ASIP is designed to effectively support the special instruction set, so that the whole operation of the processor can be more suitable for string pattern matching algorithms. In addition, to further enhance the parallelism of instructions, architecture design of multi-core processors are considered. Researches on how to couple muti-cores in order to avoid hardware competition are delivered. Finally, the string matching algorithms always cause frequently memory accessing by either single-core implementation or muti-core implementation. Therefore, appropriate memory management solutions are also important part of the study.Both single-core processor and the dual-core processor are implemented on Field Programmable Gate Arrays(FPGA). The results show that the special features on our ASIP can meet the needs of practical application and can be effective in performance of string pattern matching by comparing with some other GPPs.Main contributions of this paper include:â‘ Today network-based string pattern matching of handling not only need to improve the speed of string pattern matching, but also require flexibility and versatility. In this paper, we propose a research of design ASIP which can take into account both of the requirements mentioned above.â‘¡Through a dedicated ASIP architecture process, we focus on how a customized ASIP is structured and designed from reality, and how to further improve the parallelism of the system and deliver higher performance.â‘¢Some key modules is invented and carefully designed to reduce the frequency of memory access and improve the efficiency of processing. The function and structure of these modules will be useable and helpful for researches in this field.