* Hamilton et al. (2017b) William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017b.  Inductive Representation Learning on Large Graphs. In _Proceedings of NeurIPS ’17_. 1024–1034.
  * Hammond et al. (2011) David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. 2011\.  Wavelets on Graphs via Spectral Graph Theory.  _Applied and Computational Harmonic Analysis_ 30, 2 (2011).
  * Han et al. (2019) Peng Han, Peng Yang, Peilin Zhao, Shuo Shang, Yong Liu, Jiayu Zhou, Xin Gao, and Panos Kalnis. 2019\.  GCN-MF: Disease-Gene Association Identification By Graph Convolutional Networks and Matrix Factorization. In _Proceedings of KDD ’19_. 705–713.
  * He and Niyogi (2003) Xiaofei He and Partha Niyogi. 2003.  Locality Preserving Projections. In _Proceedings of NIPS ’03_. 153–160.
  * Hospedales et al. (2020) Timothy M. Hospedales, Antreas Antoniou, Paul Micaelli, and Amos J. Storkey. 2020.  Meta-Learning in Neural Networks: A Survey.  _CoRR_ abs/2004.05439 (2020).
  * Ivanov and Burnaev (2018) Sergey Ivanov and Evgeny Burnaev. 2018.  Anonymous Walk Embeddings. In _Proceedings of ICML ’18_ , Jennifer G. Dy and Andreas Krause (Eds.), Vol. 80. 2191–2200.
  * Ji et al. (2020) Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. 2020.  A Survey on Knowledge Graphs: Representation, Acquisition and Applications.  _CoRR_ abs/2002.00388 (2020).
  * Jin et al. (2019) Di Jin, Xinxin You, Weihao Li, Dongxiao He, Peng Cui, Françoise Fogelman-Soulié, and Tanmoy Chakraborty. 2019\.  Incorporating Network Embedding into Markov Random Field for Better Community Detection. In _Proceedings of AAAI ’19_. 160–167.
  * Kim et al. (2018) Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang. 2018\.  SIDE: Representation Learning in Signed Directed Networks. In _Proceedings of WWW ’18_. 509–518.
  * Kipf and Welling (2016) Thomas N. Kipf and Max Welling. 2016.  Variational Graph Auto-Encoders. In _Proceedings of NeurIPS ’16 workshop on BDL_.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _Proceedings of ICLR ’17_.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2012\.  ImageNet Classification with Deep Convolutional Neural Networks. In _Proceedings of NeurIPS ’12_. 1106–1114.
  * Lai et al. (2017) Yi-An Lai, Chin-Chi Hsu, Wen-Hao Chen, Mi-Yen Yeh, and Shou-De Lin. 2017.  PRUNE: Preserving Proximity and Global Ranking for Network Embedding. In _Proceedings of NeurIPS ’17_. 5257–5266.
  * Lerer et al. (2019) Adam Lerer, Ledell Wu, Jiajun Shen, Timothée Lacroix, Luca Wehrstedt, Abhijit Bose, and Alexander Peysakhovich. 2019.  PyTorch-BigGraph: A Large-scale Graph Embedding System. In _Proceedings of SysML ’19_.
  * Liao et al. (2018) Lizi Liao, Xiangnan He, Hanwang Zhang, and Tat-Seng Chua. 2018\.  Attributed Social Network Embedding.  _IEEE Trans. Knowl. Data Eng._ 30, 12 (2018), 2257–2270.
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning Entity and Relation Embeddings for Knowledge Graph Completion. In _Proceedings of AAAI ’15_. 2181–2187.
  * Liu et al. (2019) Ninghao Liu, Qiaoyu Tan, Yuening Li, Hongxia Yang, Jingren Zhou, and Xia Hu. 2019\.  Is a Single Vector Enough?: Exploring Node Polysemy for Network Embedding. In _Proceedings of KDD ’19_. 932–940.
  * Ma et al. (2018) Jianxin Ma, Peng Cui, and Wenwu Zhu. 2018.  DepthLGP: Learning Embeddings of Out-of-Sample Nodes in Dynamic Networks. In _Proceedings of AAAI ’18_. 370–377.
  * Marino et al. (2017) Kenneth Marino, Ruslan Salakhutdinov, and Abhinav Gupta. 2017\.  The More You Know: Using Knowledge Graphs for Image Classification. In _Proceedings of CVPR ’17_. 20–28.
  * Mikolov et al. (2013a) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a.  Efficient Estimation of Word Representations in Vector Space. In _Proceedings of ICLR ’13_.
  * Mikolov et al. (2013b) Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. 2013b.  Distributed Representations of Words and Phrases and their Compositionality. In _Proceedings of NeurIPS ’13_. 3111–3119.
  * Morin and Bengio (2005) Frederic Morin and Yoshua Bengio. 2005.  Hierarchical Probabilistic Neural Network Language Model. In _Proceedings of AISTATS ’05_.
  * Narayanan et al. (2017) Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. 2017.  graph2vec: Learning Distributed Representations of Graphs.  _CoRR_ abs/1707.05005 (2017).  http://arxiv.org/abs/1707.05005
  * Ni et al. (2018) Jingchao Ni, Shiyu Chang, Xiao Liu, Wei Cheng, Haifeng Chen, Dongkuan Xu, and Xiang Zhang. 2018.  Co-Regularized Deep Multi-Network Embedding. In _Proceedings of WWW ’18_. 469–478.
  * Page et al. (1998) Larry Page, Sergey Brin, R. Motwani, and T. Winograd. 1998\.  The PageRank Citation Ranking: Bringing Order to the Web.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  DeepWalk: online learning of social representations. In _Proceedings of KDD ’14_. 701–710.
  * Perozzi et al. (2017) Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. 2017.  Don’t Walk, Skip!: Online Learning of Multi-scale Network Embeddings. In _Proceedings of ASONAM ’17_. 258–265.
  * Qiu et al. (2018) Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018\.  Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In _Proceedings of WSDM ’18_. 459–467.
  * Qu et al. (2017) Meng Qu, Jian Tang, Jingbo Shang, Xiang Ren, Ming Zhang, and Jiawei Han. 2017\.  An Attention-based Collaboration Framework for Multi-View Network Representation Learning. In _Proceedings of CIKM ’17_. 1767–1776.
  * Ribeiro et al. (2017) Leonardo Filipe Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. 2017.  _struc2vec_ : Learning Node Representations from Structural Identity. In _Proceedings of KDD ’17_. 385–394.
  * Rossi et al. (2018) Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2018.  Deep Inductive Network Representation Learning. In _Proceedings of WWW ’18_. 953–960.
  * Rozemberczki et al. (2019) Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles A. Sutton. 2019.  GEMSEC: graph embedding with self clustering. In _Proceedings of ASONAM ’19_. 65–72.
  * Rozemberczki and Sarkar (2020) Benedek Rozemberczki and Rik Sarkar. 2020.  Fast Sequence-Based Embedding with Diffusion Graphs.  _CoRR_ abs/2001.07463 (2020).  arXiv:2001.07463 https://arxiv.org/abs/2001.07463
  * Shang et al. (2019) Chao Shang, Yun Tang, Jing Huang, Jinbo Bi, Xiaodong He, and Bowen Zhou. 2019\.  End-to-End Structure-Aware Convolutional Networks for Knowledge Base Completion. In _Proceedings of AAAI ’19_. 3060–3067.
  * Sun et al. (2017) Bing-Jie Sun, Huawei Shen, Jinhua Gao, Wentao Ouyang, and Xueqi Cheng. 2017.  A Non-negative Symmetric Encoder-Decoder Approach for Community Detection. In _Proceedings of CIKM ’17_. 597–606.
  * Sun et al. (2019b) Fan-Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wei Huang, and Jian Tang. 2019b.  vGraph: A Generative Model for Joint Community Detection and Node Representation Learning. In _Proceedings of NeurIPS ’19_. 512–522.
  * Sun et al. (2019c) Yiwei Sun, Suhang Wang, Tsung-Yu Hsieh, Xianfeng Tang, and Vasant G. Honavar. 2019c.  MEGAN: A Generative Adversarial Network for Multi-View Network Embedding. In _Proceedings of IJCAI ’19_. 3527–3533.
  * Sun et al. (2019a) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019a.  RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In _Proceedings of ICLR ’19_.
  * Szegedy et al. (2013) Christian Szegedy, Alexander Toshev, and Dumitru Erhan. 2013\.  Deep Neural Networks for Object Detection. In _Proceedings of NeurIPS ’13_. 2553–2561.
  * Tang et al. (2015a) Jian Tang, Meng Qu, and Qiaozhu Mei. 2015a.  PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks. In _Proceedings of KDD ’15_. 1165–1174.
  * Tang et al. (2015b) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015b.  LINE: Large-scale Information Network Embedding. In _Proceedings of WWW ’15_. 1067–1077.
  * Trivedi et al. (2019) Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. 2019.  DyRep: Learning Representations over Dynamic Graphs. In _Proceedings of ICLR ’19_.
  * Tsitsulin et al. (2018) Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. 2018.  VERSE: Versatile Graph Embeddings from Similarity Measures. In _Proceedings of WWW ’18_. 539–548.
  * Tu et al. (2018) Ke Tu, Peng Cui, Xiao Wang, Philip S. Yu, and Wenwu Zhu. 2018.  Deep Recursive Network Embedding with Regular Equivalence. In _Proceedings of KDD ’18_. 2357–2366.
  * Tu et al. (2019) Ke Tu, Jianxin Ma, Peng Cui, Jian Pei, and Wenwu Zhu. 2019.  AutoNE: Hyperparameter Optimization for Massive Network Embedding. In _Proceedings of the 25th ACM SIGKDD ’19_. 216–225.
  * Velickovic et al. (2018) Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks. In _Proceedings of ICLR ’18_.
  * Wang et al. (2016) Daixin Wang, Peng Cui, and Wenwu Zhu. 2016.  Structural Deep Network Embedding. In _Proceedings of KDD ’16_. 1225–1234.
  * Wang et al. (2018) Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. 2018\.  GraphGAN: Graph Representation Learning With Generative Adversarial Nets. In _Proceedings of AAAI ’18_. 2508–2515.
  * Wang et al. (2017b) Suhang Wang, Jiliang Tang, Charu C. Aggarwal, Yi Chang, and Huan Liu. 2017b.  Signed Network Embedding in Social Media. In _Proceedings of SDM ’17_. 327–335.
  * Wang et al. (2017a) Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. 2017a.  Community Preserving Network Embedding. In _Proceedings of AAAI ’17_. 203–209.
  * Wang et al. (2019) Zekai Wang, Hongzhi Liu, Yingpeng Du, Zhonghai Wu, and Xing Zhang. 2019.  Unified Embedding Model over Heterogeneous Information Network for Personalized Recommendation. In _Proceedings of IJCAI ’19_. 3813–3819.
  * Wei et al. (2020) Wenqi Wei, Qi Zhang, and Ling Liu. 2020.  DLForecast: Deep Spatiotemporal Forecasting on Bitcoin Transactions.  _under the submission of IEEE Trans. Emerging Topics Comput._ (2020).
  * Wu et al. (2019a) Jun Wu, Jingrui He, and Jiejun Xu. 2019a.  DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification. In _Proceedings of KDD ’19_. 406–415.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2016.  Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.  _CoRR_ abs/1609.08144 (2016).
  * Wu et al. (2019b) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2019b.  A Comprehensive Survey on Graph Neural Networks.  _CoRR_ abs/1901.00596 (2019).
  * Xu et al. (2019) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019\.  How Powerful are Graph Neural Networks?. In _Proceedings of ICLR ’19_.
  * Yang et al. (2015) Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. 2015.  Network Representation Learning with Rich Text Information. In _Proceedings of IJCAI ’15_. 2111–2117.
  * Yang and Yang (2018) Shuang Yang and Bo Yang. 2018.  Enhanced Network Embedding with Text Information. In _Proceedings of ICPR ’18_. 326–331.
  * Yu et al. (2018) Adams Wei Yu, David Dohan, Minh-Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V. Le. 2018.  QANet: Combining Local Convolution with Global Self-Attention for Reading Comprehension. In _Proceedings of ICLR ’18_.
  * Yu et al. (2019) Lei Yu, Qi Zhang, Donna Dillenberger, Ling Liu, Calton Pu, Ka Ho Chow, Mehmet Emre Gursoy, Stacey Truex, Hong Min, Arun Iyengar, and Gong Su. 2019.  GRAHIES: Multi-Scale Graph Representation Learning with Latent Hierarchical Structure. In _Proceedings of CogMI ’19_. 8–15.
  * Yuan et al. (2013) Pingpeng Yuan, Pu Liu, Buwen Wu, Hai Jin, Wenya Zhang, and Ling Liu. 2013.  TripleBit: a Fast and Compact System for Large Scale RDF Data.  _Proc. VLDB Endow._ 6, 7 (2013), 517–528.
  * Zhang et al. (2018c) Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. 2018c.  SINE: Scalable Incomplete Network Embedding. In _Proceedings of ICDM ’18_. 737–746.
  * Zhang and Chen (2018) Muhan Zhang and Yixin Chen. 2018.  Link Prediction Based on Graph Neural Networks. In _Processings of NeurIPS ’18_. 5171–5181.
  * Zhang et al. (2019) Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay. 2019.  Bayesian Graph Convolutional Neural Networks for Semi-Supervised Classification. In _Proceedings of AAAI ’19_. 5829–5836.
  * Zhang et al. (2018a) Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu. 2018a.  Arbitrary-Order Proximity Preserved Network Embedding. In _Proceedings of KDD ’18_. 2778–2786.
  * Zhang et al. (2018b) Zhen Zhang, Hongxia Yang, Jiajun Bu, Sheng Zhou, Pinggang Yu, Jianwei Zhang, Martin Ester, and Can Wang. 2018b.  ANRL: Attributed Network Representation Learning via Deep Neural Networks. In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden_. 3155–3161.
  * Zhou et al. (2019) Fan Zhou, Zijing Wen, Goce Trajcevski, Kunpeng Zhang, Ting Zhong, and Fang Liu. 2019\.  Disentangled Network Alignment with Matching Explainability. In _Proceedings of INFOCOM ’19_. 1360–1368.
  * Zhou and Fan (2019) Jingya Zhou and Jianxi Fan. 2019.  TransLink: User Identity Linkage across Heterogeneous Social Networks via Translating Embeddings. In _Proceedings of INFOCOM ’19_. 2116–2124.
  * Zhou et al. (2018) Le-kui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. 2018.  Dynamic Network Embedding by Modeling Triadic Closure Process. In _Proceedings of AAAI ’18_. 571–578.
  * Zhu et al. (2019) Zhaocheng Zhu, Shizhen Xu, Jian Tang, and Meng Qu. 2019\.  GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding. In _Proceedings of WWW ’19_. 2494–2504.


