GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing

Ernst Houtgast; Vlad Sima; Koen Bertels; Zaid Al-Ars

doi:10.1007/978-3-319-30695-7_10

GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing

Ernst Houtgast, Vlad Sima, Koen Bertels, Zaid Al-Ars

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

17 Citations (Scopus)

Abstract

Genomic sequencing is rapidly becoming a premier generator of Big Data, posing great computational challenges. Hence, acceleration of the algorithms used is of utmost importance. This paper presents a GPU-accelerated implementation of BWA-MEM, a widely used algorithm to map genomic sequences onto a reference genome. BWA-MEM contains three main computational functions: Seed Generation, Seed Extension and Output Generation. This paper discusses acceleration of the Seed Extension function on a GPU accelerator.
The GPU-based Extend kernel achieves three times higher performance and, by offloading the kernel onto an accelerator and overlapping its execution with the other functions, this results in an overall improvement to application-level execution time of up to 1.6x.
To ensure that using an accelerator always results in an overall performance improvement, especially when considering slower GPUs, an adaptive load balancing solution is introduced, which intelligently distributes work between host and GPU. This provides, compared to not using load balancing, up to +46 % more performance.

Original language	English
Title of host publication	Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016
Editors	Frank Hannig, João M. P. Cardoso, Thilo Pionteck, Dietmar Fey, Wolfgang Schröder-Preikschat, Jürgen Teich
Publisher	Springer
Pages	130-142
Number of pages	13
ISBN (Electronic)	978-3-319-30695-7
ISBN (Print)	978-3-319-30694-0
DOIs	https://doi.org/10.1007/978-3-319-30695-7_10
Publication status	Published - 2016
Event	Architecture of Computing Systems, ARCS 2016: 29th International Conference - Nuremberg, Germany Duration: 4 Apr 2016 → 7 Apr 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9637

Conference

Conference	Architecture of Computing Systems, ARCS 2016
Country/Territory	Germany
City	Nuremberg
Period	4/04/16 → 7/04/16

Keywords

Acceleration
BWA-MEM
GPU
High performance genomics

Access to Document

10.1007/978-3-319-30695-7_10

Cite this

Houtgast, E., Sima, V., Bertels, K., & Al-Ars, Z. (2016). GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing. In F. Hannig, J. M. P. Cardoso, T. Pionteck, D. Fey, W. Schröder-Preikschat, & J. Teich (Eds.), Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016 (pp. 130-142). (Lecture Notes in Computer Science; Vol. 9637). Springer. https://doi.org/10.1007/978-3-319-30695-7_10

Houtgast, Ernst ; Sima, Vlad ; Bertels, Koen et al. / GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing. Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016. editor / Frank Hannig ; João M. P. Cardoso ; Thilo Pionteck ; Dietmar Fey ; Wolfgang Schröder-Preikschat ; Jürgen Teich . Springer, 2016. pp. 130-142 (Lecture Notes in Computer Science).

@inproceedings{9da44df16aab469b9773d0431b23cb3e,

title = "GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing",

abstract = "Genomic sequencing is rapidly becoming a premier generator of Big Data, posing great computational challenges. Hence, acceleration of the algorithms used is of utmost importance. This paper presents a GPU-accelerated implementation of BWA-MEM, a widely used algorithm to map genomic sequences onto a reference genome. BWA-MEM contains three main computational functions: Seed Generation, Seed Extension and Output Generation. This paper discusses acceleration of the Seed Extension function on a GPU accelerator.The GPU-based Extend kernel achieves three times higher performance and, by offloading the kernel onto an accelerator and overlapping its execution with the other functions, this results in an overall improvement to application-level execution time of up to 1.6x.To ensure that using an accelerator always results in an overall performance improvement, especially when considering slower GPUs, an adaptive load balancing solution is introduced, which intelligently distributes work between host and GPU. This provides, compared to not using load balancing, up to +46 % more performance.",

keywords = "Acceleration, BWA-MEM, GPU, High performance genomics",

author = "Ernst Houtgast and Vlad Sima and Koen Bertels and Zaid Al-Ars",

year = "2016",

doi = "10.1007/978-3-319-30695-7_10",

language = "English",

isbn = "978-3-319-30694-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "130--142",

editor = "Frank Hannig and Cardoso, {Jo{\~a}o M. P.} and Thilo Pionteck and Dietmar Fey and Wolfgang Schr{\"o}der-Preikschat and {Teich }, J{\"u}rgen",

booktitle = "Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016",

note = "Architecture of Computing Systems, ARCS 2016 : 29th International Conference ; Conference date: 04-04-2016 Through 07-04-2016",

}

