Search

Nanopore Sensitivity/Specificity details

All supplementary data except table S3A and S3B

Purpose:Pediatric high-grade glioma (pHGG) diagnosis portends poor prognosis and therapeutic monitoring remains difficult. Tumors release cell-free tumor DNA (cf-tDNA) into cerebrospinal fluid (CSF), allowing for potential detection of tumor-associated mutations by CSF sampling. We hypothesized that direct, electronic analysis of cf-tDNA with a handheld platform (Oxford Nanopore MinION) could quantify patient-specific CSF cf-tDNA variant allele fraction (VAF) with improved speed and limit of detection compared with established methods.Experimental Design:We performed ultra-short fragment (100–200 bp) PCR amplification of cf-tDNA for clinically actionable alterations in CSF and tumor samples from patients with pHGG (n = 12) alongside nontumor CSF (n = 6). PCR products underwent rapid amplicon-based sequencing by Oxford Nanopore Technology (Nanopore) with quantification of VAF. Additional comparison to next-generation sequencing (NGS) and droplet digital PCR (ddPCR) was performed.Results:Nanopore demonstrated 85% sensitivity and 100% specificity in CSF samples (n = 127 replicates) with 0.1 femtomole DNA limit of detection and 12-hour results, all of which compared favorably with NGS. Multiplexed analysis provided concurrent analysis of H3.3A (H3F3A) and H3C2 (HIST1H3B) mutations in a nonbiopsied patient and results were confirmed by ddPCR. Serial CSF cf-tDNA sequencing by Nanopore demonstrated correlation of radiological response on a clinical trial, with one patient showing dramatic multi-gene molecular response that predicted long-term clinical response.Conclusions:Nanopore sequencing of ultra-short pHGG CSF cf-tDNA fragments is feasible, efficient, and sensitive with low-input samples thus overcoming many of the barriers restricting wider use of CSF cf-tDNA diagnosis and monitoring in this patient population.

ReadUntil enables Oxford Nanopore Technology’s (ONT) sequencers to selectively sequence reads of target species in real-time. This enables efficient microbial enrichment for applications such as microbial abundance estimation and is particularly beneficial for metagenomic samples with a very high fraction of non-target reads (>99% can be human reads). However, read-until requires a fast and accurate software filter that analyzes a short prefix of a read and determines if it belongs to a microbe of interest (target) or not. The baseline Read Until pipeline uses a deep neural network-based basecaller called Guppy and is slow and inaccurate for this task (∼60% of bases sequenced are unclassified).We present RawMap, an efficient CPU-only microbial species-agnostic Read Until classifier for filtering non-target human reads in the squiggle space. RawMap uses a Support Vector Machine (SVM), which is trained to distinguish human from microbe using non-linear and non-stationary characteristics of ONT’s squiggle output (continuous electrical signals). Compared to the baseline Read Until pipeline, RawMap is a 1327X faster classifier and significantly improves the sequencing time and cost, and compute time savings. We show that RawMap augmented pipelines reduce sequencing time and cost by ∼24% and computing cost by ∼22%. Additionally, since RawMap is agnostic to microbial species, it can also classify microbial species it is not trained on.We also discuss how RawMap may be used as an alternative to the RT-PCR test for viral load quantification of SARS-CoV-2.Availability and implementationSoftware is released with MIT License and available on GitHub:https://github.com/harisankarsadasivan/RawMap

