Our Research

The Center conducts fundamental research on foundations and applications of automata computing; the Automata Processor is a novel, massively parallel computational accelerator capable of 1-2 order-of-magnitude speedups within existing computer system form factors and power constraints.

The Center’s collaborative approach facilitates teaming and accelerates commercialization.Mission-driven agencies can partner with the Center to research how automata computing can address critical challenges, including NP-hard problems that are currently considered unsolvable. The Center’s partnership with UVa’s Applied Research Institute provides access to secure research facilities for conducting sensitive research and development.

Research areas include:

  • algorithm development
  • hybrid computing
  • new programming languages
  • biomedical informatics
  • business/consumer informatics
  • cyber-security
  • entity resolution
  • graph analytics
  • heirarchical temporal memory
  • natural language processing
As an emerging computer scientist and an early-career computer architecture researcher, I am thrilled to be working on Micron’s new Automata Processor (AP). The opportunity to be the first to benchmark, evaluate and develop applications for an industry-new technology is extraordinary.  I am drawn to the novelty of the AP’s unique MISD architecture.  We have already successfully demonstrated performance superiority of this new processor for certain class of applications.  I am very excited to continue my work exploring new capabilities for the AP.
quote1

Jack Wadden, Graduate Research Assistant

CAP Research Tools

MNCaRT

An open-source, multi-architecture automata processing ecosystem with Docker image.

VASIM

An Automata Simulator for the CPU.

ANMLZoo

Automata Benchmarks.

REAPR

A framework for accelerating automata on FPGAs.

DFAGE

A framework for accelerating DFAs on GPUs.

MNRL

JSON Automata Representation

AutomataToRouting

An open-source toolchain to design and evaluate island style spatial automata processing architectures.

CAP Publications, Reports, and Presentations

Performance Evaluation of Regular Expression Matching Engines Across Different Computer Architectures
V. Dang, J. Wadden, M. El-Hadedy, X. Huang, K. Wang, M. Stan, and K. Skadron. SRC TechCon, Austin, TX, 2016 (TECHCON2016)

Entity resolution acceleration using Micron’s Automata Processor
C. Bo, K. Wang, J. Fox, and K. Skadron. SRC TechCon, Austin, TX, 2016 (TECHCON2016)

Sequential pattern mining with the Micron Automata Processor
K. Wang, E. Sadredini, K. Skadron.  ACM International Conference on Computing Frontiers (CF 2016)

RAPID Programming of Pattern-Recognition Processors
K. Angstadt, W. Weimer, and K. Skadron.  Proceedings of the ACM International Symposium on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2016, to appear)

Brill Tagging on the Micron Automata Processor
K. Zhou, K. Wang, J. Fox, and D. Brown.  IEEE International Conference on Semantic Computing (ICSC 2015)

Entity Resolution using the Micron Automata Processor
C. Bo, K. Wang, J. Fox, and K. Skadron. 5th International Workshop on Architectures and Systems for Big Data (ASBD), in conjunction with the 42nd International Symposium on Computer Architecture (ISCA 2015).

Association Rule Mining with the Micron Automata Processor
K. Wang, M. Stan, and K. Skadron. 29th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2015).

Generating efficient and high-quality pseudo-random behavior on Automata Processors
J.Wadden, N. Brunelle, K. Wang, M. El-Hadedy, G. Robins, M. Stan, and K. Skadron. 2016 IEEE 344th International Conference on Computer Design (ICCD16)

An Overview of Micron’s Automata Processor
K. Wang, K. Angstadt, C. Bo, N. Brunelle, E. Sadredini, T. Tracy II, J. Wadden, M. R. Stan, and K. Skadron. Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), Oct. 2016.

Frequent Subtree Mining on the Automata Processor: Challenges and Opportunities
E. Sadredini, K. Wang, and K. Skadron. Proceedings of the ACM International Conference on Supercomputing (ICS), June 2017.

Automata-to-Routing: An Open-Source Toolchain for Design-Space Exploration of Spatial Automata Processing Architectures
J. Wadden, Samira Khan, and K. Skadron. Proceedings of the IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM), Apr. 2017.

MNRL and MNCaRT: An Open-Source, Multi-Architecture State Machine Research and Execution Ecosystem
K. Angstadt, J. P. Wadden, W. Weimer, and K. Skadron. Tech. Report CS-2017-01, Univ. of Virginia Dept. of Computer Science, May 2017

RAPID: Accelerating pattern search applications with reconfigurable hardware
K. Angstadt, J. Wadden, X. Huang, M. El-Hadedy, W. Weimer, and K. Skadron, SRC TechCon, Austin, TX, 2016 (TECHCON2016)