#  Deterministic vs. Non Deterministic Finite Automata in Automata Processing

Farzana Ahmed Siddique, Tommy James Tracy II, Nathan Brunelle, Kevin Skadron
University of Virginia
{farzana, tjt7a, njb2b<EMAIL_ADDRESS>
###### Abstract

Linear-time pattern matching engines have seen promising results using Finite
Automata (FA) as their computation model. Among different FA variants,
deterministic (DFA) and non-deterministic (NFA) are the most commonly used
computation models for FA-based pattern matching engines. Moreover, NFA is the
prevalent model in pattern matching engines on spatial architectures. The
reasons are: i) DFA size, as in #states, can be exponential compared to
equivalent NFA, ii) DFA cannot exploit the massive parallelism available on
spatial architectures. This paper performs an empirical study on the #state of
minimized DFA and optimized NFA across a diverse set of real-world benchmarks
and shows that if distinct DFAs are generated for distinct patterns, #states
of minimized DFA are typically equal to their equivalent optimized NFA.
However, NFA is more robust in maintaining the low #states for some
benchmarks. Thus, the choice of NFA vs. DFA for spatial architecture is less
important than the need to generate distinct DFAs for each pattern and support
these distinct DFAs’ parallel processing. Finally, this paper presents a
throughput study for von Neumann’s architecture-based (CPU) vs. spatial
architecture-based (FPGA) automata processing engines. The study shows that,
based on the workload, neither CPU-based automata processing engine nor FPGA-
based automata processing engine is the clear winner. If #patterns matched per
workload increases, the CPU-based automata processing engine’s throughput
decreases. On the other hand, the FPGA-based automata processing engine lacks
the memory spilling option; hence, it fails to accommodate an entire automata
if it does not fit into FPGA’s logic fabric. In the best-case scenario, the
CPU has a 4.5x speedup over the FPGA, while for some benchmarks, the FPGA has
a 32,530x speedup over the CPU.

