Rapid technological advancements in sequencing technologies allow producing cost effective and high volume sequencing data. Processing this data for real-time clinical diagnosis is potentially time-consuming if done on a single computing node. This work presents a complete variant calling workflow, implemented using the Message Passing Interface (MPI) to leverage the benefits of high bandwidth interconnects. This solution (GenMPI) is portable and flexible, meaning it can be deployed to any private or public cluster/cloud infrastructure. Any alignment or variant calling application can be used with minimal adaptation. To achieve high performance, compressed input data can be streamed in parallel to alignment applications while uncompressed data can use internal file seek functionality to eliminate the bottleneck of streaming input data from a single node. Alignment output can be directly stored in multiple chromosome-specific SAM files or a single SAM file. After alignment, a distributed queue using MPI RMA (Remote Memory Access) atomic operations is created for sorting, indexing, marking of duplicates (if necessary) and variant calling applications. We ensure the accuracy of variants as compared to the original single node methods. We also show that for 300x coverage data, alignment scales almost linearly up to 64 nodes (8192 CPU cores). Overall, this work outperforms existing Big Data based workflows by a factor of two and is almost 20% faster than other MPI-based implementations for alignment without any extra memory overheads. Sorting, indexing, duplicate removal and variant calling is also scalable up to 8 nodes cluster. For pair-end short-reads (Illumina) data, we integrated the BWA-MEM aligner and three variant callers (GATK HaplotypeCaller, DeepVariant and Octopus), while for long-reads data, we integrated the Minimap2 aligner and three different variant callers (DeepVariant, DeepVariant with WhatsHap for phasing (PacBio) and Clair3 (ONT)).

This paper introduces SENMap, a mapping and synthesis tool for a scalable energy efficient neuromorphic computing architecture frameworks. SENECA a flexible architectural design optimized for executing edge AI SNN/ANN inference applications efficiently. To speed up the silicon tapeout and chip design for SENECA, an accurate emulator SENSIM was designed. While SENSIM supports direct mapping of SNNs on neuromorphic architectures, as the SNN/ANN grow in size, achieving optimal mapping for objectives like energy, throughput, area, and accuracy becomes challenging. This paper introduces SENMap, flexible mapping software for efficiently mapping large SNN/ANN applications onto adaptable architectures. SENMap considers architectural, pretrained SNN/ANN realistic examples, and event rate-based parameters and is open-sourced along with SENSIM to aid flexible neuromorphic chip design before fabrication. Experimental results show SENMap enables 40 percent energy improvements for a baseline SENSIM operating on timestep asynchronous mode of operation. SENMap is designed in such a way that it facilitates mapping large spiking neural networks for future modifications as well.1

In this paper, we present SENSIM, which is an open-source simulator designed specifically for the SENECA neuromorphic processor. This simulator is unique in that it combines features from both hardware-specific and hardware-agnostic spiking neural network simulators, resulting in a hybrid event-driven and time-step-driven simulation approach. This allows for flexibility between accuracy and speed during different stages of simulation. Our work highlights the open-source SENSIM platform, which enables the mapping of large-scale SNN/DNN models to the SENECA cores, as well as the benchmarking of crucial KPIs such as power and latency estimations1.

As dedicated hardware is becoming more prevalent in accelerating complex applications, methods are needed to enable easy integration of multiple hardware components into a single accelerator system. However, this vision of composable hardware is hindered by the lack of standards for interfaces that allow such components to communicate. To address this challenge, the Tydi standard was proposed to facilitate the representation of streaming data in digital circuits, notably providing interface specifications of composite and variable-length data structures. At the same time, constructing hardware in a Scala embedded language (Chisel) provides a suitable environment for deploying Tydi-centric components due to its abstraction level and customizability. This article introduces Tydi-Chisel, a library that integrates the Tydi standard within Chisel, along with a toolchain and methodology for designing data-streaming accelerators. This toolchain reduces the effort needed to design streaming hardware accelerators by raising the abstraction level for streams and module interfaces, hereby avoiding writing boilerplate code, and allows for easy integration of accelerator components from different designers. This is demonstrated through an example project incorporating various scenarios where the interface-related declaration is reduced by 6–14 times. Tydi-Chisel project repository is available athttps://github.com/abs-tudelft/Tydi-Chisel.

This paper offers a systematic method for creating medical knowledge-grounded patient records for use in activities involving differential diagnosis. Additionally, an assessment of machine learning models that can differentiate between various conditions based on given symptoms is also provided. We use a public disease-symptom data source called SymCat in combination with Synthea to construct the patients records. In order to increase the expressive nature of the synthetic data, we use a medically-standardized symptom modeling method called NLICE to augment the synthetic data with additional contextual information for each condition. In addition, Naive Bayes and Random Forest models are evaluated and compared on the synthetic data. The paper shows how to successfully construct SymCat-based and NLICE-based datasets. We also show results for the effectiveness of using the datasets to train predictive disease models. The SymCat-based dataset is able to train a Naive Bayes and Random Forest model yielding a 58.8% and 57.1% Top-1 accuracy score, respectively. In contrast, the NLICE-based dataset improves the results, with a Top-1 accuracy of 82.0% and Top-5 accuracy values of more than 90% for both models. Our proposed data generation approach solves a major barrier to the application of artificial intelligence methods in the healthcare domain. Our novel NLICE symptom modeling approach addresses the incomplete and insufficient information problem in the current binary symptom representation approach.

Motion prediction is a key factor towards the full deployment of autonomous vehicles. It is fundamental in order to assure safety while navigating through highly interactive complex scenarios. In this work, the framework IAMP (Interaction-Aware Motion Prediction), producing multi-modal probabilistic outputs from the integration of a Dynamic Bayesian Network and Markov Chains, is extended with a learning-based approach. The integration of a machine learning model tackles the limitations of the ruled-based mechanism since it can better adapt to different driving styles and driving situations. The method here introduced generates context-dependent acceleration distributions used in a Markov-chain-based motion prediction. This hybrid approach results in better evaluation metrics when compared with the baseline in the four highly-interactive scenarios obtained from publicly available datasets.

Many researchers have proposed replacing the aggregation server in federated learning with a blockchain system to improve privacy, robustness, and scalability. In this approach, clients would upload their updated models to the blockchain ledger and use a smart contract to perform model averaging. However, the significant delay and limited computational capabilities of blockchain systems make it inefficient to support machine learning applications on the blockchain. In this article, we propose a new public blockchain architecture called DFL, which is specially optimized for distributed federated machine learning. Our architecture inherits the merits of traditional blockchain systems while achieving low latency and low resource consumption by waiving global consensus. To evaluate the performance and robustness of our architecture, we implemented a prototype and tested it on a physical four-node network, and also developed a simulator to simulate larger networks and more complex situations. Our experiments show that the DFL architecture can reach over 90% accuracy for non-I.I.D. datasets, even in the presence of model poisoning attacks, while ensuring that the blockchain part consumes less than 5% of hardware resources.

Sequence alignment forms an important backbone in many sequencing applications. A commonly used strategy for sequence alignment is an approximate string matching with a two-dimensional dynamic programming approach. Although some prior work has been conducted on GPU acceleration of a sequence alignment, we identify several shortcomings that limit exploiting the full computational capability of modern GPUs. This paper presents SALoBa, a GPU-accelerated sequence alignment library focused on seed extension. Based on the analysis of previous work with real-world sequencing data, we propose techniques to exploit the data locality and improve work-load balancing. The experimental results reveal that SALoBa significantly improves the seed extension kernel compared to state-of-the-art GPU-based methods.

