Efficient parallel UPGMA algorithm based on multiple GPUs

Che Lun Hung; Chun Yuan Lin; Fu Che Wu; Yu Wei Chan

doi:10.1109/BIBM.2016.7822640

Efficient parallel UPGMA algorithm based on multiple GPUs

Che Lun Hung, Chun Yuan Lin, Fu Che Wu, Yu Wei Chan

Institute of Biomedical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

A phylogenetic tree is used to present the evolutionary relationships among the interesting biological species based on the similarities in their genetic sequences. The UPGMA is one of the popular algorithms to construct a phylogenetic tree according to the distance matrix created by the pairwise distances among taxa. To solve the performance issue of the UPGMA, the implementation of the UPGMA method on a single GPU has been proposed. However, it is not capable of handling the large taxa set. This work describes a novel parallel UPGMA approach on multiple GPUs that is able to build a tree from extremely large datasets. The experimental results show that the proposed approach with 4 NVIDIA GTX 980 achieves an approximately × fold speedup over the implementation of UPGMA on CPU and GPU, respectively.

Original language	English
Title of host publication	Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016
Editors	Kevin Burrage, Qian Zhu, Yunlong Liu, Tianhai Tian, Yadong Wang, Xiaohua Tony Hu, Qinghua Jiang, Jiangning Song, Shinichi Morishita, Kevin Burrage, Guohua Wang
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	870-873
Number of pages	4
ISBN (Electronic)	9781509016105
DOIs	https://doi.org/10.1109/BIBM.2016.7822640
State	Published - 17 Jan 2017
Event	2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016 - Shenzhen, China Duration: 15 Dec 2016 → 18 Dec 2016

Publication series

Name	Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016

Conference

Conference	2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016
Country/Territory	China
City	Shenzhen
Period	15/12/16 → 18/12/16

Keywords

GPU
Multiple GPU
Parallel computing
Phylogenetic tree
UPGMA

Access to Document

10.1109/BIBM.2016.7822640

Cite this