##  I Introduction

Pattern matching is essential in many applications, including genomics, virus
detection, network intrusion detection, and machine learning techniques such
as random forest. Most of these applications are latency-sensitive. If the
pattern matching rate is not fast enough, it acts as a performance bottleneck
for those applications. Finite Automata (FA) have proven to be a great
computation model for linear time pattern matching [1, 2, 3, 4, 5]. For
example, Schulz et al. used FA to accelerate the pattern matching for genomics
applications [6]. On the other hand, network devices such as the Cisco family
of security appliances and networking software such as Snort [7] use regular
expressions to represent safe payload patterns; prior works have used FA to
accelerate regexes [2, 1].

FA has different variants. The most commonly used FA variants in pattern
matching engines are 1. Deterministic Finite Automata (DFA) and 2. Non-
deterministic Finite Automata (NFA). Even though both of the variants are
functionally equivalent, their structure (state count & transition) differs
[8]. As a result, while designing an FA-based pattern matching engine, the
underlying hardware architecture influences the selection between NFA and DFA.
NFA is less preferred for von Neumann architecture because the possibility of
multiple active states leads to multiple random memory lookups, and high
memory latency is a performance bottleneck in von Neumann’s architecture [9].
Micron’s Automata Processor [10] and spatial architectures, such as Field
Programmable Gate Arrays (FPGA), offer workarounds to hide the high memory
latency. For these architectures, NFA is a popular choice over DFA [2, 5, 11]
for several reasons. The crucial one is if an NFA has $n$ states, its
equivalent DFA can have $2^{n}$ states [12, 8]. For instance, Yu et al. [13]
stated that 20% of the Snort [7] DFAs suffer from exponential state growth
relative to the corresponding NFAs. Moreover, prior works show that generating
one DFA from a set of patterns could result in an enormous time and space
overhead [13, 14].

