Non-deterministic Finite Automata (NFA) is a powerful computational model which is widely used in a number of application domains such as data analytics and data mining [7,41], network security [16,25,29,44], bioinformatics [13,34,42], tokenization of web pages [30], computational finance [1,28] and software engineering [2,11,32]. These applications require processing tens to thousands of patterns for a stream of input data. NFAs are especially useful for efficient regular expression matching, as they can provide high-speed analysis of unstructured textual data, which is being generated in large volumes in forms such as system logs, social media posts, emails, and news articles [17].
NFA computation is inherently hard to speedup using compute centric processing. Modern multi-core processors and accelerators [37,38] are limited by the number of transitions they can do in a given cycle. Both CPUs and GPGPUs perform poorly as automata processing is dominated by irregular memory access patterns and memory bandwidth limitations.
In comparison, a memory centric processing model can facilitate highly parallel and energy efficient processing of finite state automata in hardware. For instance, Micron's DRAM-based Automata Processor (AP) [14] has been shown to accelerate several applications like entity resolution in databases [7](by 434×) and motif search in biological sequences [34] (by 201×). Recent efforts at Virginia's Center for Automata Processing have demonstrated that AP can outperform x86 CPUs by 256×, GPGPUs by 32×, and accelerators such as XeonPhi by 62×, across a wide variety of automata benchmarks [39].
The success of memory centric models such as AP relies on two factors: massive parallelism and eliminating overheads in moving data between memory and compute units. Massive parallelism is due to the fact that all states (mapped to columns in DRAM arrays) can be independently activated in a given cycle. An AP chip can support up to 48K transitions in each cycle. Thus it can efficiently execute massive Non-deterministic Finite Automata (NFA) that encapsulate hundreds to thousands of patterns.
Given the large benefits of memory centric models, we explore cache as a substrate for automata processing. Caches have two advantages over DRAMs. First, SRAM-based caches are faster and more energy efficient compared to DRAM. Second, caches are integrated on processor dies which are manufactured in cutting edge technology nodes and performance optimized logic. Thus cache based automata processing can utilize significantly faster interconnects and logic.
On the flip side, caches typically have lower capacity compared to DRAM. Interestingly, we observe that DRAM-based AP sacrifices a huge fraction of die area to accommodate the routing matrix and other non-memory components required for automaton processing. An AP die can store 12 Mbits of data, while a conventional DRAM die of equivalent area can store 200 Mbits of data (16.6× area overhead) [18]. Thus, while DRAM memory's packing density is high, DRAM automata processor's packing density is comparable to caches. A rank of AP (8 dies) can accommodate 384K states. Typical high-performance processors can have 20-40MB of last level cache [8] and can accommodate 640K-1280K states, if the entire cache is utilized to save NFAs.
In this paper, we propose the Cache Automaton architecture which repurposes existing Last Level Cache (LLC) slices to enable efficient automata processing. While the memory technology benefits of moving to SRAM are apparent, repurposing the 40-60% passive LLC die area for massively parallel automata computation comes with several challenges. A naive approach that processes an input symbol every LLC access (∼20-30 cycles @ 4GHz), would lead to an operating frequency comparable to DRAM-based AP (∼200 MHz), negating the memory technology benefits. Increasing operating frequency further can be made possible only by two insights.
First, architecting an in-situ computation model that is cognizant of the internal geometry of LLC slices. We observe that LLC access latency is dominated by wire-delays inside a cache slice, accessing upper-level cache control structures, and network-on-chip. Thus, while a typical LLC access can take ∼30 cycles, an SRAM array access is only 1 cycle. Fortunately, in-situ architectures such as cache automaton require only SRAM array accesses and do not incur the overheads of a traditional cache access. Furthermore, we leverage the internal geometry of LLC slices to build a hierarchical state-transition interconnect.
Second, accelerating the two phases of input symbol processing common in memory-centric automata processing models. These are state-match, where the set of active states whose label matches the input symbol are determined through an array read operation and state-transition, where the matching states activate their corresponding next states by propagating signals through wires and switches. Accelerating state-match is challenging because industrial LLC subarrays are optimized for packing density and designed in a manner that many bit-lines share I/O (or sense amplifiers) via a column multiplexer. In our LLC design modeled exactly after the Xeon E5 processor [10,19], 8 states share a sense amplifier. This implies that reading out all states will require 8 cycles, resulting in a low throughput system. We observe that unlike conventional cache accesses, automata processing requires reading out all the bits which are sharing a sense amplifier and propose a sense amplifier cycling technique to address this bottleneck. In the optimized read sequence, all the bit-lines are pre-charged in parallel, which is then followed by sequential sensing of each bit-line. This optimization can improve our system throughput by 2×-3× depending on state packing density.
Accelerating state-transition at low-area cost requires the design of a scalable interconnect that efficiently encodes and supports multiple state-transitions on the same cycle, often to the same destination state. Automata switches also need to store a large array of connectivity bits that are representative of transition edges between states. We observe that an 8T SRAM memory array can be repurposed to become a compact state-transition crossbar for automata. Alternatively, traditional crossbar designs that require arbitration every cycle for determining input-output connections have prohibitive area costs. Furthermore they cannot support large fan-in of states, i.e. multiple inputs connecting to one output. Supporting this feature would need multiple arbitrations/traversals through the crossbars or multiple crossbars, making the state-transition either slow or have higher area overheads.
Even with such compact switches, supporting all-to-all connectivity between states requires prohibitively large and slow switches. We observe that large real-world NFA are typically composed of several connected components, each of which can be grouped into densely connected partitions with only few (8)(9)(10)(11)(12)(13)(14)(15)(16) interconnections between partitions. This motivated us to explore a hierarchical switch topology with local switches providing rich intra-partition connectivity and global switches providing sparse inter-partition connectivity. To this end, we develop a Cache Automaton compiler which scales to real world NFAs with several thousand states and maps them efficiently to hundreds of SRAM arrays. Our compiler uses graph partitioning techniques [23] to satisfy the connectivity constraints while maximizing space utilization.
To further improve throughput and parallelism, we develop a fully pipelined design. Pipelining is possible because Cache Automaton processes a stream of input symbols (MBs to GBs) sequentially, and SRAM access for the current input symbol can be overlapped with the switch propagation delay for processing the previous input symbol.
In summary this paper offers the following contributions:
• This is the first work to explore automata processing in cache.
In this section we provide an overview of NFAs, explain the concept of Cache Automaton and provide a simple working example.
A Non-deterministic Finite Automaton (NFA) is formally described by a quintuple ⟨Q, Σ, δ , q 0 , F⟩, where Q is a set of states, Σ is the input symbol alphabet, q 0 is the set of start states and F is the set of reporting or accepting states. The transition function δ (Q, α ) defines the set of states reached by Q on input symbol α. The nondeterminism is due to the fact that an NFA can have multiple states active at the same time and have multiple transitions on the same input symbol. The classic representation is transformed to ANML NFA representation [14] where each state has valid incoming transitions for only one input symbol. Thus each state in an ANML NFA can be labeled by one unique input symbol. There exists various algorithms (e.g. [35]) to transform a classical NFA to an optimized ANML NFA format. Figure 1
ANML NFA computation entails processing a stream of input symbols one at a time. Initially, all the start states are active states. Each step has two phases. In state match phase, we identify which of the active states have the same label as the current input symbol. In the next state transition phase, we look up the transition table to determine the destination states for these matched states. These destination states would become the active states for the next step. Now, we discuss how Cache Automaton implements these two phases efficiently. State Match: We adapt Micron's AP processor [14] design for implementing the state match phase. Each NFA state is mapped as a State Transition Element (STE) to a column of SRAM arrays in the last-level cache. The value of an STE column is set to the one-hot encoding of the 8-bit input symbol it is mapped to. This means that each STE (or column) is 256 bits and each bit position signifies an input symbol in the ASCII alphabet. Figure 2 (a) shows an SRAM array in Cache Automaton which holds 256 STEs. Every cycle, the current input symbol is broadcasted to all SRAM arrays as a row address and the corresponding row is read out. If an STE has a '1' bit set in the row, it means that the label of the state it has stored matches the input symbol. Thus, by broadcasting the input symbol to all SRAM arrays, it is possible to determine in parallel all the states which match the current input symbol.
The row corresponding to the input symbol is read out and stored in a match vector. An active state vector (one bit per STE; 256-bit vector in our example) stores which STEs are active in a given cycle. A logical AND of match and active state vectors determines the subset of active states which match the current input symbol. The destination states of these matched states would become the next set of active states. Section 2.6 discusses solutions to implement this state match phase efficiently in cache sub-arrays. State Transition: This phase determines the destination states of the matched states found in the previous phase. These states would then become the next set of active states. We observe that a matrix-based crossbar switch (essentially a N × N matrix of input and output ports) is suitable to encode a transition function. In a crossbar, an input port is connected to an output port via a cross-point. Each STE connects to one input port of the switch. A cross-point is enabled if the input STE connects to a specific output STE. The result of state-matches serve as inputs to the switch, and the output of the switch is the next set of active states.
The switches in the cache automaton architecture have modest wiring requirements (256-512 input and output wires; see Table 2), as data-bus width is only 1-bit. However, cache automaton switches have two major differences from conventional switches. First, there is no need for arbitration. The connections between the input and output ports can be configured once during initialization for an NFA and then used for processing all the input symbols. Since there is no arbitration, the enable bits must be stored in the crosspoints. Automaton switches have a large number of cross-points, and therefore we need a compact design to store the enable bit at each cross-point. Second, unlike a conventional crossbar, an output can be connected to multiple inputs at the same time. The output is a logical OR of all active inputs. Section 2.7 discusses our proposed switch architecture for Cache Automaton which supports the above features.
Ideally, the entire transition function could be encoded in one switch to provide maximum connectivity. However, such a design will be incredibly slow. To scale to thousands of states and many SRAM arrays, we adopt a hierarchical switch architecture as discussed in Section 2.4.
We describe a simplified example which brings together all the above concepts. Figure 1 shows an example NFA which accepts patterns {bat, bar, bart, ar, at, art, car, cat, cart} and how it is mapped to SRAM arrays and switches. The figure starts with a classical representation of an NFA in terms of states and transitions (Figure 1 (a)). Figure 1 (b) shows ANML NFA representation for the same automata. Figure 1 (c) shows the transition table for ANML NFA with STEs. This example NFA requires only 8 STEs. Real world NFAs have tens of thousands of states which need to be mapped into hundreds of SRAM arrays.
For this example, let us assume we have two small SRAM arrays which can each accommodate 4 STEs as shown in Figure 1 (d). The NFA requires 8 STEs, so we split the states into 4 STEs in Array_1 and Array_2. Each array has a 6 × 4 local switch, and together they share a 2 × 2 global switch. Each STE can connect to all STEs in its array. In this example, only two STEs (ST E 1 and ST E 2 ) in an array are allowed to connect to all STEs in the other array via the global switch.
The transition table in Figure 1 (c) is mapped to local and global switches. For instance, S 1_a and S 4_r , are mapped to ST E 1 and ST E 3 , of Array_1. Since S 1_a can transition to S 4_r , the local switch crosspoint between ST E 1 and ST E 3 is set to connected (represented by black dot). The figure also shows how a connection via global switch is established for states S 2_a mapped to ST E 2 of Array_1, and S 4_t mapped to ST E 4 of Array_2. This is accomplished by (1) feeding ST E 2 as an input to global switch, (2) connecting second input of global switch to G 4 output which feeds as an input to Array_2's local switch, (3) G 4 input is connected to ST E 4 output (or S 4_t ) of Array_2's local switch.
The proposed cache automaton is implemented in the Last-Level Cache (LLC) in order to accommodate large NFA with thousands of states. Figure 2 (b) shows the overall organization of a slice of LLC with the Cache Automaton architecture. The depicted LLC slice is modelled exactly after Xeon E5 processors [10,19]. Each LLC slice is 2.5MB. Intel processors support 8-16 such slices [8]. Each slice has a central cache control box (CBOX). Remainder of the slice is organized into 20 columns. A column consists of eight 16 KB data sub-arrays, and a tag array. Each column represents a way of setassociative cache. Internally a 16 KB data sub-array consists of four SRAM arrays with 256×128 6T bit-cells as shown in Figure 2 (c). Each array has 2 redundant columns and 4 redundant rows to map peak power is high, the energy consumed is orders of magnitude lower than that expended by conventional CPUs due to savings in data movement and instruction processing overheads.
We adopt a configuration model similar to Micron's Automata Processor (AP). Before processing the NFA, the switches have to be configured and the cache arrays have to be initialized with STEs. The switches can be configured by utilizing their write-mode, where they simply function as SRAM arrays. We assume switch locations are I/O mapped and addressable by CPU load instructions.
The initialization of cache arrays can be done by CPU load instructions which fetch data from memory to caches. Our compiler creates binary pages which consists of STEs stored in the order in which they need to be mapped to cache arrays. The compiler carefully orders the STEs based on physical address decoding logic of underlying cache architecture. These binary pages with STEs are loaded in memory, just like code pages. Most LLC cache sets are addressable by last 16 bits of memory address. These bits can be kept same for both virtual pages and physical pages by mapping the binary data (containing STEs) to huge pages [24]. LLC hashing is disabled during configuration as discussed in Section 2.9.
The average initialization time is dictated by the number of SRAM arrays occupied by an NFA. For our largest benchmark, we found this to be about 0.2ms on a Xeon server workstation. In contrast AP's configuration time can be up to tens of milliseconds [36]. Once configured, in typical use cases such as log processing, network traffic monitoring and DNA alignment, NFAs typically process GBs/TBs of data, thus processing time easily offsets configuration time. But configuration may be costly when frequently switching between structurally different automata. For these, optimizations like overlapping the configuration of one LLC slice with processing in others and prefetching may be explored. We leave this exploration to future work.
An ISA interface is required to specify (1) when to start processing in Cache Automaton mode and (2) start address from which input data needs to fetched to fill up input FIFO buffer. (3) the number of input symbols to be processed. One new instruction can encapsulate all the above information. Compiler can insert this special instruction in code whenever it needs to process NFA data. An interrupt service routine handles output buffer full reporting events.
In this section we explain our compiler that takes as input an NFA description consisting of several thousands of states and efficiently maps them onto cache banks and sub-arrays. Care is taken to ensure maximum cache utilization while respecting the connectivity constraints of the underlying interconnect architecture. The algorithms proposed are general and the insights provided are also applicable for mapping NFAs to any spatial reconfigurable substrate with memory like FPGAs or memristor crossbar arrays.
The compiler takes as input an NFA described in a compact XML-like format (ANML) and generates a bit-stream containing information about the NFA state to cache array mapping and the configuration enable bits to be stored in the various crossbar switches of the automaton interconnect. We propose two mapping policies leading to two Cache Automaton designs, one optimized for performance CA_P and the other optimized for space utilization CA_S. Before proceeding to explain the mapping algorithm used by the compiler (Section 3.2), we motivate the insights behind each of these designs in Section 3.1.
Real-world NFAs are composed of several connected components (CCs) with only a few hundred states each. Each connected component describes a pattern or group of common patterns to be matched. Since these connected components have no state transitions between them, they can be treated as atomic units by the mapping algorithm. Each connected component can be viewed as operating independently matching against the input symbol in parallel.
Performance Optimized Mapping: In their baseline NFAs, most benchmarks have connected components with less than 256 states (refer Table 1), making it possible to fit at least one connected component in each partition (256 STEs stored in two 4KB SRAM arrays, Figure 2 (a)). This motivates our performance-optimized mapping scheme that greedily packs connected components onto cache arrays. We were able to operate all of the baseline NFA benchmarks while limiting the connectivity across cache arrays to within a way. Only cache arrays which are mapped to physical address with A[16] = 0 (Array_L in Figure 2 (c)) are used for mapping NFA and cache arrays with A[16] = 1 (Array_L in Figure 2 (c)) can be used for storing regular data provided that compiler can ensure that regular data are placed in 64KB segments in the virtual address space or does not use physical pages with A[16] = 1. As we discuss in Section 5.1, the performance-optimized design can operate at a frequency of 2 GHz.
Space Optimized Mapping: However, just using the baseline NFAs forgoes algorithmic optimizations on NFAs that seek to remove redundant automata states and state traversals. These redundancies are common in practice, since many patterns share common prefixes (for example, patterns like art and artifact) and these common prefixes can be matched once for all connected components together. Eliminating redundancies helps reduce the space footprint of the NFA. It also reduces the average number of active states, leading to reduction in dynamic energy consumption. This has been the motivation for several state-merging algorithms in literature that merge common prefixes across pattens [4]. However, it must be kept in mind that since these optimizations merge states across many connected components they tend to reduce the number of connected components and increase the average connected component size. Larger connected components require richer connectivity and demand more interconnect resources (crossbar switches and wires). To support such state-merged NFA, we propose a space-optimized mapping policy that leverages graph partitioning techniques (Section 3.2) to minimize outgoing edges between partitions. We also provision additional global crossbar switches to ensure connectivity across 4-8 ways of a cache slice. Our hierarchical switch design provides a richer average fan-out transitions and fan-in transitions per state compared to the AP (Section 5.4). However, richer connectivity comes at the cost of higher latency due to increased wire delay, therefore the space-optimized design operates at a lower frequency (1.2 GHz) compared to the performance-optimized design (2 GHz).
The algorithm takes as input the ANML NFA description of the benchmark, the number of cache arrays available and the size of each cache array. The output is a mapping of NFA states to cache arrays. It operates in three steps. In the first step, all connected components which have size less than partition_size (i.e., 256 states) are identified. As discussed earlier, a connected component forms the smallest mapping unit. Next, these connected components are mapped greedily onto the cache arrays to pack multiple connected components onto the same cache array when possible. We do not partition the connected component in the first stage, since the connected component inherently groups together states that have plenty of state-transitions between them and mapping these states to the same array leads to a more space-efficient packing. Connected components larger than partition_size, need to be partitioned across k-different partitions (in the same way or across multiple ways of the cache slice). We utilize the open-source graph partitioning framework METIS [23] to solve this k-way partitioning problem. METIS partitions the connected component into different partitions such that the number of outgoing state transitions between any two partitions is minimized. It works by first coarsening the input connected component, performing bisections on the coarsened connected component and later refining the partitions produced to minimize the edge cuts. We ensure that METIS produces load-balanced partitions with nearly equal number of states per partition. For all of our benchmarks (in Table 1) METIS consistently produces connected component partitions that have less than 16 state-transitions between them. The maximum number of outgoing state-transitions from an array determines the radix of the global-switch to be supported. From the final mapping obtained, it can be seen that a fairly dense packing of CCs is achieved. It can be seen that both CC 0 and CC 1 are allocated the same array. CC 2 takes up a separate array while CC 4 spans across 3 ways. Local switches at each array and global switches for both 1 and 4 ways support intra-array and inter-array state transitions respectively. Furthermore, the densely connected arrays for CC 4 (having many outgoing transitions) are also allocated to arrays in the same way.
In this section we first describe our workloads, followed by a discussion on the experimental setup and finally report the different system parameters.
NFA workloads: We evaluated the proposed approach and mapping schemes on a wide range of benchmark FSMs from the AN-MLZoo [39] and the Regex [5] benchmark suites. These real world benchmarks span multiple domains including network packet monitoring [5], gene sequence matching [34] and natural language processing [49]. The NFAs used in this work form the core of many end-to-end applications. For example, the oligo_scan routine used for pattern matching in Weeder 2.0, an open-source tool for motif discovery in DNA sequences, uses an automaton similar to Protomata that contributes 30-62% of the total runtime. In the Apriori algorithm for frequent itemset mining, NFA processing accounts for 33-95% of the execution time, based on the frequency threshold. FSM-like computations form the core of many activities inside a web browser, taking about 40% of the loading time for many web pages [22,48]. Table 1 summarizes some of the important characteristics of these FSMs and the parameters used in our simulations. We used the 10MB input traces for our evaluation. Similar trends in results are observed for larger inputs.
Experimental Setup:
We utilize the open-source virtual automata simulator VASim [39] to simulate the proposed architecture. VASim allows for fast NFA emulation by traversing paths only for active states. The simulator takes as input the NFA partitions produced by METIS and simulates each input cycle by cycle. After processing the input stream, we use the per-cycle statistics on number of active states in each array to derive energy statistics.
Table 2 provides the various delay and energy parameters assumed in our design. To estimate the area, power and delay of the memory array we use a standard foundry memory compiler for the 28nm technology node. The nominal voltage for this technology is 0.9 Table 2: Switch Parameters V. Our 8T crossbar switches are similar to an 8T SRAM array, except without the associated decoding and control logic overheads present in a regular 8T SRAM array. The energy for access to 6T 256 × 256 cache sub-arrays was estimated to be 22pJ. The global wire delays were determined using wire models from the design kit using SPICE modeling. Our analysis takes into account crosscoupling capacitance of neighboring wires and metal layers. The global wires have pitch 1µm and are routed on 4X metal layers with double track assignment and repeaters spaced 1mm apart. The wire delay was found to be 66ps/mm and wire energy was found to be 0.07pJ/mm/bit.
In this section we first present the speedups obtained by the proposed Cache Automaton (CA) architecture, followed by analysis of cache space utilization, energy consumption and reachability of the proposed automaton architecture. As discussed in Section 3.1, we evaluate two designs for Cache Automaton. The first design is optimized for performance, and provides lower connectivity. We refer to the performance optimized design as CA_P and space optimized design as CA_S throughout the results section.
Overall performance of the Cache Automaton is dictated by the clockperiod of pipeline. Table 3 shows the delay of various pipeline stages across both performance optimized and space optimized designs. For the performance optimized design (CA_P), the state-match stage accesses 256 STEs. In our proposed architecture modelled after Xeon's LLC slice, each 16KB data sub-array is 8-way multiplexed. Internally the sub-array is organized into two 8KB chunks which can operate independently. Each chunk has two halves: Array_H and Array_L which share I/O and 32 sense-amps. Each half consists of 256 × 128 6T SRAM arrays. A column multiplexer in each half feeds 32 sense-amps, allowing only 32 bits to be read in a cycle per chunk. Thus, together across the two chunks, it is possible to match 64 STEs in a cycle. The SRAM arrays can operate from 1.2 GHz to 4.6 GHz frequency range [10,19]. We limit the highest possible operating frequency for each SRAM array to 4 GHz or 256 ps cycle time. Thus four cycles or 1024ps is necessary to match 256 STEs without sense-amplifier cycling. With our proposed sense-amplifier cycling optimization, the state match time for 256 STEs is 438ps as shown in Table 3 The G-Switch stage requires 227ps composed of 99ps due to wire-delay and 128ps due to global switch. The distance between SRAM array and global switch is estimated to be 1.5mm assuming a slice dimension of 3.19mm × 3mm. The L-Switch stage requires 263ps. The pipeline clock period or frequency is determined by the slowest stage. Thus the maximum possible frequency for (CA_P) is 2.2 GHz. We choose to operate at 2 GHz. For the space optimized design (CA_S), an operating frequency of 1.4 GHz can be achieved and we choose to operate at 1.2 GHz. The space optimized design is slower due to longer wire delays between the arrays and global switch, and larger global switches.
In the Cache Automaton, since all state-matches and state-transitions can happen in parallel, the system has a deterministic throughput of one input symbol per cycle and is independent of input benchmarks. This is true for Micron's Automata Processor (AP) as well which
The Unified Automata Processor (UAP) [15] and HARE [17] are two recently proposed accelerators that have demonstrated impressive line rates for automata processing and regular expression matching on a number of network intrusion detection and log processing benchmarks. UAP is noteworthy because of its generality and ability to efficiently support many finite automata models using state transition packing and multi-stream processing at low area and power costs. Similarly, HARE has been able to saturate DRAM bandwidth (256 Gbps) while scanning up to 16 regular expressions.
The major advantage of Cache Automaton is its ability to execute several thousand state transitions in parallel (e.g., 128K state transitions in a single cycle using 8 ways of LLC slice). This massive parallelism enables matching against several thousand patterns (e.g., 5700 in Snort ruleset), while achieving ideal line rate, i.e., 1 symbol/cycle. In contrast, HARE incurs high area and power costs (80mm 2 ,125W) when scanning for more than 16 patterns and UAP's line rate drops for large NFA patterns with many concurrent activations, 0.27-0.75 symbols/cycle [15]. For fair quantitative comparison, we use Dotstar0.9, containing 1000 regular expressions and ∼38K states as used in UAP/HARE for a 10MB input stream. It must be noted that CA can support >3000 such regular expressions using less than 8 ways of LLC slice and shows greater benefits for larger number of patterns and if more ways are used to store NFA. From Table 5, it can be seen that CA_P and CA_S provide 3.9× and 2.34× speedup over HARE and 3× and 1.8× speedup over UAP respectively. While UAP is more energy efficient than CA_P due to efficient compression of statetransitions, CA_S can provide comparable energy efficiency while repurposing the LLC. Note that the 16 kB local memory in UAP can accommodate only few Dotstar0.9 patterns without memory sharing across lanes and we expect several additional DRAM accesses for reading new patterns. This energy is not accounted in Table 5. UAP incurs lesser area overhead than CA_P and CA_S, but its 8-entry combining queue may be insufficient to support benchmarks with several thousand active states (e.g., Fermi-4715).
To the best of our knowledge, this is the first work that demonstrates the feasibility of in-situ FSM processing in the last-level cache. Below we discuss some of the closely related works.
Compute-Centric Architectures: Compute-centric architectures typically store the complete state-transition matrix as a lookup table in cache/memory. These architectures have main limitations: (1) need for high memory bandwidth or memory capacity especially for large NFA with many active states and (2) high instruction processing overheads per state transition (as many as 24 x86 instructions for a single DFA state transition [6]). As a result, several CPU/GPUbased automata processing engines have either limited themselves to DFAs [3,6,45,46] or have explored SIMD operations to deal with the high cache miss rates and branch misprediction rates [26,30]. Several speculative and enumerative parallelization approaches have also been proposed to speedup FSM processing [21,30,33,47,48]. However, all of the above approaches have been evaluated only for small DFA. Scaling these approaches to NFAs is non-trivial because of the huge computational complexity involved [43].
ASIC implementations: While several regular expression matching and NFA processing ASIC designs have been proposed in literature [37,38], we extensively discuss and evaluate two most relevant and recent designs, HARE [17] and the Unified Automata Processor (UAP) [15] in Section 5.6. In general, while ASIC implementations offer high line rates for small DFA/NFA, they are limited by the number of parallel matches and state transitions.
Memory-Centric Architectures: Memory-centric architectures like the Micron Automata Processor (AP) [14,40] leverage the inherent bit-level parallelism of DRAM to support multiple parallel state matches at bandwidths that far exceed available pin bandwidth with reduced instruction processing overheads. A programmable routing matrix enables efficient support for state-transitions without the associated data movement costs as in a compute-centric architecture. Since the DRAM AP is not optimized for logic, it is slower and runs at a low frequency (133 MHz), with the routing matrix accounting for nearly 30% of the die area. In this work we demonstrate that several real world NFA can be efficiently mapped onto LLC arrays and propose two fully-pipelined designs that provide nearly an order of magnitude throughput improvement compared to AP at low area overheads. Similar to the Micron AP whose throughput scales with the number of ranks and devices, the Cache Automaton architecture can also exploit increased cache capacity in multi-chip/multi-socket servers for throughput scaling based on the peak power requirements of different NFAs.
This paper proposes the Cache Automaton architecture to accelerate NFA processing in the last-level cache. Efficient NFA processing requires both highly parallel state-matches as well as an interconnect architecture that supports low-latency transitions and rich connectivity between states. To optimize for state-matches we propose a sense-amplifier cycling scheme that exploits spatial locality in statematches. To enable efficient state transitions, we adopt a hierarchical topology of highly compact 8T-based local and global switches. We also develop a Cache Automaton compiler that fully automates the process of mapping NFA states to SRAM arrays. The two proposed designs are fully pipelined, utilize on an average 1MB of cache space across benchmarks and can provide a speedup of 12× over AP .