Current cluster scaled genomics data processing solutions rely on big data frameworks like Apache Spark, Hadoop and HDFS for data scheduling, processing and storage. These frameworks come with additional computation and memory overheads by default. It has been observed that scaling genomics dataset processing beyond 32 nodes is not efficient on such frameworks.To overcome the inefficiencies of big data frameworks for processing genomics data on clusters, we introduce a low-overhead and highly scalable solution on a SLURM based HPC batch system. This solution uses Apache Arrow as in-memory columnar data format to store genomics data efficiently and Arrow Flight as a network protocol to move and schedule this data across the HPC nodes with low communication overhead.As a use case, we use NGS short reads DNA sequencing data for pre-processing and variant calling applications. This solution outperforms existing Apache Spark based big data solutions in term of both computation time (2x) and lower communication overhead (more than 20-60% depending on cluster size). Our solution has similar performance to MPI-based HPC solutions, with the added advantage of easy programmability and transparent big data scalability. The whole solution is Python and shell script based, which makes it flexible to update and integrate alternative variant callers. Our solution is publicly available on GitHub at https://github.com/abs-tudelft/time-to-fly-high/tree/main/genomics

MOTIVATION: Agent-based modeling is an indispensable tool for studying complex biological systems. However, existing simulation platforms do not always take full advantage of modern hardware and often have a field-specific software design. RESULTS: We present a novel simulation platform called BioDynaMo that alleviates both of these problems. BioDynaMo features a modular and high-performance simulation engine. We demonstrate that BioDynaMo can be used to simulate use cases in: neuroscience, oncology and epidemiology. For each use case, we validate our findings with experimental data or an analytical solution. Our performance results show that BioDynaMo performs up to three orders of magnitude faster than the state-of-the-art baselines. This improvement makes it feasible to simulate each use case with one billion agents on a single server, showcasing the potential BioDynaMo has for computational biology research. AVAILABILITY AND IMPLEMENTATION: BioDynaMo is an open-source project under the Apache 2.0 license and is available at www.biodynamo.org. Instructions to reproduce the results are available in the supplementary information. SUPPLEMENTARY INFORMATION: Available at https://doi.org/10.5281/zenodo.5121618.

JSON is a popular data interchange format for many web, cloud, and IoT systems due to its simplicity, human readability, and widespread support. However, applications must first parse and convert the data to a native in-memory format before being able to perform useful computations. Many big data applications with high performance requirements convert JSON data to Apache Arrow RecordBatches, the latter being a widely-used columnar in-memory format for large tabular data sets used in data analytics. In this paper, we analyze the performance characteristics of such applications and show that JSON parsing represents a bottleneck in the system. Various strategies are explored to speed up JSON parsing on CPU and GPU as much as possible. Due to performance limitation of the CPU and GPU implementations, we furthermore present an FPGA accelerated implementation. We explain how hardware components that can parse variable-sized and nested structures can be combined to produce JSON parsers for any type of JSON document. Several fully integrated FPGA-accelerated JSON parser implementations are presented using the Intel Arria 10 GX and Xilinx VU37P devices, and compared to the performance of their respective host systems; an Intel Xeon and an IBM POWER9 system. Result show the accelerators achieve an end-to-end throughput close to 7 GB/s with the Arria 10 GX using PCIe, and close to 20 GB/s with the VU37P using OpenCAPI 3. Depending on the complexity of the JSON data to parse, the bandwidth is limited by the host-to-accelerator interface or available FPGA resources. Overall, this provides a throughput increase of up to 6x, compared to the baseline application. Also, we observe a full system energy efficiency improvement of up to 59x more JSON data parsed per joule.

Data-free compression raises a new challenge because the original training dataset for a pre-trained model to be compressed is not available due to privacy or transmission issues. Thus, a common approach is to compute a reconstructed training dataset before compression. The current reconstruction methods compute the reconstructed training dataset with a generator by exploiting information from the pre-trained model. However, current reconstruction methods focus on extracting more information from the pre-trained model but do not leverage network engineering. This work is the first to consider network engineering as an approach to design the reconstruction method. Specifically, we propose the AutoReCon method, which is a neural architecture search-based reconstruction method. In the proposed AutoReCon method, the generator architecture is designed automatically given the pre-trained model for reconstruction. Experimental results show that using generators discovered by the AutoRecon method always improve the performance of data-free compression.

Cyber-Physical Systems (CPS) are dynamic and reactive systems interacting with processes, environment and, sometimes, humans. They are often distributed with sensors and actuators, smart, adaptive, predictive and react in real-time. Indeed, as sight for human beings, image- and video-processing pipelines are a prime source for environmental information for systems allowing them to take better decisions according to what they see. Therefore, in FitOptiVis we are developing novel methods and tools to integrate complex image and video processing pipelines. FitOptiVis aims to deliver a reference architecture for describing and optimizing quality and resource management for imaging and video pipelines in CPS both at design- and run-time. The architecture is concretized in low-power, high-performance, smart components, and in methods and tools for combined design-time and run-time multi-objective optimization and adaptation within system and environment constraints.

Computational neuroscience uses models to study the brain. The Hodgkin-Huxley (HH) model, and its extensions, is one of the most powerful, biophysically meaningful models currently used. The high experimental value of the (extended) Hodgkin-Huxley (eHH) models comes at the cost of steep computational requirements. Consequently, for larger networks, neuroscientists either opt for simpler models, losing neuro-computational features, or use high-performance computing systems. The eHH models can be efficiently implemented as a dataflow application on a FPGA-based architecture. The state-of-the-art FPGA-based implementations have proven to be time-consuming because of the long-duration synthesis requirements. We have developed flexHH, a flexible hardware library, compatible with a widely used neuron-model description format, implementing five FPGA-accelerated and parameterizable variants of eHH models (standard HH with optional extensions: custom ion-gates, gap junctions, and/or multiple cell compartments). Therefore, flexHH is a crucial step towards high-flexibility and high-performance FPGA-based simulations, eschewing the penalty of re-engineering and re-synthesis, dismissing the need for an engineer. In terms of performance, flexHH achieves a speedup of 1,065x against NEURON, the simulator standard in computational neuroscience, and speedups between 8x-20x against sequential C. Furthermore, flexHH is faster per simulation step compared to other HPC technologies, provides 65% or better performance density (in FLOPS/LUT) compared to related works, and only shows a marginal performance drop in real-time simulations.

Binary Convolutional Neural Networks (CNNs) have significantly reduced the number of arithmetic operations and the size of memory storage needed for CNNs, which makes their deployment on mobile and embedded systems more feasible. However, after binarization, the CNN architecture has to be redesigned and refined significantly due to two reasons: 1. the large accumulation error of binarization in the forward propagation, and 2. the severe gradient mismatch problem of binarization in the backward propagation. Even though substantial effort has been invested in designing architectures for single and multiple binary CNNs, it is still difficult to find an optimized architecture for binary CNNs. In this paper, we propose a strategy, named NASB, which adapts Neural Architecture Search (NAS) to find an optimized architecture for the binarization of CNNs. In the NASB strategy, the operations and their connections define a unique searching space and the training and binarization of the network progress in the three-stage training algorithm.1Due to the flexibility of this automated strategy, the obtained architecture is not only suitable for binarization but also has low overhead, achieving a better trade-off between the accuracy and computational complexity compared to hand-optimized binary CNNs. The implementation of the NASB strategy is evaluated on the ImageNet dataset and demonstrated as a better solution compared to existing quantized CNNs. With insignificant overhead increase, NASB outperforms existing single and multiple binary CNNs by up to 4.0% and 1.0% Top-1 accuracy respectively, bringing them closer to the precision of their full precision counterpart.

