PANDA: Processing in Magnetic Random-Access Memory-Accelerated de Bruijn Graph-Based DNA Assembly

Shaahin Angizi, Naima Ahmed Fahmi, Deniz Najafi, Wei Zhang, Deliang FanJournal of Low Power Electronics and Applications 2024 · DOI

TL;DR

This paper introduces PANDA, a novel processing-in-memory (PIM) platform that leverages SOT-MRAM to accelerate DNA genome assembly. By performing key computations directly within the memory, PANDA significantly reduces data movement, leading to substantial improvements in speed and energy efficiency compared to traditional CPU-based approaches.

What Problem Does This Paper Address?

The rapid advancement of high-throughput sequencing technologies has generated massive amounts of genomic data. Assembling this data into complete genomes is a computationally intensive and time-consuming process, often bottlenecked by the constant movement of data between the CPU and memory. Traditional von Neumann architectures struggle with this "memory wall" challenge, leading to high energy consumption and slow processing times. While PIM architectures offer a promising solution by bringing computation closer to data, existing PIM solutions often face limitations in performing complex logic operations efficiently, particularly the bit-wise X(N)OR operations crucial for DNA assembly. This paper addresses the need for a PIM architecture specifically optimized for the computational demands of de novo genome assembly, focusing on efficient execution of these critical operations.

Methods

The core of PANDA is its innovative use of Spin-Orbit Torque Magnetic Random-Access Memory (SOT-MRAM) as both storage and processing units. The authors designed a PANDA platform that exploits MRAM's inherent capabilities to perform bulk bit-wise X(N)OR comparison and addition operations, essential for genome assembly. This is achieved through a reconfigurable sense amplifier (SA) capable of executing a full set of 2- and 3-input logic operations directly within the MRAM chip.

To effectively utilize this hardware, PANDA employs a custom, hardware-friendly DNA assembly algorithm. This algorithm is broken down into three main stages: k-mer hashing, de Bruijn graph construction, and graph traversal for contig generation. A key innovation is the proposed data partitioning and mapping technique, which ensures local storage and processing, maximizing parallelism at the algorithm level. This approach avoids the need to move large intermediate datasets, a common bottleneck in traditional systems.

Datasets

The paper does not explicitly mention training datasets. For evaluation, they generated 60,952 short reads from a Trinity sample genome bank with 519,771 unique k-mers. This dataset was used to test the PANDA platform across different k-mer lengths (k=22, 25, 27, 32).

Key Insights and Ideas

  • MRAM as a Compute Engine: The paper demonstrates that MRAM, beyond its memory capabilities, can be effectively repurposed as a powerful processing unit for computationally intensive tasks like DNA assembly.
  • Efficient X(N)OR Operations: By designing specialized logic within the SOT-MRAM sense amplifiers, PANDA overcomes a significant hurdle in PIM architectures: the efficient execution of bit-wise X(N)OR operations, which are fundamental to genome assembly.
  • Data Partitioning for Parallelism: The novel data partitioning and mapping strategy is crucial for unlocking the full potential of PIM. It ensures that data is organized for local processing, maximizing the inherent parallelism of the PANDA architecture.
  • Holistic Cross-Layer Optimization: PANDA's success stems from a co-design approach, integrating hardware (SOT-MRAM, reconfigurable SA), algorithm (hardware-friendly DNA assembly), and data management (partitioning and mapping) to achieve significant performance gains.

Key Results

  • Significant Speedup: PANDA reduces DNA assembly run time by approximately 18x compared to a CPU.
  • Dramatic Power Reduction: The platform achieves an 11x reduction in power consumption compared to the CPU.
  • Competitive PIM Performance: PANDA offers speed-ups of up to 2.5x to 10x compared to other recent processing-in-memory platforms like STT-MRAM, ReRAM, and DRAM for similar tasks.
  • Reduced Memory Bottleneck: The Memory Bottleneck Ratio (MBR) for PANDA is significantly lower (~17%) compared to the CPU (~65%), indicating much less time spent on data transfer.
  • High Resource Utilization: PANDA achieves a high Resource Utilization Ratio (RUR) of up to ~82%, demonstrating efficient use of its computational resources.

Limitations and Future Work

  • Area Overhead: The PANDA platform incurs an area overhead of approximately 7.9% compared to a standard MRAM die, primarily due to the controller, drivers, and SA modifications.
  • Reliability Considerations: While the paper discusses reliability and sense margin improvements through increased oxide thickness or sense current, it acknowledges that these can impact power consumption.
  • Future Work: The authors suggest several avenues for future research:
  • Exploring other innovative PIM platforms to further enhance speed in different DNA assembly phases.
  • Developing new hardware mapping and processing techniques to minimize overhead from intermediate result write-backs.
  • Introducing algorithmic innovations in graph construction to further boost accelerator performance.
  • Augmenting PANDA with reliability guarantees, such as ECC techniques, for enhanced data integrity.

Summary updated

Abstract

In this work, we present an efficient Processing in MRAM-Accelerated De Bruijn Graph-based DNA Assembly platform, named PANDA, based on an optimized and hardware-friendly genome assembly algorithm. PANDA is able to assemble large-scale DNA sequence datasets from all-pair overlaps. We first design a PANDA platform that exploits MRAM as computational memory and converts it to a potent processing unit for genome assembly. PANDA can not only execute efficient bulk bit-wise X(N)OR-based comparison/addition operations heavily required for the genome assembly task but also a full set of 2-/3-input logic operations inside the MRAM chip. We then develop a highly parallel and step-by-step hardware-friendly DNA assembly algorithm for PANDA that only requires the developed in-memory logic operations. The platform is then configured with a novel data partitioning and mapping technique that provides local storage and processing to utilize the algorithm level’s parallelism fully. The cross-layer simulation results demonstrate that PANDA reduces the run time and power by a factor of 18 and 11, respectively, compared with CPU. Moreover, speed-ups of up to 2.5 to 10× can be obtained over other recent processing in-memory platforms to perform the same task, like STT-MRAM, ReRAM, and DRAM.
BibTeX
@article{angizi2024panda,
  author = {Shaahin Angizi and Naima Ahmed Fahmi and Deniz Najafi and Wei Zhang and Deliang Fan},
  title = {{PANDA: Processing in Magnetic Random-Access Memory-Accelerated de Bruijn Graph-Based DNA Assembly}},
  journal = {Journal of Low Power Electronics and Applications},
  year = {2024},
  doi = {10.3390/jlpea14010009},
}
Figure