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

Providence University Taiwan

研究成果: 圖書/報告稿件的類型 › 會議稿件 › 同行評審

3 引文斯高帕斯（Scopus）

摘要

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.

原文	英語
主出版物標題	Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016
編輯	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.
頁面	870-873
頁數	4
ISBN（電子）	9781509016105
DOIs	https://doi.org/10.1109/BIBM.2016.7822640
出版狀態	已出版 - 17 01 2017
事件	2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016 - Shenzhen, 中國持續時間: 15 12 2016 → 18 12 2016

出版系列

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

Conference

Conference	2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016
國家/地區	中國
城市	Shenzhen
期間	15/12/16 → 18/12/16

文獻附註

Publisher Copyright:
© 2016 IEEE.

存取文件

10.1109/BIBM.2016.7822640

其它文件與鏈接

Link to publication in Scopus

引用此

Hung, C. L., Lin, C. Y., Wu, F. C., & Chan, Y. W. (2017). Efficient parallel UPGMA algorithm based on multiple GPUs. 於 K. Burrage, Q. Zhu, Y. Liu, T. Tian, Y. Wang, X. T. Hu, Q. Jiang, J. Song, S. Morishita, K. Burrage, & G. Wang (編輯), Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016 (頁 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 等. / Efficient parallel UPGMA algorithm based on multiple GPUs. Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016. 編輯 / 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. 頁 870-873 (Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016).

@inproceedings{cc244b20df0944ea81a2621e75e8a31c,

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 {\texttimes} 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.; 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016 ; Conference date: 15-12-2016 Through 18-12-2016",

year = "2017",

month = jan,

day = "17",

doi = "10.1109/BIBM.2016.7822640",

language = "英语",

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 = "美国",

}

Hung, CL, Lin, CY, Wu, FC & Chan, YW 2017, Efficient parallel UPGMA algorithm based on multiple GPUs. 於 K Burrage, Q Zhu, Y Liu, T Tian, Y Wang, XT Hu, Q Jiang, J Song, S Morishita, K Burrage & G Wang (編輯), 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., 頁 870-873, 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016, Shenzhen, 中國, 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 等.
Proceedings - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016. 編輯 / 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).

研究成果: 圖書/報告稿件的類型 › 會議稿件 › 同行評審

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 - https://www.scopus.com/pages/publications/85013231222

U2 - 10.1109/BIBM.2016.7822640

DO - 10.1109/BIBM.2016.7822640

M3 - 会议稿件

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.

T2 - 2016 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2016

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. 於 Burrage K, Zhu Q, Liu Y, Tian T, Wang Y, Hu XT, Jiang Q, Song J, Morishita S, Burrage K, Wang G, 編輯, 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

摘要

出版系列

Conference

文獻附註

存取文件

其它文件與鏈接

指紋

引用此