Data movement has long been identified as the biggest challenge facing modern computer systems' designers. To tackle this challenge, many novel data compression algorithms have been developed. Often variable rate compression algorithms are favored over fixed rate. However, variable rate decompression is difficult to parallelize. Most existing algorithms adopt a single parallelization strategy suited for a particular HW platform. Such an approach fails to harness the parallelism found in diverse modern HW architectures. We propose a parallelization method for tiled variable rate compression algorithms that consists of multiple strategies that can be applied interchangeably. This allows an algorithm to apply the strategy most suitable for a specific HW platform. Our strategies are based on generating metadata during encoding, which is used to parallelize the decoding process. To demonstrate the effectiveness of our strategies, we implement them in a state-of-the-art compression algorithm called ZFP. We show that the strategies suited for multicore CPUs are different from the ones suited for GPUs. On a CPU, we achieve a near optimal decoding speedup and an overhead size which is consistently less than 0.04% of the compressed data size. On a GPU, we achieve average decoding rates of up to 100 GiB/s. Our strategies allow the user to make a trade-off between decoding throughput and metadata size overhead.

BACKGROUND: In Overlap-Layout-Consensus (OLC) based de novo assembly, all reads must be compared with every other read to find overlaps. This makes the process rather slow and limits the practicality of using de novo assembly methods at a large scale in the field. Darwin is a fast and accurate read overlapper that can be used for de novo assembly of state-of-the-art third generation long DNA reads. Darwin is designed to be hardware-friendly and can be accelerated on specialized computer system hardware to achieve higher performance. RESULTS: This work accelerates Darwin on GPUs. Using real Pacbio data, our GPU implementation on Tesla K40 has shown a speedup of 109x vs 8 CPU threads of an Intel Xeon machine and 24x vs 64 threads of IBM Power8 machine. The GPU implementation supports both linear and affine gap, scoring model. The results show that the GPU implementation can achieve the same high speedup for different scoring schemes. CONCLUSIONS: The GPU implementation proposed in this work shows significant improvement in performance compared to the CPU version, thereby making it accessible for utilization as a practical read overlapper in a DNA assembly pipeline. Furthermore, our GPU acceleration can also be used for performing fast Smith-Waterman alignment between long DNA reads. GPU hardware has become commonly available in the field today, making the proposed acceleration accessible to a larger public. The implementation is available at https://github.com/Tongdongq/darwin-gpu .

In-silico brain simulations are the de-facto tools computational neuroscientists use to understand large-scale and complex brain-function dynamics. Current brain simulators do not scale efficiently enough to large-scale problem sizes (e.g., >100,000 neurons) when simulating biophysically complex neuron models. The goal of this work is to explore the use of true multi-GPU acceleration through NVIDIA’s GPUDirect technology on computationally challenging brain models and to assess their scalability. The brain model used is a state-of-the-art, extended Hodgkin-Huxley, biophysically meaningful, three-compartmental model of the inferior-olivary nucleus. The Hodgkin-Huxley model is the most widely adopted conductance-based neuron representation, and thus the results from simulating this representative workload are relevant for many other brain experiments. Not only the actual network-simulation times but also the network-setup times were taken into account when designing and benchmarking the multi-GPU version, an aspect often ignored in similar previous work. Network sizes varying from 65K to 2M cells, with 10 and 1,000 synapses per neuron were executed on 8, 16, 24, and 32 GPUs. Without loss of generality, simulations were run for 100 ms of biological time. Findings indicate that communication overheads do not dominate overall execution while scaling the network size up is computationally tractable. This scalable design proves that large-network simulations of complex neural models are possible using a multi-GPU design with GPUDirect.

Rapid increases in storage bandwidth, combined with a desire for operating on large datasets interactively, drives the need for improvements in high-bandwidth decompression. Existing designs either process only one token per cycle or process multiple tokens per cycle with low area efficiency and/or low clock frequency. We propose two techniques to achieve high single-decoder throughput at improved efficiency by keeping only a single copy of the history data across multiple BRAMs and operating on each BRAM independently. A first stage efficiently refines the tokens into commands that operate on a single BRAM and steers the commands to the appropriate one. In the second stage, a relaxed execution model is used where each BRAM command executes immediately and those with invalid data are recycled to avoid stalls caused by the read-after-write dependency. We apply these techniques to Snappy decompression and implement a Snappy decompression accelerator on a CAPI2-attached FPGA platform equipped with a Xilinx VU3P FPGA. Experimental results show that our proposed method achieves up to 7.2 GB/s output throughput per decompressor, with each decompressor using 14.2% of the logic and 7% of the BRAM resources of the device. Therefore, a single decompressor can easily keep pace with an NVMe device (PCIe Gen3 x4) on a small FPGA, while a larger device, integrated on a host bridge adapter and instantiating multiple decompressors, can keep pace with the full OpenCAPI 3.0 bandwidth of 25 GB/s.

Cyber-Physical Systems (CPS) are systems that are in feedback with their environment, possibly with humans in the loop. They are often distributed with sensors and actuators, smart, adaptive and predictive and react in real-time. Image- and video-processing pipelines are a prime source for environmental information improving the possibilities of active, relevant feedback. In such a context, FitOptiVis aims to provide end-to-end multi-objective optimization for imaging and video pipelines of CPS, with emphasis on energy and performance, leveraging on a reference architecture, supported by low-power, high-performance, smart devices, and by methods and tools for combined design-time and run-time multi-objective optimization within system and environment constraints.

Snappy is a widely used (de) compression algorithm in many big data applications. Such a data compression technique has been proven to be successful to save storage space and to reduce the amount of data transmission from/to storage devices. In this paper, we present a fine-grained parallel Snappy decompressor on FPGAs running under a relaxed execution model that addresses the following main challenges in existing solutions. First, existing designs either can only process one token per cycle or can process multiple tokens per cycle with low area efficiency and/or low clock frequency. Second, the high read-after-write data dependency during decompression introduces stalls which pull down the throughput.

Modern big data systems are highly heterogeneous. The components found in their many layers of abstraction are often implemented in a wide variety of programming languages and frameworks. Due to language implementation differences, interfaces between these components, including hardware accelerated components, are often burdened by serialization overhead. Serialization bandwidth of many high-level language frameworks is an order of magnitude lower than contemporary FPGA accelerator interface bandwidth, especially when objects are small but numerous. Therefore, serialization bounds the effective end-to-end performance of FPGA-accelerated solutions integrated with applications written in high-level languages. The Apache Arrow project defines a language agnostic columnar in-memory format optimized for big data applications, preventing the need to serialize or even make copies during communication between components. To enable FPGA accelerators to benefit from the approach of Arrow, we first investigate the properties of its format in relation to hardware interfaces and establish that the format is usable. Second, we present the Fletcher framework, that automatically generates highly efficient hardware interfaces to access data of potentially complex, nested Arrow data types. Our approach allows 11 of the languages supported by Apache Arrow libraries to efficiently communicate large data sets with FPGA accelerators at system bandwidth. Furthermore, on the hardware side, the generated interfaces deliver any data type that Arrow can represent as groups of streams, providing a better starting point for data-flow-oriented kernel development, compared to manually creating custom interfaces to address issues related to pointer arithmetic, bus word misalignment and latency. For example applications, as measured on an AWS EC2 F1 and CAPI2-enabled POWER9 system, accelerated end-to-end application performance improves by 1.3x - 49x compared to a hardware accelerated solution that still requires serialization.

