---
# System prepended metadata

title: Automata
tags: [Accelerator]

---

# Automata
###### tags: `Accelerator`
###### members: @張凱雋

## Home Page
* [CGRA 統整](https://hackmd.io/5e12xCClQJ-A2-JiVmKDKA)

## Topic 

## Prior Work
### Architecture
:::spoiler [**REAPR: Reconfigurable engine for automata processing**](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8056759&tag=1)
![](https://i.imgur.com/03gytvC.png)
:::

[**Automata Processing in Reconfigurable Architectures**](https://dl.acm.org/doi/pdf/10.1145/3314576)

[**APmap: An Open-Source Compiler for Automata Processors**](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9364279)

**Micron's Automata Processor**
* [An Efficient and Scalable Semiconductor Architecture for Parallel Automata Processing](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6719386)
* 



### Algorithm
:::spoiler [**Scalable FSM Parallelization via Path Fusion and Higher-Order Speculation**](https://dl.acm.org/doi/pdf/10.1145/3445814.3446705)
* Prior works fall into two basic parallelization schemes: 
![](https://i.imgur.com/4R11N7t.png)
    * **State enumeration**
        * Unknown starting state must be one of the states in the FSM, we can enumerate all of them by forking an execution path for each state.
    * **State speculation**
        * Guess the starting state of the second chunk, the predicted state must be validated against the ending state of the prior chunk
* Solution
    * **Path Fusion**
    * **Higher Order Speculation**
:::
## Weekly Progress
* [之前的](https://hackmd.io/@nycu-cas/SJL7oWTaO)