{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T16:30:16Z","timestamp":1789230616868,"version":"build-2803163510"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>\n            Finite-state Machine (FSM) is the key kernel behind many popular applications, including regular expression matching, text tokenization, and Huffman decoding. Parallelizing FSMs is extremely difficult because of the strong dependencies and unpredictable memory accesses. Previous efforts have largely focused on multi-core parallelization and used different approaches, including\n            <jats:italic>speculative<\/jats:italic>\n            and\n            <jats:italic>enumerative<\/jats:italic>\n            execution, both of which have been effective but also have limitations. With increasing width and improving flexibility in SIMD instruction sets, this article focuses on combining SIMD and many\/multi-core parallelism for FSMs. We have developed a novel strategy, called\n            <jats:italic>enumerative speculation<\/jats:italic>\n            . Instead of speculating on a single state as in speculative execution or enumerating all possible states as in enumerative execution, our strategy speculates transitions from several possible states, reducing the prediction overheads of speculation approach and the large amount of redundant work in the enumerative approach. A simple lookback approach produces a set of guessed states to achieve high speculation success rates in our enumerative speculation. In addition, to enable continued scalability of enumerative speculation with a large number of threads, we have developed a parallel merge method. We evaluate our method with four popular FSM applications: Huffman decoding, regular expression matching, HTML tokenization, and Div7. We obtain up to 2.5\u00d7 speedup using SIMD on 1 core and up to 95\u00d7 combining SIMD with 60 cores of an Intel Xeon Phi. On a single core, we outperform the best single-state speculative execution version by an average of 1.6\u00d7, and in combining SIMD and many-core parallelism, outperform enumerative execution by an average of 2\u00d7. Finally, when evaluate on a GPU, we show that our parallel merge implementations are 2.02--6.74\u00d7 more efficient than corresponding sequential merge implementations and achieve better scalability on an Nvidia V100 GPU.\n          <\/jats:p>","DOI":"10.1145\/3399714","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:38:56Z","timestamp":1592793536000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Combining SIMD and Many\/Multi-core Parallelism for Finite-state Machines with Enumerative Speculation"],"prefix":"10.1145","volume":"7","author":[{"given":"Peng","family":"Jiang","sequence":"first","affiliation":[{"name":"The University of Iowa, IA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Xia","sequence":"additional","affiliation":[{"name":"The Ohio State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gagan","family":"Agrawal","sequence":"additional","affiliation":[{"name":"Augusta University, GA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562783"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854046"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201902)","author":"Franchetti F.","unstructured":"F. Franchetti and M. Puschel . 2002. A SIMD Vectorizing Compiler for Digital Signal Processing Algorithms . In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201902) . IEEE, 20--26. F. Franchetti and M. Puschel. 2002. A SIMD Vectorizing Compiler for Digital Signal Processing Algorithms. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201902). IEEE, 20--26."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IEEE Inernational Parallel and Distributed Processing Symposium (IPDPS\u201903)","author":"Garca C.","unstructured":"C. Garca , R. Lario , M. Prieto , L. Piuel , and F. Tirado . 2003. Vectorization of Multigrid Codes Using SIMD ISA Extensions . Proceedings of the IEEE Inernational Parallel and Distributed Processing Symposium (IPDPS\u201903) . 58a. C. Garca, R. Lario, M. Prieto, L. Piuel, and F. Tirado. 2003. Vectorization of Multigrid Codes Using SIMD ISA Extensions. Proceedings of the IEEE Inernational Parallel and Distributed Processing Symposium (IPDPS\u201903). 58a."},{"key":"e_1_2_1_6_1","first-page":"12","article-title":"Data parallel algorithms","volume":"29","author":"Daniel Hillis W.","year":"1986","unstructured":"W. Daniel Hillis and Guy L. Steele , Jr. 1986 . Data parallel algorithms . Commun. ACM 29 , 12 (Dec. 1986). W. Daniel Hillis and Guy L. Steele, Jr. 1986. Data parallel algorithms. Commun. ACM 29, 12 (Dec. 1986).","journal-title":"Commun. ACM"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02979-0_9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.848212"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926285"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing (HPDC\u201914)","author":"Khorasani Farzad","unstructured":"Farzad Khorasani , Keval Vora , Rajiv Gupta , and Laxmi N. Bhuyan . 2014. CuSha: Vertex-centric graph processing on GPUs . In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing (HPDC\u201914) . Farzad Khorasani, Keval Vora, Rajiv Gupta, and Laxmi N. Bhuyan. 2014. CuSha: Vertex-centric graph processing on GPUs. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing (HPDC\u201914)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145824"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/46.5.487"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2465013"},{"key":"e_1_2_1_15_1","first-page":"2","article-title":"Speculative parallel pattern matching","volume":"6","author":"Luchaup D.","year":"2011","unstructured":"D. Luchaup , R. Smith , C. Estan , and S. Jha . 2011 . Speculative parallel pattern matching . IEEE Trans. Info. Forensics Secur. 6 , 2 (June 2011), 438--451. D. Luchaup, R. Smith, C. Estan, and S. Jha. 2011. Speculative parallel pattern matching. IEEE Trans. Info. Forensics Secur. 6, 2 (June 2011), 438--451.","journal-title":"IEEE Trans. Info. Forensics Secur."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145832"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541988"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201908)","author":"Pan Yinfei","unstructured":"Yinfei Pan , Ying Zhang , and K. Chiu . 2008. Simultaneous transducers for data-parallel XML parsing . In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201908) . 1--12. Yinfei Pan, Ying Zhang, and K. Chiu. 2008. Simultaneous transducers for data-parallel XML parsing. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS\u201908). 1--12."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS\u201913)","author":"Pennycook Simon J.","unstructured":"Simon J. Pennycook , Chris J. Hughes , M. Smelyanskiy , and S. A. Jarvis . 2013. Exploring SIMD for molecular dynamics, using intel xeon processors and intel xeon phi coprocessors . In Proceedings of the IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS\u201913) . Simon J. Pennycook, Chris J. Hughes, M. Smelyanskiy, and S. A. Jarvis. 2013. Exploring SIMD for molecular dynamics, using intel xeon processors and intel xeon phi coprocessors. In Proceedings of the IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS\u201913)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806603"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967938.2967965"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/16.8.699"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the IEEE 26th International Parallel and Distributed Processing Symposium Workshops 8 PhD Forum (IPDPSW\u201912)","author":"Erik","year":"2012","unstructured":"Erik Saule and \u00dcmit V. Catalyurek. 2012. An early evaluation of the scalability of graph algorithms on the intel MIC architecture . In Proceedings of the IEEE 26th International Parallel and Distributed Processing Symposium Workshops 8 PhD Forum (IPDPSW\u201912) . IEEE, Washington, DC, 1629--1639. DOI:https:\/\/doi.org\/10.1109\/IPDPSW. 2012 .204 10.1109\/IPDPSW.2012.204 Erik Saule and \u00dcmit V. Catalyurek. 2012. An early evaluation of the scalability of graph algorithms on the intel MIC architecture. In Proceedings of the IEEE 26th International Parallel and Distributed Processing Symposium Workshops 8 PhD Forum (IPDPSW\u201912). IEEE, Washington, DC, 1629--1639. DOI:https:\/\/doi.org\/10.1109\/IPDPSW.2012.204"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2738600.2738618"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786763.2694369"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2654822.2541989"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3399714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3399714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:13Z","timestamp":1750199893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3399714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3399714"],"URL":"https:\/\/doi.org\/10.1145\/3399714","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}