BACKGROUND: Due the computational complexity of sequence alignment algorithms, various accelerated solutions have been proposed to speedup this analysis. NVBIO is the only available GPU library that accelerates sequence alignment of high-throughput NGS data, but has limited performance. In this article we present GASAL2, a GPU library for aligning DNA and RNA sequences that outperforms existing CPU and GPU libraries. RESULTS: The GASAL2 library provides specialized, accelerated kernels for local, global and all types of semi-global alignment. Pairwise sequence alignment can be performed with and without traceback. GASAL2 outperforms the fastest CPU-optimized SIMD implementations such as SeqAn and Parasail, as well as NVIDIA's own GPU-based library known as NVBIO. GASAL2 is unique in performing sequence packing on GPU, which is up to 750x faster than NVBIO. Overall on Geforce GTX 1080 Ti GPU, GASAL2 is up to 21x faster than Parasail on a dual socket hyper-threaded Intel Xeon system with 28 cores and up to 13x faster than NVBIO with a query length of up to 300 bases and 100 bases, respectively. GASAL2 alignment functions are asynchronous/non-blocking and allow full overlap of CPU and GPU execution. The paper shows how to use GASAL2 to accelerate BWA-MEM, speeding up the local alignment by 20x, which gives an overall application speedup of 1.3x vs. CPU with up to 12 threads. CONCLUSIONS: The library provides high performance APIs for local, global and semi-global alignment that can be easily integrated into various bioinformatics tools.

Following publication of the original article [1], the author requested changes to the figures 4, 7, 8, 9, 12 and 14 to align these with the text. The corrected figures are supplied below.

With the continued down-scaling of IC technology and increase in manufacturing process variations, it is becoming ever more difficult to accurately estimate circuit performance of manufactured devices. This poses significant challenges on the effective application of adaptive voltage scaling (AVS) which is widely used as the most important power optimization method in modern devices. Process variations specifically limit the capabilities of Process Monitoring Boxes (PMBs), which represent the current industrial state-of-the-art AVS approach. To overcome this limitation, in this paper we propose an alternative solution using delay testing, which is able to eliminate the need for PMBs, while improving the accuracy of voltage estimation. The paper shows, using simulation of ISCAS’99 benchmarks with 28nm FD-SOI library, that using delay test patterns result in an error of 5.33% for transition fault testing (TF), error of 3.96% for small delay defect testing (SDD), and an error as low as 1.85% using path delay testing (PDLY). In addition, the paper also shows the impact of technology scaling on the accuracy of delay testing for performance estimation during production. The results show that the 65nm technology node exhibits the same trends identified for the 28nm technology node, namely that PDLY is the most accurate, while, TF is the least accurate performance estimator.

Bioinformatics workloads are characterized by huge data sets and complex algorithms, requiring enormous data processing and making high performance heterogeneous computation platforms such as FPGAs and GPUs highly relevant. We compare three accelerated implementations of the widely used BWA-MEM genomic mapping tool as a case study on design-time optimization for heterogeneous architectures: BWA-MEM-CUDA, BWA-MEM-OpenCL, and BWA-MEM-VHDL, each using an optimized Smith-Waterman algorithm implementation. Optimization of design-time is important because of the significant development effort of such implementations: BWA-MEM-CUDA and BWA-MEM-OpenCL require 5-7x more lines of code to express the Smith-Waterman algorithm, while BWA-MEM-VHDL requires more than 40x as many lines of code. Similar differences hold for required implementation time, ranging from one month for BWA-MEM-OpenCL to six months for BWA-MEM-VHDL. The advantages and disadvantages of each implementation are described using both quantitative and qualitative metrics, and recommendations are given for future algorithm implementations.

In order to improve the accuracy of indel detection, micro-assembly is used in multiple variant callers, such as the GATK HaplotypeCaller to reassemble reads in a specific region of the genome. Assembly is a computationally intensive process that causes runtime bottlenecks. In this paper, we propose a GPU-based de Bruijn graph construction algorithm for micro-assembly in the GATK HaplotypeCaller to improve its performance. Various synthetic datasets are used to compare the performance of the GPU-based de Bruijn graph construction implementation with the software-only baseline, which achieves a speedup of up to 3x. An experiment using two human genome datasets is used to evaluate the performance shows a speedup of up to 2.66x.

Adaptive voltage scaling (AVS) has been used widely to compensate for process, voltage, and temperature variations as well as power optimization of integrated circuits. The current industrial state-of-the-art AVS approaches using Process Monitoring Boxes (PMBs) have shown several limitations such as huge characterization effort, which makes these approaches very expensive, and a low accuracy that results in extra margins, which consequently lead to yield loss and performance limitations. To overcome those limitations, in this paper we propose an alternative solution using transition fault test patterns, which is able to eliminate the need for PMBs, while improving the accuracy of voltage estimation. The paper shows, using simulation of ISCAS'99 benchmarks with 28nm FD-SOI library, that AVS using transition fault testing (TF-based AVS) results in an error as low as 5.33%. The paper also shows that the PMB approach can only account for 85% of the uncertainty in voltage measurements, which results in power waste, while the TF-based approach can account for 99% of that uncertainty.

In deep sub-micron technologies, the increasing effect of process and environmental variations has lead chip manufacturers to use adaptive voltage scaling techniques in order to adapt operation parameters exclusively to each chip. The increasing effect of process variation is limiting the effectiveness of current chip monitoring approaches, such as on-chip performance monitor boxes (PMBs), which results in yield loss and high design margins, thus high power consumption. This paper proposes an alternative solution for adaptive voltage scaling using delay test patterns, which is able to eliminate the need for PMBs, and thus the long expensive characterization phase of tuning PMBs to each design, while improving the yield as well as power optimization. Results show, using an industrial grade 28nm FD-SOI library developed for low power devices, that delay testing for performance prediction reduces the inaccuracy down to 1.85%.

Much research has been dedicated to reducing the computational time associated with the analysis of genome data, which resulted in shifting the bottleneck from the time needed for the computational analysis part to the actual time needed for sequencing of DNA information. DNA sequencing is a time consuming process, and all existing DNA analysis methods have to wait for the DNA sequencing to completely finish before starting the analysis. In this paper, we propose a new DNA analysis approach where we start the genome analysis before the DNA sequencing is completely finished. The genome analysis is started when the DNA reads are still in the process of being sequenced. We use algorithms to predict the unknown bases and their corresponding base quality scores of the incomplete read. Results show that our method of predicting the unknown bases and quality scores achieves more than 90% similarity with the full dataset for 50 unknown bases (slashing more than a day of sequencing time). We also show that our base quality value prediction scheme is highly accurate, only reducing the similarity of the detected variants by 0.45%. However, there is still room to introduce more accurate prediction schemes for the unknown bases to increase the effectiveness of the analysis by up to 5.8%.

The Smith-Waterman algorithm is widely used in bioinformatics and is often used as a benchmark of FPGA performance. Here we present our highly optimized Smith-Waterman implementation on Intel FPGAs using OpenCL. Our implementation is both faster and more efficient than other current Smith-Waterman implementations, obtaining a theoretical performance of 214 GCUPS. Moreover, due to the streaming, implicit synchronizing nature of our implementation, which streams alignments and places no restrictions on the number of alignments in flight, it achieves 99.8% of this performance in practice, almost three times as fast as previous implementations. The expressiveness of OpenCL results in a significant reduction in lines of code, and in a significant reduction of development time compared to programming in regular hardware description languages.

