MGUPGMA: A Fast UPGMA Algorithm With Multiple Graphics Processing Units Using NCCL.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Phylogenetic trees visualize evolutionary relationships between species.
• Distance-matrix methods, like UPGMA, are common for tree construction but face computational challenges with large datasets.
• Existing high-performance solutions have not fully resolved these performance issues.

Purpose of the Study:

• To develop a high-performance parallel algorithm for constructing phylogenetic trees.
• To address the computational performance limitations of traditional distance-matrix methods for large-scale sequence data.

Main Methods:

• Proposed a novel parallel Unweighted Pair Group Method with Arithmetic Mean (UPGMA) algorithm.
• Implemented the parallel UPGMA approach utilizing multiple Graphics Processing Units (GPUs).
• Tested the method on extremely large sets of biological sequences.

Main Results:

• The parallel UPGMA approach achieved significant speedups on a DGX-1 server with 8 NVIDIA P100 GPUs.
• Demonstrated a 3-fold speedup compared to a modern CPU implementation.
• Showed a 7-fold speedup compared to a single GPU implementation.

Conclusions:

• The proposed multi-GPU parallel UPGMA method offers a substantial performance improvement for phylogenetic tree construction.
• This approach is effective for handling extremely large biological sequence datasets.
• Accelerated phylogenetic analysis can facilitate broader evolutionary studies.