請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96166完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 楊佳玲 | zh_TW |
| dc.contributor.advisor | Chia-Lin Yang | en |
| dc.contributor.author | 蔡名翔 | zh_TW |
| dc.contributor.author | Ming-Hsiang Tsai | en |
| dc.date.accessioned | 2024-11-19T16:07:24Z | - |
| dc.date.available | 2024-11-20 | - |
| dc.date.copyright | 2024-11-19 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-10-15 | - |
| dc.identifier.citation | M. Aldridge, L. Baldassini, and O. Johnson. Group testing algorithms: Bounds and simulations. IEEE Transactions on Information Theory, 60(6):3671–3687, 2014.
S. Andrews et al. Fastqc: a quality control tool for high throughput sequence data, 2010. S. Angizi, J. Sun, W. Zhang, and D. Fan. Aligns: A processing-in-memory accelerator for dna short read alignment leveraging sot-mram. In Proceedings of the 56th Annual Design Automation Conference 2019, pages 1–6, 2019. T. Batu, F. Ergun, and C. Sahinalp. Oblivious string embeddings and edit distance approximations. In SODA, volume 6, pages 792–801, 2006. Z. Bingöl, M. Alser, O. Mutlu, O. Ozturk, and C. Alkan. Gatekeeper-gpu: Fast and accurate pre-alignment filtering in short read mapping. IEEE Transactions on Computers, 2024. A. M. Bolger, M. Lohse, and B. Usadel. Trimmomatic: a flexible trimmer for illumina sequence data. Bioinformatics, 30(15):2114–2120, 2014. D. S. Cali, G. S. Kalsi, Z. Bingöl, C. Firtina, L. Subramanian, J. S. Kim, R. Ausavarungnirun, M. Alser, J. Gomez-Luna, A. Boroumand, et al. Genasm: A high-performance, low-power approximate string matching acceleration framework for genome sequence analysis. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 951–966. IEEE, 2020. D. S. Cali, K. Kanellopoulos, J. Lindegger, Z. Bingöl, G. S. Kalsi, Z. Zuo, C. Firtina, M. B. Cavlak, J. Kim, N. M. Ghiasi, et al. Segram: A universal hardware accelerator for genomic sequence-to-graph and sequence-to-sequence mapping. In Proceedings of the 49th Annual International Symposium on Computer Architecture, pages 638–655, 2022. D. Chakraborty, D. Das, E. Goldenberg, M. Kouckỳ, and M. Saks. Approximating edit distance within constant factor in truly sub-quadratic time. Journal of the ACM (JACM), 67(6):1–22, 2020. M. Charikar, O. Geri, M. P. Kim, and W. Kuszmaul. On estimating edit distance: Alignment, dimension reduction, and embeddings. arXiv preprint arXiv:1804.09907, 2018. F. Chen, L. Song, Y. Chen, et al. Parc: A processing-in-cam architecture for genomic long read pairwise alignment using reram. In 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), pages 175–180. IEEE, 2020. L. Chen, J. Zhu, G. Peng, M. Liu, S. Wei, and L. Liu. Gem: Ultra-efficient near-memory reconfigurable acceleration for read mapping by dividing and predictive scattering. IEEE Transactions on Parallel and Distributed Systems, 2023. P. Chen, C. Wang, X. Li, and X. Zhou. Accelerating the next generation long read mapping with the fpga-based system. IEEE/ACM transactions on computational biology and bioinformatics, 11(5):840–852, 2014. J. Choe. Memory technology 2021: Trends & challenges. In 2021 international conference on simulation of semiconductor processes and devices (SISPAD), pages 111–115. IEEE, 2021. G. P. Consortium, A. Auton, L. Brooks, R. Durbin, E. Garrison, and H. Kang. A global reference for human genetic variation. Nature, 526(7571):68–74, 2015. A. T. Do, Z. C. Lee, B. Wang, I.-J. Chang, X. Liu, and T. T.-H. Kim. 0.2 v 8t sram with pvt-aware bitline sensing and column-based data randomization. IEEE Journal of Solid-State Circuits, 51(6):1487–1498, 2016. M. Doblas, O. Lostes-Cazorla, Q. Aguado-Puig, N. Cebry, P. Fontova-Musté, C. F. Batten, S. Marco-Sola, and M. Moretó. Gmx: Instruction set extensions for fast, scalable, and efficient genome sequence alignment. In Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture, pages 1466– 1480, 2023. D. L. Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289–1306, 2006. R. Edgar. Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences. PeerJ, 9:e10805, 2021. C. Firtina, J. Park, M. Alser, J. S. Kim, D. S. Cali, T. Shahroodi, N. M. Ghiasi, G. Singh, K. Kanellopoulos, C. Alkan, et al. Blend: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis. NAR Genomics and Bioinformatics, 5(1):lqad004, 2023. D. Fujiki, A. Subramaniyan, T. Zhang, Y. Zeng, R. Das, D. Blaauw, and S. Narayanasamy. Genax: A genome sequencing accelerator. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pages 69–82. IEEE, 2018. D. Fujiki, S. Wu, N. Ozog, K. Goliya, D. Blaauw, S. Narayanasamy, and R. Das. Seedex: A genome sequencing accelerator for optimal alignments in sub-minimal space. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 937–950. IEEE, 2020. E. Garrison and G. Marth. Haplotype-based variant detection from short-read sequencing. arXiv preprint arXiv:1207.3907, 2012. N. M. Ghiasi, J. Park, H. Mustafa, J. Kim, A. Olgun, A. Gollwitzer, D. S. Cal, C. Firtina, H. Mao, N. A. Alserr, et al. Genstore: A high-performance and energy-efficient in-storage computing system for genome sequence analysis. arXiv preprint arXiv:2202.10400, 2022. S. group Ciampi Antonio 8 Greenwood Celia MT (co-chair) 7 8 14 19 Hendricks Audrey E. 1 12 Li Rui 7 13 14 Metrustry Sarah 5 Oualkacha Karim 80 Tachmazidou Ioanna 1 Xu ChangJiang 7 8 Zeggini Eleftheria (co-chair) 1 et al. The uk10k project identifies rare variants in health and disease. Nature, 526(7571):82–90, 2015. Y. Gu, A. Subramaniyan, T. Dunn, A. Khadem, K.-Y. Chen, S. Paul, M. Vasimuddin, S. Misra, D. Blaauw, S. Narayanasamy, et al. Gendp: A framework of dynamic programming acceleration for genome sequencing analysis. In Proceedings of the 50th Annual International Symposium on Computer Architecture, pages 1–15, 2023. F. Hach, I. Sarrafi, F. Hormozdiari, C. Alkan, E. E. Eichler, and S. C. Sahinalp. mrsfast-ultra: a compact, snp-aware mapper for high performance sequencing applications. Nucleic acids research, 42(W1):W494–W500, 2014. D. Ho, J. Ding, S. Misra, N. Tatbul, V. Nathan, V. Md, and T. Kraska. Lisa: towards learned dna sequence search. arXiv preprint arXiv:1910.04728, 2019. Y. Huang, L. Kong, D. Chen, Z. Chen, X. Kong, J. Zhu, K. Mamouras, S. Wei, K. Yang, and L. Liu. Casa: An energy-efficient and high-speed cam-based smem seeding accelerator for genome alignment. In Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture, pages 1423–1436, 2023. W. Huangfu, S. Li, X. Hu, and Y. Xie. Radar: A 3d-reram based dna alignment accelerator architecture. In Proceedings of the 55th Annual Design Automation Conference, pages 1–6, 2018. W. Huangfu, X. Li, S. Li, X. Hu, P. Gu, and Y. Xie. Medal: Scalable dimm based near data processing accelerator for dna seeding algorithm. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 587–599, 2019. M. Jung, J. Zhang, A. Abulila, M. Kwon, N. Shahidi, J. Shalf, N. S. Kim, and M. Kandemir. Simplessd: Modeling solid state drives for holistic system simulation. IEEE Computer Architecture Letters, 17(1):37–41, 2017. S. K. Khatamifard, Z. Chowdhury, N. Pande, M. Razaviyayn, C. Kim, and U. R. Karpuzcu. Genvom: Read mapping near non-volatile memory. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(6):3482–3496, 2021. J. S. Kim, D. Senol Cali, H. Xin, D. Lee, S. Ghose, M. Alser, H. Hassan, O. Ergin, C. Alkan, and O. Mutlu. Grim-filter: Fast seed location filtering in dna read mapping using processing-in-memory technologies. BMC genomics, 19:23–40, 2018. D. C. Koboldt, Q. Zhang, D. E. Larson, D. Shen, M. D. McLellan, L. Lin, C. A. Miller, E. R. Mardis, L. Ding, and R. K. Wilson. Varscan 2: somatic mutation and copy number alteration discovery in cancer by exome sequencing. Genome research, 22(3):568–576, 2012. R. Langarita, A. Armejach, J. Setoain, P. Ibanez-Marin, J. Alastruey-Benedé, and M. Moretó. Compressed sparse fm-index: Fast sequence alignment using large k-steps. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(1):355–368, 2020. B. Langmead and S. L. Salzberg. Fast gapped-read alignment with bowtie 2. Nature methods, 9(4):357–359, 2012. H. Lee, M. Kim, D. Min, J. Kim, J. Back, H. Yoo, J.-H. Lee, and J. Kim. 3d-fpim: An extreme energy-efficient dnn acceleration system using 3d nand flash-based in-situ pim unit. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 1359–1376. IEEE, 2022. H. Li. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics, 34(18):3094–3100, 2018. H. Li and R. Durbin. Fast and accurate short read alignment with burrows–wheeler transform. bioinformatics, 25(14):1754–1760, 2009. E. R. Mardis. The impact of next-generation sequencing technology on genetics. Trends in Genetics, 24(3):133–141, 2008. A. McKenna, M. Hanna, E. Banks, A. Sivachenko, K. Cibulskis, A. Kernytsky, K. Garimella, D. Altshuler, S. Gabriel, M. Daly, et al. The genome analysis toolkit: a mapreduce framework for analyzing next-generation dna sequencing data. Genome research, 20(9):1297–1303, 2010. Micro. Mt40a1g8, 2016. July, 2024. A. Nag, C. Ramachandra, R. Balasubramonian, R. Stutsman, E. Giacomin, H. Kambalasubramanyam, and P.-E. Gaillardon. Gencache: Leveraging in-cache operators for efficient sequence alignment. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 334–346, 2019. S. B. Ng, K. J. Buckingham, C. Lee, A. W. Bigham, H. K. Tabor, K. M. Dent, C. D. Huff, P. T. Shannon, E. W. Jabs, D. A. Nickerson, et al. Exome sequencing identifies the cause of a mendelian disorder. Nature genetics, 42(1):30–35, 2010. Phison. Ps5019-e19t, 2020. July, 2024. R. Poplin, P.-C. Chang, D. Alexander, S. Schwartz, T. Colthurst, A. Ku, D. New- burger, J. Dijamco, N. Nguyen, P. T. Afshar, et al. A universal snp and small-indel variant caller using deep neural networks. Nature biotechnology, 36(10):983–987, 2018. E. Price and J. Scarlett. A fast binary splitting approach to non-adaptive group testing. arXiv preprint arXiv:2006.10268, 2020. R. Ramanarayanan, S. Mathew, F. Sheikh, S. Srinivasan, A. Agarwal, S. Hsu, H. Kaul, M. Anders, V. Erraguntla, and R. Krishnamurthy. 18gbps, 50mw reconfigurable multi-mode sha hashing accelerator in 45nm cmos. In 2010 Proceedings of ESSCIRC, pages 210–213. IEEE, 2010. G. Rizk and D. Lavenier. Gassst: global alignment short sequence search tool. Bioinformatics, 26(20):2534–2540, 2010. A. Shafiee, A. Nag, N. Muralimanohar, R. Balasubramonian, J. P. Strachan, M. Hu, R. S. Williams, and V. Srikumar. Isaac: A convolutional neural network accelerator with in-situ analog arithmetic in crossbars. ACM SIGARCH Computer Architecture News, 44(3):14–26, 2016. A. B. Singleton. Exome sequencing: a transformative technology. The Lancet Neurology, 10(10):942–946, 2011. M. Šošić and M. Šikić. Edlib: a c/c++ library for fast, exact sequence alignment using edit distance. Bioinformatics, 33(9):1394–1395, 2017. J. E. Soto, C. Hernández, and M. Figueroa. Jacc-fpga: A hardware accelerator for jaccard similarity estimation using fpgas in the cloud. Future Generation Computer Systems, 138:26–42, 2023. G. Stracquadanio, K. Yang, J. D. Boeke, and J. S. Bader. Biopartsdb: a synthetic biology workflow web-application for education and research. Bioinformatics, 32(22):3519–3521, 2016. A. Subramaniyan, J. Wadden, K. Goliya, N. Ozog, X. Wu, S. Narayanasamy, D. Blaauw, and R. Das. Accelerated seeding for genome sequence alignment with enumerated radix trees. In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), pages 388–401. IEEE, 2021. P.-H. Tseng, S.-Y. Fang, Y.-H. Lin, F.-M. Lee, J.-Y. Liao, Y.-Y. Lin, M.-H. Lee, K.-Y. Hsieh, K.-C. Wang, and C.-Y. Lu. 3d-nand based filtering cube with high resolution 2d query and tunable feature length for computational ssd. In 2024 IEEE International Memory Workshop (IMW), pages 1–4. IEEE, 2024. P.-H. Tseng, F.-M. Lee, Y.-H. Lin, L.-Y. Chen, Y.-C. Li, H.-W. Hu, Y.-Y. Wang, C.-C. Hsieh, M.-H. Lee, H.-L. Lung, et al. In-memory-searching architecture based on 3d-nand technology with ultra-high parallelism. In 2020 IEEE International Electron Devices Meeting (IEDM), pages 36–1. IEEE, 2020. Y. Turakhia, G. Bejerano, and W. J. Dally. Darwin: A genomics co-processor provides up to 15,000 x acceleration on long read assembly. ACM SIGPLAN Notices, 53(2):199–213, 2018. M. Vasimuddin, S. Misra, H. Li, and S. Aluru. Efficient architecture-aware acceleration of bwa-mem for multicore systems. In 2019 IEEE international parallel and distributed processing symposium (IPDPS), pages 314–324. IEEE, 2019. R. Wilton and A. S. Szalay. Arioc: High-concurrency short-read alignment on multiple gpus. PLoS computational biology, 16(11):e1008383, 2020. F. Zokaee, H. R. Zarandi, and L. Jiang. Aligner: A process-in-memory architecture for short read alignment in rerams. IEEE Computer Architecture Letters, 17(2):237–240, 2018. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96166 | - |
| dc.description.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%。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-11-19T16:07:24Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-11-19T16:07:24Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements iii 摘要 v Abstract vii Contents ix List of Figures xiii List of Tables xv Chapter 1 Introduction 1 Chapter 2 Background 5 2.1 Genome Sequence Analysis 5 2.2 Accelerating Read Mapping 6 2.2.1 Exact Match Filter in GenStore Architecture 6 2.3 3D-NAND Based In-Memory-Search 9 2.4 Group Test 10 Chapter 3 Motivation 13 3.1 Read Overhead in the GenStore 13 3.2 Opportunity and Challenges 15 Chapter 4 Filtering Algorithm 17 4.1 Overall Filtering Pipeline 17 4.2 Exact Match Filter 18 4.2.1 Mapping to Group Testing 19 4.2.2 Adaptive Test Matrix and Decoder 20 4.2.3 Requirement of bloom filter 21 Chapter 5 Propose Design 25 5.1 Overview 25 5.2 Reference Index Build and Data Pre-process 26 5.2.1 Reference data 27 5.2.2 Data Placement of Reference Sequence 28 5.2.3 Read data 28 5.3 Implementation of Item Selection 28 5.4 Location Lookup 29 Chapter 6 Evaluation 31 6.1 Methodology 31 6.2 End-to-end Performance 34 6.3 Energy and Area Analysis 37 6.3.1 Energy Analysis 37 6.3.2 Power Breakdown 38 6.3.3 Area Breakdown 39 6.4 Design Trade-off of Bloom Filter Size 39 Chapter 7 Related Work 43 7.1 Accelerating Seeding 43 7.2 Accelerating Alignment 44 7.3 Accelerating Pre-alignment Filtering 45 Chapter 8 Conclusion 47 References 49 | - |
| dc.language.iso | en | - |
| dc.subject | 記憶體內運算 | zh_TW |
| dc.subject | 固態硬碟 | zh_TW |
| dc.subject | 序列比對 | zh_TW |
| dc.subject | 基因組學 | zh_TW |
| dc.subject | 三維快閃記憶體 | zh_TW |
| dc.subject | 記憶體內搜尋 | zh_TW |
| dc.subject | 群測試 | zh_TW |
| dc.subject | Group testing | en |
| dc.subject | Genomics | en |
| dc.subject | Read mapping | en |
| dc.subject | SSD | en |
| dc.subject | 3D NAND Flash | en |
| dc.subject | In-memory computing | en |
| dc.subject | In-memory search | en |
| dc.title | 基於三維快閃記憶體內運算結合群測試加速基因序列比對 | zh_TW |
| dc.title | Accelerating Genome Alignment Pipeline with In-NAND Search Technology and Group Testing Techniques | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 113-1 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 陳依蓉;鄭湘筠 | zh_TW |
| dc.contributor.oralexamcommittee | Yi-Jung Chen;Hsiang-Yun Cheng | en |
| dc.subject.keyword | 基因組學,序列比對,固態硬碟,三維快閃記憶體,記憶體內運算,記憶體內搜尋,群測試, | zh_TW |
| dc.subject.keyword | Genomics,Read mapping,SSD,3D NAND Flash,In-memory computing,In-memory search,Group testing, | en |
| dc.relation.page | 57 | - |
| dc.identifier.doi | 10.6342/NTU202404462 | - |
| dc.rights.note | 未授權 | - |
| dc.date.accepted | 2024-10-16 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電子工程學研究所 | - |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-113-1.pdf 未授權公開取用 | 2.83 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。