There are algorithms [15, 16] to generate minimized DFAs for which state count
is smaller than the expected exponential growth (although exponential growth
remains a worst-case for arbitrary automata). Tabakov et al. [17] performed a
study on synthetic automata and illustrated that based on the automata
structure, DFA states exhibit a growth rate of the order polynomial to sub-
exponential compared to the NFA, and in some cases, minimized DFAs have a
smaller state count than the equivalent non-optimized NFA. Motivated by their
study, this paper fills a very important gap in automata processing work. Our
paper demonstrates the state count analysis of the minimized DFA and its
equivalent optimized NFA using a broad set of real-world benchmarks. The
analysis shows that for the real-world benchmarks, the DFA state count
exhibits linear or polynomial growth. Therefore, DFAs can be considered a
viable alternative to any FA-based pattern matching engine that uses NFA as
the computation model. Please note that unlike prior work [17], NFAs used in
this analysis are optimized using a heuristics-based approach.

Another reason for choosing NFA over DFA while designing FA-based pattern
matching engines on FPGAs is that NFAs may activate multiple states per symbol
cycle, which exploits FPGAs’ massive parallelism [18, 19, 11, 2]. However,
this paper shows that DFAs can also exploit the parallel architecture of the
FPGAs if, instead of creating a single large DFA for all the patterns of an
application, separate DFAs are generated for distinct patterns, and these DFAs
are processed in parallel (section IV).

Finally, this paper presents another interesting finding: the state-of-the-art
CPU-based automata processing engine, Hyperscan [20] sometimes outperforms the
state-of-the-art FPGA-based automata processing engine, Grapefruit, in terms
of throughput (pattern matching rate). Even though FPGAs offer massive
parallelism, FPGAs’ clock rate is considerably lower than CPUs. On top of
that, applications face performance degradation if the computation model does
not fit into the CPU cache. Prior works show that in the worst case, the FPGA-
based pattern matching engine has equal throughput compared to the CPU-based
pattern matching engine [2, 5]. Contrary to that, this paper shows that for
some real-world benchmarks, the CPU gets 4.5x speedup over the FPGA (Section
V). However, if a workload is such that it matches many distinct patterns, CPU
throughput degrades. So, it can be affirmed that neither CPU nor FPGA is a
clear winner for the FA-based pattern matching engine.

In summary, this paper makes the following contributions:

  * •

It presents a detailed analysis of the state count of the optimized NFA vs.
minimized DFA across various real-world automata benchmarks (section III).

  * •

It shows that on FPGA, the choice of NFA over DFA is less important than the
need to keep individual DFA separate and the ability to support parallel
processing of a large number of DFAs (section IV).

  * •

This paper presents an in-depth performance analysis of the state-of-the-art
CPU-based automata processing engine vs. the state-of-the-art FPGA-based
automata processing engine (section V).

(a) Snort

(b) Brill

(c) ClamAV

(d) Hamming

(e) Levenshtein

(f) DotStar

Figure 1: State count comparison between optimized NFA and minimized DFA by
generating distinct DFA/NFA for each individual pattern (shown in log-log
scale). For Snort, Brill, ClamAV, and DotStar a few of the DFA’s states have
polynomial growth rate compared to the NFA states. Hamming DFA state count is
always equal to its equivalent NFA’s state count. DFA shows polynomial growth
in state count compared to it’s equivalent NFA for Levenshtein.

(a) Regex Benchmark

(b) Mesh Benchmark

(c) Synthetic Benchmark

Figure 2: State count comparison between optimized NFA and minimized DFA by
merging multiple patterns into a single automaton (shown in log-log scale).
Regex-based benchmarks show linear growth-rate in state count for minimized
DFA compared to its equivalent optimized NFA. Minimized DFAs for Mesh-
Benchmarks exhibit exponential growth-rate while for synthetic benchmark, they
have equal number of states as their equivalent NFA.

##  II Related Work

The state count of the NFA and DFA has been studied previously from the
perspective of network-intrusion detection, and synthetic benchmarks [21, 13,
22]. The studies on the network-intrusion detection benchmarks showed that
generating a DFA for a specified pattern set can exponentially increase the
DFA state count. They demonstrate that regular expressions containing
constraints such as dot-star (pq.*rs) and repeated sub-patterns (xyz.{100}abc)
induce exponential growth in DFA states. Contrary to the prior works, this
paper performs state count analysis for a diverse state of real-world
benchmarks and shows that if separate DFAs are generated for each pattern, the
DFA state count is equal to the equivalent optimized NFA. However, in the
worst-case DFA state count shows a polynomial growth rate.

