Efficient parallel algorithm for compound comparisons on multi-GPUs

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.