The large amount of data generated by NextGeneration Sequencing (NGS) technology, usually in the order of hundreds of gigabytes per experiment, has to be analyzed quickly to generate meaningful variant results. The first step in analyzing such data is to map those sequenced reads to their corresponding positions in the human genome. One of the most popular tools to do such sequence alignment is the Burrows-Wheeler Aligner (BWA mem). One limitation of the BWA program though is that it cannot be run on a cluster. In this paper, we propose StreamBWA, a new framework that allows the BWA mem program to run on a cluster in a distributed fashion, at the same time while the input data is being streamed into the cluster. It can process the input data directly from a compressed file, which either lies on the local file system or on a URL. Moreover, StreamBWA can start combining the output files of the distributed BWA mem tasks at the same time while these tasks are still being executed on the cluster. Empirical evaluation shows that this streaming distributed approach is approximately 2x faster than the nonstreaming approach. Furthermore, our streaming distributed approach is 5x faster than other state-of-the-art solutions such as SparkBWA. The source code of StreamBWA is publicly available at https://github.com/HamidMushtaq/StreamBWA.

Due to its high-throughput and low cost, Next Generation Sequencing (NGS) technology is becoming increasingly popular in many genomics research labs. However, handling the massive raw data generated by the NGS platforms poses a significant computational challenge to genomics analysis tools. This paper presents a GPU acceleration of the GATK HaplotypeCaller (GATK HC), a widely used DNA variant caller in the clinic. Moreover, this paper proposes a load-balanced multi-process optimization of GATK HaplotypeCaller to address its implementation limitation which forces the sequential execution of the program and prevents effective utilization of hardware acceleration. In single-threaded mode, the GPU-based GATK HC is 1.71x and 1.21x faster than the baseline HC implementation and the vectorized GATK HC implementation, respectively. Moreover, the GPU-based implementation achieves up to 2.04x and 1.40x speedup in load-balanced multi-process mode over the baseline implementation and the vectorized GATK HC implementation in non-load-balanced multi-process mode, respectively.

Sequence alignment is a core step in the processing of DNA and RNA sequencing data. In this paper, we present a high performance GPU accelerated set of APIs (GASAL) for pairwise sequence alignment of DNA and RNA sequences. The GASAL APIs provide accelerated kernels for local, global as well as semi-global alignment, allowing the computation of the alignment score, and optionally the start and end positions of the alignment. GASAL outperforms the fastest CPU-optimized SIMD implementations such as SSW and Parasail. It also outperforms NVBIO, NVIDIA's own CUDA library for sequence analysis of high-throughput sequencing data. GASAL uses the unique approach of also performing the sequence packing on GPU, which is over 200× faster than the NVBIO approach. Overall on Tesla K40c GASAL is 10-14× faster than 28 Intel Xeon cores and 3-4× faster than NVBIO with a query length of 100 bases. The APIs are included in an easy to use library to allow integration into various bioinformatics tools.

DNA read alignment is a major step in genome analysis. However, as DNA reads continue to become longer, new approaches need to be developed to effectively use these longer reads in the alignment process. Modern aligners commonly use a two-step approach for read alignment: 1. seeding, 2. extension. In this paper, we have investigated various seeding and extension techniques used in modern DNA read alignment algorithms to find the best seeding and extension combinations. We developed an open source generic DNA read aligner that can be used to compare the alignment accuracy and total execution time of different combinations of seeding and extension algorithms. For extension, our results show that local alignment is the best extension approach, achieving up to 3.6× more accuracy than other extension techniques, for longer reads. For seeding, if BLAST-like seed extension is used, the best seeding approach is identifying all SMEMs in the DNA read (e.g., approach used by BWA-MEM). This combination is up to 6× more accurate than other seeding techniques, for longer reads. With local alignment, we observed that the seeding technique does not impact the alignment accuracy. Furthermore, we showed that an optimized implementation of local alignment using vector instructions, enabling 4.5× speedup, makes it the fastest of all extension techniques. Overall, we show that using local alignment with non-overlapping maximal exact matching seeds is the best seeding-extension combination due to its high accuracy and higher potential for optimization/acceleration for future DNA reads.

In the analysis of next-generation DNA sequencing data, Hidden Markov Models (HMMs) are used to perform variant calling between DNA sequences and a reference genome. The PairHMM model is solved by the Forward Algorithm, for which the performance and power efficiency can be increased tremendously using systolic arrays (SAs) in FPGAs. We model the performance characteristics of such SAs, and propose a novel architecture that allows the computational units to continuously perform useful work on the input data. The implementation achieves up to 90% of the theoretical throughput for a real dataset. The implementation of the proposed architecture achieves more than 2.5× throughput over the state-of-the-art on a similar contemporary platform.

In order to handle the massive raw data generated by next generation sequencing (NGS) platforms, GPUs are widely used by many genetic analysis tools to speed up the used algorithms. In this paper, we use GPUs to accelerate the pair-HMMs forward algorithm, which is used to calculate the overall alignment probability in many genomics analysis tools. We firstly evaluate two different implementation methods to accelerate the pair-HMMs forward algorithm according to their effectiveness on GPU platforms. Based on these two methods, we present several implementations of the pair-HMMs forward algorithm. We execute these implementations on the NVIDIA Tesla K40 card using different datasets to compare the performance. Experimental results show that the intra-task implementation has the highest throughput in most cases, achieving pure computational throughput as high as 23.56 GCUPS for synthetic datasets. On a real dataset, the inter-task implementation achieves 4.82× speedup compared with a parallelized software implementation executed on a 20-core POWER8 system.

We propose a novel FPGA-accelerated BWA-MEM implementation, a popular tool for genomic data mapping. The performance and power-efficiency of the FPGA implementation on the single Xilinx Virtex-7 Alpha Data add-in card is compared against a software-only baseline system. By offloading the Seed Extension phase onto the FPGA, a two-fold speedup in overall application-level performance is achieved and a 1.6x gain in power-efficiency. To facilitate platform and tool-agnostic comparisons, the base pairs per Joule unit is introduced as a measure of power-efficiency. The FPGA design is able to map up to 34 thousand base pairs per Joule.

Fast progress in next generation sequencing has dramatically increased the throughout of DNA sequencing, resulting in the availability of large DNA data sets ready for analysis. However, post-sequencing DNA analysis has become the bottleneck in using these data sets, as it requires powerful and scalable tools to perform the needed analysis. A typical analysis pipeline consists of a number of steps, not all of which can readily scale on a distributed computing infrastructure. Recently, tools like Halvade, a Hadoop MapReduce solution, and Churchill, an HPC cluster-based solution, addressed this issue of scalability in the GATK DNA analysis pipeline. In this paper, we present a framework that implements an in-memory distributed version of the GATK pipeline using Apache Spark. Our framework reduced execution time by keeping data active in the memory between the map and reduce steps. In addition, it has a dynamic load balancing algorithm that better utilizes system performance using runtime statistics of the active workload. Experiments on a 4 node cluster with 64 virtual cores show that this approach is 63% faster than a Hadoop MapReduce based solution.