Toward machine learning on the Automata Processor
T. Tracy II, Y. Fu, I. Roy, E. Jonas, P. Glendenning. International Supercomputing Conference – High Performance Computing (ISC-HPC 2016).

Cellular Automata on the Micron Automata Processor
K. Wang and K. Skadron; University of Virginia Technical Report #CS-2015-03.

Nondeterministic Finite Automata in Hardware – the Case of the Levenshtein Automaton
T. Tracy, M. Stan, N. Brunelle, J. Wadden, K. Wang, K. Skadron, G. Robins. 5th International Workshop on Architectures and Systems for Big Data (ASBD), in conjunction with the 42nd International Symposium on Computer Architecture (ISCA 2015).

Regular expression acceleration on the micron automata processor: Brill tagging as a case study
Zhou et al;  IEEE International Conference on Big Data (Big Data 2015)

Fast Track Pattern Recognition in High Energy Physics Experiments with the Automata Processor

M. Wang, , G. Cancelo, C. Greena, D. Guo, K. Wang, and T. Zmuda. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment.

ANMLZoo: A benchmark Suite for exploring bottlenecks in Automata Processing engines and architectures
J. Wadden, V. Dang, N. Brunelle, T. Tracy, D. Guo, E. Sadredini, K. Wang, C. Bo, G. Robins, M. Stan, and K. Skadron. 2016 IEEE International Symposium on Workload Characterization (IISWC’16)

Feature Extraction and Image Retrieval on an Automata Structure
T. Ly, R. Sarkar, K. Skadron, and S. T. Acton. Proceedings of the 50th Asilomar Conference on Signals, Systems and Computers, Nov. 2016.

Entity Resolution Acceleration using Micron’s Automata Processor
C. Bo, K. Wang, J. Fox, and K. Skadron. Proceedings of the 2016 IEEE International Conference on Big Data (BigData), Dec. 2016.

Hierarchical Pattern Mining with the Micron Automata Processor
K. Wang, E. Sadredini, and K. Skadron. International Journal of Parallel Programming (IJPP), Jan. 2017.

Fast Searching for Potential gRNA Off-Target Sites for CRISPR/Cas9 using Automata Processing
C. Bo, E. Sadredini, and K. Skadron. SRC TechCon, Austin, TX, 2016 (TECHCON2017)

REAPR: Reconfigurable Engine for Automata Processing
T. Xie, V. Dang, J. Wadden, K. Skadron, and M. Stan. 27th International Conference on Field Programmable Logic and Applications (FPL 2017)

CAP White Papers

Our group has demonstrated tremendous application potential using Micron’s Automata Processor. Below are some example application areas that may be of interest to industry partners and government sponsors. In addition to leading expertise on (and to date, exclusive access to) AP technology, our team also has extensive experience and expertise with hardware acceleration in general.

If you are a company or research lab, and are interested in exploring how the AP and other hardware acceleration technologies can be applied to meet your needs, please contact us and we will respond shortly; and if appropriate, we will be more than happy to develop a white paper to address your needs.

Cybersecurity

The AP’s massively parallel operation allows it to quickly check for prescribed patterns and their variations. This capability enables the AP to be uniquely suited for cybersecurity applications such as packet inspection and attribution. We believe there is a wide range of applications for AP technology in industry and national defense.

Data Reduction

The advent of Big Data bring unprecedented opportunities but also significant analytics challenges. The AP’s ability to quickly implement association rule mining (ARM) algorithms such as frequent itemset, sequential pattern mining, and frequent subtree mining can quickly identify relations and patterns in massive datasets. We also believe tremendously valuable insight can also be gained from open internet sources such as social media platforms. However, the volume, variety, velocity, and veracity challenges of internet open source data is a formidable challenge. The AP’s ability to speedup implementation of entity resolution (ER) can be leveraged to perform attribution on internet open source data. ARM and ER are a few examples of how we think the AP can be effectively applied for data reduction.

Approximate string matching/ Bioinformatics

Aligning DNA reads to a reference genome is a common and time consuming process. We have demonstrated significant speedups implementing DNA alignment on the AP. Furthermore, the AP’s NFA flexibility allows it to be very effective at tolerating variations (gaps, mutation, and insertions) in candidate patterns. This is capability is analogous to approximate string matching. That is, the AP is able to effectively match string patterns with varied edit distance. We envision many relevant research and industry applications based on this powerful capability.

The History Of AP

1943

Warren McCulloch & Walter Pitts: Finite automata

Lettvin_Pitts

