多核平台PAML并行算法研究

J4 ›› 2013, Vol. 35 ›› Issue (9): 15-19.

多核平台PAML并行算法研究

杨菊，吴卓锋，王刚，刘晓光

（南开大学计算机与控制工程学院，天津 300071）

收稿日期:2013-03-13 修回日期:2013-07-04 出版日期:2013-09-25 发布日期:2013-09-25

Parallel algorithm for PAML on multicore platform

YANG Ju,WU Zhuofeng,WANG Gang,LIU Xiaoguang

（College of Computer and Control Engineering,Nankai University,Tianjin 300071,China）

Received:2013-03-13 Revised:2013-07-04 Online:2013-09-25 Published:2013-09-25

摘要/Abstract

摘要：

PAML是一款利用最大似然法进行系统发育分析的软件包，被广泛使用。然而，由于模型复杂、参数众多，PAML的计算过程非常耗时。对PAML中最重要的codeml程序进行了并行算法研究，通过算法分析和程序Profiling确定程序瓶颈。在此基础上，利用现代CPU的多核并行能力和SIMD并行机制优化程序瓶颈，从而提高了程序整体的运行速度。实际数据集和人工数据集上的实验表明并行算法有效提高了codeml的计算速度，加速比最高达7.94倍。

关键词: 并行算法, PAML, 多核CPU, 单指令流多数据流

Abstract:

PAML, which is widely used, is a package of programs for maximum likelihood phylogenetic analysis of protein and DNA sequences. However, its calculation is time consuming because of too many parameters and complex models. The paper focus on the most important part in PAML: codeml. After analyzing the algorithm and finding program bottleneck by profiling, we parallelize the bottlenecks based on the capacity of modern multicore CPU and SIMD technology in order to reduce the overall operating time. The experimental results on both real and simulated data show that our parallel algorithm for PAML can improve the calculation efficiency. The final speedup is up to 7.94.

Key words: parallel algorithm;PAML;multicore CPU;SIMD

杨菊，吴卓锋，王刚，刘晓光. 多核平台PAML并行算法研究[J]. J4, 2013, 35(9): 15-19.

YANG Ju,WU Zhuofeng,WANG Gang,LIU Xiaoguang. Parallel algorithm for PAML on multicore platform [J]. J4, 2013, 35(9): 15-19.

[1]	肖调杰, 周峰, 郑翾宇, 刘剑, 陈琳, 刘杰, 易明宽, 陈旭光, 龚春叶, 杨博, 甘新标, 李胜国, 左克, . 大规模三维频率域电磁积分方程法数值模拟[J]. 计算机工程与科学, 2023, 45(11): 1901-1910.
[2]	许晓阳, 王斯棋. 基于粒子分解的SPH并行算法研究与应用[J]. 计算机工程与科学, 2022, 44(06): 964-970.
[3]	刘杰, 龚春叶, 杨博, 郭晓威, 甘新标, 李胜国, 李超, 陈旭光, 肖调杰, 穆利安, 宋敏, 赵冬勇, 鞠羽中. YH-ACT：热工流体力学并行应用程序[J]. 计算机工程与科学, 2021, 43(01): 58-69.
[4]	李雯, 迟利华, 张会, 张哲, 刘杰, . 潜艇使用自航式声诱饵防御鱼雷模型并行计算方法研究[J]. 计算机工程与科学, 2020, 42(12): 2163-2168.
[5]	王俊吉1,2,朱朝艳1,2,4,陈建军1,2,郑澎3，5,徐权3. 基于无锁原子操作的多线程并行Delaunay三角化算法[J]. 计算机工程与科学, 2018, 40(05): 773-779.
[6]	章子凯，武继刚，姜文超，刘竹松. 容错处理器阵列的多逻辑列并行重构算法[J]. 计算机工程与科学, 2018, 40(01): 24-33.
[7]	李娟1，汤德佑1，傅娟2，3. 一种基于蚁群算法的生物序列并行比对方法[J]. 计算机工程与科学, 2017, 39(09): 1610-1616.
[8]	宋威，吉红蕾，李晋宏. 一种高效用项集并行挖掘算法[J]. J4, 2015, 37(03): 422-428.
[9]	周琛，陈振杰，张帅. 基于边界代数法的矢量栅格化并行算法设计与实现[J]. J4, 2013, 35(4): 37-41.
[10]	王多雷，龙汉，陈璇. 组合打击下一类面目标易损性的并行计算研究[J]. J4, 2013, 35(4): 42-46.
[11]	刘立国，莫锦军，袁乃昌. 基于“天河一号”的并行电磁计算求解器[J]. J4, 2013, 35(3): 43-47.
[12]	焦善飞1,2，何晨2，豆育升2，唐红1,2. 短程力分子模拟在Hadoop上的实现及优化[J]. J4, 2013, 35(2): 26-31.
[13]	龚春叶1,2,3,包为民1,闵昌万1,张烨琛1，刘杰3. 分数阶微分方程的一种细粒度数据级并行算法[J]. J4, 2013, 35(11): 76-79.
[14]	徐莹，徐磊，姜恺. 三维NavierStokes方程分步法的并行算法在异构平台上实现初探[J]. J4, 2012, 34(9): 33-39.
[15]	徐莹，徐磊. 三维Navier-Stokes方程的差分-谱方法混合法在GPU上的实现与优化[J]. J4, 2012, 34(8): 53-58.