异构平台上协同计算的相关研究

《异构平台上协同计算的相关研究》由会员分享，可在线阅读，更多相关《异构平台上协同计算的相关研究（73页珍藏版）》请在金锄头文库上搜索。

1、 异 构 平 台 上 协 同 计 算 的 相 关 研 究 国 防 科 学 技 术 大 学 研 究 生 院 分类号 TP314 学号 09060056 密级 公 开 工学硕士学位论文 异构平台上异构平台上协同计算协同计算的相关研究的相关研究 硕士生姓名 石志才 学 科 领 域 计算机科学与技术 研 究 方 向 计算机软件与理论 指 导 教 师 杨灿群 研究员 国防科学国防科学技术大学研究生院技术大学研究生院 二一一年十一月二一一年十一月 Research for Collaborative Computing on Heterogeneous System Candidate：Shi Zhica

2、i Advisor：Prof. Yang Canqun A thesis Submitted in partial fulfillment of the requirements for the degree of Master of Engineering in Computer Science and Technology Graduate School of National University of Defense Technology Changsha，Hunan，P.R.China November，2011 （此页放置（此页放置独创性声明和学位论文版权使用授权书独创性声明和学位

3、论文版权使用授权书 复印件，复印件，其其原件存放在学位申请材料中。原件存放在学位申请材料中。） 国防科学技术大学研究生院工学硕士学位论文 第 I 页 目目 录录 摘 要 . i ABSTRACT iii 第一章 引言 1 1.1 课题背景 . 1 1.1.1 异构体系结构 1 1.1.2 数据并行应用 3 1.2 研究现状 . 4 1.2.1 MD5 Crypt 破解算法的相关研究 . 4 1.2.2 Lared-P 程序的相关研究 5 1.2.3 异构平台上的相关研究 6 1.3 本文研究内容与主要工作 . 6 1.4 本文结构 . 8 第二章 背景知识 . 9 2.1 异构系统 . 9 2

4、.1.1 GPU 系统结构 . 9 2.1.2 GPU 编程模型 . 11 2.1.3 基于 GPU 的异构系统 18 2.2 MD5 Crypt 破解算法 19 2.2.1 MD5 加密算法 . 19 2.2.2 MD5 Crypt 算法 . 19 2.2.3 MD5 Crypt 算法的暴力破解 . 21 2.3 Lared-P 应用 . 22 2.3.1 Lared-P 算法简介 22 2.3.2 粒子运动方程 24 2.3.3 粒子云方程 24 2.4 本章小结 . 25 第三章 MD5 Crypt 破解算法在异构系统上的协同计算 . 26 3.1 基于 MPI-OpenMP-CUDA

5、的层次化设计方法 26 3.2 大规模异构系统上 MD5 Crypt 破解算法的设计 . 28 3.2.1 破解算法的层次化设计方法 28 3.2.2 并行破解算法中的任务划分 29 国防科学技术大学研究生院工学硕士学位论文 第 II 页 3.3 GPU 平台上的实现与优化 30 3.3.1 破解算法在 GPU 平台上的实现 30 3.3.2 MD5 Crypt 算法在 GPU 平台上的性能优化 . 32 3.4 CPU 与 GPU 之间的协同计算 33 3.5 大规模节点间的扩展 . 33 3.6 本章小结 . 35 第四章 Lared-P 算法在异构系统上的协同计算 . 36 4.1 La

6、red-P 算法中的数据相关分析 . 36 4.2 多核 CPU 上的并行实现 . 37 4.3 GPU 上的并行实现 38 4.3.1 基于 SIMT 的并行方案 . 38 4.3.2 八色分解方案 40 4.3.2 数据组织与共享 41 4.4 CPU 与 GPU 之间的协同计算 43 4.4.1 数据传输优化 43 4.4.2 多进程共享 GPU . 44 4.4.3 任务划分与映射 45 4.5 本章小结 . 46 第五章 性能评测 . 47 5.1 实验环境 . 47 5.2 MD5 Crypt 破解算法性能评测 47 5.2.1 GPU 程序的测试结果 . 47 5.2.2 单个节