Tabakov et al. [17] evaluated Hopcroft’s [15] and Brzozowski’s [16] DFA
minimization algorithm using a synthetic automata type called random automata.
Their analysis illustrates that the state count of a DFA depends on the
automata graph’s transition density111For each symbol ratio of the total
number of transitions to the total number of states. Details can be found at
[17].. For smaller transition densities, the DFA state grows super-
polynomially but sub-exponentially. Additionally, their result shows that
minimized DFA has a smaller state count than the equivalent NFAs with greater
transition densities. One limitation of this analysis is that the NFAs used
are not optimized. Even though NFA minimization is a PSPACE-complete problem
[23], a heuristics-based approach can generate optimized NFA, as shown in this
paper.

Since Floyd et al. [24] introduced hardware implementation of NFA, there has
been a substantial amount of work on high-performance automata processors
using either DFA [4, 13, 25] or NFA [3, 2, 26, 1] as a computation model. The
state-of-the-art CPU-based automata processing engine Hyperscan [20] uses
regex decomposition to separate the pattern into disjoint strings and FA.
Moreover, to process FA, Hyperscan exploits SIMD vector operation to perform
the maximum possible state transition for each memory access. Hyperscan
encounters throughput degradation due to the CPU’s high memory latency if the
working set size does not fit into the CPU cache. Grapefruit [5], a state-of-
the-art FPGA-based automata processing engine, maps a cluster of automata into
the FPGA logic fabric. Even though this approach helps in accelerating
Grapefruit’s throughput, if the automata graph does not fit into the FPGA
logic fabric, Grapefruit fails to process it. This paper does not discuss GPU-
based automata processing engine because prior works [27, 28] have presented
that GPU is not promising for processing FA.

Xie et al. [2] examined throughput comparison between the state-of-the-art
CPU-based automata processing engine, Hyperscan [20] and an FPGA-based
automata processing engine, REAPR. Their analysis shows that in the worst
case, REAPR performs the same as Hyperscan, whereas, in the best case, REAPR
has a 2,000x speedup over Hyperscan. However, this paper shows that, based on
the workload and the benchmark, neither Hyperscan nor Grapefruit is a clear
winner for the FA-based pattern matching engine.

Becchi et al. [14] presented a performance evaluation of a network processor
and a general-purpose processor using NFA, DFA, and hybrid-FA. Hybrid-FA is a
variant of automata formed by halting the NFA$\rightarrow$DFA conversion in
places where DFA blowup occurs. The evaluation at [14] shows that hybrid-FA
has the overall best throughput across the network and general-purpose
processors. The reason is that the DFA part of the hybrid-FA is less
susceptible to high memory latency, and the NFA part of the hybrid-FA keeps a
check on the state explosion issue of the DFA. This performance evaluation is
limited to von Neumann architecture, whereas this paper does the performance
evaluation for von Neumann vs. spatial architecture.

##  III NFA vs. DFA State Count Analysis

By definition, if an NFA requires $n$ states to express a regular language $L$
or pattern $P$, the equivalent DFA will require at most $2^{n}$ states [8]. As
a result, DFAs are disregarded for designing FA-based pattern matching engines
on FPGA [21, 2]. The state count study of DFA vs. NFA across diverse real-
world benchmarks is extremely important for automata processing research.
Because it would resolve if, for real-world benchmarks, minimized DFAs’ state
count exhibits an exponential growth rate compared to its equivalent NFA. The
scope of prior works that perform such study is limited to network intrusion
detection and synthetic benchmarks [13, 17]. This section presents an
empirical analysis of the state count of DFA vs. NFA using a diverse benchmark
set taken from the real workload [29].

While a DFA representing multiple distinct patterns may be significantly
larger [13], a simplified, single pattern DFA can be as small as its
equivalent NFA [15]. Thus, this paper performs state count analysis from two
different perspectives. First, the state count for minimized DFA and optimized
NFA is analyzed by generating distinct NFAs and DFAs for each pattern (Fig 1).
Second, the state count is compared by incrementally adding patterns to a
single NFA or DFA (Fig 2). These two analyses show that while generating
individual DFA for each pattern, DFA’s state count is typically equal to the
state count of the NFA. However, few DFAs exhibit polynomial growth in their
state count in the worst case. If multiple patterns are merged into a single
DFA, the DFA state count may show exponential growth compared to the
equivalent NFA.

### Experimental Setup

AutomataZoo [29] benchmark suite has been used for this experiment. Each
benchmark of AutomataZoo comes with a single NFA, and that NFA contains all
the patterns for that particular benchmark. However, the state count analysis
needs distinct NFAs representing distinct patterns, so VASim’s [30] _compute
connected component_ option is used to divide individual patterns into
separate NFA graphs. Then using Brzozowski’s DFA minimization algorithm,
minimized DFA is generated for each NFA. NFA minimization is a PSPACE-complete
problem [23]. So, a heuristic-based approach is used to generate optimized
NFA: if multiple states have equivalent outgoing transitions (for all the
symbols, they transition into the same states), merge those states into one
state. All these steps compare the state count of NFA vs. DFA for distinct
patterns. An extra step is needed for the comparison where multiple patterns
are merged into a single NFA/DFA graph, incrementally add patterns into an NFA
and create corresponding minimized DFA and optimized NFA using the above
approach.

### Evaluation

Figure 1 & 2 shows the summary of optimized NFA vs. minimized DFA state count
analysis.

  1. 1.

