NAPOLY: A Non-deterministic Automata Processor OverLaY

被引:1
作者
Karakchi, Rasha [1 ]
Bakos, Jason D. [1 ]
机构
[1] Univ South Carolina, Columbia, SC 29208 USA
基金
美国国家科学基金会;
关键词
FPGA; automata processing; FPGA overlay; pattern matching; ARCHITECTURE;
D O I
10.1145/3593586
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Deterministic and Non-deterministic Finite Automata (DFA and NFA) comprise the core of many big data applications. Recent efforts to develop Domain-Specific Architectures (DSAs) for DFA/NFA have taken divergent approaches, but achieving consistent throughput for arbitrarily-large pattern sets, state activation rates, and pattern match rates remains a challenge. In this article, we present NAPOLY (Non-Deterministic Automata Processor OverLaY), an FPGA overlay and associated compiler. A common limitation of prior efforts is a limit on NFA size for achieving the advertised throughput. NAPOLY is optimized for fast re-programming to permit practical time-division multiplexing of the hardware and permit high asymptotic throughput for NFAs of unlimited size, unlimited state activation rate, and high pattern reporting rate. NAPOLY also allows for offline generation of configurations having tradeoffs between state capacity and transition capacity. In this article, we (1) evaluate NAPOLY using benchmarks packaged in the ANMLZoo benchmark suite, (2) evaluate the use of an SAT solver for allocating physical resources, and (3) compare NAPOLY's performance against existing solutions. NAPOLY performs most favorably on larger benchmarks, benchmarks with higher state activation frequency, and benchmarks with higher reporting frequency. NAPOLY outperforms the fastest of the CPU and GPU implementations in 10 out of 12 benchmarks.
引用
收藏
页数:25
相关论文
共 36 条
[1]   MNCaRT: An Open-Source, Multi-Architecture Automata-Processing Research and Execution Ecosystem [J].
Angstadt, Kevin ;
Wadden, Jack ;
Dang, Vinh ;
Xie, Ted ;
Kramp, Dan ;
Weimer, Westley ;
Stan, Mircea ;
Skadron, Kevin .
IEEE COMPUTER ARCHITECTURE LETTERS, 2018, 17 (01) :84-87
[2]  
[Anonymous], 2012, P 2012 ACM SIGMOD IN
[3]  
Bakos Jason D., 2023, NFATOOL
[4]  
Becchi Michela., 2009, Data structures, algorithms and architectures for efficient regular expression evaluation
[5]   Debugging Support for Pattern-Matching Languages and Accelerators [J].
Casias, Matthew ;
Angstadt, Kevin ;
Tracy, Tommy, II ;
Skadron, Kevin ;
Weimer, Westley .
TWENTY-FOURTH INTERNATIONAL CONFERENCE ON ARCHITECTURAL SUPPORT FOR PROGRAMMING LANGUAGES AND OPERATING SYSTEMS (ASPLOS XXIV), 2019, :1073-1086
[6]   An Efficient and Scalable Semiconductor Architecture for Parallel Automata Processing [J].
Dlugosch, Paul ;
Brown, Dave ;
Glendenning, Paul ;
Leventhal, Michael ;
Noyes, Harold .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2014, 25 (12) :3088-3098
[7]   Fast Support for Unstructured Data Processing: the Unified Automata Processor [J].
Fang, Yuanwei ;
Hoang, Tung T. ;
Becchi, Michela ;
Chien, Andrew A. .
PROCEEDINGS OF THE 48TH ANNUAL IEEE/ACM INTERNATIONAL SYMPOSIUM ON MICROARCHITECTURE (MICRO-48), 2015, :533-545
[8]  
Flicek P, 2009, NAT METHODS, V6, pS6, DOI [10.1038/NMETH.1376, 10.1038/nmeth.1376]
[9]  
Guo Danhua., 2008, Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS '08, P60
[10]  
Harris Alan, 2010, DISTRIBUTED CACHING, P165, DOI [10.1007/978-1-4302-2713-7_6, DOI 10.1007/978-1-4302-2713-7_6]