论文摘要
系统发育分析是生物信息学的重要研究方向,它包含了多种算法,用于序列分析和生成系统发育树。随着序列数据规模的不断增大,人们开始关注这些算法的性能问题,对这些算法的并行化研究也越来越多。PHYLIP作为一个使用广泛的系统发育分析软件包同样面临性能问题,它的一些程序拥有较高的时间复杂度,经常需要几小时甚至几十个小时来处理大规模的序列数据。虽然目前已经有了一些对PHYLIP软件包的并行化研究工作,但是这些工作大多基于PHYLIP的早期版本,并使用基于消息传递的并行环境。随着多核CPU的流行和通用GPU的出现,这些基于多核的并行环境为我们的优化工作提供了更多的选择。相比基于消息传递的集群环境,多核CPU并行环境,尤其是通用GPU并行环境所需的软硬件投入较少,拥有更好的性价比。本文分别使用多核CPU和通用GPU并行环境,对PHYLIP中的距离矩阵算法和最大似然算法的程序进行并行优化。我们对算法进行了详细的分析,并结合各并行环境的特点,设计适当的并行策略和优化方式,最终获得了满意的性能提升。在4核8线程的CPU环境下,经过OpenMP优化后,生成距离矩阵的程序可以获得7倍到8倍的加速比,最大似然算法的实现程序也可以获得2倍到6倍的加速比;在一块NVIDIA Tesla C2050上,使用CUDA进行并行后,两个生成距离矩阵程序的加速比分别可以达到16倍和72倍,而DNA序列最大似然算法实现程序的加速比也超过了9倍。从本文的工作可以得到这样的结论:多核CPU和通用GPU环境是有效且高性价比的并行环境,可以有效提升距离矩阵算法和最大似然算法的程序性能。同时,正确分析算法的可并行性,并根据并行环境的特点合理选择优化方式,是提升算法性能的必要条件。