Impala: Algorithm/Architecture Co-Design for In-Memory Multi-Stride Pattern Matching
Authors:
- 1 February 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 86-98
Abstract
High-throughput and concurrent processing of thousands of patterns on each byte of an input stream is critical for many applications with real-time processing needs, such as network intrusion detection, spam filters, virus scanners, and many more. The demand for accelerated pattern matching has motivated several recent in-memory accelerator architectures for automata processing, which is an efficient computation model for pattern matching. Our key observations are: (1) all these architectures are based on 8-bit symbol processing (derived from ASCII), and our analysis on a large set of real-world automata benchmarks reveals that the 8-bit processing dramatically underutilizes hardware resources, and (2) multi-stride symbol processing, a major source of throughput growth, is not explored in the existing in-memory solutions. This paper presents Impala, a multi-stride in-memory automata processing architecture by leveraging our observations. The key insight of our work is that transforming 8-bit processing to 4-bit processing exponentially reduces hardware resources for state-matching and improves resource utilization. This, in turn, brings the opportunity to have a denser design, and be able to utilize more memory columns to process multiple symbols per cycle with a linear increase in state-matching resources. Impala thus introduces three-fold area, throughput, and energy benefits at the expense of increased offline compilation time. Our empirical evaluations on a wide range of automata benchmarks reveal that Impala has on average 2.7X (up to 3.7X) higher throughput per unit area and 1.22X lower power consumption than Cache Automaton, which is the best performing prior work.Keywords
This publication has 48 references indexed in Scilit:
- Scalable Algorithms for NFA Multi-Striding and NFA-Based Deep Packet Inspection on GPUsIEEE/ACM Transactions on Networking, 2015
- Discovering Motifs in Biological Sequences Using the Micron Automata ProcessorIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015
- Predicting future product performance2013
- A-DFAACM Transactions on Architecture and Code Optimization, 2013
- MS-DFA: Multiple-Stride Pattern Matching for Scalable Deep Packet InspectionThe Computer Journal, 2010
- iNFAntACM SIGCOMM Computer Communication Review, 2010
- A Scalable Architecture For High-Throughput Regular-Expression Pattern MatchingACM SIGARCH Computer Architecture News, 2006
- Hitting the memory wallACM SIGARCH Computer Architecture News, 1995
- Multiple-Valued Minimization for PLA OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- THE ABSTRACT THEORY OF AUTOMATARussian Mathematical Surveys, 1961