Title: A Data Stream Processing System for a Multiple Regular Expression Matching using FPGA

Abstract: First, we briefly introduce our work environment for remote FPGA design. Then, we will present an efficient pattern matching over a high-speed data stream using a reconfigurable FPGA (Field Programmable Gate Array). First, we introduce a subclass of regular expressions called linear regular expressions, then, for the subclass, we present a hardware algorithm BPRH (Bit-Parallel Regular expression matching on Reconfigurable Hardware) on an FPGA that performs an efficient string matching based on a pattern matching technique, bit-parallel pattern matching. Then, we give analyses on the complexity of the algorithm. Finally, we show a regular-structured hardware architecture of a data stream processing system that solves a multiple regular expression matching problem on an input stream.

CV: Dr. Shin-ichi Minato is an associate professor of Graduate School of information Science and Technology, Hokkaido University, Sapporo, Japan. His research interests include data structures and algorithms for large-scale combinatorial logic data. E-mail: minato@ist.hokudai.ac.jp . Mr. Yusaku Kaneta is a PhD course student of the same graduate school. E-mail: y-kaneta@ist.hokudai.ac.jp .

Title: High-speed Regular Expression Matching Engine Using Multi-character NFA

Abstract: An approach is presented for high throughput matching of regular expressions by first converting them into corresponding NFAs (Non-deterministic Finite Automata) which are then configured onto a FPGA (Field Programmable Gate Array). The key novel feature is a technique that, for any given regular expressions, constructs an NFA that processes multiple characters per clock cycle. An efficient algorithm is proposed that outputs an NFA which processes twice the number of characters as the input one. A program has been written that implements above ideas to convert regular expressions into NFAs specified in a structural Hardware Design Language, which are then mapped onto a FPGA. Performance is evaluated using regular expressions rule set of “Snort”, which is one of the most popular open source NIDS (Network Intrusion Detection System) software. The results demonstrate the practical utility of the approach.

CV: Mr. Satoshi Kamiya is a research manager of System IP Core Research Laboratories, NEC Corporation. His research interests include network processing, hardware processing engine and network node system. E-mail: kamiya@ak.jp.nec.com .

Title: Hardware Accelerators for Regular Expression Matching and Approximate String Matching

Abstract: This report introduces hardware accelerators for regular expression matching and approximate string matching. The hardware for regular expression matching accepts a subclass of regular expressions, and achieves a high throughput string matching for a wide range of patterns. In addition, since the hardware is pattern-independent, we can update patterns immediately without reconfiguring the hardware. Therefore, it is useful for applications that require quick pattern updating, such as network intrusion detection. The hardware for approximate string matching calculates the edit distance as a degree of similarity between two strings at high speed. Therefore, it accelerates processing for text retrieval in database, analysis of DNA, protein sequences in bioinformatics, and so on.

CV: Dr. Shinobu Nagayama is an assistant professor of Graduate School of Information Sciences, Hiroshima City University, 3-4-1 Ozuka-higashi, Asaminami-ku, Hiroshima 731-3194 Japan. E-mail: naga@hiroshima-cu.ac.jp

Title: The Paradigm Shift of SOC for Information Communication Technology and Applications

Abstract: System on chip (SOC) plays important role as the driving force on the progressing of information and communication technology (ICT) industry. Due to the information convergence, the barrier of the processed data inside the devices for computer, communication and consumer electronics are almost disappeared. This also enables the potential to provide more rich functionalities in an individual devices or products. Many fancy and useful applications, ex. feature-rich phone, smart phone, satisfy the needs of more convenient digital life. On the other hand, the progressing in semiconductor technology continuously goes further not only in More Moore direction with incredible complexity, but also in More than Moore direction with many heterogeneous integration. Those trends imply the paradigm shift for SOC design and industry. The designers need to take care about all the components including: multi-core, sensor & actuator, wireless, SSD, LVLP, embedded software, and interfacing devices. Several concepts on solution-based platform design and open innovation platform will also be addressed during this presentation.

CV: Prof. Liang-Gee Chen is the Distinguished Professor of Department of Electrical Engineering in National Taiwan University. He also serves as Deputy Dean, College of EECS, National Taiwan University, and Co-Director General of National SoC Program. He is IEEE Fellow, the TPC Co-Chair of 2009 IEEE ICASSP and the TPC Co-chair of IEEE ISCAS 2012.