7、点内的测试结果 48 5.2.3 多个节点上的测试结果 48 5.3 Lared-P 程序性能评测 . 49 5.3.1 GPU 程序的测试结果 . 49 5.3.2 单个节点内的测试结果 50 5.4 本章小结 . 52 第六章 结束语 53 6.1 工作总结 . 53 6.2 进一步的工作 . 54 致 谢 55 参考文献 . 56 国防科学技术大学研究生院工学硕士学位论文 第 III 页 作者在学期间取得的学术成果 . 60 国防科学技术大学研究生院工学硕士学位论文 第 IV 页 表 目 录 表 2.1 CUDA 的存储模型 15 表 2.2 MD5 Crypt 算法部分源代码 . 20

8、 表 2.3 不同字符集与密码长度所对应的密码空间 21 表 5.1 破解算法在 GPU 平台上采取不同优化措施所取得的性能对比 47 表 5.2 破解算法在不同计算部件上所取得的性能对比 48 表 5.3 TianHe-1A 破解不同长度密码的期望时间 . 49 国防科学技术大学研究生院工学硕士学位论文 第 V 页 图 目 录 图 1.1 NVIDIA GPU 与 Intel CPU 性能对比图 2 图 2.1 Fermi 架构的体系结构简图 10 图 2.2 NVIDIA GPU 异构编程的软件接口 11 图 2.3 CUDA 中的线程模型 12 图 2.4 CUDA 中软件与硬件的映射关

9、系 13 图 2.5 线程块中线程的组织示意图 14 图 2.6 CPU+GPU 异构系统中的存储结构与通信 . 16 图 2.7 数据传输与数据处理的异步执行 17 图 2.8 CPU+GPU 的异构体系结构 . 18 图 2.9 暴力破解算法计算过程的流程图 22 图 2.10 二维模拟空间中的网格与粒子 23 图 2.11 Lared-P 算法计算过程的主要公式 23 图 3.1 MPI-OpenMP-CUDA 的层次化设计方法示意图 27 图 3.2 密码空间在大规模异构系统中所有处理核心上的划分与映射 28 图 3.3 密码索引的分解示意图 29 图 3.4 破解算法在 GPU 上实

10、现过程的流程图 31 图 3.5 断点保存过程中主进程与从进程之间的交互 34 图 3.6 断点保存过程中子任务状态转换示意图 35 图 4.1 多个粒子更新守卫网格电流值时存在的写冲突 36 图 4.2 CPU 端并行方法中模拟空间的分解与编号 . 38 图 4.3 三维模型中守卫网格的编号 39 图 4.4 warp 内线程之间同步的二维示意图 . 40 图 4.5 三维模型中 warp 块之间的八色分解 41 图 4.6 处理一个网格和一个 warp 块所需网格数据量的示意图 42 图 4.7 两个连续 warp 块的守卫网格在 Z 维上的连续 43 图 4.8 多个进程共享 GPU 时

11、的处理流程示意图 45 图 4.9 CPU 与 GPU 协同计算时的多层次线程并行示意图 . 46 图 5.1 破解算法在 TianHe-1A 上不同节点规模下所获得的性能示意图 48 图 5.2 粒子云方程不同并行方法在 GPU 上的性能对比图 49 图 5.3 不同数据通信优化措施所取得的加速效果对比图 50 图 5.4 不同规模进程共享 GPU 时相对一个进程所获得的性能加速效果图 51 图 5.5 扩展计算规模后不同程序相对 CPU 串行程序的加速效果图 51 国防科学技术大学研究生院工学硕士学位论文 第 i 页 摘 要 近年来，高性能计算机体系结构的发展日新月异，其中基于 GPU 的

