CAP Research

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.” – Jack Wadden, Graduate Research Assistant

CAP Research Tools

Grapefruit – An FPGA implementation for accelerating automata processing.

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

VASIM - An Automata Simulator for the CPU.

ANMLZoo - Automata Benchmarks.

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

Sunder: Enabling Low-Overhead and Scalable Near Data Pattern Matching Acceleration - E. Sadredini, R. Rahimi, M. Imani, and K. Skadron. In Proceedings of the IEEE/ACM International Symposium on Microarchitecture (MICRO), Oct. 2021, to appear.

Runtime Verification on FPGAs with LTLf Specifications - T. Tracy II, L. Tabajara, M. Vardi, and K. Skadron. In Proceedings of the Formal Methods in Computer-Aided Design (FMCAD), Sept. 2020.

Grapefruit: An Open-Source, Full-Stack, and Customizable Automata Processing on FPGAs - R. Rahimi, E. Sadredini, M. Stan, and K. Skadron. The 28th IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2020.

FlexAmata: A Universal and Efficient Adaption of Applications to Spatial Automata Processing Accelerators - E. Sadredini, R. Rahimi, M. Lenjani, M. Stan, and K. Skadron. The 25th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2020.

Impala: Algorithm/Architecture Co-Design for In-Memory Multi-Stride Pattern Matching - E. Sadredini, R. Rahimi, M. Lenjani, M. Stan, and K. Skadron. The 26th IEEE International Symposium on High-Performance Computer Architecture (HPCA).

eAP: A Scalable and Efficient In-Memory Accelerator for In-Memory Processing - E. Sadredini, R. Rahimi, V. Verma, M. Stan, and K. Skadron. In Proceedings of the ACM/IEEE International Symposium on Microarchitecture (MICRO), Oct. 2019.

Automata Processing in Reconfigurable Architectures: In-the-cloud Deployment, Cross-platform Evaluation, and Fast Symbol-only Reconfiguration. C. Bo, V. Dang, T. Xie, J. Wadden, M. Stan, and K. Skadron. ACM Transactions on Reconfigurable Technology and Systems (TRETS), to appear.

Debugging Support for Pattern-Matching Languages and Accelerators- M. Casias, K. Angstadt, T. Tracy II, K. Skadron, and W. Weimer. In Proceedings of the ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Apr. 2019.

ASPEN: A Scalable In-SRAM Architecture for Pushdown Automata - K. Angstadt, A. Subramaniyan, E. Sadredini, R. Rahimi, W. Weimer, K. Skadron, and R. Das. In Proceedings of the ACM/IEEE International Symposium on Microarchitecture (MICRO), Oct. 2018.

AutomataZoo: A Modern Automata Processing Benchmark Suite - J. Wadden, T. Tracy II, E. Sadredini, L. Wu, C. Bo, J. Du,** Y. Zhou, M. Wallace,* J. Udall,* M. Stan, and K. Skadron. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC), Oct. 2018.

A Scalable Solution for Rule-Based Part-of-Speech Tagging on Novel Hardware Accelerators - E. Sadredini, D. Guo, C. Bo, R. Rahimi, K. Skadron, and H. Wang. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Applied Data Science track, full paper with poster presentation, Aug. 2018.

MNCaRT: An Open-Source, Multi-Architecture Automata-Processing Research and Execution Ecosystem - K. Angstadt, J. Wadden, V. Dang, T. Xie, D. Kramp, W. Weimer, M. Stan, and K. Skadron. IEEE Computer Architecture Letters, published online Dec. 2017, published in print 17(1):84-87, Jan.-June 2018. DOI 10.1109/LCA.2017.2780105.

Characterizing and Mitigating Output Reporting Bottlenecks in Spatial-Reconfigurable Automata Processing Architectures - J. Wadden, K. Angstadt, and K. Skadron. In Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA), Feb. 2018.

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 brought 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.