Efficient parallel algorithm for compound comparisons on multi-GPUs

Chun Yuan Lin; Chung Hung Wang; Che Lun Hung; Yu Shiang Lin

doi:10.1109/BIBM.2014.6999307

Efficient parallel algorithm for compound comparisons on multi-GPUs

Chun Yuan Lin
, Chung Hung Wang
, Che Lun Hung^*
, Yu Shiang Lin

^*Corresponding author for this work

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

2 Scopus citations

Abstract

Compound comparison is an important task for computational chemistry. By the comparison reulsts, potential inhibitors can be found and then used for the following experiments. The time complexity of a pairwise compound comparison is O(n²), where n is the maximal length of compounds. In general, the compound length is small, and the cost of computation time is short. However, more and more compounds have been synthesized and extracted now, even more than ten of millions. Therefore, it still will be time-consuming when comparing with a large amount of compounds (multiple compound comparisons). In this paper, we propose a parallel algorithm for multiple compound comparisons on multi-GPUs. Four load-balancing strategies were considered in the proposed algorithm in order to accelerate the computation speed among thread blocks on GPUs. The proposed algorithm was implemented by C+OpenMP+CUDA, and achieved more than 50 times speedup by comparing with its CPU version under the experiemtal results.

Original language	English
Title of host publication	Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014
Editors	Huiru Zheng, Xiaohua Tony Hu, Daniel Berrar, Yadong Wang, Werner Dubitzky, Jin-Kao Hao, Kwang-Hyun Cho, David Gilbert
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	30-35
Number of pages	6
ISBN (Electronic)	9781479956692
DOIs	https://doi.org/10.1109/BIBM.2014.6999307
State	Published - 29 12 2014
Event	2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014 - Belfast, United Kingdom Duration: 02 11 2014 → 05 11 2014

Publication series

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

Conference

Conference	2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014
Country/Territory	United Kingdom
City	Belfast
Period	02/11/14 → 05/11/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

CUDA
Compound comparison
Load-Balancing
OpenMP
SMILES

Access to Document

10.1109/BIBM.2014.6999307

Cite this

