多核CPU和GPU系统上Motif发现并行算法研究

摘要

Motif(模体)是指DNA序列中长度较短、具有保守功能的序列片段,Motif发现即从DNA序列中寻找出Motif的过程,该问题是生物信息学中一个基础而重要的研究课题。利用计算机技术来解决该问题的目标是寻找更长l的Motif。因此,在多核CPU和GPU系统上研究设计访存高效、加速比高、可扩展性好的(l,d)-Motif发现并行算法具有现实意义。
　　本文结合多核计算机的多级缓存存储结构特点,设计实现了一种访存高效、加速比高、可扩展性好的线程级并行(l,d)-Motif发现算法。充分利用多核结构的共享三级缓存、私有二级和一级缓存容量大小,将求解(l,d)-Motif发现问题过程中产生的大量不同位置组合的数据,以多轮方式调度分配到各级缓存中,使得各个核心在并行求解(l,d)-Motif发现问题时,大大减少了数据在主存和缓存之间的交换次数,实现了并行算法的访存高效;同时,通过线程绑定平衡了各计算核心的负载、减少了线程迁移开销。实验测试综合考虑了不同(l,d)-Motif发现问题规模、处理核心数、线程数目、各级缓存可利用大小等多种因素对多核计算机上(l,d)-Motif发现并行算法性能的影响。实验结果表明,随着处理核心数的增加,本文多核计算机上(l,d)-Motif发现并行算法表现出越高的效率,具有良好的加速比和可扩展性,在并行求解较长l的(l,d)-Motif发现问题时,其所需的运行时间明显少于同类研究的其他算法。
　　根据GPU的结构特点以及存储器特点,将求解(l,d)-Motif发现问题过程中产生的大量不同位置组合的数据和候选序列集合绑定到纹理存储器中,通过缓存加速访问,减少访存时间;对不同的(l,d)-Motif发现问题规模,依据组合数据大小设置GPU端线程块的尺寸,设计实现了多核CPU与单GPU混合机器上(l,d)-Motif发现并行算法,为提高处理较大规模(l,d)-Motif发现问题的加速效果,同时设计实现了多核CPU与多GPU混合机器上(l,d)-Motif发现并行算法。实验测试综合考虑了不同(l,d)-Motif发现问题规模、不同线程块尺寸、GPU数目等多种因素对多核CPU与GPU混合机器上(l,d)-Motif发现并行算法性能的影响。实验结果表明,与多核计算机上(l,d)-Motif发现并行算法相比,多核CPU与单GPU混合机器上的(l,d)-Motif发现并行算法具有更高的加速比,当求解更长l的(l,d)-Motif发现问题时,多核CPU与多GPU混合机器上(l,d)-Motif发现并行算法的运行时间更短,效果更优。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景

1.2 Motif发现问题的研究现状及水平

1.3 论文的研究内容和章节组织结构

第二章 多核计算机上访存高效的（l，d）-Motif发现并行算法

2.1 问题的提出

2.2 Modeling算法的分析

2.3 多核计算机上基于Modeling计算的(l，d)-Motif发现并行算法

2.4 多核计算机上访存高效的(l，d)-Motif发现并行算法的实验

2.5 本章小结

第三章 多核CPU与GPU混合机器上(l，d)-Motif发现并行算法

3.1 问题的提出

3.2 多核CPU与GPU混合机器上(l，d)-Motif发现并行算法的设计与分析

3.3 多核CPU与GPU混合机器上(l，d)-Motif发现并行算法的实验

3.4 本章小结

第四章 总结与展望

4.1 主要工作

4.2 主要贡献和创新

4.3 下一步的研究工作

参考文献

致谢

攻读硕士学位期间参加的科研项目

攻读硕士学位期间发表的学术论文