search

DanieleParravicini / regex_coprocessor

An accelerator to which you can offload RE matching and that does not use backtracking
7 stars 6 forks source link
architectures domain-specific-architecture fpga pynq-z1 regular-expression ultra96 ultra96-v2

readme

Cicero

Cicero is a domain specific architecture that can be employed to perform exact regular expression (RE) matching using FPGAs. The cool fact about Cicero is that - as other software libraries one among the other RE2 - does not suffer from backtracking problem. This means that when it elaborate a REs that carry some kind of non-determinsm (e.,g. a?a ) it does not take a guess and then backtrack but can explore all the different options in a single pass of the input string.

If you are interested in the topic I will suggest you to take a look at Russ Cox article

Here it follows an high level overview of Cicero Engines and how they can be combined together.

cicero_engine_multi_char cicero_multi_new_interconnection 1

Cicero has its own compiler that converts REs in our custom ISA.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

If you find this repository useful, please use the following citation:

@article{parravicini2021cicero,
    title = {{CICERO}: A Domain-Specific Architecture for Efficient Regular Expression Matching},
    author = {Daniele Parravicini and Davide Conficconi and Emanuele Del Sozzo and Christian Pilato and Marco D. Santambrogio}, 
    journal = {{ACM} Transactions on Embedded Computing Systems},
    year = 2021,
    month = {oct},
    publisher = {Association for Computing Machinery ({ACM})},
    volume = {20},
    number = {5s},
    pages = {1--24},
    doi = {10.1145/3476982},
    url = {https://doi.org/10.1145%2F3476982},
 }