基於三維快閃記憶體內運算結合群測試加速基因序列比對

Abstract

基因序列分析用以解析生物體的 DNA，為各種生物和醫學應用提供了關鍵的資訊。次世代測序（Next-Generation Sequencing, NGS）技術實現了高通量測序，但需要大量計算資源來將片段化序列重構為完整的序列。現有的解決方案如GenStore，通過使用 pre-seeding filters 消除與參考基因中完全相同的序列來加快基因比對速度，並利用了 SSD 內部的高頻寬以減少需經由 PCIe 的數據傳輸量。 然而，GenStore 因為需要將儲存於 NAND Flash 中的所有可能參考基因序列片段取出，從而產生性能瓶頸。為了解決這些問題，我們提出利用一種新型的計算型 3D NAND Flash，通過在記憶體中直接進行匹配檢測，從而消除了讀取參考序列的需求。為了應對三維快閃記憶體長的訪問時間以及同一 block 中共享 pagebuffer 的限制，我們採用了群測試技術來實現 block 級的並行處理。 本論文首次將群測試技術與三維快閃記憶體內搜尋技術相結合，協同群測試與複數 block 搜尋架構，以加速基因序列分析中的序列匹配過程。我們的方法相較於 GenStore 實現了 1.46 倍至 4.58 倍的加速，顯著減少了數據移動並提高了能效。將 bloom filter 與群測試技術結合，減少的試驗次數和數據移動量達到72%，從而實現了 1.06 倍至 2.6 倍的加速。我們探討了 bloom filter 大小與群測試試驗次數之間的關係，並展示其如何影響性能。評估結果顯示，我們的設計相比GenStore 提升了 66% 至 303% 的能效，而整體電路開銷僅增加 4.5%。

Genome sequence analysis decodes and interprets an organism's DNA, providing essential insights for various biological and medical applications. Next-Generation Sequencing (NGS) enables high-throughput sequencing but requires substantial computational effort to reconstruct fragmented reads into complete sequences. Existing solutions, such as GenStore, use pre-seeding filters to enhance mapping speed by eliminating reads identical to sequences in the reference genome, leveraging the high internal bandwidth of SSDs and reduce data transmission volume over PCIe. However, GenStore encounters performance bottlenecks due to the amplification of reference sequence loading, necessitating the generation, sorting, and storage of all possible mapped segments in the NAND Flash device. Our novel computational 3D NAND Flash device addresses these challenges by performing match detection directly within the memory, thereby eliminating the need to load reference sequences . To tackle the flash long access latency and shared page buffer constraints, we employ group testing to enable block-level parallelism. This thesis is the first to employ group testing with in-memory search technology to accelerate the exact match filter process, proposing a novel SSD architecture that synergizes group testing with multiple block access to enhance genomics sequence analysis. Our approach achieves a 1.46x to 4.58x speedup over GenStore, significantly reduces data movement, and increases energy efficiency. Integrating Bloom filters with on-die group testing reduces trial numbers and data movement by 72%, providing a 1.06x to 2.6x speedup. We explore the trade-offs between Bloom filter size and the number of trials in group testing, demonstrating how these trade-offs impacts the performance. Evaluations show that our design offers 66% to 303% higher energy efficiency than GenStore with only a 4.5% overall circuit overhead.