Purpose: Pediatric high-grade glioma (pHGG) diagnosis portends poor prognosis and therapeutic monitoring remains difficult. Tumors release cell-free tumor DNA (cf-tDNA) into cerebrospinal fluid (CSF), allowing for potential detection of tumor-associated mutations by CSF sampling. We hypothesized that direct, electronic analysis of cf-tDNA with a handheld platform (Oxford Nanopore MinION) could quantify patient-specific CSF cf-tDNA variant allele fraction (VAF) with improved speed and limit of detection compared with established methods. Experimental Design: We performed ultra-short fragment (100–200 bp) PCR amplification of cf-tDNA for clinically actionable alterations in CSF and tumor samples from patients with pHGG (n = 12) alongside nontumor CSF (n = 6). PCR products underwent rapid amplicon-based sequencing by Oxford Nanopore Technology (Nanopore) with quantification of VAF. Additional comparison to next-generation sequencing (NGS) and droplet digital PCR (ddPCR) was performed. Results: Nanopore demonstrated 85% sensitivity and 100% specificity in CSF samples (n = 127 replicates) with 0.1 femtomole DNA limit of detection and 12-hour results, all of which compared favorably with NGS. Multiplexed analysis provided concurrent analysis of H3.3A (H3F3A) and H3C2 (HIST1H3B) mutations in a nonbiopsied patient and results were confirmed by ddPCR. Serial CSF cf-tDNA sequencing by Nanopore demonstrated correlation of radiological response on a clinical trial, with one patient showing dramatic multi-gene molecular response that predicted long-term clinical response. Conclusions: Nanopore sequencing of ultra-short pHGG CSF cf-tDNA fragments is feasible, efficient, and sensitive with low-input samples thus overcoming many of the barriers restricting wider use of CSF cf-tDNA diagnosis and monitoring in this patient population.

Background Diffuse Midline Glioma (DMG) with the H3K27M mutation is a lethal childhood brain cancer, with patients rarely surviving 2 years from diagnosis. Methods We conducted a multi-site Phase 1 trial of the imipridone ONC201 for children with H3K27M-mutant glioma (NCT03416530). Patients enrolled on Arm D of the trial (n = 24) underwent serial lumbar puncture for cell-free tumor DNA (cf-tDNA) analysis and patients on all arms at the University of Michigan underwent serial plasma collection. We performed digital droplet polymerase chain reaction (ddPCR) analysis of cf-tDNA samples and compared variant allele fraction (VAF) to radiographic change (maximal 2D tumor area on MRI). Results Change in H3.3K27M VAF over time (“VAF delta”) correlated with prolonged PFS in both CSF and plasma samples. Nonrecurrent patients that had a decrease in CSF VAF displayed a longer progression free survival (P = .0042). Decrease in plasma VAF displayed a similar trend (P = .085). VAF “spikes” (increase of at least 25%) preceded tumor progression in 8/16 cases (50%) in plasma and 5/11 cases (45.4%) in CSF. In individual cases, early reduction in H3K27M VAF predicted long-term clinical response (>1 year) to ONC201, and did not increase in cases of later-defined pseudo-progression. Conclusion Our work demonstrates the feasibility and potential utility of serial cf-tDNA in both plasma and CSF of DMG patients to supplement radiographic monitoring. Patterns of change in H3K27M VAF over time demonstrate clinical utility in terms of predicting progression and sustained response and possible differentiation of pseudo-progression and pseudo-response.

The MinION is a recent-to-market handheld nanopore sequencer. It can be used to determine the whole genome of a target virus in a biological sample. Its Read Until feature allows us to skip sequencing a majority of non-target reads (DNA/RNA fragments), which constitutes more than 99% of all reads in a typical sample. However, it does not have any on-board computing, which significantly limits its portability. We analyze the performance of a Read Until metagenomic pipeline for detecting target viruses and identifying strain-specific mutations. We find new sources of performance bottlenecks (basecaller in classification of a read) that are not addressed by past genomics accelerators. We present SquiggleFilter, a novel hardware accelerated dynamic time warping (DTW) based filter that directly analyzes MinION's raw squiggles and filters everything except target viral reads, thereby avoiding the expensive basecalling step. We show that our 14.3W 13.25mm2 accelerator has 274X greater throughput and 3481X lower latency than existing GPU-based solutions while consuming half the power, enabling Read Until for the next generation of nanopore sequencers., Comment: https://micro2021ae.hotcrp.com/paper/12?cap=012aOJj-0U08_9o

