Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm

Johan Peltenburg; Shanshan Ren; Zaid Al-Ars

doi:10.1109/BIBM.2016.7822616

Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm

Johan Peltenburg, Shanshan Ren, Zaid Al-Ars

Computer Engineering

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

17 Citations (Scopus)

Abstract

In the analysis of next-generation DNA sequencing data, Hidden Markov Models (HMMs) are used to perform variant calling between DNA sequences and a reference genome. The PairHMM model is solved by the Forward Algorithm, for which the performance and power efficiency can be increased tremendously using systolic arrays (SAs) in FPGAs. We model the performance characteristics of such SAs, and propose a novel architecture that allows the computational units to continuously perform useful work on the input data. The implementation achieves up to 90\% of the theoretical throughput for a real dataset. The implementation of the proposed architecture achieves more than 2.5x throughput over the state-of-the-art on a similar contemporary platform.

Original language	English
Title of host publication	Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)
Editors	Tianhai Tian, Qinghua Jiang, Yunlong Liu, Kevin Burrage, Jiangning Song, Yadong Wang, Xiaohua Hu, Shinichi Morishita, Qian Zhu, Guohua Wang
Place of Publication	Piscataway, NJ
Publisher	IEEE
Pages	758-762
Number of pages	5
ISBN (Electronic)	978-1-5090-1610-5
DOIs	https://doi.org/10.1109/BIBM.2016.7822616
Publication status	Published - Dec 2016
Event	IEEE International Conference on Bioinformatics and Biomedicine 2016 - Kylin Villa Hotel, Shenzhen, China Duration: 15 Dec 2016 → 18 Dec 2016 https://cci.drexel.edu/ieeebibm/bibm2016/

Conference

Conference	IEEE International Conference on Bioinformatics and Biomedicine 2016
Abbreviated title	BIBM 2016
Country/Territory	China
City	Shenzhen
Period	15/12/16 → 18/12/16
Internet address	https://cci.drexel.edu/ieeebibm/bibm2016/

Keywords

High-Throughput Sequencing
GATK
Haplotype-Caller
PairHMM
Systolic Array
FPGA

Access to Document

10.1109/BIBM.2016.7822616

17 Citations
1 Dissertation (TU Delft)

Methods for Efficient Integration of FPGA Accelerators with Big Data Systems
Peltenburg, J. W., 2020, 153 p.
Research output: Thesis › Dissertation (TU Delft)

Open Access
File
249 Downloads (Pure)

Cite this

Peltenburg, J., Ren, S., & Al-Ars, Z. (2016). Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm. In T. Tian, Q. Jiang, Y. Liu, K. Burrage, J. Song, Y. Wang, X. Hu, S. Morishita, Q. Zhu, & G. Wang (Eds.), Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM) (pp. 758-762). IEEE. https://doi.org/10.1109/BIBM.2016.7822616

Peltenburg, Johan ; Ren, Shanshan ; Al-Ars, Zaid. / Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm. Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). editor / Tianhai Tian ; Qinghua Jiang ; Yunlong Liu ; Kevin Burrage ; Jiangning Song ; Yadong Wang ; Xiaohua Hu ; Shinichi Morishita ; Qian Zhu ; Guohua Wang. Piscataway, NJ : IEEE, 2016. pp. 758-762

@inproceedings{3ffa623d1e7140f88e70a19ff2812f87,

title = "Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm",

abstract = "In the analysis of next-generation DNA sequencing data, Hidden Markov Models (HMMs) are used to perform variant calling between DNA sequences and a reference genome. The PairHMM model is solved by the Forward Algorithm, for which the performance and power efficiency can be increased tremendously using systolic arrays (SAs) in FPGAs. We model the performance characteristics of such SAs, and propose a novel architecture that allows the computational units to continuously perform useful work on the input data. The implementation achieves up to 90\% of the theoretical throughput for a real dataset. The implementation of the proposed architecture achieves more than 2.5x throughput over the state-of-the-art on a similar contemporary platform.",

keywords = "High-Throughput Sequencing, GATK, Haplotype-Caller, PairHMM, Systolic Array, FPGA",

author = "Johan Peltenburg and Shanshan Ren and Zaid Al-Ars",

year = "2016",

month = dec,

doi = "10.1109/BIBM.2016.7822616",

language = "English",

pages = "758--762",

editor = "Tianhai Tian and Qinghua Jiang and Yunlong Liu and Kevin Burrage and Jiangning Song and Yadong Wang and Xiaohua Hu and Shinichi Morishita and Qian Zhu and Guohua Wang",

booktitle = "Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)",

publisher = "IEEE",

address = "United States",

note = "IEEE International Conference on Bioinformatics and Biomedicine 2016, BIBM 2016 ; Conference date: 15-12-2016 Through 18-12-2016",

url = "https://cci.drexel.edu/ieeebibm/bibm2016/",

}

