{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97496"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97496","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Hardware acceleration of the pair HMM algorithm for DNA variant calling","abstract":"Made available in DSpace on 2017-08-10T19:16:15Z (GMT). No. of bitstreams: 2 HUANG-THESIS-2017.pdf: 3198752 bytes, checksum: 355bc51ce749cb631e269cc6116f3c3f (MD5) LICENSE.txt: 4208 bytes, checksum: 29aa487d1a5b8c7beed523d9c3a35801 (MD5) Previous issue date: 2017-04-26","abstract_html":"Made available in DSpace on 2017-08-10T19:16:15Z (GMT). No. of bitstreams: 2 HUANG-THESIS-2017.pdf: 3198752 bytes, checksum: 355bc51ce749cb631e269cc6116f3c3f (MD5) LICENSE.txt: 4208 bytes, checksum: 29aa487d1a5b8c7beed523d9c3a35801 (MD5) Previous issue date: 2017-04-26","abstract_has_math":false,"creators":["Huang, Sitao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Chen, Deming","Hwu, Wen-Mei M"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:16:15Z","date_published":"2017-08-10T19:16:15Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Hardware acceleration","Field-programmable gate array (FPGA)","Forward algorithm","Pair hidden Markov model (HMM)","Computational genomics","Processing element (PE) ring"],"languages":["en"],"rights":["Copyright 2017 Sitao Huang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97496","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chen, Deming","Hwu, Wen-Mei M"]},{"key":"dc:creator","label":"Author","values":["Huang, Sitao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:16:15Z","2017-04-26","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Hardware acceleration","Field-programmable gate array (FPGA)","Forward algorithm","Pair hidden Markov model (HMM)","Computational genomics","Processing element (PE) ring"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Sitao Huang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97496"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Made available in DSpace on 2017-08-10T19:16:15Z (GMT). No. of bitstreams: 2 HUANG-THESIS-2017.pdf: 3198752 bytes, checksum: 355bc51ce749cb631e269cc6116f3c3f (MD5) LICENSE.txt: 4208 bytes, checksum: 29aa487d1a5b8c7beed523d9c3a35801 (MD5) Previous issue date: 2017-04-26","With the advent of several accurate and sophisticated statistical algorithms and pipelines for DNA sequence analysis, it is becoming increasingly possible to translate raw sequencing data into biologically meaningful information for further clinical analysis and processing. However, given the large volume of the data involved, even modestly complex algorithms would require a prohibitively long time to complete. Hence it is urgent to explore non-conventional implementation platforms to accelerate genomics research. In this thesis, we present a Field-Programmable Gate Array (FPGA) accelerated implementation of the Pair Hidden Markov Model (Pair HMM) forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular Genome Analysis Toolkit (GATK) variant calling tool. We introduce the PE ring structure which, thanks to the fine-grained parallelism allowed by the FPGA, can be built into various configurations striking a trade-off between Instruction-Level Parallelism (ILP) and data parallelism. We investigate the resource utilization and performance of different configurations. Our solution can achieve a speed-up of up to 487x compared to the C++ baseline implementation on CPU and 1.56x compared to the previous best hardware implementation.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Sitao Huang, accepted the attached license on 2017-04-26 at 15:18.","The student, Sitao Huang, submitted this Thesis for approval on 2017-04-26 at 15:33.","This Thesis was approved for publication on 2017-04-26 at 18:18.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11094 on 2017-08-10 at 13:46:42"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Hardware acceleration of the pair HMM algorithm for DNA variant calling"]}]}],"canonical_facts":{"dc:contributor":["Chen, Deming","Hwu, Wen-Mei M"],"dc:creator":["Huang, Sitao"],"dc:date":["2017-08-10T19:16:15Z","2017-04-26","2017-05"],"dc:description":["Made available in DSpace on 2017-08-10T19:16:15Z (GMT). No. of bitstreams: 2 HUANG-THESIS-2017.pdf: 3198752 bytes, checksum: 355bc51ce749cb631e269cc6116f3c3f (MD5) LICENSE.txt: 4208 bytes, checksum: 29aa487d1a5b8c7beed523d9c3a35801 (MD5) Previous issue date: 2017-04-26","With the advent of several accurate and sophisticated statistical algorithms and pipelines for DNA sequence analysis, it is becoming increasingly possible to translate raw sequencing data into biologically meaningful information for further clinical analysis and processing. However, given the large volume of the data involved, even modestly complex algorithms would require a prohibitively long time to complete. Hence it is urgent to explore non-conventional implementation platforms to accelerate genomics research. In this thesis, we present a Field-Programmable Gate Array (FPGA) accelerated implementation of the Pair Hidden Markov Model (Pair HMM) forward algorithm, the performance bottleneck in the HaplotypeCaller, a critical function in the popular Genome Analysis Toolkit (GATK) variant calling tool. We introduce the PE ring structure which, thanks to the fine-grained parallelism allowed by the FPGA, can be built into various configurations striking a trade-off between Instruction-Level Parallelism (ILP) and data parallelism. We investigate the resource utilization and performance of different configurations. Our solution can achieve a speed-up of up to 487x compared to the C++ baseline implementation on CPU and 1.56x compared to the previous best hardware implementation.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Sitao Huang, accepted the attached license on 2017-04-26 at 15:18.","The student, Sitao Huang, submitted this Thesis for approval on 2017-04-26 at 15:33.","This Thesis was approved for publication on 2017-04-26 at 18:18.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11094 on 2017-08-10 at 13:46:42"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97496"],"dc:language":["en"],"dc:rights":["Copyright 2017 Sitao Huang"],"dc:subject":["Hardware acceleration","Field-programmable gate array (FPGA)","Forward algorithm","Pair hidden Markov model (HMM)","Computational genomics","Processing element (PE) ring"],"dc:title":["Hardware acceleration of the pair HMM algorithm for DNA variant calling"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:34Z"}