1956

Stephen Kleene: Regular expression & finite automata

Screen Shot 2016-03-21 at 12.07.58 PM

2013

Micron introduction of AP technology

ap_chip-069f99515456616465beea50beb63bcdfc806abf88e8a9f5c564ee0ae84d317b

 

2013

UVA established the Center for Automata Processing

contact

2016

AP hardware available through the Center for Automata Processing

20160126-01-0003-00

Academic Membership Application

 

Your Name (required)

Your Email (must be a business/organization email)

Your Phone Number

Your Full Address

Your Question(s) And/Or Interested Membership Level

CLOSE
Machine Learning Application: Tree Kernels

 

There are many real world applications such as XML data, parse trees in natural language processing, and protein sequences in bioinformatics that can be represented by tree structures. The conventional methods used for tree structured data classification are based on dot products on the feature vectors; this can be very expensive since those vectors can be extremely large.

Tree Kernel methods have proved to be a state of the art technique for many real world problems and they are able to process tree-based information without using an explicit representation of inputs. The main bottleneck of the current solutions of the tree kernels is the processing time and because the tree structure is complex, the timing complexity is the limiting factor for the tree kernel methods. In this project, we are going to propose a novel automata solution for convolution-based tree kernels on the AP. Our method can be applied to the applications that can be represented by the ordered and unordered labelled trees such as sentiment analysis in natural language processing.

By Elaheh Sadredini

CLOSE
Performance Evaluation of Regular Expression Engines Across Different Computer Architectures

 

This project focuses on regular expression matching which is playing an important role in a variety of applications, like genome sequence analysis, data mining, network inspection, etc. Different kinds of architectures such as CPU, XeonPhi, GPU, FPGA can perform regular expression matching. However, it is difficult on Von-Neumann architectures since it requires high irregular parallelism, high memory bandwidth as well as low latency.

Micron’s Automata Processor (AP) is designed for this kind of problem, using DRAM as a highly parallel reconfigurable fabric to implement NFAs. In this work we investigate for a fair comparison of best effort regular expression processing engines across all these aforementioned architectures which involves analyzing their performances with different types of regular expressions and exploring the design spaces of each of these architectures.

Our preliminary results indicate that CPU, XeonPhi and GPU are most likely bottlenecked by memory latency for rule lookup and AP and FPGA outperform other architectures due to their high capacity, their massively parallel execution and their capabilities of processing new input symbol every clock cycle. Furthermore, unlike FPGA, AP’s throughput is immune to complexity of NFA topologies and rulesets (i.e. large number of transitions, active states).

In the future work, we continue to explore the performance evaluation on more dimensions: “complexity” of regular expressions, the number of regular expressions, and multiple packets (streams) processing capability. We also extend the work to other benchmark suites that are not natural fits for regular expression, such as association rule mining, Markov chains, String kernel etc.

By Tommy Tracy

CLOSE
Entity Resolution Acceleration Using AP

Entity Resolution (ER), the process of finding identical entities across different databases, is critical to many information integration applications. As sizes of databases explode in the big-data era, it becomes computationally expensive to recognize identical entities for all records with variations allowed across multiple databases. Profiling results show that approximate matching is the primary bottleneck.

Micron’s Automata Processor (AP), an efficient and scalable semiconductor architecture for parallel automata processing, provides a new opportunity for hardware acceleration for ER. We propose an AP-accelerated ER solution, which accelerates the performance bottleneck of fuzzy matching for similar but potentially inexactly-matched names, and use a real-world application to illustrate its effectiveness. Results show promising speedups for matching one record, with better accuracy over the existing CPU method.

By Dang, Vinh Quang

CLOSE
Sequence alignment in Bioinformatics using Micron’s Automata processor:

Sequence alignment refers to arranging sequences of DNA, RNA, or protein against reference sequences to identify regions of similarity in Bioinformatics. The major challenge is that the reads do not always perfectly match with references, and approximate matching is needed. The process is computationally expensive to compare large number of different reads against long references when fuzziness is allowed.

Micron’s Automata Processor (AP) is an efficient and scalable semiconductor architecture for parallel automata processing.  The AP is based on an adaption of memory array architecture, exploiting the inherent bit-parallelism of traditional SDRAM. This new in-memory processing hardware architecture provides a new opportunity for sequence alignment. We use the new hardware to accelerate DNA alignment and compare with other famous sequence alignment tools (Bowtie2, Bowtie and PatMaN).

Results show at least $10$x speedup is achieved and more than 10000x speedup could be achieved when more variations are needed.

By Chunkun Bo

CLOSE