Compiling Regular Expressions into Non-Deterministic State Machines for Simulation in SystemC

Abstract

With Moore s law exponentially increasing the number of transistors on inte-grated circuits, developers fail to keep up. This makes chip area an increasinglycheap resource. At the same time, researchers and developers are trying to findways to dynamically reconfigure FPGAs, preferably at run time, so as to in-crease the flexibility of hardware solutions, and close the gap between the speedof hardware and flexibility of software. A proposed way of solving both of theseissues at once is by using nondeterministic finite-state machines as a fundamen-tal unit of design. This could provide great flexibility and dynamic hardwaresolutions, but before this can be known for sure, a system like this would needto be simulated. This paper documents the planning and development of a Sys-temC library that creates nondeterministic finite-state machines from regularexpressions, and a special regular expression syntax designed for this specificapplication. The paper can also be used as a reference for the inner workingsof, and how to use, the library.