Many DNA sequence analysis tools have been developed to turn the massive raw DNA sequencing data generated by NGS (Next Generation Sequencing) platforms into biologically meaningful information. The pair-HMMs forward algorithm is widely used to calculate the overall alignment probability needed by a number of DNA analysis tools. In this paper, we propose a novel systolic array design to accelerate the pair-HMMs forward algorithm on FPGAs. A number of architectural features have been implemented to improve the performance of the design, such as early exit points to increase the utilization of the array for small sequence sizes, as well as on-chip buffering to enable the processing of long sequences effectively. We present an implementation of the design on the Convey supercomputing platform. Experimental results show that the FPGA implementation of the pair-HMMs forward algorithm is up to 67x faster, compared to software-only execution.

The fast decrease in cost of DNA sequencing has resulted in an enormous growth in available genome data, and hence led to an increasing demand for fast DNA analysis algorithms used for diagnostics of genetic disorders, such as cancer. One of the most computationally intensive steps in the analysis is represented by the DNA read alignment. In this paper, we present an accelerated version of BWA-MEM, one of the most popular read alignment algorithms, by implementing a heterogeneous hardware/software optimized version on the Convey HC2ex platform. A challenging factor of the BWA-MEM algorithm is the fact that it consists of not one, but three computationally intensive kernels: SMEM generation, suffix array lookup and local Smith-Waterman. Obtaining substantial speedup is hence contingent on accelerating all of these three kernels at once. The paper shows an architecture containing two hardware-accelerated kernels and one kernel optimized in software. The two hardware kernels of suffix array lookup and local Smith-Waterman are able to reach speedups of 2.8x and 5.7x, respectively. The software optimization of the SMEM generation kernel is able to achieve a speedup of 1.7x. This enables a total application acceleration of 2.6x compared to the original software version.

This paper describes a low overhead software-based fault tolerance approach for shared memory multicore systems. The scheme is implemented at user-space level and requires almost no changes to the original application. Redundant multithreaded processes are used to detect soft errors and recover from them. Our scheme makes sure that the execution of the redundant processes is identical even in the presence of non-determinism due to shared memory accesses. It provides a very low overhead mechanism to achieve this. Moreover it implements a fast error detection and recovery mechanism. The overhead incurred by our approach ranges from 0% to 18% for selected benchmarks. This is lower than comparable systems published in literature.

The communication infrastructure is one of the important components of a multicore system along with the computing cores and memories. A good interconnect design plays a key role in improving the performance of such systems. In this paper, we introduce a hybrid communication infrastructure using both the standard bus and our area-efficient and delay-optimized network on chip for heterogeneous multicore systems, especially hardware accelerator systems. An adaptive data communication-based mapping for reconfigurable hardware accelerators is proposed to obtain a low overhead and latency interconnect. Experimental results show that the proposed communication infrastructure and the adaptive data communication-based mapping achieves a speed-up of 2.4× with respect to a similar system using only a bus as interconnect. Moreover, our proposed system achieves a reduction of energy consumption of 56% compared to the original system.

The ever decreasing transistor size has made it possible to integrate multiple cores on a single die. On the downside, this has introduced reliability concerns as smaller transistors are more prone to both transient and permanent faults. However, the abundant extra processing resources of a multicore system can be exploited to provide fault tolerance by using redundant execution. We have designed a library for multicore processing, that can make a multithreaded user-level application fault tolerant by simple modifications to the code. It uses the abundant cores found in the system to perform redundant execution for error detection. Besides that, it also allows recovery through checkpoint/rollback. Our library is portable since it does not depend on any special hardware. Furthermore, the overhead (up to 46% for 4 threads), our library adds to the original application, is less than other existing approaches, such as Respec.

Multicore architectures, especially hardware accelerator systems with heterogeneous processing elements, are being increasingly used due to the increasing processing demand of modern digital systems. However, data communication in multicore architectures is one of the main performance bottle-necks. Therefore, reducing data communication overhead is an important method to improve the speed-up of such systems. In this paper, we propose a heuristic-based approach to address the data communication bottleneck. The proposed approach uses a detailed quantitative data communication profiling to generate interconnect designs automatically that are relatively simple, low overhead and low area solutions. Experimental results show that we can gain speed-up of 3.05× for the whole application and up to 7.8× speed-up for accelerator functions in comparison with software.

Due to rapid and continuous technology scaling, faults in semiconductor memories (and ICs in general) are becoming pervasive and weak rather than strong, a weak fault is a fault that escape the test program (because it does not cause an error/system failure). However, multiple weak faults may cause an error during the application. Components with weak faults which fail at board and system level are sent to suppliers, but only to have them returned back as No Trouble Found (NTF). This is because the conventional memory test approach assumes the presence of a single defect at a time causing a strong fault (hence an error), and is therefore unable to deal with weak faults. This paper presents a new memory test approach able to detect weak faults, it is based on assuming the presence of multiple weak faults at a time in a memory system rather than a single strong fault at a time. Being able to detect weak faults reduces the number of escapes, hence also the number of NTFs. The experimental analysis done using SPICE simulation for a case of study show that when assuming two simultaneous weak faults, the missing (defect) coverage can be reduced with 10% as compared with the conventional approach.

Parasitic memory effect can occur due to the impact of parasitic node capacitances and faulty node voltages on the electrical behavior of SRAMs. This memory effect can cause detectable faults to become undetectable using existing industrial tests. This paper analyzes, evaluates and identifies the unique detection conditions for faults in SRAMs. It demonstrates the limitation of existing industrial tests that do not take the impact of parasitic memory effect into consideration. Finally, the paper presents March SME, a memory test that detects SRAM static faults in the presence of parasitic memory effect.

Parasitic node capacitance and faulty node voltage of a defective node can induce serious parasitic effects on the electrical behavior of SRAMs. This paper evaluates the impact of parasitic memory effect on the detection of single-cell faults in SRAMs. It demonstrates that detection is significantly influenced by parasitic node components; something that is often not accounted for during memory testing. Finally, it shows the impact of parasitic node components on all possible opens in the SRAM memory cell array, using node voltages from GND to VDD.

Memory test optimization can significantly reduce test complexity, while retaining the quality of the test. In the presence of parasitic BL coupling, faults may only be detected by writing all possible coupling backgrounds (CBs) in the neighboring cells of the victim. However, using all possible CBs while testing for every fault consumes enormous test time, which can be significantly reduced, for the same fault coverage, if only limited required CBs are identified for each functional fault model (FFM). So far, no systematic approach has been proposed that identifies such limited required CBs, nor corresponding optimized memory tests generated that ap ply limited CBs. Therefore, this paper presents a systematic approach to identify such limited CBs, and thereafter presents an optimized test, March BLC, which detects all static memory faults in the presence of BL coupling using only required CBs.

The fault coverage of otherwise efficient memory tests can be dramatically reduced due to the influence of bit line coupling. This paper, analyzes the impact of parasitic bit line coupling and neighborhood coupling data backgrounds on the faulty behavior of SRAMs. It investigates and determines the worst case coupling backgrounds required to induce worst case coupling effects, and validates the analysis through defect injection and circuit simulation of all possible spot defects in the SRAM cell array. The paper clearly demonstrates the inadequacies and limitations of several industrial tests in detecting memory faults in the presence of bit line coupling. Finally, it shows how to detect all single-cell and two-cell faults, both in the absence and in the presence of bit line coupling for any possible spot defect.

Due to the decreasing dimensions of manufactured devices, the effect of bit line capacitive coupling on the behavior of faulty memory cells cannot be ignored. Neighboring cells influence the faulty behavior of defective cells through coupling. This paper analyzes and validates this behavior theoretically and through electrical simulations. The paper evaluates the impact of bit line coupling in SRAMs on cell faulty behavior and identifies necessary conditions to induce worst-case coupling effects. We present a test that guarantees detecting all single-cell static faults in the presence of capacitive coupling and worst-case neighborhood data for any possible open defect.