Lin, C. Y., Wang, C. H., Hung, C. L., & Lin, Y. S. (2014). Efficient parallel algorithm for compound comparisons on multi-GPUs. In H. Zheng, X. T. Hu, D. Berrar, Y. Wang, W. Dubitzky, J.-K. Hao, K.-H. Cho, & D. Gilbert (Eds.), Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014 (pp. 30-35). Article 6999307 (Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BIBM.2014.6999307

Lin, Chun Yuan ; Wang, Chung Hung ; Hung, Che Lun et al. / Efficient parallel algorithm for compound comparisons on multi-GPUs. Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014. editor / Huiru Zheng ; Xiaohua Tony Hu ; Daniel Berrar ; Yadong Wang ; Werner Dubitzky ; Jin-Kao Hao ; Kwang-Hyun Cho ; David Gilbert. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 30-35 (Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014).

@inproceedings{bd966f092a2c49949b4b4c70e9449ea1,

title = "Efficient parallel algorithm for compound comparisons on multi-GPUs",

abstract = "Compound comparison is an important task for computational chemistry. By the comparison reulsts, potential inhibitors can be found and then used for the following experiments. The time complexity of a pairwise compound comparison is O(n2), where n is the maximal length of compounds. In general, the compound length is small, and the cost of computation time is short. However, more and more compounds have been synthesized and extracted now, even more than ten of millions. Therefore, it still will be time-consuming when comparing with a large amount of compounds (multiple compound comparisons). In this paper, we propose a parallel algorithm for multiple compound comparisons on multi-GPUs. Four load-balancing strategies were considered in the proposed algorithm in order to accelerate the computation speed among thread blocks on GPUs. The proposed algorithm was implemented by C+OpenMP+CUDA, and achieved more than 50 times speedup by comparing with its CPU version under the experiemtal results.",

keywords = "CUDA, Compound comparison, Load-Balancing, OpenMP, SMILES",

author = "Lin, \{Chun Yuan\} and Wang, \{Chung Hung\} and Hung, \{Che Lun\} and Lin, \{Yu Shiang\}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014 ; Conference date: 02-11-2014 Through 05-11-2014",

year = "2014",

month = dec,

day = "29",

doi = "10.1109/BIBM.2014.6999307",

language = "英语",

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

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

pages = "30--35",

editor = "Huiru Zheng and Hu, \{Xiaohua Tony\} and Daniel Berrar and Yadong Wang and Werner Dubitzky and Jin-Kao Hao and Kwang-Hyun Cho and David Gilbert",

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

address = "美国",

}

Lin, CY, Wang, CH, Hung, CL & Lin, YS 2014, Efficient parallel algorithm for compound comparisons on multi-GPUs. in H Zheng, XT Hu, D Berrar, Y Wang, W Dubitzky, J-K Hao, K-H Cho & D Gilbert (eds), Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014., 6999307, Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014, Institute of Electrical and Electronics Engineers Inc., pp. 30-35, 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014, Belfast, United Kingdom, 02/11/14. https://doi.org/10.1109/BIBM.2014.6999307

Efficient parallel algorithm for compound comparisons on multi-GPUs. / Lin, Chun Yuan; Wang, Chung Hung; Hung, Che Lun et al.
Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014. ed. / Huiru Zheng; Xiaohua Tony Hu; Daniel Berrar; Yadong Wang; Werner Dubitzky; Jin-Kao Hao; Kwang-Hyun Cho; David Gilbert. Institute of Electrical and Electronics Engineers Inc., 2014. p. 30-35 6999307 (Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014).

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

TY - GEN

T1 - Efficient parallel algorithm for compound comparisons on multi-GPUs

AU - Lin, Chun Yuan

AU - Wang, Chung Hung

AU - Hung, Che Lun

AU - Lin, Yu Shiang

PY - 2014/12/29

Y1 - 2014/12/29

N2 - Compound comparison is an important task for computational chemistry. By the comparison reulsts, potential inhibitors can be found and then used for the following experiments. The time complexity of a pairwise compound comparison is O(n2), where n is the maximal length of compounds. In general, the compound length is small, and the cost of computation time is short. However, more and more compounds have been synthesized and extracted now, even more than ten of millions. Therefore, it still will be time-consuming when comparing with a large amount of compounds (multiple compound comparisons). In this paper, we propose a parallel algorithm for multiple compound comparisons on multi-GPUs. Four load-balancing strategies were considered in the proposed algorithm in order to accelerate the computation speed among thread blocks on GPUs. The proposed algorithm was implemented by C+OpenMP+CUDA, and achieved more than 50 times speedup by comparing with its CPU version under the experiemtal results.

AB - Compound comparison is an important task for computational chemistry. By the comparison reulsts, potential inhibitors can be found and then used for the following experiments. The time complexity of a pairwise compound comparison is O(n2), where n is the maximal length of compounds. In general, the compound length is small, and the cost of computation time is short. However, more and more compounds have been synthesized and extracted now, even more than ten of millions. Therefore, it still will be time-consuming when comparing with a large amount of compounds (multiple compound comparisons). In this paper, we propose a parallel algorithm for multiple compound comparisons on multi-GPUs. Four load-balancing strategies were considered in the proposed algorithm in order to accelerate the computation speed among thread blocks on GPUs. The proposed algorithm was implemented by C+OpenMP+CUDA, and achieved more than 50 times speedup by comparing with its CPU version under the experiemtal results.

KW - CUDA

KW - Compound comparison

KW - Load-Balancing

KW - OpenMP

KW - SMILES

UR - https://www.scopus.com/pages/publications/84922828132

U2 - 10.1109/BIBM.2014.6999307

DO - 10.1109/BIBM.2014.6999307

M3 - 会议稿件

AN - SCOPUS:84922828132

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

SP - 30

EP - 35

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

A2 - Zheng, Huiru

A2 - Hu, Xiaohua Tony

A2 - Berrar, Daniel

A2 - Wang, Yadong

A2 - Dubitzky, Werner

A2 - Hao, Jin-Kao

A2 - Cho, Kwang-Hyun

A2 - Gilbert, David

PB - Institute of Electrical and Electronics Engineers Inc.

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

Y2 - 2 November 2014 through 5 November 2014

ER -

Lin CY, Wang CH, Hung CL, Lin YS. Efficient parallel algorithm for compound comparisons on multi-GPUs. In Zheng H, Hu XT, Berrar D, Wang Y, Dubitzky W, Hao JK, Cho KH, Gilbert D, editors, Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 30-35. 6999307. (Proceedings - 2014 IEEE International Conference on Bioinformatics and Biomedicine, IEEE BIBM 2014). doi: 10.1109/BIBM.2014.6999307

Efficient parallel algorithm for compound comparisons on multi-GPUs

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this