Among the three regex-based benchmarks, (Fig 1(a), 1(b), 1(c)) most of the
minimized DFAs have an equal number of states as their NFAs. However, a few
minimized DFAs have a polynomial growth rate in state count compared to the
equivalent NFA. When patterns are merged, these regex benchmarks exhibit
linear growth rate in state count for minimized DFA (Fig 2(a)).

  2. 2.

There are two mesh automata benchmarks in AutomataZoo. Between them, Hamming
benchmark’s minimized DFAs have an equal number of states as their equivalent
optimized NFAs (Fig 1(d)). Whereas the Levenshtein benchmark’s minimized DFA
state count has a polynomial growth compared to the equivalent optimized NFA
(Fig 1(e)). On the other hand, if patterns are merged, the state count grows
exponentially for minimized DFA compared to the equivalent NFA.

  3. 3.

Synthetic benchmarks such as DotStar show a linear growth in minimized DFA
state count except for some polynomial growth (Fig 1(f)). The DFA state count
shows linear growth when patterns are merged for this benchmark.

  4. 4.

All the patterns for the Random Forest [11] benchmark have an equal number of
states for the NFAs. Moreover, the state count of DFA is the same as the NFA.
As there is only one data point for this benchmark, it is not included in Fig
1.

TABLE I: NFA vs. DFA Performance Analysis on FPGA. Benchmark |  | #Patterns
---
| FSA
---
| #States
---
(k)
| LUTs
---
(k)
| FFs
---
(k)
| Frequency
---
(MHz)
| Throughput
---
(Gbps)
Brill | 5,946 | NFA | 116 | 151 | 112 | 500 |  4
| mDFA | 126 | 163 | 115 | 345 |  2.8
Snort | 2,348 | NFA | 143 | 163 | 135 | 200 |  1.6
| mDFA | 196 | 277 | 168 | 103 |  0.8
ClamAV | 14,300 | NFA | 848 | 1,047 | 848 | 172 |  1.4
| mDFA | 851 | 1,058 | 849 | 164 |  1.3
YARA | 2,620 | NFA | 115 | 136 | 115 | 194 |  1.5
| mDFA | 120 | 150 | 118 | 333.33 |  2.7
Hamming | 1,000 | NFA | 108 | 56 | 64 | 556 |  4.4
| mDFA | 108 | 67 | 63 | 556 |  4.4
Levenshtein | 1,000 | NFA | 106 | 125 | 103 | 263 |  2.1
| mDFA | 735 | 783 | 528 | 222 |  1.8
Random Forest | 8,000 | NFA | 248 | 407 | 240 | 303 |  2.4
| mDFA | 248 | 409 | 240 | 257 |  2.1
Entity Resolution | 10,000 | NFA | 413 | 465 | 260 | 204 |  1.6
| mDFA | 422 | 541 | 275 | 250 |  2.0
FileCarving | 9 | NFA | 0.179 | 0.187 | 0.122 | 666.67 |  5.3
| mDFA | 0.184 | 0.211 | 0.128 | 666.67 |  5.3
|  |  |  |  |  |  |

##  IV NFA vs. DFA Performance Analysis on FPGA

Prior works on FPGA-based automata processing engine [2, 5, 3] selected NFA as
their computation model because NFA enables processing multiple states
simultaneously, which exploits FPGA’s parallel execution capability. Prior
works also pointed out that DFA conversion and processing are expensive as DFA
might suffer from exponential state growth [21]. In contrast, Section III of
this paper shows that the DFA conversion will not be as expensive if distinct
DFA is generated per individual pattern. This section shows that DFAs can also
exploit parallelism offered by FPGA if distinct DFAs are processed in parallel
(table I).

### Experimental Setup

For this analysis, state-of-the-art FPGA-based automata processing engine,
Grapefruit [5] is used to generate the Hardware Description Language (HDL) for
the synthesis, and the FPGA throughput for NFA/DFA is calculated using the
maximum frequency reported after finishing the synthesis. The DFAs and NFAs
used in this experiment are all optimized.

### Evaluation

Table I presents the detailed result of the experiment. On the FPGA, DFA has
1.8x and 1.3x speedup for YARA and Entity Resolution benchmarks, respectively.
Further investigation shows that NFA graphs have a higher fan-out or node
degree for these two benchmarks than the DFA. High fan-out or node degree
works as a performance bottleneck for FPGA processing. FPGA has identical
throughput for ClamAV, Hamming, and Random Forest benchmarks for both the NFA
and DFA. For the rest of the benchmarks, FPGA has 2x-1.1x speedup while
processing NFA instead of DFA.

##  V CPU vs. FPGA Performance Analysis

Researchers designing high-performance FA-based pattern matching engines
prefer FPGA over CPU because i) CPU has limited parallelism, while FPGA offers
massive parallelism, ii) CPU faces high memory latency, but FPGA does not as
automata states can be mapped into the logic fabric [2, 5]. This section shows
that the choice of CPU vs. FPGA is not trivial.

High memory latency negatively affects the CPU’s throughput if the automata
graph does not fit into the cache. On the other hand, FPGA has a significantly
lower clock rate compared to the CPU. For example, in practice, FPGA’s achieve
200-500MHz, while high-end CPUs are 2-3 GHz or more. Besides, if the entire
benchmark do not fit into the FPGA logic fabric, FPGA needs an optimal memory
spilling technique to accommodate all the patterns of the benchmark. For
example, even though Grapefruit [5] is the current state-of-the-art FPGA-based
pattern matching engine, it fails to process the entire ClamAV benchmark (33k
patterns) because it does not have a memory spilling option. Instead, it
breaks the application into chunks and processes those in multiple passes over
the input. On the other hand, the state-of-the-art CPU-based pattern matching
engine, Hyperscan [20], can, in fact, process the entire ClamAV benchmark. Not
only that, Hyperscan has 4.5x speedup over Grapefruit, even though Grapefruit
was processing only 43.3% of the ClamAV benchmark. Having said that,
Grapefruit has 32,530x speedup over Hyperscan for the APPRNG benchmark. So, it
can safely be asserted that neither Grapefruit nor Hyperscan is the clear
winner here.