As diagnostic testing for memory devices increasingly gains in importance, companies are looking for flexible, cost effective methods to perform diagnostics on their failing devices. This paper proposes the new concept of test primitives as a method to diagnose memory faults. Test primitives provide an easy-to-use, extensible, low-cost memory fault diagnosis method that is universally applicable, since it uses simple platform-independent test sequences. The paper defines the concept of test primitives, shows their importance and gives examples to the way they are derived and used in a memory test environment.

Due to the rapid decrease of technology feature size speed related faults, such as Address Decoder Delay Faults (ADDFs), are becoming very important. In addition, increased leakage currents demand for improved tests for Bit Line Imbalance Faults (BLIFs)(caused by memory cell pass transistor leakage). This paper contributes to new and improved algorithms for detecting these faults. First it provides an improved version of existing GalPat algorithm and introduces two new algorithms to detect ADDFs; the paper also shines a new light on the use of the different stress combinations (counting methods, data-backgrounds) and their importance for the detection of ADDFs. Second, it provides an improved algorithm for detecting BLIFs; it increases the defect coverage by being able to detect lower leakage currents.

The Smith-Waterman (SW) algorithm is a local sequence alignment algorithm that attempts to align two biological sequences of varying length such that the alignment score is maximum. In this paper, we propose a new approach to reduce the time needed to perform the SW algorithm. This is done by applying the concept of recursive variable expansion, which exposes more parallelism in the algorithm than any other published method. The paper estimates the speed and hardware overhead for the newly proposed approach relative to other known acceleration methods. Using the new approach, it is possible to achieve a minimum speedup of 400 times better than the serial case for a typical sequence length of 500, which is 1.6 times higher than any other published method. The paper also shows that further speedup can be achieved using extra hardware to expose even more parallelism in the algorithm.

Efficient and effective methods are needed to generate defect oriented tests for todays VLSI circuits. This paper describes an industrial case study for using defect injection and Spice simulation to generate defect oriented tests for the so-called strap defects in DRAMs, taking both the sensitivity of this defect to process variations and bit line coupling into consideration. The paper discusses all the different stages of the test generation process, starting with defect modeling, followed by the simulation methodology, test generation and optimization, and finally test application and industrial evaluation performed in Qimonda. Results show that the generated tests have the same coverage as previously used tests with possible test time reduction of up to 59%. The analysis also identifies the slow process corner and the data backgrounds 11 and 01 as the most stressful combinations to test the strap. The paper also discusses a test method used to account for process variations and detect the fault in any process corner.

Up to 53% of the time spent on testing current Intel microprocessors is needed to test on-chip caches, due to the high complexity of memory tests and to the large amount of transistors dedicated to such memories. This paper discusses the methodology used to develop effective and efficient cache tests, and the way it is implemented to optimize the test set used at Intel to test their 512-kB caches manufactured in a 0.13- mum technology. An example is shown where a maximal test set of 15 tests with a corresponding maximum test time of 160.942 ms/chip is optimized to only six tests that require a test time of only 30.498 ms/chip.

This paper summarizes advanced test patterns designed to target dynamic and time-related faults caused by new defect mechanisms in deep-submicron memory technologies. Such tests are industrially evaluated together with the traditional tests at "Design of Systems on Silicon (DS2)" in Spain in order to (a) validate the used fault models and (b) investigate the added value of the new tests and their impact on the PPM level. The preliminary silicon results are presented and analyzed. They validate some of the new dynamic fault models and show the importance of considering dynamic faults for high outgoing product quality.

Soft faults in DRAMs are faults that do not get sensitized directly after an operation is performed, but require a time to pass before the fault can be detected. Tests developed to detect these faults are rather complex and take an exceptionally long time to apply on the memory. This paper discusses a number of methods to optimize the test length for soft faults, based on the electrical design of the memory and the topology of the layout. These methods make it possible to reduce the delay time needed in the test such that it does not scale with the number of cells in the memory

DRAMs play an important role in the semiconductor industry, due to their highly dense layout and their low price per bit. This paper presents the first framework of fault models specifically designed to describe the faulty behavior of DRAMs. The fault models in this paper are the outcome of a close collaboration with the industry, and are validated using a detailed. Spice-based analysis of the faulty behavior of real DRAMs. The resulting fault space is then used to derive a couple of new DRAM-specific tests, needed to detect some of the faults in practice

DRAM testing has always been theoretically considered as a subset of general memory testing, despite the disagreement of this assumption with the DRAM test practice. This paper presents a recently developed space of DRAM faults that describes the unique aspects of DRAM behavior, it validates this fault space using extensive Spice simulation, and it identifies the memory tests necessary to detect these faults. Six different tests are derived and shown to correspond to highly effective DRAM tests in practice

This paper presents a complete electrical analysis of address decoder delay faults "ADFs" caused by resistive opens in RAMs. A classification between inter and intragate opens is made. A systematic way is introduced to explore the space of possible tests to detect these faults; it is based on generating appropriate sensitizing address transitions and the corresponding sensitizing operation sequences. DFT features are given to facilitate the BIST implementation of the new tests

With the continued advances in miniaturization, bit-line (BL) coupling is becoming ever more influential on the memory behavior. This paper discusses the effects of BL coupling on the faulty behavior of defective dynamic RAMs. It starts with an analytical evaluation of coupling effects, followed by a simulation-based fault analysis using a Spice simulation model. Two BL coupling mechanisms are identified (pre-sense and post-sense coupling), which are found to have a partly opposing effect on the faulty behavior. It is shown that BL coupling causes a special kind of coupling fault between adjacent memory cells. In addition, the influence of BL twisting on the faulty behavior of the memory is analyzed and simulated. The results indicate strong correspondence between theory and simulation and show the importance of Spice simulation as a vital tool for fault analysis

Fabrication process improvements and technology scaling results in modifications in the characteristics and in the behavior of manufactured memory chips, which also modifies the faulty behavior of the memory. This paper introduces an analytical (equation-based) method to give a rough analysis of the faulty behavior of cell opens in the memory, that simplifies the understanding and identifies the major factors responsible for the faulty behavior. Having these factors makes it easier to optimize the circuit and allows extrapolation of the behavior of future technologies. The paper also compares the results of the analytical approach with those from the simulation-based analysis and discusses the advantages and disadvantages of both

With the increasing complexity of memory behavior, attempts are being made to come up with a methodical approach that employs electrical simulation to tackle the memory test problem. This paper describes a framework of algorithms and tools developed jointly by the Delft University of Technology and Infineon Technologies to systematically generate DRAM tests using Spice simulation. The proposed Spice-based test approach enjoys the advantage of being relatively inexpensive, yet highly accurate in describing the desired memory faulty behavior.

This paper presents an industrial evaluation of tests for intra-word faults in word oriented memories, applied to big arrays with bit-interleaved organization as well as to small arrays with bit-adjacent organization, in order to investigate the influence of the memory organization on the intra-word faults. The test results show that the intra-word faults are also significantly important for interleaved memories, even though that the cells within a single word are not physically adjacent.

