Item Details

Print View

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

Wadden, Jack; Wang, Ke; Stan, Mircea; Skadron, Kevin
Format
Report
Author
Wadden, Jack
Wang, Ke
Stan, Mircea
Skadron, Kevin
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.
Language
English
Date Received
2016-04-04
Published
University of Virginia, Department of Computer Science, 2015
Published Date
2015
Rights
All rights reserved (no additional license for public reuse)
Collection
Libra Open Repository

Availability

Access Online