Peltenburg, J, Ren, S & Al-Ars, Z 2016, Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm. in T Tian, Q Jiang, Y Liu, K Burrage, J Song, Y Wang, X Hu, S Morishita, Q Zhu & G Wang (eds), Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, Piscataway, NJ, pp. 758-762, IEEE International Conference on Bioinformatics and Biomedicine 2016, Shenzhen, China, 15/12/16. https://doi.org/10.1109/BIBM.2016.7822616

Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm. / Peltenburg, Johan; Ren, Shanshan; Al-Ars, Zaid.
Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). ed. / Tianhai Tian; Qinghua Jiang; Yunlong Liu; Kevin Burrage; Jiangning Song; Yadong Wang; Xiaohua Hu; Shinichi Morishita; Qian Zhu; Guohua Wang. Piscataway, NJ: IEEE, 2016. p. 758-762.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm

AU - Peltenburg, Johan

AU - Ren, Shanshan

AU - Al-Ars, Zaid

PY - 2016/12

Y1 - 2016/12

N2 - In the analysis of next-generation DNA sequencing data, Hidden Markov Models (HMMs) are used to perform variant calling between DNA sequences and a reference genome. The PairHMM model is solved by the Forward Algorithm, for which the performance and power efficiency can be increased tremendously using systolic arrays (SAs) in FPGAs. We model the performance characteristics of such SAs, and propose a novel architecture that allows the computational units to continuously perform useful work on the input data. The implementation achieves up to 90\% of the theoretical throughput for a real dataset. The implementation of the proposed architecture achieves more than 2.5x throughput over the state-of-the-art on a similar contemporary platform.

AB - In the analysis of next-generation DNA sequencing data, Hidden Markov Models (HMMs) are used to perform variant calling between DNA sequences and a reference genome. The PairHMM model is solved by the Forward Algorithm, for which the performance and power efficiency can be increased tremendously using systolic arrays (SAs) in FPGAs. We model the performance characteristics of such SAs, and propose a novel architecture that allows the computational units to continuously perform useful work on the input data. The implementation achieves up to 90\% of the theoretical throughput for a real dataset. The implementation of the proposed architecture achieves more than 2.5x throughput over the state-of-the-art on a similar contemporary platform.

KW - High-Throughput Sequencing

KW - GATK

KW - Haplotype-Caller

KW - PairHMM

KW - Systolic Array

KW - FPGA

U2 - 10.1109/BIBM.2016.7822616

DO - 10.1109/BIBM.2016.7822616

M3 - Conference contribution

SP - 758

EP - 762

BT - Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)

A2 - Tian, Tianhai

A2 - Jiang, Qinghua

A2 - Liu, Yunlong

A2 - Burrage, Kevin

A2 - Song, Jiangning

A2 - Wang, Yadong

A2 - Hu, Xiaohua

A2 - Morishita, Shinichi

A2 - Zhu, Qian

A2 - Wang, Guohua

PB - IEEE

CY - Piscataway, NJ

T2 - IEEE International Conference on Bioinformatics and Biomedicine 2016

Y2 - 15 December 2016 through 18 December 2016

ER -

Peltenburg J, Ren S, Al-Ars Z. Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm. In Tian T, Jiang Q, Liu Y, Burrage K, Song J, Wang Y, Hu X, Morishita S, Zhu Q, Wang G, editors, Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). Piscataway, NJ: IEEE. 2016. p. 758-762 doi: 10.1109/BIBM.2016.7822616

Maximizing Systolic Array Efficiency to Accelerate the PairHMM Forward Algorithm

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output

Methods for Efficient Integration of FPGA Accelerators with Big Data Systems

Cite this