The Design And Implementation Of A Lightweight Automata Processor

With the advent of the information age,we are generating large amounts of data every day.Among them,there are a large amount of unstructured text data,such as network data packets transmitted on the Internet,daily emails sent and received,bio-logical gene sequences,and various log files recorded by computer systems.On the one hand,we may need to monitor the text data in some systems for security purposes.For example,we can perform deep inspections on the received TCP date packets to protect the computer system from intrusion and damage.On the other hand,we can mine valuable information from these text data.For example,by analyzing the log files of a distributed system,we can diagnose recent errors in the system.In these ap-plications,we need to simultaneously search and match many specified patterns in a large-scale character stream,which is called multi-pattern matching.However,CPU and GPU are not suitable for high-performance multi-pattern matching computations.CPU and GPU will generate a large number of unpredictable conditional branches and memory accesses when performing multi-pattern matching computations,which will frequently cause wrong branch predictions and Cache Misses,thereby greatly reducing processing speed and energy efficiency.In order to achieve more efficient multi-pattern matching computations,we designed and implemented a lightweight automata proces-sor LAP based on a domain-specific architecture.This processor can use few hardware resources to achieve high-throughput multi-pattern matching computations.The first work of this thesis is to provide an efficient automata processor design so-lution supporting fast ADFA execution.When performing multi-pattern matching com-putations based on an automata processor,we need to compile the set of regular expres-sions into a corresponding finite automata model,and then generate a binary program that can be recognized by the dedicated processor.Given a set of regular expressions to be matched,if we can generate a binary program with a smaller memory footprint,our automata processor will be able to search for more patterns simultaneously.In order to achieve this goal,we enabled the support for ADFA model(an enhanced DFA model)in LAP.Incremental storage is enabled in ADFA model,which results in effective com-pression of the automata model.Therefore,the binary program generated based on the ADFA model is also very small.However,the processing speed of existing hardware solutions is not satisfactory when running ADFA models.To improve this,we propose two new hardware instructions dedicated to the ADFA model.In order to support these two instructions,we proposed a new hardware architecture for automata processors,and at the same time modified the existing compilation algorithms.Experiments show that compared to another lightweight automata processor UAP,LAP has improved its pro-cessing speed by 32%to 91%when they both running ADFA models.What's more,we designed and implemented a 4-stage stall-free pipeline that can efficiently support the LAP instruction set.We implemented the LAP processor core using Verilog language,and deployed it to Xilinx Artix-7 FPGA at 263 MHz.Experiments also show that due to the utilization of ADFA model and the efficient compilation algorithm,the storage efficiency of LAP's binary program is 8× higher than that of IBM's RegX accelerator and Micron's AP.The second work of this thesis is to provide a complete design of a heterogeneous computing system(LAP_SoC)based on the LAP core and ARM CPUs.The hardware system mainly includes three parts:a general-purpose computing system;a dedicated computing system for multi-pattern matching tasks composed of LAP cores;and DMA hardware controllers responsible for mass data transmission.The system on chip can actually run on the FPGA board and be used to solve the actual multi-pattern matching problem in real life.Not only that,LAP_SoC has a good user interface.We deployed the Linux operating system on the ARM CPU system,and wrote drivers for LAP and DMA controllers in C language.Users only need to have the ability to write C lan-guage to drive the LAP core to perform efficient multi-pattern matching computations.Finally,we deployed the system-on-chip to Zedboard evaluation board.We found that adding a LAP core to Zedboard's dual-core Cortex-A9 processor system can increase the processing throughput for multi-pattern matching tasks by more than 40× while only increasing power consumption by 5%.