12、异构体系 结构成为一种主流的设计方法。相比传统的同构多处理机系统，集成 CPU 和 GPU 的异构系统能够提供更好的计算性能和功耗效率，非常适合处理数据并行应用， 在工业制造、生物医药、石油物探、气象预测等领域有着广泛的应用前景。目前， 限制异构计算的瓶颈在于异构编程环境仍不够成熟，如何高效地利用异构系统中 多核 CPU 和众核 GPU 进行协同计算是目前高性能计算领域中研究的热点和难点 问题。 MD5 Crypt破解算法和 Lared-P激光等离子体模拟算法是两道典型的数据并行 程序，分别在信息安全和物理模型模拟领域有着十分重要的应用价值。这两个应 用代表了两类典型的数据并行应用： MD5

13、Crypt 破解算法在并行求解过程中数据相 互独立不相关；Lared-P 算法则在并行求解过程中存在十分复杂的数据相关。本文 针对这两类应用对异构系统上 CPU 和 GPU 的协同计算进行了研究。主要取得了 如下成果： （1） 采用了一种基于 MPI-OpenMP-CUDA 混合编程模型实现了异构系统上的 的协同计算。使用 MPI 编程接口实现同构节点之间的协作；采用 OpenMP 实现节 点内 CPU 和 GPU 之间的协同计算；当计算任务分配到 CPU 上时，采用嵌套的 OpenMP 线程对计算任务进行处理，当计算任务分配到 GPU 上时，则采用 CUDA 线程对计算任务进行处理。 （2）

14、实现了 MD5 Crypt 破解算法在异构系统上的协同计算。采用基于 MPI-OpenMP-CUDA 的协同计算方法，将整个密码空间作为总的计算任务，分成 多个子任务后通过 MPI 在节点间进行平均分配；在节点内部分别在 CPU 和 GPU 上使用 OpenMP 和 CUDA 对分配的任务进行并行处理；针对 GPU 上的 CUDA 程 序采用了使用常量内存、内存操作优化以及使用共享内存等方法进行了优化；针 对 CPU 与 GPU 之间的性能差异， 采用两路攻击的策略实现了 CPU 与 GPU 之间计 算任务的动态分配和负载平衡；在多个节点上采用主从的并行模式，通过主进程 对任务池的维护，实现了

15、破解算法的断点续算功能。实验结果表明，MD5 Crypt 破解程序在 TianHe-1A 系统上仅使用 CPU 时每秒可处理 4.3 万个密码， 而 CPU 和 GPU 协同计算时，每秒处理的密码数则可达 25 万，若全系统运行每秒可以处理 18 亿组密码，对 MD5 Crypt 算法的安全性提出了挑战。 （3）实现了 Lared-P 算法在异构平台上的并行分解和协同计算。将整个模拟 区域作为总的计算任务，通过 MPI 进程将计算任务划分并分配到节点上；在节点 内使用 OpenMP 的动态调度方法实现了计算任务在 CPU 和 GPU 上的动态分配； 国防科学技术大学研究生院工学硕士学位论文 第

16、 ii 页 针对粒子云方程中存在的数据相关，在 CPU 上采用隔离存在冲突网格的方法实现 计算任务的并行分解， 在 GPU 上则提出了一种基于 CUDA 中 SIMT 并行机制的并 行方法和八色分解方案，实现了任务的并行分解以及数据共享；通过多个 MPI 进 程共享 GPU 的方法使得数据初始化和 GPU 计算异步执行，提高了 GPU 的利用率 和程序的执行效率；采用页锁定内存和最小数据量传输的方法对程序的数据传输 进行优化，在提高传输速度的同时减少了数据的传输量。最终 Lared-P 程序在 Tianhe-1A 的单个节点上的测试性能则相对于 CPU 串行程序的性能提高了 29 倍， 缩短了整个程序的运行时间。 关键字：异构系统；GPU；协同计算；MD5 Crypt；暴力破解；粒子云方程； 写冲突 国防科学技术大学研究生院工学硕士学位论文 第 iii 页 ABSTRACT In recent years, the architecture