基于GPU集群的蛋白质数据系统发育推断及连续禁忌搜索算法求解CNOP

# 基于GPU集群的蛋白质数据系统发育推断及连续禁忌搜索算法求解CNOP ## 1 ta(MC)3在MrBayes中的优化与实验 ### 1.1 块大小选择 在ta(MC)3中，实际驻留线程束的数量由内核使用的寄存器数量决定。当块大小设置为400时，每个块占用400 × 36 = 14,400个寄存器，每个多处理器最多可容纳4个块，一个块中有13个线程束，总共52个线程束，超过了隐藏延迟所需的40个线程束，满足充分利用的要求。此外，块大小为400与转移概率矩阵的大小相匹配，即20 × 20 = 400个单元，可实现合并内存访问并避免空闲线程。实验结果也表明400是一个不错的块大小选择。 ### 1.2 精度优化 在分析蛋白质数据时，MrBayes可能会出现非收敛问题，根源在于分析大型数据集时截断误差的累积。为解决此问题，ta(MC)3采用Kahan求和算法来提高精度。具体操作如下： 在计算条件似然时，在GPU端实现该算法。在算法4中，(a) 在第7行后声明新寄存器y、el、er和t，并将el和er初始化为零；(b) 将第9行替换为： ```plaintext 1: y ← TMl[m][k] × cl − el 2: t ← tl + y 3: el ← (t − tl) − y 4: tl ← t ``` 对第10行进行类似修改。Kahan求和通过保留一个变量来处理截断误差，在下次迭代中进行校正，可使最坏情况下的误差与n无关，仅取决于机器的浮点精度。 ### 1.3 内存分配限制 实际氨基酸序列长度可达数万甚至数十万，加上研究的分类单元数量，会增加系统内存需求。由于MrBayes的串行版本和并行版本仍使用32位变量，即使GPU设备有足够内存，也无法分析超过4GB内存需求的数据集。为解决此问题，ta(MC)3使用64位变量，并重新设计负责内存管理的程序组件以处理64位地址和管理大内存空间。具体更改的变量如下表所示： | Variable | Description | | --- | --- | | numCompressedChars | 位点数量 | | condLikeRowSize | CPT的行大小 | | globaloneMatSize | CPT的大小 | | offsetclP, offsetclL, offsetclR, offsetclA | CPT中的偏移量 | ### 1.4 实验结果 使用八个真实世界的数据集评估ta(MC)3的性能，这些数据集可在TreeBASE存储库中找到。较大的数据集（7和8）需要更多的内存和处理时间，使用八个NVIDIA Titan卡的GPU集群进行测试。实验在桌面服务器和天河 - 1A异构多核超级计算机上进行，每个执行使用相同的替换模型，数据集1至6运行100000代，数据集7和8运行10000代。 #### 桌面服务器实验 在桌面服务器上测试ta(MC)3，与a(MC)3和MrBayes 3.2.1进行性能比较，以MrBayes 3.1.2的串行版本作为基线串行算法。实验运行时间如下表所示： | Dataset | MrBayes 3.1.2 Execution time (sec.) | MrBayes 3.2.1 Execution time (sec.) | a(MC)3 Execution time (sec.) | ta(MC)3 Execution time (sec.) | MrBayes 3.2.1 Speedup | a(MC)3 Spe