Uses for Random and Stochastic Input on Micron’s Automata Processor

Report
Authors:Wadden, Jack, Department of Computer ScienceUniversity of Virginia Wang, Ke, Department of Computer ScienceUniversity of Virginia Stan, Mircea, Department of Computer ScienceUniversity of Virginia Skadron, Kevin, Department of Computer ScienceUniversity of Virginia
Abstract:

Micron's Automata Processor (AP) is a configurable memory-based device, purpose-built to emulate a theoretical non-deterministic finite automata (NFA). While NFAs are not particularly suited for floating point computation, they are extremely powerful and effcient pattern matchers and have been shown to provide large speedups over traditional von Neumann execution for rule-based, data-mining applications. While these kernels like associative rule mining, Brill tagging, protein motif identification have seen impressive orders of magnitude speedups, the exact capabilities of the AP and its advantage over traditional von Neumann architectures like CPUs and GPUs remains an open research area. As an example of the potential power of the AP, we demonstrate its ability to simulate probabilistic automaton and accomplish stochastic computation using a random or stochastic input stream. The combination of probabilistic automata and stochastic computation open up a wide range of application kernels, previously not known to be implementable on the AP, with the potential for impressive speedups over CPUs and GPUs. This paper first presents the construction of probabilistic automata, and shows how they can be used to simulate Markov chains, Brownian motion, and stochastic computation. We then suggest small, low-cost changes to the AP architecture that would enable more effcient construction of these previously unimplementable application kernels.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Wadden, Jack, Ke Wang, Mircea Stan, and Kevin Skadron. "Uses for Random and Stochastic Input on Micron’s Automata Processor." University of Virginia Dept. of Computer Science Tech Report (2015).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2015