  Regular pattern matching is used in numerous application domains, including
text processing, bioinformatics, and network security. Patterns are typically
expressed with an extended syntax of regular expressions that include the
computationally challenging construct of bounded iteration or counting, which
describes the repetition of a pattern a fixed number of times. We develop a
design for a specialized in-memory hardware architecture for NFA execution that
integrates counter and bit vector elements. The design is inspired by the
theoretical model of nondeterministic counter automata (NCA). A key feature of
our approach is that we statically analyze regular expressions to determine
bounds on the amount of memory needed for the occurrences of counting. The
results of this analysis are used by a regex-to-hardware compiler in order to
make an appropriate selection of counter or bit vector elements. We evaluate
the performance of our hardware implementation on a simulator based on circuit
parameters collected by SPICE simulation using a TSMC 28nm process. We find the
usage of counter and bit vector quickly outperforms unfolding solutions by
orders of magnitude with small counting quantifiers. Experiments concerning
realistic workloads show up to 76% energy reduction and 58% area reduction in
comparison to traditional in-memory NFA processors.
