{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:59:29Z","timestamp":1767855569804,"version":"3.49.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T00:00:00Z","timestamp":1631836800000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>Regular Expression (RE) matching is a computational kernel used in several applications. Since RE complexity and data volumes are steadily increasing, hardware acceleration is gaining attention also for this problem. Existing approaches have limited flexibility as they require a different implementation for each RE. On the other hand, it is complex to map efficient RE representations like non-deterministic finite-state automata onto software-programmable engines or parallel architectures. In this work, we present CICERO\u00a0, an end-to-end framework composed of a domain-specific architecture and a companion compilation framework for RE matching. Our solution is suitable for many applications, such as genomics\/proteomics and natural language processing. CICERO aims at exploiting the intrinsic parallelism of non-deterministic representations of the REs. CICERO can trade-off accelerators\u2019 efficiency and processors\u2019 flexibility thanks to its programmable architecture and the compilation framework. We implemented CICERO prototypes on embedded FPGA achieving up to 28.6\u00d7 and 20.8\u00d7 more energy efficiency than embedded and mainstream processors, respectively. Since it is a programmable architecture, it can be implemented as a custom ASIC that is orders of magnitude more energy-efficient than mainstream processors.<\/jats:p>","DOI":"10.1145\/3476982","type":"journal-article","created":{"date-parts":[[2021,9,17]],"date-time":"2021-09-17T18:36:51Z","timestamp":1631903811000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["CICERO: A Domain-Specific Architecture for Efficient Regular Expression Matching"],"prefix":"10.1145","volume":"20","author":[{"given":"Daniele","family":"Parravicini","sequence":"first","affiliation":[{"name":"Politecnico di Milano, Milano, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5834-0812","authenticated-orcid":false,"given":"Davide","family":"Conficconi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3101-8118","authenticated-orcid":false,"given":"Emanuele Del","family":"Sozzo","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milano, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9315-1788","authenticated-orcid":false,"given":"Christian","family":"Pilato","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milano, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9883-9693","authenticated-orcid":false,"given":"Marco D.","family":"Santambrogio","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Milano, Italy"}]}],"member":"320","published-online":{"date-parts":[[2021,9,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE International Conference on Field Programmable Logic and Applications (FPL). 360\u20133607","author":"Abbas M.","unstructured":"M. Abbas and V. Betz . 2018. Latency insensitive design styles for FPGAs . In Proceedings of the IEEE International Conference on Field Programmable Logic and Applications (FPL). 360\u20133607 . M. Abbas and V. Betz. 2018. Latency insensitive design styles for FPGAs. In Proceedings of the IEEE International Conference on Field Programmable Logic and Applications (FPL). 360\u20133607."},{"key":"e_1_2_1_2_1","volume-title":"Joseph James Gebis, Parry Husbands, Kurt Keutzer, David A. Patterson, William Lester Plishker, John Shalf, Samuel Webb Williams, and Katherine A. Yelick.","author":"Asanovic K.","year":"2006","unstructured":"K. Asanovic , Ras Bodik , Bryan Christopher Catanzaro , Joseph James Gebis, Parry Husbands, Kurt Keutzer, David A. Patterson, William Lester Plishker, John Shalf, Samuel Webb Williams, and Katherine A. Yelick. 2006 . The landscape of parallel computing research: A view from Berkeley . (2006). K. Asanovic, Ras Bodik, Bryan Christopher Catanzaro, Joseph James Gebis, Parry Husbands, Kurt Keutzer, David A. Patterson, William Lester Plishker, John Shalf, Samuel Webb Williams, and Katherine A. Yelick. 2006. The landscape of parallel computing research: A view from Berkeley. (2006)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1364654.1364656"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1477942.1477950"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211922.3211926"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314576"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.3"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 131\u2013137","author":"Comodi Alessandro","unstructured":"Alessandro Comodi , Davide Conficconi , Alberto Scolari , and Marco D. Santambrogio . 2018. TiReX: Tiled regular expression matching architecture . In Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 131\u2013137 . Alessandro Comodi, Davide Conficconi, Alberto Scolari, and Marco D. Santambrogio. 2018. TiReX: Tiled regular expression matching architecture. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 131\u2013137."},{"key":"e_1_2_1_9_1","unstructured":"Russ Cox. 2007. Regular expression matching can be simple and fast (but is slow in java perl php python ruby ...). http:\/\/swtch.com\/rsc\/regexp\/regexp1.html.  Russ Cox. 2007. Regular expression matching can be simple and fast (but is slow in java perl php python ruby ...). http:\/\/swtch.com\/rsc\/regexp\/regexp1.html."},{"key":"e_1_2_1_10_1","unstructured":"Russ Cox. 2009. Regular expression matching: the virtual machine approach. http:\/\/swtch.com\/rsc\/regexp\/regexp2.html.  Russ Cox. 2009. Regular expression matching: the virtual machine approach. http:\/\/swtch.com\/rsc\/regexp\/regexp2.html."},{"key":"e_1_2_1_11_1","unstructured":"Russ Cox. 2012. Regular Expression Matching with a Trigram Index or How Google Code Search Worked. https:\/\/swtch.com\/ rsc\/regexp\/regexp4.html.  Russ Cox. 2012. Regular Expression Matching with a Trigram Index or How Google Code Search Worked. https:\/\/swtch.com\/ rsc\/regexp\/regexp4.html."},{"key":"e_1_2_1_12_1","volume-title":"2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 214\u2013217","author":"Tucci Lorenzo Di","unstructured":"Lorenzo Di Tucci , Davide Conficconi , Alessandro Comodi , Steven Hofmeyr , David Donofrio , and Marco D. Santambrogio . 2018. A parallel, energy efficient hardware architecture for the meraligner on FPGA using chisel HCL . In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 214\u2013217 . Lorenzo Di Tucci, Davide Conficconi, Alessandro Comodi, Steven Hofmeyr, David Donofrio, and Marco D. Santambrogio. 2018. A parallel, energy efficient hardware architecture for the meraligner on FPGA using chisel HCL. In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 214\u2013217."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3195638.3195692"},{"key":"e_1_2_1_15_1","unstructured":"Google. 2020. Google re2. https:\/\/github.com\/google\/re2.  Google. 2020. Google re2. https:\/\/github.com\/google\/re2."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM\/IEEE Annual International Symposium on Computer Architecture (ISCA).","author":"John","unstructured":"John L. Hennessy and David A. Patterson. 2018. A new golden age for computer architecture: Domain-specific hardware\/software co-design, enhanced security, open instruction sets, and agile chip development . In Proceedings of the ACM\/IEEE Annual International Symposium on Computer Architecture (ISCA). John L. Hennessy and David A. Patterson. 2018. A new golden age for computer architecture: Domain-specific hardware\/software co-design, enhanced security, open instruction sets, and agile chip development. In Proceedings of the ACM\/IEEE Annual International Symposium on Computer Architecture (ISCA)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1454320"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC.2014.6757323"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2016.61"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCC.2014.6912600"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90426-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2897984"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1929820.1929831"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079100"},{"key":"e_1_2_1_25_1","volume-title":"Fpga accelerated computing using aws f1 instances. AWS Public Sector Summit","author":"Pellerin David","year":"2017","unstructured":"David Pellerin . 2017. Fpga accelerated computing using aws f1 instances. AWS Public Sector Summit ( 2017 ). David Pellerin. 2017. Fpga accelerated computing using aws f1 instances. AWS Public Sector Summit (2017)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM48280.2020.00027"},{"key":"e_1_2_1_27_1","unstructured":"Alex Roichman and Adar Weidman. 2012. Regular Expression Denial of Service.  Alex Roichman and Adar Weidman. 2012. Regular Expression Denial of Service."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378459"},{"key":"e_1_2_1_30_1","volume-title":"2018 IEEE 29th International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE, 1\u20138.","author":"Sampietro Davide","unstructured":"Davide Sampietro , Chiara Crippa , Lorenzo Di Tucci , Emanuele Del Sozzo , and Marco D. Santambrogio . 2018. Fpga-based pairhmm forward algorithm for dna variant calling . In 2018 IEEE 29th International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE, 1\u20138. Davide Sampietro, Chiara Crippa, Lorenzo Di Tucci, Emanuele Del Sozzo, and Marco D. Santambrogio. 2018. Fpga-based pairhmm forward algorithm for dna variant calling. In 2018 IEEE 29th International Conference on Application-specific Systems, Architectures and Processors (ASAP). IEEE, 1\u20138."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035954"},{"key":"e_1_2_1_32_1","volume-title":"Prasanna","author":"Singapura Shreyas G.","year":"2015","unstructured":"Shreyas G. Singapura , Yi-Hua E. Yang , Anand Panangadan , Tamas Nemeth , and Viktor K . Prasanna . 2015 . FPGA Based Accelerator for Pattern Matching in YARA Framework. Technical Report. CE, Los Angeles, CA. Shreyas G. Singapura, Yi-Hua E. Yang, Anand Panangadan, Tamas Nemeth, and Viktor K. Prasanna. 2015. FPGA Based Accelerator for Pattern Matching in YARA Framework. Technical Report. CE, Los Angeles, CA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195546"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 1\u201312","author":"Wadden J.","unstructured":"J. Wadden , V. Dang , N. Brunelle , T. T. II, D. Guo , E. Sadredini , K. Wang , C. Bo , G. Robins , M. Stan , and K. Skadron . 2016. ANMLzoo: A benchmark suite for exploring bottlenecks in automata processing engines and architectures . In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 1\u201312 . J. Wadden, V. Dang, N. Brunelle, T. T. II, D. Guo, E. Sadredini, K. Wang, C. Bo, G. Robins, M. Stan, and K. Skadron. 2016. ANMLzoo: A benchmark suite for exploring bottlenecks in automata processing engines and architectures. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 1\u201312."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 13\u201324","author":"Wadden J.","unstructured":"J. Wadden , T. Tracy , E. Sadredini , L. Wu , C. Bo , J. Du , Y. Wei , J. Udall , M. Wallace , M. Stan , and K. Skadron . 2018. AutomataZoo: A modern automata processing benchmark suite . In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 13\u201324 . J. Wadden, T. Tracy, E. Sadredini, L. Wu, C. Bo, J. Du, Y. Wei, J. Udall, M. Wallace, M. Stan, and K. Skadron. 2018. AutomataZoo: A modern automata processing benchmark suite. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 13\u201324."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968456.2976763"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the IEEE International Conference on Field Programmable Logic and Applications (FPL). 1\u20138.","author":"Xie T.","unstructured":"T. Xie , V. Dang , J. Wadden , K. Skadron , and M. Stan . 2017. REAPR: Reconfigurable engine for automata processing . In Proceedings of the IEEE International Conference on Field Programmable Logic and Applications (FPL). 1\u20138. T. Xie, V. Dang, J. Wadden, K. Skadron, and M. Stan. 2017. REAPR: Reconfigurable engine for automata processing. In Proceedings of the IEEE International Conference on Field Programmable Logic and Applications (FPL). 1\u20138."},{"key":"e_1_2_1_39_1","volume-title":"PYNQ: Python for Productivity for ZYNQ","year":"2016","unstructured":"Xilinx. 2016 . PYNQ: Python for Productivity for ZYNQ . http:\/\/www.pynq.io\/. Xilinx. 2016. PYNQ: Python for Productivity for ZYNQ. http:\/\/www.pynq.io\/."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the IEEE International Conference on Communications (ICC). 1\u20137.","author":"Yang J.","unstructured":"J. Yang , L. Jiang , Q. Tang , Q. Dai , and J. Tan . 2016. PiDFA: A practical multi-stride regular expression matching engine based on FPGA . In Proceedings of the IEEE International Conference on Communications (ICC). 1\u20137. J. Yang, L. Jiang, Q. Tang, Q. Dai, and J. Tan. 2016. PiDFA: A practical multi-stride regular expression matching engine based on FPGA. In Proceedings of the IEEE International Conference on Communications (ICC). 1\u20137."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 1083\u20131100","author":"Zhao Zhipeng","year":"2020","unstructured":"Zhipeng Zhao , Hugo Sadok , Nirav Atre , James C. Hoe , Vyas Sekar , and Justine Sherry . 2020 . Achieving 100Gbps intrusion prevention on a single server . In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 1083\u20131100 . Zhipeng Zhao, Hugo Sadok, Nirav Atre, James C. Hoe, Vyas Sekar, and Justine Sherry. 2020. Achieving 100Gbps intrusion prevention on a single server. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI). 1083\u20131100."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363776"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476982","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:46Z","timestamp":1750188646000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476982"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,17]]},"references-count":41,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3476982"],"URL":"https:\/\/doi.org\/10.1145\/3476982","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,17]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}