Memory testing in general, and DRAM testing in particular, has become greatly dependent on the modification of stresses (timing, temperature and voltages) in a way that is difficult to justify using the current understanding of memory faults. This paper introduces a new class of fault models (soft faults) based on a special classification of memory faults, that shows why it is fundamentally necessary to apply stresses. The paper calculates the relative probability of soft faults for a specific failure mechanism and compares this probability in DRAMs with that in SRAMs. In addition, the concept of soft faults is validated using defect injection and electrical simulation of a Spice DRAM model.

This paper presents an electrical analysis of Address decoder Delay Faults 'AFDs' caused by resistive inter-gate opens in RAMs. It introduces a systematic method to explore the space of possible tests to detect these faults. The method is based on generating appropriate sensitizing address transitions and the corresponding sensitizing operation sequences.

With the shrinking dimensions of manufactured structures on memory chips and the increase in memory size, bit line coupling is becoming ever more influential on the memory behavior. This paper discusses the effects of bit line coupling on the faulty behavior of DRAMs. It starts with an analytical evaluation of coupling effects, followed by a simulation-based fault analysis using a SPICE simulation model. Two bit line coupling mechanisms are identified, pre-sense and post-sense coupling, and found to have a partly opposing effect on the faulty behavior. In addition, the impact of neighboring cells on these coupling mechanisms is investigated.

The analysis of linked faults (LFs), which are faults that influence the behavior of each other, such that masking can occur, has proven to be a source for new memory tests, characterized by an increased fault coverage. However, many newly reported fault models have not been investigated from the point-of-view of LFs. This paper presents a complete analysis of LFs, based on the concept of fault primitives, such that the whole space of LFs is investigated and accounted for and validated. Some simulated defective circuits, showing linked-fault behavior, will be also presented. The paper establishes detection conditions along with new tests to detect each fault class. The tests are merged into a single test March SL detecting all considered LFs. Preliminary test results, based on Intel advanced caches, show that its fault coverage is high as compared with all other traditional tests and that it detects some unique faults; this makes March SL very attractive industrially.

As a result of variations in the fabrication process, different memory components are produced with different operational characteristics, a situation that complicates the fault analysis process of manufactured memories. This paper discusses the issue of process variations, and shows how to deal with it in the context of fault analysis and test generation. The paper also introduces the concept of border resistance traces as a tool to optimize test stresses and inspect the impact of process variations on the optimization procedure. The concepts are discussed in the paper with the help of a practical example of a specific defect in the memory.

The analysis of linked faults has proven to be a source for new memory tests, characterized by an increased fault coverage. The paper gives a set of five new tests to target all possible linked faults. The tests are merged into a single test, March SL, detecting all faults in the linked fault space. The preliminary test results of an experiment done at Intel are reported; they show that March SL scores high and detects some unique faults.

Spot defects in memory devices are caused by imperfections in the fabrication process of these devices. In order to analyze the faulty effect of spot defects on the memory behavior, simulations have been performed on an electrical model of the memory in which the defects are injected, causing opens, shorts, or bridges. In this paper, simulation is used to analyze the faulty behavior of embedded DRAM (eDRAM) devices produced by Infineon Technologies. The paper applies the new approach of fault primitives to perform this analysis. The analysis shows the existence of most traditional memory fault models and establishes new ones. The paper also investigates the concept of dynamic faulty behavior and establishes its importance for eDRAMs. Conditions to test the newly established fault models, together with a test, are also given.

Although electrical simulation has become a vital tool in the design process of memory devices, memory testing has not yet been able to employ electrical simulation as an integral part of the test generation and optimization process. This is due to the exponential complexity of the simulation-based fault analysis, a complexity that made such an analysis impractical. This paper describes new methods to reduce the complexity of the fault analysis from exponential to constant with respect to the number of analyzed operations, thereby making it possible: 1) to use electrical simulation to generate test patterns; and 2) to perform simulation-based stress optimization of tests. The paper also discusses ways to analyze the impact of idle time on the faulty behavior. In addition, results of a fault analysis study performed to verify the new analysis method are shown, where the new analysis reduces the analysis time by a factor of 30.

To limit the exponential complexity required to analyze the dynamic faulty behavior of DRAMs, algorithms have been published to approximate the faulty behavior of DRAM cell defects. These algorithms, however, have limited practical application since they are based on generic memory operations (writes and reads) rather than the DRAM specific operations (activation, precharge, etc.). This paper extends the approximation algorithms by incorporating the DRAM specific operations, making them directly applicable in practice. In addition, based on the new extended method, the paper shows results of a fault analysis study of cell defects using electrical simulation.

It has always been assumed that fault models in memories are sufficiently precise for specifying the faulty behavior This means that, given a fault model, it should be possible to construct a test that ensures detecting the modeled fault. This paper shows that some faults, called partial faults, are particularly difficult to detect. For these faults, more operations are required to complete their fault effect and to ensure detection. The paper also presents fault analysis results, based on defect injection and simulation, where partial faults have been observed. The impact of partial faults on testing is discussed and a test to detect these partial faults is given.

Analyzing the dynamic faulty behavior in DRAMs is a severely time consuming task, because of the exponential growth of the analysis time needed with each memory operation added to the sensitizing operation sequence of the fault. In this paper, a new fault analysis approach for DRAM cell defects is presented where the total infinite space of dynamic faulty behavior can be approximated within a limited amount of analysis time. The paper also presents the analysis results for some cell defects using the new approach, in combination with detection conditions that guarantee the detection of any detectable dynamic faults in the defective cell.

The ever increasing trend to reduce DPM levels of memories requires tests with very high fault coverage. The important class of dynamic faults, therefore, cannot be ignored any more. It is shown that conventional memory tests constructed to detect static faulty behavior of a specific defect do not necessarily detect the dynamic faulty behavior. Indeed, dynamic faulty behavior can take place in the absence of static faults. The paper presents new memory tests derived to target the dynamic fault class.

This paper shows the shortcomings of the current, generic notation for fault models and extends it to allow the description of fault models for DRAMs. The advantage is that the extended fault models can easily be translated into operation sequences and tests that detect the described fault. Examples are given to show that the new notation results in optimized, memory specific, tests that have a shorter run time for a given fault coverage.

Fault analysis of memory devices using defect injection and simulation is becoming increasingly important as the complexity of memory faulty behavior increases. In this paper this approach is used to study the effects of opens and shorts on the faulty behavior of embedded DRAM (eDRAM) devices produced by Infineon Technologies. The analysis shows the existence of previously defined memory fault models, and establishes new ones. The paper also investigates the concept of dynamic faulty behavior and establishes its importance for memory devices. Conditions to test the newly established fault models are also given.

Temperature has proven to be an effective stress condition, commonly used to stress memory devices and to detect special types of failure mechanisms. In this paper a new approach is presented where temperature is used as a test parameter to increase the fault coverage of specific tests. This is done using defect injection and simulation of a memory model at different temperatures. The analysis presents new types of detection conditions for memories and evaluates the impact of temperature on these conditions.

Establishing functional faults, based on defect injection and circuit simulation, has become an important method in understanding faulty memory behavior and in improving memory tests. In this paper this approach is used to study the effects of bridges on the faulty behavior of embedded DRAM (eDRAM) devices. The paper applies the new approach of fault primitives to perform this analysis. The analysis shows the existence of previously defined memory fault models, and (re)establishes new ones. The paper also investigates the concept of dynamic faulty behavior and establishes its importance for memory devices.

This paper presents a notation for describing functional fault models, which may occur in memory devices. Using this notation, the space of all possible memory faults has been constructed. It has been shown that this space is infinite, and contains the currently established fault models. New fault models in this space have been identified and verified using resistive and capacitive defect injection and simulation of a DRAM model.