TABLE II: Hyperscan vs. Grapefruit Throughput Comparison Benchmark |  | Hyperscan
---
Throughput
(Gbps)
| Grapefruit
---
Throughput
(Gbps)
Brill | 0.007 | 4
Snort | 0.359 | 1.6
SeqMatch | 0.020 | 2.3
Levenshtein | 0.0002 | 2.1
Hamming | 0.0003 | 4.4
Protomata | 0.016 | 2.9
Random Forest | 0.005 | 2.4
Entity Resolution | 0.014 | 1.6
APPRNG | 0.000083 | 2.7
ClamAV | 6.245 | 1.4
YARA | 6.877 | 1.5
FileCarve | 22.475 | 5.3
|  |

### Experimental Setup

Hyperscan is used for the CPU-based pattern matching engine and Grapefruit as
the FPGA-based pattern matching engine. Hyperscan is run on an Intel i7-6700K
CPU running at 4 GHz with 32 GB memory. Intel Xeon E5-2686 v4 processor
running at 2.3 GHz and 32 GB memory is used as FPGA host computer. Following
approach explains the Hyperscan throughput calculation step for each benchmark
of the AutomataZoo [29]:

  1. 1.

Compile: Hyperscan takes regular expression and compiles it into a pattern
database [31]. However, all the benchmarks in AutomataZoo have their automata
expressed either in ANML or MNRL format. As a result, to feed the automata to
Hyperscan, I use hscompile’s [32] to compile the MNRL file to a pattern
database.

  2. 2.

Scan: I use $hsrun$ [33] executable of the hscompile tool to scan the input
file of each benchmark, and log the scan time for this process. Then I
calculate the throughput using equation 1.

$throughput_{Hyperscan}(Gbps)=\frac{Input\\_Size(Gb)}{Scan\\_Time(sec)}$ (1)

Hyperscan uses regex decomposition as one of its throughput optimization
techniques. The throughput obtained here is cross-checked by running Hyperscan
with the regex version of the benchmarks to confirm that the optimization
technique does not fall short if NFAs are directly fed to Hyperscan.

Grapefruit throughput is calculated only for computation kernel, excluding
I/O, based on the fact that the FPGA process one input symbol per clock.

### Evaluation

Figure 3: Hyperscan throughput decreases as #patterns matched/input increases

Table II shows the throughput (Gbps) comparison between the Grapefruit and the
Hyperscan. Except for ClamAV, YARA, and FileCarve, Grapefruit has
significantly higher throughput (max speedup 32,530x) than Hyperscan.
FileCarve is a special case as the benchmark size is very small (only nine
patterns). However, further exploration into the characteristic (#patterns,
#pattern matched per input) of ClamAV and YARA benchmarks show that the
#pattern matched per input is significantly low for these benchmarks, which
means only a small portion of the automata graphs are traversed.

This paper hypothesized that Hyperscan throughput is sensitive to #pattern
matched per input. In support of this hypothesis, another empirical study is
performed. First, a set of input is generated synthetically for the
benchmarks. Next, Hyperscan’s throughput is calculated for those benchmarks
using the synthetic inputs. Fig 3 shows the result for this analysis. It can
be seen that, Hyperscan’s throughput decreases as the #pattern matched per
input increases. The findings in this section shows that, the CPU might not
offer high parallelism or suffer from high memory latency, but the CPU is
better than the FPGA if the workload does not cause high memory access. Thus,
a high-performance FA-based pattern matching engine may entail a heterogeneous
system, where workloads are divided intelligently between the CPU and FPGA.

##  VI Conclusion

Tabakov et al. [17] showed that sometimes DFAs can be more compact in state
count than their equivalent NFAs. However, their work does not use optimized
NFAs, while their DFAs are minimized. Motivated by their work, this paper
performed a state count analysis for minimized DFA and heuristically-optimized
NFA across a diverse set of real-world automata benchmarks. The analysis
focuses on two perspectives: i) distinct DFA and NFA are generated for each
pattern, and ii) multiple patterns are merged into a single DFA/NFA. This
study shows that if distinct DFAs/NFAs are generated for each pattern,
minimized DFAs’ state count growth rate is often similar to its equivalent
optimized NFA for these benchmarks. However, some DFAs’ state counts show
exponential growth rates if multiple patterns are merged into a single DFA.
Based on this finding, we hypothesized that if individual distinct DFAs are
generated for each distinct pattern and are processed in parallel, the FPGA
throughput for processing DFA would be similar to the FPGA throughput for
processing NFA. Furthermore, an empirical analysis of the NFA vs. DFA
throughput presented in this paper supports this hypothesis. Finally, unlike
prior work [5, 2], this paper shows that based on the workload and the
benchmark, neither CPU nor FPGA is a clear winner for the FA-based pattern
matching engine. Further optimization of our FPGA framework is ongoing.

## Acknowledgement

This work was supported by Center for Research on Intelligent Storage and
Processing in Memory (CRISP) and Semiconductor Research Corporation (SRC).

