TY - GEN
T1 - GPU acceleration of regular expression matching for large datasets
T2 - 2013 ACM International Conference on Computing Frontiers, CF 2013
AU - Yu, Xiaodong
AU - Becchi, Michela
PY - 2013
Y1 - 2013
N2 - Regular expression matching is a central task in several networking (and search) applications and has been accelerated on a variety of parallel architectures, including general purpose multi-core processors, network processors, field programmable gate arrays, and ASIC- and TCAM-based systems. All of these solutions are based on finite automata (either in deterministic or non-deterministic form) and mostly focus on effective memory representations for such automata. More recently, a handful of proposals have exploited the parallelism intrinsic in regular expression matching (i.e., coarse-grained packet-level parallelism and fine-grained data structure parallelism) to propose efficient regex-matching designs for GPUs. However, most GPU solutions aim at achieving good performance on small datasets, which are far less complex and problematic than those used in real-world applications. In this work, we provide a more comprehensive study of regular expression matching on GPUs. To this end, we consider datasets of practical size and complexity and explore advantages and limitations of different automata representations and of various GPU implementation techniques. Our goal is not to show optimal speedup on specific datasets, but to highlight advantages and disadvantages of the GPU hardware in supporting state-of-the-art automata representations and encoding schemes, approaches that have been broadly adopted on other parallel memory-based platforms.
AB - Regular expression matching is a central task in several networking (and search) applications and has been accelerated on a variety of parallel architectures, including general purpose multi-core processors, network processors, field programmable gate arrays, and ASIC- and TCAM-based systems. All of these solutions are based on finite automata (either in deterministic or non-deterministic form) and mostly focus on effective memory representations for such automata. More recently, a handful of proposals have exploited the parallelism intrinsic in regular expression matching (i.e., coarse-grained packet-level parallelism and fine-grained data structure parallelism) to propose efficient regex-matching designs for GPUs. However, most GPU solutions aim at achieving good performance on small datasets, which are far less complex and problematic than those used in real-world applications. In this work, we provide a more comprehensive study of regular expression matching on GPUs. To this end, we consider datasets of practical size and complexity and explore advantages and limitations of different automata representations and of various GPU implementation techniques. Our goal is not to show optimal speedup on specific datasets, but to highlight advantages and disadvantages of the GPU hardware in supporting state-of-the-art automata representations and encoding schemes, approaches that have been broadly adopted on other parallel memory-based platforms.
KW - CUDA
KW - Deep packet inspection
KW - Finite automata
KW - GPGPU
KW - Regular expression matching
UR - http://www.scopus.com/inward/record.url?scp=84879545779&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84879545779&partnerID=8YFLogxK
U2 - 10.1145/2482767.2482791
DO - 10.1145/2482767.2482791
M3 - Conference contribution
AN - SCOPUS:84879545779
SN - 9781450320535
T3 - Proceedings of the ACM International Conference on Computing Frontiers, CF 2013
BT - Proceedings of the ACM International Conference on Computing Frontiers, CF 2013
Y2 - 14 May 2013 through 16 May 2013
ER -