- 學位論文
基於 3D NAND 快閃記憶體近似字串比對架構之儲存內 DNA 序列比對系統
An In-Storage DNA Read Mapping System based on 3D-NAND Flash Approximate String Matching Architecture
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
目前，序列比對 (Read mapping) 是基因組序列分析的效能瓶頸之一，因為其需要進行複雜的近似字串比對演算法，以找出定序儀的讀取序列輸出 (即 reads) 和參考序列之間的潛在對齊位置。先前的研究表明，預對齊過濾 (pre-alignment filtering) 演算法透過過濾對齊分數較低的位置，能夠大幅減少複雜對齊算法的執行次數，並顯著提升序列比對的效能。考慮到預對齊過濾算法需要密集存取記憶體的特性，已經有許多基於記憶體內運算的處理架構被提出以提高該算法的效能。然而，我們發現將該計算架構與當前最先進的序列比對軟體 Minimap2 整合時，預對齊過濾的運算速度會顯著低於 Minimap2 的執行速度，使過濾延遲無法透過管線 (Pipeline) 化執行隱藏在 Minimap2 的執行時間中。這是由於在大多數情況下，每個讀取序列的潛在對齊位置數量遠小於記憶體內運算架構提供的運算平行度，大幅限制了預對齊過濾的效能。 在本篇論文中，我們提出一個基於 3D NAND flash 的儲存內預對齊過濾架構，以提高序列比對的效能。我們利用了讀取序列資料集中的序列深度特性，設計了一種新的以讀取序列為中心的預對齊過濾方法，能夠更好的利用底層硬體提供的運算平行度。然而，若將讀取序列為中心的過濾方法應用到先前在主機系統實現的記憶體內部運算架構時，還需要在 PCIe 通道間進行額外的資料搬移才能實現。因此，我們進行了軟硬體共同設計，使得該過濾方法能夠利用 3D NAND flash 的近似比對架構直接在儲存端內部實現預對齊過濾演算法，藉此減少大量的資料搬移。實驗結果顯示，在與目前最先進的記憶體內運算架構相比，我們提出的設計在過濾階段平均可以提升 42.69 倍的吞吐量，並且可以帶來 19.69% 的端到端效能提升。
並列摘要
Read mapping is currently the performance bottleneck of genome sequence analysis since it needs to perform costly approximate string matching to identify the potential matches between the sequencing output (i.e., reads) and an already-known reference genome sequence. Prior works have demonstrated that pre-alignment filtering, which filters out unnecessary mapping locations that will result in a poor match, can significantly improve the performance of read mapping. Considering the memory-intensive characteristic of pre-alignment filtering, processing-in-memory (PIM) designs have been proposed to improve the filtering throughput. However, we find that when integrating the PIM-based pre-alignment filter with the SOTA read mapper, Minimap2, the filtering latency overhead cannot be completely hidden as the filtering throughput lags behind the mapping throughput. The limited number of potential matching locations per read restricts the parallelism of pre-alignment filtering, even though the underlying PIM architecture enables highly parallel in-memory computing. In this work, we propose a 3D NAND flash-based in-storage pre-alignment filtering architecture to improve read mapping performance. To increase the filtering throughput, we exploit the read depth property present in most read datasets to design a new read-centric pre-alignment filtering approach. The read-centric design enables multiple reads to be filtered concurrently to better utilize the parallelism provided by the underlying hardware. Nevertheless, extra data movements across PCIe channels are required if it is implemented on the host memory side. Thus, we co-design the software and hardware to enable read-centric pre-alignment filtering to be in-situ processed in the storage, leveraging the approximate parallel search capability of 3D NAND Flash. The evaluation results show that the proposed design on average achieves 42.69x higher filtering throughput compared to the SOTA PIM solution and can provide up to 19.69% end-to-end performance improvement.
並列關鍵字
SSD ； In Storage Computing ； Computing-in-Memory ； 3D NAND Flash ； In Memory Search ； Read Mapping參考文獻
[1] G. S. Ginsburg and K. A. Phillips, “Precision Medicine: From Science To Value,” Health Affairs (Project Hope), vol. 37, no. 5, pp. 694–701, 2018.
[2] G. S. Ginsburg and H. F. Willard, “Genomic and personalized medicine: Foundations and applications,” Translational Research: The Journal of Laboratory and Clinical Medicine, vol. 154, no. 6, pp. 277–287, 2009.
[3] C. A. Gilchrist, S. D. Turner, M. F. Riley, W. A. Petri, and E. L. Hewlett, “Whole-genome sequencing in outbreak analysis,” Clinical Microbiology Reviews, vol. 28, no. 3, pp. 541–563, 2015.
[4] J. S. Bloom, L. Sathe, C. Munugala, E. M. Jones, M. Gasperini, N. B. Lubock, F. Yarza, E. M. Thompson, K. M. Kovary, J. Park, D. Marquette, S. Kay, M. Lucas, T. Love, A. Sina Booeshaghi, O. F. Brandenberg, L. Guo, J. Boocock, M. Hochman, S. W. Simpkins, I. Lin, N. LaPierre, D. Hong, Y. Zhang, G. Oland, B. J. Choe, S. Chandrasekaran, E. E. Hilt, M. J. Butte, R. Damoiseaux, C. Kravit, A. R. Cooper, Y. Yin, L. Pachter, O. B. Garner, J. Flint, E. Eskin, C. Luo, S. Kosuri, L. Kruglyak, and V. A. Arboleda, “Massively scaled-up testing for SARS-CoV-2 RNA via next-generation sequencing of pooled and barcoded nasal and saliva samples,” Nature Biomedical Engineering, vol. 5, no. 7, pp. 657–665, 2021.
[5] J. Gagan and E. M. Van Allen, “Next-generation sequencing to guide cancer therapy,” Genome Medicine, vol. 7, no. 1, p. 80, 2015.