## References

  * [1] Dlugosch P, Brown D, Glendenning P, Leventhal M, Noyes H.  An efficient and scalable semiconductor architecture for parallel automata processing.  IEEE Transactions on Parallel and Distributed Systems. 2014;25(12):3088-98.
  * [2] Xie T, Dang V, Wadden J, Skadron K, Stan M.  REAPR: Reconfigurable engine for automata processing.  In: 2017 27th International Conference on Field Programmable Logic and Applications (FPL). IEEE; 2017. p. 1-8.
  * [3] Sidhu R, Prasanna VK.  Fast regular expression matching using FPGAs.  In: The 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’01). IEEE; 2001. p. 227-38.
  * [4] Hieu TT, Tran NT.  A memory efficient FPGA-based pattern matching engine for stateful NIDS.  In: 2013 Fifth International Conference on Ubiquitous and Future Networks (ICUFN). IEEE; 2013. p. 252-7.
  * [5] Rahimi R, Sadredini E, Stan M, Skadron K.  Grapefruit: An Open-Source, Full-Stack, and Customizable Automata Processing on FPGAs.  In: 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). IEEE; 2020. p. 138-47.
  * [6] Schulz KU, Mihov S.  Fast string correction with Levenshtein automata.  International Journal on Document Analysis and Recognition. 2002;5(1):67-85.
  * [7] Roesch M, et al.  Snort: Lightweight intrusion detection for networks.  In: Lisa. vol. 99; 1999. p. 229-38.
  * [8] Hopcroft JE, Motwani R, Ullman JD.  Introduction to automata theory, languages, and computation.  Acm Sigact News. 2001;32(1):60-5.
  * [9] Wulf WA, McKee SA.  Hitting the memory wall: implications of the obvious.  ACM SIGARCH computer architecture news. 1995;23(1):20-4.
  * [10] Wang K, Angstadt K, Bo C, Brunelle N, Sadredini E, Tracy T, et al.  An overview of micron’s automata processor.  In: Proceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis; 2016. p. 1-3.
  * [11] Tracy T, Fu Y, Roy I, Jonas E, Glendenning P.  Towards machine learning on the automata processor.  In: International Conference on High Performance Computing. Springer; 2016\. p. 200-18.
  * [12] Rabin MO, Scott D.  Finite automata and their decision problems.  IBM journal of research and development. 1959;3(2):114-25.
  * [13] Yu F, Chen Z, Diao Y, Lakshman TV, Katz RH.  Fast and memory-efficient regular expression matching for deep packet inspection.  In: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems; 2006. p. 93-102.
  * [14] Becchi M, Wiseman C, Crowley P.  Evaluating regular expression matching engines on network and general purpose processors.  In: Proceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems; 2009. p. 30-9.
  * [15] Hopcroft J.  An n log n algorithm for minimizing states in a finite automaton.  In: Theory of machines and computations. Elsevier; 1971. p. 189-96.
  * [16] Brzozowski JA.  Canonical regular expressions and minimal state graphs for definite events.  Mathematical theory of Automata. 1962;12(6):529-61.
  * [17] Tabakov D, Vardi MY.  Experimental evaluation of classical automata constructions.  In: International Conference on Logic for Programming Artificial Intelligence and Reasoning. Springer; 2005. p. 396-411.
  * [18] Paxson V.  Bro: a system for detecting network intruders in real-time.  Computer networks. 1999;31(23-24):2435-63.
  * [19] Liu C, Wu J.  Fast deep packet inspection with a dual finite automata.  IEEE Transactions on Computers. 2011;62(2):310-21.
  * [20] Wang X, Hong Y, Chang H, Park K, Langdale G, Hu J, et al.  Hyperscan: a fast multi-pattern regex matcher for modern cpus.  In: 16th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 19); 2019. p. 631-48.
  * [21] Becchi M, Crowley P.  A hybrid finite automaton for practical deep packet inspection.  In: Proceedings of the 2007 ACM CoNEXT conference; 2007. p. 1-12.
  * [22] Kumar S, Chandrasekaran B, Turner J, Varghese G.  Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia.  In: Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems; 2007. p. 155-64.
  * [23] Jiang T, Ravikumar B.  Minimal NFA problems are hard.  SIAM Journal on Computing. 1993;22(6):1117-41.
  * [24] Floyd RW, Ullman JD.  The compilation of regular expressions into integrated circuits.  In: 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). IEEE; 1980. p. 260-9.
  * [25] Kumar S, Dharmapurikar S, Yu F, Crowley P, Turner J.  Algorithms to accelerate multiple regular expressions matching for deep packet inspection.  ACM SIGCOMM Computer Communication Review. 2006;36(4):339-50.
  * [26] Yang YH, Prasanna V.  High-performance and compact architecture for regular expression matching on FPGA.  IEEE Transactions on Computers. 2011;61(7):1013-25.
  * [27] Angstadt K, Wadden J, Dang V, Xie T, Kramp D, Weimer W, et al.  MNCaRT: An Open-Source, Multi-Architecture Automata-Processing Research and Execution Ecosystem.  IEEE Computer Architecture Letters. 2018;17(1):84-7.
  * [28] Liu H, Pai S, Jog A.  Why gpus are slow at executing NFAs and how to make them faster.  In: Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems; 2020. p. 251-65.
  * [29] Wadden J, Tracy T, Sadredini E, Wu L, Bo C, Du J, et al.  AutomataZoo: A modern automata processing benchmark suite.  In: 2018 IEEE International Symposium on Workload Characterization (IISWC). IEEE; 2018. p. 13-24.
  * [30] Wadden J, Skadron K.  VASim: An open virtual automata simulator for automata processing application and architecture research.  University of Virginia, Tech Rep CS2016-03. 2016.
  * [31] Hyperscan-Compiling Patterns; 2020-08-07.  Available from: http://intel.github.io/hyperscan/dev-reference/compilation.html#compilation.
  * [32] hscompile; 2020-08-07.  Available from: https://github.com/kevinaangstadt/hscompile.
  * [33] Hyperscan-Scanning for Patterns; 2020-08-07.  Available from: http://intel.github.io/hyperscan/dev-reference/runtime.html#runtime.