Houtgast, E, Sima, V, Bertels, K & Al-Ars, Z 2016, GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing. in F Hannig, JMP Cardoso, T Pionteck, D Fey, W Schröder-Preikschat & J Teich (eds), Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016. Lecture Notes in Computer Science, vol. 9637, Springer, pp. 130-142, Architecture of Computing Systems, ARCS 2016, Nuremberg, Germany, 4/04/16. https://doi.org/10.1007/978-3-319-30695-7_10

GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing. / Houtgast, Ernst; Sima, Vlad; Bertels, Koen et al.
Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016. ed. / Frank Hannig; João M. P. Cardoso; Thilo Pionteck; Dietmar Fey; Wolfgang Schröder-Preikschat; Jürgen Teich . Springer, 2016. p. 130-142 (Lecture Notes in Computer Science; Vol. 9637).

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

TY - GEN

T1 - GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing

AU - Houtgast, Ernst

AU - Sima, Vlad

AU - Bertels, Koen

AU - Al-Ars, Zaid

PY - 2016

Y1 - 2016

N2 - Genomic sequencing is rapidly becoming a premier generator of Big Data, posing great computational challenges. Hence, acceleration of the algorithms used is of utmost importance. This paper presents a GPU-accelerated implementation of BWA-MEM, a widely used algorithm to map genomic sequences onto a reference genome. BWA-MEM contains three main computational functions: Seed Generation, Seed Extension and Output Generation. This paper discusses acceleration of the Seed Extension function on a GPU accelerator.The GPU-based Extend kernel achieves three times higher performance and, by offloading the kernel onto an accelerator and overlapping its execution with the other functions, this results in an overall improvement to application-level execution time of up to 1.6x.To ensure that using an accelerator always results in an overall performance improvement, especially when considering slower GPUs, an adaptive load balancing solution is introduced, which intelligently distributes work between host and GPU. This provides, compared to not using load balancing, up to +46 % more performance.

AB - Genomic sequencing is rapidly becoming a premier generator of Big Data, posing great computational challenges. Hence, acceleration of the algorithms used is of utmost importance. This paper presents a GPU-accelerated implementation of BWA-MEM, a widely used algorithm to map genomic sequences onto a reference genome. BWA-MEM contains three main computational functions: Seed Generation, Seed Extension and Output Generation. This paper discusses acceleration of the Seed Extension function on a GPU accelerator.The GPU-based Extend kernel achieves three times higher performance and, by offloading the kernel onto an accelerator and overlapping its execution with the other functions, this results in an overall improvement to application-level execution time of up to 1.6x.To ensure that using an accelerator always results in an overall performance improvement, especially when considering slower GPUs, an adaptive load balancing solution is introduced, which intelligently distributes work between host and GPU. This provides, compared to not using load balancing, up to +46 % more performance.

KW - Acceleration

KW - BWA-MEM

KW - GPU

KW - High performance genomics

U2 - 10.1007/978-3-319-30695-7_10

DO - 10.1007/978-3-319-30695-7_10

M3 - Conference contribution

SN - 978-3-319-30694-0

T3 - Lecture Notes in Computer Science

SP - 130

EP - 142

BT - Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016

A2 - Hannig, Frank

A2 - Cardoso, João M. P.

A2 - Pionteck, Thilo

A2 - Fey, Dietmar

A2 - Schröder-Preikschat, Wolfgang

A2 - Teich , Jürgen

PB - Springer

T2 - Architecture of Computing Systems, ARCS 2016

Y2 - 4 April 2016 through 7 April 2016

ER -

Houtgast E, Sima V, Bertels K, Al-Ars Z. GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing. In Hannig F, Cardoso JMP, Pionteck T, Fey D, Schröder-Preikschat W, Teich J, editors, Proceedings - 29th International Conference on Architecture of Computing Systems, ARCS 2016. Springer. 2016. p. 130-142. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-30695-7_10

GPU-Accelerated BWA-MEM Genomic Mapping Algorithm Using Adaptive Load Balancing

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this