bit FCB mode except the code length and the number of working CAMs.
Although this mode has the max compression for symbol classes, this 32-bit mode has the worst area utilization and consumes the highest power.

\subsection{Pipeline, Input and Output}
There are two versions of CAMA, namely CAMA-E and CAMA-T, targeting high energy efficiency and high throughput, respectively. CAMA-E saves energy by only precharging the enabled STEs during state transition (Figure~\ref{circuit}(a)), where the transition results are directly sent back to CAM and the column precharger performs the AND operation. However, CAMA-E cannot pipeline state matching and state transition because the next symbol must obtain the transition results from the last symbol but the direct feedback causes conflicts. As shown in Figure~\ref{circuit}(a), the non-pipelined architecture leads to relatively low clock frequency. On the other hand, CAMA-T, a configuration optimized for throughput, connects transition results to AND gates instead of feeding back them to the CAM to realize the pipeline as shown in the Figure~\ref{circuit}(b) and Figure~\ref{pipeline}(b). In the state matching phase, the results are stored in the Match Vector register which acts as the pipeline register. The rest of the operations are similar to CA. Since the trade-off between the energy and throughput is application-dependent, we evaluate both non-pipelined (CAMA-E) and pipelined (CAMA-T) in the experiments.





\begin{figure}[t]
      \centering
      \includegraphics[scale=0.3]{pipeline16_crop.pdf}
      \vskip -2.5ex
      \caption{Timing diagram of (a) non-pipeline and (b) pipeline implementations.}
      \label{pipeline}
        \vskip -3ex
  \end{figure}
As for the data storage, CAMA uses two buffers to store the input symbols and output report vectors. The input symbols are stored in the 128-entry input buffer similar to CA. Every cycle one symbol is deleted and distributed to all arrays through the bus. Every time the input buffer is empty, the buffer will cause an interruption and get a set of new symbols. 
\par
A 64-entry output buffer is designed to keep a similar interruption frequency between input and output. Similar to input interruption, every time the output buffer is full, an interruption is sent to the CPU, and CPU will get the reports and clear all entries. \cite{wadden_characterizing_2018} characterizes the reporting behavior on ANMLZoo, showing that 10 out of 12 benchmarks have less than 0.5 reports per cycle on average on 1MB input.
Therefore, this ratio inspires us to adopt the 64-entry output buffer to hide the output interruption behind input interruption. Each entry stores the matching results and the corresponding reporting state ID. The mapping of the report states is realized by setting up a report mask for each bank. Once a report is detected, the bank will create an output entry and store the active state ID, partition ID, input symbol, and the reporting cycle.
\section{Evaluation Methodology}
\par
\noindent\textbf{NFA workloads: }We evaluate the proposed architecture and algorithmic optimization by using ANMLZoo\cite{wadden_anmlzoo_2016} and Regex\cite{becchi_workload_2008} benchmarks. These benchmarks cover a wide range of real-world applications, including network intrusion detection\cite{becchi_workload_2008}, machine learning, gene sequence matching\cite{roy_discovering_2016} and data mining\cite{wang_pattern_mining_2016}. While a more recent benchmark suite AutomataZoo\cite{wadden_automatazoo_2018} extends ANMLZoo with larger benchmarks. ANMLZoo is selected in our evaluation because (1) the AP chip with up to 48k states only supports ANMLZoo, (2) evaluating an automata accelerator on large benchmarks in AutomataZoo is excessively time consuming, and (3) 
prior studies on automata acceleration, including CA~\cite{subramaniyan_cache_2017}, Impala~\cite{sadredini_impala_2020}, AP~\cite{dlugosch_efficient_2014}, FlexAmata~\cite{sadredini_flexamata_2020}, and Grapefruit~\cite{rahimi_grapefruit_2020}, all adopt ANMLZoo for evaluation. 10MB inputs are used for all evaluations. 
\par
\noindent\textbf{Experiment Setup: }The open-source virtual automata simulator VASim~\cite{wadden_anmlzoo_2016} is used to evaluate CAMA and prior designs. VASim is modified to support the proposed encoding scheme. The simulator takes in one ANML or MNRL file, and calculates matches and transitions of each input symbol cycle by cycle and provides cycle-accurate energy estimation of the archtectures.

Table~\ref{table:symbol-set} lists memory parameters in our evaluations, including access energy, delay and area. These numbers come from SPICE simulations on custom designed SRAM and CAM arrays in TSMC 28nm CMOS. The 6T SRAM parameters at different sizes and configurations are very close to 6T SRAMs from TSMC compilers. We cannot entirely rely on the compiler because it does not offer some of the memory types and configurations in our evaluations. For fair comparison, we re-simulate SOTA architectures with the same circuit models. 

\par

\begin{table}[t]
\vskip -1.5ex
  \caption{Circuit models in 28nm}
\centering
\vskip -2.5ex
  \begin{adjustbox}{width=\columnwidth, center}
  \huge
  \begin{tabular}{c|ccccc}
  
    \hline
   
   
   
    
     {\textbf{Type}} & {\textbf{Size}} & {\textbf{Energy (pJ)}} & {\textbf{Delay (ps)}} & {\textbf{Area ($\mu$m$^2$)}}& {\textbf{Leakage ($\mu$A)}} \\
    \hline
    \hline
   
   
    
    
   
   
   
    \multirow{2}{*}{6T SRAM}
   
    
     & 256$\times$256&19.45&416&14877&532\\
    \cline{2-6}
     & 16$\times$256& 15.3&317&3659&247\\
    \hline
   
   
    
    
     \multirow{2}{*}{8T SRAM} & 128$\times$128 & 8.67& 292& 5655&243 \\
    \cline{2-6}
    
    & 256$\times$256&17.9&394&18153&584\\
   
   
    \hline
    8T CAM & 16$\times$256&16.78& 325& 3919&299\\
   
    \hline
  
  \end{tabular}
  
  \end{adjustbox}
  
  \label{table:symbol-set}
  \vskip -3ex
\end{table}

\section{Results}
In this section, we first compare the throughput of existing in-memory automata processors, followed by analysis of area efficiency, compute density and energy/power consumption. 

\subsection{Overall Performance}

The overall performance of the spatial automata processing architectures is defined as the clock period or throughput (frequency$\times$bits/cycle). As Table~\ref{table:delay} shows, CAMA and 2-stride Impala’s state matching has less delay than CA and eAP. This is because both designs have a denser state matching array and reduce the length of BLs from 256 to 16. Shorter BLs result in less RC delay. Benefiting from the compact local switch design, CAMA and eAP will have less delay in local switch. Because of the long-distance routing in the global switch, the delay consists of two parts: the wire delay and the memory access delay. Based on CA's model, the wire delay on global routing is 99ps. As a result, the global delay for CA is 493ps with 394ps read delay and 99ps wire delay in 28nm. Since 2-stride Impala has 2$\times$ less state matching area overhead than CA and CAMA is 4$\times$ less than CA (area listed in Table~\ref{table:symbol-set}), the wire delay of 2-stride Impala and CAMA is estimated as 48.69ps and 26.1ps, repectively. Due to the large area of 8T SRAM in state matching, eAP has the largest wire delay of 121ps.
It is worth mentioning that the original three-stage pipeline used in CA will cause a data-hazard issue \cite{sadredini_eap_2019}. Thus, we adjust the original CA pipeline and make the local switch and global switch process simultaneously, similar to the settings in \cite{sadredini_eap_2019}. 
\par 
\begin{table}[t]
  \caption{Delays and frequency in 28