FASim: An Open Source Simulation and Analysis Platform for Finite Automata Applications and Architecture Research

  • Authors:
    John Wadden (UVA), Kevin Angstadt (UVA), Sanil Rao (UVA), Jesse Du (UVA), Mohamed E-Hadedy (UVA), Xiaoping Huang (UVA), Kevin Skadron (UVA)
    Publication ID:
    P089143
    Publication Type:
    Paper
    Received Date:
    8-Sep-2016
    Last Edit Date:
    8-Sep-2016
    Research:
    2384.007 (University of Michigan)

Abstract

Newly-available data-flow accelerators and software-development frameworks for execution of finite automata have inspired researchers to evaluate new application domains for finite automata. However, existing tools for finite automata transformations, evaluation, profiling, and automata processing architecture research are either inadequate or non-existent, slowing the pace of research in this field. We present FASim, an open, extensible Finite Automata Simulator for finite automata processing research. FASim is a common repository for optimizations and transformations, allowing for easy sharing of state-of-the-art automata processing methods and contains a highly optimized simulation core, enabling fast, multi-threaded functional evaluation of finite automata.

Additionally, we develop and validate a cycle accurate performance model for the Micron D480 Automata Processor using FASim and identify bottlenecks in the output reporting architecture. We then propose a new compiler optimization, which we call Disjoint Report Merging, and an architectural modification to the D480 to reduce the impact of these bottlenecks. We use the cycle accurate performance model to evaluate these modifications, and measure up to 93.4% reduction in output reporting overheads for real-world applications.