Molecular markers are essential for cancer diagnosis, clinical trial enrollment, and some surgical decision making, motivating ultra-rapid, intraoperative variant detection. Sequencing-based detection is considered the gold standard approach, but typically takes hours to perform due to time-consuming DNA extraction, targeted amplification, and library preparation times. In this work, we present a proof-of-principle approach for sub-1 hour targeted variant detection using real-time DNA sequencers. By modifying existing protocols, optimizing for diagnostic time-to-result, we demonstrate confirmation of a hot-spot mutation from tumor tissue in ~52 minutes. To further reduce time, we explore rapid, targeted Loop-mediated Isothermal Amplification (LAMP) and design a bioinformatics tool—LAMPrey—to process sequenced LAMP product. LAMPrey’s concatemer aware alignment algorithm is designed to maximize recovery of diagnostically relevant information leading to a more rapid detection versus standard read alignment approaches. Using LAMPrey, we demonstrate confirmation of a hot-spot mutation (250x support) from tumor tissue in less than 30 minutes.

Read alignment is a time-consuming step in genome sequencing analysis. The most widely used software for read alignment, BWA-MEM, and the recently published faster version BWA-MEM2 are based on the seed-and-extend paradigm for read alignment. The seeding step of read alignment is a major bottleneck contributing ~40% to the overall execution time of BWA-MEM2 when aligning whole human genome reads from the Platinum Genomes dataset. This is because both BWA-MEM and BWA-MEM2 use a compressed index structure called the FMD-Index, which results in high bandwidth requirements, primarily due to its character-by-character processing of reads. For instance, to seed each read (101 DNA base-pairs stored in 37.8 bytes), the FMD-Index solution in BWA-MEM2 requires ~68.5 KB of index data. We propose a novel indexing data structure named Enumerated Radix Tree (ERT) and design a custom seeding accelerator based on it. ERT improves bandwidth efficiency of BWA-MEM2 by 4.5X while guaranteeing 100% identical output to the original software, and still fitting in 64 GB DRAM. Overall, the proposed seeding accelerator implemented on AWS F1 FPGA (f1.4xlarge) improves seeding throughput of BWA-MEM2 by 3.3X. When combined with seed-extension accelerators, we observe a 2.1X improvement in overall read alignment throughput over BWA-MEM2. The software implementation of ERT is integrated into BWA-MEM2 (ert branch: https://github.com/bwa-mem2/bwa-mem2/tree/ert) and is open sourced for the benefit of the research community.

We present a general automata processing framework on FPGAs, which generates an RTL kernel for automata processing together with an AXI and PCIe based I/O circuitry. We implement the framework on both local nodes and cloud platforms (Amazon AWS and Nimbix) with novel features. A full performance comparison of the proposed framework is conducted against state-of-the-art automata processing engines on CPUs, GPUs, and Micron’s Automata Processor using the ANMLZoo benchmark suite and some real-world datasets. Results show that FPGAs enable extremely high-throughput automata processing compared to von Neumann architectures. We also collect the resource utilization and power consumption on the two cloud platforms, and find that the I/O circuitry consumes most of the hardware resources and power. Furthermore, we propose a fast, symbol-only reconfiguration mechanism based on the framework for large pattern sets that cannot fit on a single device and need to be partitioned. The proposed method supports multiple passes of the input stream and reduces the re-compilation cost from hours to seconds.

As the hardware found within data centers becomes more heterogeneous, it is important to allow for efficient execution of algorithms across architectures. We present RAPID, a high-level programming language and combined imperative and declarative model for functionally- and performance-portable execution of sequential pattern-matching applications across CPUs, GPUs, Field-Programmable Gate Arrays (FPGAs), and Micron’s D480 AP. RAPID is clear, maintainable, concise, and efficient both at compile and run time. Language features, such as code abstraction and parallel control structures, map well to pattern-matching problems, providing clarity and maintainability. For generation of efficient runtime code, we present algorithms to convert RAPID programs into finite automata. Our empirical evaluation of applications in the ANMLZoo benchmark suite demonstrates that the automata processing paradigm provides an abstraction that is portable across architectures. We evaluate RAPID programs against custom, baseline implementations previously demonstrated to be significantly accelerated. We also find that RAPID programs are much shorter in length, are expressible at a higher level of abstraction than their handcrafted counterparts, and yield generated code that is often more compact.

Molecular markers are becoming increasingly important for cancer diagnosis, proper clinical trial enrollment, and even surgical decision making, motivating ultra-rapid, intraoperative variant detection. Sequencing-based detection is considered the gold standard approach, but typically takes hours to perform. In this work, we present Threshold Sequencing, a methodology for designing protocols for targeted variant detection on real-time sequencers with a minimal time to result. Threshold Sequencing analytically identifies a time-optimal threshold to stop target amplification and begin sequencing. To further reduce diagnostic time, we explore targeted Loop-mediated Isothermal Amplification (LAMP) and design a LAMP-specific bioinformatics tool—LAMPrey—to process sequenced LAMP product. LAMPrey’s concatemer aware alignment algorithm is designed to maximize recovery of diagnostically relevant information leading to a more rapid detection versus standard read alignment approaches. Coupled with time-optimized DNA extraction and library preparation, we demonstrate confirmation of a hot-spot mutation (250x support) from tumor tissue in less than 30 minutes.

Diffuse midline glioma (DMG) with H3K27M mutation is a lethal childhood brain cancer, with limited means of monitoring beyond serial MRI scans. We conducted a multi-site Phase 1 trial of the imipridone ONC201 for children with H3K27M-mutant glioma (NCT03416530). Patients on Arm D of the trial (n=24) underwent serial lumbar puncture (baseline, 2 and 6-months) for cell-free tumor DNA (cf-tDNA) analysis at time of MRI. Additionally, patients on all arms of the trial at the University of Michigan underwent serial plasma collection. We collected a total of 96 plasma-samples and 53 CSF-samples from 29 patients. We performed ddPCR analysis of cf-tDNA samples and compared variant allele fraction (VAF) to radiographic change (maximal tumor area on MRI). For our H3F3A-mutated (K27M) patients, cf-tDNA was positive in 53/62 plasma samples (sensitivity 85.4%) and 28/29 CSF samples (sensitivity 96.5%) and overall specificity of 100%. There was no direct correlation between percent-change in tumor-area and plasma (p=0.47) or CSF VAF (p=0.89), implying that VAF provided information supplemental to radiographic assessments. “Spikes” in plasma cf-tDNA VAF (increase of ≥25%) co-occurred with progression in 2/9 (22%) cases and preceded progression in 5/9 cases (55%) by an average of 1.22 months. In CSF, spikes preceded progression in 4/6 cases (66%) by an average of 1.8 months. Two patients had increases in tumor-area with no increase in plasma VAF; both were later confirmed as pseudo-progressors, suggesting additional potential utility of cf-tDNA VAF monitoring. A 14yo male with spinal cord glioma received concurrent bevacizumab with ONC201, which resulted in a decrease in tumor area but continued increase in plasma VAF, predicting radiologic progression at the next time. In summary, we present data which suggests monitoring serial CSF/plasma H3K27M tDNA is a promising clinical tool. Changes in cf-tDNAVAF over time appear to correlate with response, predict progression, and differentiate pseudo-progression.

Oxford Nanopore sequencers provide results in real time as DNA passes through a nanopore and can eject a molecule after it has been partly sequenced. However, the computational challenge of deciding whether to keep or reject a molecule in real time has limited the application of this capability. We present SquiggleNet, the first deep learning model that can classify nanopore reads directly from their electrical signals. SquiggleNet operates faster than the DNA passes through the pore, allowing real-time classification and read ejection. When given the amount of sequencing data generated in one second, the classifier achieves significantly higher accuracy than base calling followed by sequence alignment. Our approach is also faster and requires an order of magnitude less memory than approaches based on alignment. SquiggleNet distinguished human from bacterial DNA with over 90% accuracy, generalized to unseen species, identified bacterial species in a human respiratory meta genome sample, and accurately classified sequences containing human long interspersed repeat elements.

Diffuse midline glioma (DMG) with the H3K27M mutation is a lethal childhood brain cancer, with patients rarely surviving 2 years from diagnosis. We conducted a multi-site Phase 1 trial of the imipridone ONC201 for children with H3K27M-mutant glioma ({"type":"clinical-trial","attrs":{"text":"NCT03416530","term_id":"NCT03416530"}}NCT03416530). Patients enrolled on Arm D of the trial (n=24) underwent serial lumbar puncture (baseline, 2, 6 months) for cell-free tumor DNA (cf-tDNA) analysis at time of MRI. Additionally, patients on all arms of the trial at the University of Michigan underwent serial plasma collection. CSF collection was feasible in this cohort, with no procedural complications. We collected 96 plasma samples and 53 CSF samples from 29 patients, including those with H3F3A (H3.3) (n=13), HIST13HB (H3.1) (n= 4), and unknown H3 status/not biopsied (n=12) [range of 0–8 CSF samples and 0–10 plasma samples]. We performed digital droplet polymerase chain reaction (ddPCR) analysis and/or amplicon-based electronic sequencing (Oxford Nanopore) of cf-tDNA samples and compared variant allele fraction (VAF) to radiographic change (maximal 2D tumor area on MRI). Preliminary analysis of samples demonstrates a correlation between changes in tumor size and H3K27M cf-tDNA VAF, when removing samples with concurrent bevacizumab. In multiple cases, early reduction in CSF cf-tDNA predicts long-term clinical response (>1 year) to ONC201, and does not increase in cases of later-defined pseudo-progression (radiation necrosis). For example, a now 9-year old patient with thalamic H3K27M-mutant DMG underwent treatment with ONC201 after initial radiation and developed increase in tumor size at 4 months post-radiation (124% baseline) of unclear etiology at the time. Meanwhile, her ddPCR declined from baseline 6.76% VAF to

MotivationRead alignment is a time-consuming step in genome sequence analysis. In the read alignment software BWA-MEM and the recently published faster version BWA-MEM2, the seeding step is a major bottleneck, for instance, contributing 38% to the overall execution time in BWA-MEM2 when aligning single-end whole human genome reads from the Platinum Genomes dataset. This is because both BWA-MEM and BWA-MEM2 use a compressed index structure called the FMD-Index, which results in high memory bandwidth requirements for seeding, primarily due to its character-by-character processing of reads.ResultsWe propose a memory bandwidth-aware data structure for maximal-exact-match seeding called Enumerated Radix Tree (ERT). ERT trades off memory capacity to improve seeding performance (∼60 GB index for human genome). Together with optimizations to the seeding algorithm and mate-rescue step, ERT when integrated into BWA-MEM2 speeds up overall read alignment by 1.28× and provides up to 2.1× higher seeding performance while guaranteeing identical output to the original software. Furthermore, we prototype an FPGA implementation of ERT on Amazon EC2 F1 cloud and observe 1.6× higher seeding throughput over a 48-thread optimized CPU-ERT implementation.Availability and implementationhttps://github.com/arun-sub/bwa-mem2Contactarunsub@umich.edu, reetudas@umich.edu

We present MNCaRT, a comprehensive software ecosystem for the study and use of automata processing across hardware platforms. Tool support includes manipulation of automata, execution of complex machines, high-speed processing of NFAs and DFAs, and compilation of regular expressions. We provide engines to execute automata on CPUs (with VASim and Intel Hyperscan), GPUs (with custom DFA and NFA engines), and FPGAs (with an HDL translator). We also introduce MNRL, an open-source, general-purpose and extensible state machine representation language developed to support MNCaRT. The representation is flexible enough to support traditional finite automata (NFAs, DFAs) while also supporting more complex machines, such as those which propagate multi-bit signals between processing elements. We hope that our ecosystem and representation language stimulates new efforts to develop efficient and specialized automata processing applications.

BACKGROUND For pediatric high-grade glioma (pHGG), non-invasive methods for diagnosis and surveillance are needed. Tumors release DNA (tDNA) into cerebrospinal fluid (CSF), allowing for detection of tumor-associated mutations by CSF sampling. We hypothesized that direct, electronic analysis of tDNA with a novel, hand-held platform (Oxford Nanopore MinION) could quantify patient-specific CSF tDNA variant allele fraction (VAF) with improved speed and limit of detection compared to established methods. METHODS We integrated required multi-timepoint (0, 2, and 6 months) correlate lumbar punctures (LP) in two ongoing pHGG clinical trials. Using Nanopore technology, we performed amplicon-based PCR on CSF tDNA for recurrent mutations from patient samples (n=19) and normal controls. VAF were determined via MinKNOW, Guppy, MiniMap2, and Integrated Genome Browser. RESULTS Nanopore CSF tDNA demonstrated improved sensitivity (91%) when compare to NGS sequencing (50%). Nanopore analysis of serially diluted CSF sample demonstrated significantly lower limit of detection (attomolar) than typical NGS sample requirement (nanomolar). H3K27M mutation was reliably detected with 1,000x depth sequencing, which was achieved in less than 15 minutes of sequencing after amplification. Multiplexed Nanopore analysis of H3F3A and HIST1H3B was employed when H3 status was unknown. Serial CSF tDNA analysis confirmed multi-gene (H3F3A K27M, PIK3CA, and TP53) molecular remission in a 17-year-old with thalamic diffuse midline glioma that correlated with sustained clinical response to ONC201 (14 months and ongoing). CONCLUSIONS Use of a hand-held, electronic DNA analysis platform allows quantification of multi-gene molecular response with improved speed and limit of detection in the CSF of children with high-grade glioma.

Automata Processing is an important kernel for many application domains, and is challenging to accelerate using general purpose, von Neumann computers. New research into accelerators for automata processing motivated the creation of ANMLZoo, a standardized automata benchmark suite that reflects the many modern use-cases for automata processing. While researchers have adopted ANMLZoo as the de-facto benchmark suite to measure improvements in automata processing, certain drawbacks have emerged after years of use. In this work, we first examine opportunities for improvement over ANMLZoo’s benchmarking methodology. We then propose a new benchmarking methodology that aims to generate benchmarks better suited for modern automata processing research.We then present AutomataZoo, a new automata processing benchmark suite that uses our new benchmarking methodology. AutomataZoo is composed of 24 automata processing benchmarks from well-known domains, as well as from newly published and novel use-cases for automata processing. AutomataZoo benchmarks use open-source tools to generate full automata applications and provide standard, large input stimuli. Where arbitrary choice is involved, we design multiple benchmarks that vary important design parameters in order to help architects evaluate application-level trade-offs affecting performance/power and/or chip capacity. This paper shows the advantages of these new properties by performing previously difficult-to-perform experiments and comparisons.

Automata processing has seen a resurgence in importance due to its usefulness for pattern matching and pattern mining of "big data." While large-scale automata processing is known to bottleneck von Neumann processors due to unpredictable memory accesses, spatial architectures excel at automata processing. Spatial architectures can implement automata graphs by wiring together automata states in reconfigurable arrays, allowing parallel automata state computation, and point-to-point state transitions on-chip. However, spatial automata processing architectures can suffer from output constraints (up to 255x in commercial systems!) due to the physical placement of states, output processing architecture design, I/O resources, and the massively parallel nature of the architecture. To understand this bottleneck, we conduct the first known characterization of output requirements of a realistic set of automata processing benchmarks. We find that most benchmarks report fairly frequently, but that few states report at any one time. This observation motivates new output compression schemes and reporting architectures. We evaluate the benefit of one purely software automata transformation and show that output reporting costs can be greatly reduced (improving performance by up to 40% without hardware modification. We then explore bottlenecks in the reporting architecture of a commercial spatial automata processor and propose a new architecture that improves performance by up to 5.1x.

While the popularity of using graphics processing units (GPUs) as massively parallel co-processors has increased dramatically over the last 10 years, improvements in GPU reliability have lagged behind adoption. GPUs are first and foremost gaming products, and therefore usually do not demand high reliability. However, GPUs are now being used to accelerate applications in medical imaging, nuclear science, materials science, social science, finance, and more that all require extremely high reliability. GPUs have even made their way into high-node-count data centers and many of the fastest supercomputers in the world, exacerbating system failure rates. Thus GPU reliability in these high-node-count environments has become an urgent, first-class design constraint. This chapter surveys the state-of-the-art research in GPU reliability in the context of the large, existing body of research on CPU reliability techniques.

Reliability for general purpose processing on the GPU (GPGPU) is becoming a weak link in the construction of reliable supercomputer systems. Because hardware protection is expensive to develop, requires dedicated on-chip resources, and is not portable across different architectures, the efficiency of software solutions such as redundant multithreading (RMT) must be explored. This paper presents a real-world design and evaluation of automatic software RMT on GPU hardware. We first describe a compiler pass that automatically converts GPGPU kernels into redundantly threaded versions. We then perform detailed power and performance evaluations of three RMT algorithms, each of which provides fault coverage to a set of structures in the GPU. Using real hardware, we show that compilermanaged software RMT has highly variable costs. We further analyze the individual costs of redundant work scheduling, redundant computation, and inter-thread communication, showing that no single component in general is responsible for high overheads across all applications; instead, certain workload properties tend to cause RMT to perform well or poorly. Finally, we demonstrate the benefit of architectural support for RMT with a specific example of fast, register-level thread communication

Micron's new Automata Processor (AP) architecture exploits the very high and natural level of parallelism found in DRAM technologies to achieve native-hardware implementation of non-deterministic finite automata (NFAs). The use of DRAM technology to implement the NFA states provides high capacity and therefore provide extraordinary parallelism for pattern recognition. In this paper, we give an overview of AP's architecture, programming and applications.

Micron's Automata Processor (AP) efficiently emulates non-deterministic finite automata and has been shown to provide large speedups over traditional von Neumann execution for massively parallel, rule-based, data-mining and pattern matching applications. We demonstrate the AP's ability to generate high-quality and energy efficient pseudo-random behavior for use in pseudo-random number generation or in chip simulation. By recognizing that transition rules become probabilistic when input characters are randomized, the AP is also capable of simulating Markov chains. Combining hundreds of parallel Markov chains creates high-quality, high-throughput pseudo-random number sequences with greater power efficiency than state-of-the-art CPU and GPU algorithms. This indicates that the AP could potentially accelerate other Markov Chain-based applications such as agent-based simulation. We explore how to achieve throughputs upwards of 40GB/s per AP chip, with power efficiency 6.8x greater than state-of-the-art pseudo-random number generation on GPUs.

High-performance automata-processing engines are traditionally evaluated using a limited set of regular expressionrulesets. While regular expression rulesets are valid real-world examples of use cases for automata processing, they represent a small proportion of all use cases for automata-based computing. With the recent availability of architectures and software frameworks for automata processing, many new applications have been found to benefit from automata processing. These show a wide variety of characteristics that differ from prior, popular regular-expression benchmarks, and these should be considered when designing new systems for automata processing. This paper presents ANMLZoo, a benchmark repository for automata-based applications as well as automata engines for both von-Neumann and reconfigurable dataflow architectures. To demonstrate the usefulness of ANMLZoo, we first characterize diversity in the benchmark suite. We then present insights from five experiments showing how ANMLZoo can be used to expose bottlenecks in both automata-processing software engines and hardware architectures.

Brill tagging is a classic rule-based algorithm for part-of-speech (POS) tagging that assigns tags, such as nouns, verbs, adjectives, etc., to input tokens. Due to the the intense memory requirements of rule matching, CPU implementations of the Brill tagging algorithm have been found to be slow. We show that Micron's Automata Processor (AP) — a new computing architecture that can perform massively parallel pattern matching — can greatly accelerate the second stage of Brill tagging via rule template matching. The 218 contextual rules are first converted into regular expressions (regex). Regex is used widely in natural language processing (NLP) tasks, thus, this case study involving Brill Tagging also shows how the AP might accelerate other applications that are able to be framed as regexes. We compare single-threaded, and multithreaded versions of Regex matching on an Intel i7 CPU, an Intel XeonPhi co-processor, and the AP. The results show a 63.90X speed-up using the AP as a regex accelerator over the fastest multi-threaded CPU version. We also investigate how performance of regex matching on both CPU architectures varies depending on the complexity of the regex. Taken together, these results demonstrate the potential for significant performance improvements by using accelerators for various NLP computational tasks, particularly those that involve rule-based or pattern-matching approaches.

We present a novel, compliant mechanism that provides the capability to navigate extremely confined spaces for the purpose of infrastructure inspection. Extremely confined spaces are commonly encountered during infrastructure inspection. Examples of such spaces can include pipes, conduits, and ventilation ducts. Often these infrastructure features go uninspected simply because there is no viable way to access their interior. In addition, it is not uncommon for extremely confined spaces to possess a maze-like architecture that must be selectively navigated in order to properly perform an inspection. Efforts by the imaging sensor community have resulted in the development of imaging sensors on the millimeter length scale. Due to their compact size, they are able to inspect many extremely confined spaces of interest, however, the means to deliver these sensors to the proper location to obtain the desired images are lacking. To address this problem, we draw inspiration from the field of endoscopic surgery. Specifically we consider the work that has already been done to create long flexible needles that are capable of being steered through the human body. These devices are typically referred to as 'steerable needles.' Steerable needle technology is not directly applicable to the problem of navigating maze-like arrangements of extremely confined spaces, but it does provide guidance on how this problem should be approached. Specifically, the super-elastic nitinol tubing material that allows steerable needles to operate is also appropriate for the problem of navigating maze-like arrangements of extremely confined spaces. Furthermore, the portion of the mechanism that enters the extremely confined space is completely mechanical in nature. The mechanical nature of the device is an advantage when the extremely confined space features environmental hazards such as radiation that could degrade an electromechanically operated mechanism. Here, we present a compliant mechanism developed to navigate maze-like arrangements of extremely confined spaces. The mechanism is shown to be able to selectively navigate past three 90° bends. The ability to selectively navigate extremely confined spaces opens up new possibilities to use emerging miniature imaging technology for infrastructure inspection.

We present a novel, compliant mechanism that provides the capability to navigate extremely confined spaces for the purpose of infrastructure inspection. Extremely confined spaces are commonly encountered during infrastructure inspection. These spaces can include pipes and ventilation ducts. Often these infrastructure features go uninspected simply because there is no viable way to access their interior. In addition, it is not uncommon for extremely confined spaces to be laid-out in a maze-like fashion that must be selectively navigated in order to execute an inspection. In this work this problem is addressed by taking inspiration from the field of steerable needles. Steerable needles are typically made from super-elastic nitinol. This material has the property that it can experience high strain without yielding. This property makes superelastic nitnol an attractive material for navigating a tube through a maze-like arrangement of extremely confined spaces