An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm

Ernst Houtgast; VM Sima; K Bertels; Z Al-Ars

doi:10.1109/SAMOS.2015.7363679

An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm

Ernst Houtgast, VM Sima, K Bertels, Z Al-Ars

Computer Engineering

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

36 Citations (Scopus)

113 Downloads (Pure)

Abstract

We present the first accelerated implementation of BWA-MEM, a popular genome sequence alignment algorithm widely used in next generation sequencing genomics pipelines. The Smith-Waterman-like sequence alignment kernel requires a significant portion of overall execution time. We propose and evaluate a number of FPGA-based systolic array architectures, presenting optimizations generally applicable to variable length Smith-Waterman execution. Our kernel implementation is up to 3x faster, compared to software-only execution. This translates into an overall application speedup of up to 45%, which is 96% of the theoretically maximum achievable speedup when accelerating only this kernel.

Original language	English
Title of host publication	Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV
Editors	D Soudris, L Carro
Place of Publication	Piscataway, NJ, USA
Publisher	IEEE Society
Pages	221-227
Number of pages	7
ISBN (Print)	978-1-4673-7311-1
DOIs	https://doi.org/10.1109/SAMOS.2015.7363679
Publication status	Published - 28 Dec 2015
Event	SAMOSXV, Samos, Greege - Piscataway Duration: 19 Jul 2015 → 23 Jul 2015

Publication series

Name
Publisher	IEEE

Conference

Conference	SAMOSXV, Samos, Greege
Period	19/07/15 → 23/07/15

Bibliographical note

Accepted Author Manuscript

Keywords

Kernel
Arrays
Acceleration
Field programmable gate arrays
Bioinformatics
Genomics

Access to Document

10.1109/SAMOS.2015.7363679

3210798Accepted author manuscript, 4.19 MB

Cite this

Houtgast, E., Sima, VM., Bertels, K., & Al-Ars, Z. (2015). An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm. In D. Soudris, & L. Carro (Eds.), Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV (pp. 221-227). IEEE Society. https://doi.org/10.1109/SAMOS.2015.7363679

@inproceedings{eab31b940c3d431585a73f888f97d70e,

title = "An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm",

abstract = "We present the first accelerated implementation of BWA-MEM, a popular genome sequence alignment algorithm widely used in next generation sequencing genomics pipelines. The Smith-Waterman-like sequence alignment kernel requires a significant portion of overall execution time. We propose and evaluate a number of FPGA-based systolic array architectures, presenting optimizations generally applicable to variable length Smith-Waterman execution. Our kernel implementation is up to 3x faster, compared to software-only execution. This translates into an overall application speedup of up to 45%, which is 96% of the theoretically maximum achievable speedup when accelerating only this kernel.",

keywords = "Kernel, Arrays, Acceleration, Field programmable gate arrays, Bioinformatics, Genomics",

author = "Ernst Houtgast and VM Sima and K Bertels and Z Al-Ars",

note = "Accepted Author Manuscript; SAMOSXV, Samos, Greege ; Conference date: 19-07-2015 Through 23-07-2015",

year = "2015",

month = dec,

day = "28",

doi = "10.1109/SAMOS.2015.7363679",

language = "English",

isbn = "978-1-4673-7311-1",

publisher = "IEEE Society",

pages = "221--227",

editor = "D Soudris and L Carro",

booktitle = "Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV",

}

Houtgast, E, Sima, VM, Bertels, K & Al-Ars, Z 2015, An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm. in D Soudris & L Carro (eds), Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV. IEEE Society, Piscataway, NJ, USA, pp. 221-227, SAMOSXV, Samos, Greege, 19/07/15. https://doi.org/10.1109/SAMOS.2015.7363679

An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm. / Houtgast, Ernst; Sima, VM; Bertels, K; Al-Ars, Z.

Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV. ed. / D Soudris; L Carro. Piscataway, NJ, USA : IEEE Society, 2015. p. 221-227.

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

TY - GEN

T1 - An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm

AU - Houtgast, Ernst

AU - Sima, VM

AU - Bertels, K

AU - Al-Ars, Z

N1 - Accepted Author Manuscript

PY - 2015/12/28

Y1 - 2015/12/28

N2 - We present the first accelerated implementation of BWA-MEM, a popular genome sequence alignment algorithm widely used in next generation sequencing genomics pipelines. The Smith-Waterman-like sequence alignment kernel requires a significant portion of overall execution time. We propose and evaluate a number of FPGA-based systolic array architectures, presenting optimizations generally applicable to variable length Smith-Waterman execution. Our kernel implementation is up to 3x faster, compared to software-only execution. This translates into an overall application speedup of up to 45%, which is 96% of the theoretically maximum achievable speedup when accelerating only this kernel.

AB - We present the first accelerated implementation of BWA-MEM, a popular genome sequence alignment algorithm widely used in next generation sequencing genomics pipelines. The Smith-Waterman-like sequence alignment kernel requires a significant portion of overall execution time. We propose and evaluate a number of FPGA-based systolic array architectures, presenting optimizations generally applicable to variable length Smith-Waterman execution. Our kernel implementation is up to 3x faster, compared to software-only execution. This translates into an overall application speedup of up to 45%, which is 96% of the theoretically maximum achievable speedup when accelerating only this kernel.

KW - Kernel

KW - Arrays

KW - Acceleration

KW - Field programmable gate arrays

KW - Bioinformatics

KW - Genomics

UR - http://resolver.tudelft.nl/uuid:eab31b94-0c3d-4315-85a7-3f888f97d70e

U2 - 10.1109/SAMOS.2015.7363679

DO - 10.1109/SAMOS.2015.7363679

M3 - Conference contribution

SN - 978-1-4673-7311-1

SP - 221

EP - 227

BT - Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV

A2 - Soudris, D

A2 - Carro, L

PB - IEEE Society

CY - Piscataway, NJ, USA

T2 - SAMOSXV, Samos, Greege

Y2 - 19 July 2015 through 23 July 2015

ER -

Houtgast E, Sima VM, Bertels K, Al-Ars Z. An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm. In Soudris D, Carro L, editors, Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS XV. Piscataway, NJ, USA: IEEE Society. 2015. p. 221-227 https://doi.org/10.1109/SAMOS.2015.7363679

An FPGA-based systolic array to accelerate the BWA-MEM genomic mapping algorithm

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this