Hung, C. L., Lin, C. Y., Wu, F. C., & Chan, Y. W. (2017). Efficient parallel UPGMA algorithm based on multiple GPUs. In K. Burrage, Q. Zhu, Y. Liu, T. Tian, Y. Wang, X. T. Hu, Q. Jiang, J. Song, S. Morishita, K. Burrage, & G. Wang (Eds.), Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016 (pp. 870-873). [7822640] (Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BIBM.2016.7822640

Hung, Che Lun ; Lin, Chun Yuan ; Wu, Fu Che et al. / Efficient parallel UPGMA algorithm based on multiple GPUs. Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016. editor / Kevin Burrage ; Qian Zhu ; Yunlong Liu ; Tianhai Tian ; Yadong Wang ; Xiaohua Tony Hu ; Qinghua Jiang ; Jiangning Song ; Shinichi Morishita ; Kevin Burrage ; Guohua Wang. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 870-873 (Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016).

@inproceedings{98841603a55349cc8cf7e4343112a9b8,

title = "Efficient parallel UPGMA algorithm based on multiple GPUs",

abstract = "A phylogenetic tree is used to present the evolutionary relationships among the interesting biological species based on the similarities in their genetic sequences. The UPGMA is one of the popular algorithms to construct a phylogenetic tree according to the distance matrix created by the pairwise distances among taxa. To solve the performance issue of the UPGMA, the implementation of the UPGMA method on a single GPU has been proposed. However, it is not capable of handling the large taxa set. This work describes a novel parallel UPGMA approach on multiple GPUs that is able to build a tree from extremely large datasets. The experimental results show that the proposed approach with 4 NVIDIA GTX 980 achieves an approximately × fold speedup over the implementation of UPGMA on CPU and GPU, respectively.",

keywords = "GPU, Multiple GPU, Parallel computing, Phylogenetic tree, UPGMA",

author = "Hung, {Che Lun} and Lin, {Chun Yuan} and Wu, {Fu Che} and Chan, {Yu Wei}",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; null ; Conference date: 15-12-2016 Through 18-12-2016",

year = "2017",

month = jan,

day = "17",

doi = "10.1109/BIBM.2016.7822640",

language = "English",

series = "Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "870--873",

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

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

address = "United States",

}

Hung, CL, Lin, CY, Wu, FC & Chan, YW 2017, Efficient parallel UPGMA algorithm based on multiple GPUs. in K Burrage, Q Zhu, Y Liu, T Tian, Y Wang, XT Hu, Q Jiang, J Song, S Morishita, K Burrage & G Wang (eds), Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016., 7822640, Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016, Institute of Electrical and Electronics Engineers Inc., pp. 870-873, 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016, Shenzhen, China, 15/12/16. https://doi.org/10.1109/BIBM.2016.7822640

Efficient parallel UPGMA algorithm based on multiple GPUs. / Hung, Che Lun; Lin, Chun Yuan; Wu, Fu Che et al.

Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016. ed. / Kevin Burrage; Qian Zhu; Yunlong Liu; Tianhai Tian; Yadong Wang; Xiaohua Tony Hu; Qinghua Jiang; Jiangning Song; Shinichi Morishita; Kevin Burrage; Guohua Wang. Institute of Electrical and Electronics Engineers Inc., 2017. p. 870-873 7822640 (Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient parallel UPGMA algorithm based on multiple GPUs

AU - Hung, Che Lun

AU - Lin, Chun Yuan

AU - Wu, Fu Che

AU - Chan, Yu Wei

PY - 2017/1/17

Y1 - 2017/1/17

N2 - A phylogenetic tree is used to present the evolutionary relationships among the interesting biological species based on the similarities in their genetic sequences. The UPGMA is one of the popular algorithms to construct a phylogenetic tree according to the distance matrix created by the pairwise distances among taxa. To solve the performance issue of the UPGMA, the implementation of the UPGMA method on a single GPU has been proposed. However, it is not capable of handling the large taxa set. This work describes a novel parallel UPGMA approach on multiple GPUs that is able to build a tree from extremely large datasets. The experimental results show that the proposed approach with 4 NVIDIA GTX 980 achieves an approximately × fold speedup over the implementation of UPGMA on CPU and GPU, respectively.

AB - A phylogenetic tree is used to present the evolutionary relationships among the interesting biological species based on the similarities in their genetic sequences. The UPGMA is one of the popular algorithms to construct a phylogenetic tree according to the distance matrix created by the pairwise distances among taxa. To solve the performance issue of the UPGMA, the implementation of the UPGMA method on a single GPU has been proposed. However, it is not capable of handling the large taxa set. This work describes a novel parallel UPGMA approach on multiple GPUs that is able to build a tree from extremely large datasets. The experimental results show that the proposed approach with 4 NVIDIA GTX 980 achieves an approximately × fold speedup over the implementation of UPGMA on CPU and GPU, respectively.

KW - GPU

KW - Multiple GPU

KW - Parallel computing

KW - Phylogenetic tree

KW - UPGMA

UR - http://www.scopus.com/inward/record.url?scp=85013231222&partnerID=8YFLogxK

U2 - 10.1109/BIBM.2016.7822640

DO - 10.1109/BIBM.2016.7822640

M3 - Conference contribution

AN - SCOPUS:85013231222

T3 - Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016

SP - 870

EP - 873

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

A2 - Burrage, Kevin

A2 - Zhu, Qian

A2 - Liu, Yunlong

A2 - Tian, Tianhai

A2 - Wang, Yadong

A2 - Hu, Xiaohua Tony

A2 - Jiang, Qinghua

A2 - Song, Jiangning

A2 - Morishita, Shinichi

A2 - Burrage, Kevin

A2 - Wang, Guohua

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 15 December 2016 through 18 December 2016

ER -

Hung CL, Lin CY, Wu FC, Chan YW. Efficient parallel UPGMA algorithm based on multiple GPUs. In Burrage K, Zhu Q, Liu Y, Tian T, Wang Y, Hu XT, Jiang Q, Song J, Morishita S, Burrage K, Wang G, editors, Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016. Institute of Electrical and Electronics Engineers Inc. 2017. p. 870-873. 7822640. (Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016). doi: 10.1109/BIBM.2016.7822640

Efficient parallel UPGMA algorithm based on multiple GPUs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this