基于GPU的TSP遗传算法研究与实现 湖南大学工程硕士学位论文

学校代号 10532 学 号 G07100034 分 类 号 密 级 普通 工程硕士学位论文 基于 GPU 的 TSP 遗传算法研究与实现 学位申请人姓名 欧阳陈华 培 养 单 位 信息科学与工程学院 导师姓名及职称 李肯立 教授 申亚宁 高级工程师 学 科 专 业 计算机技术 研 究 方 向 并行计算 论 文 提 交 日 期 2012 年 4 月 25 日 学校代号 10532 学 号 G071000346 密级 普通普 通 湖南大学工程硕士学位论文湖南大学工程硕士学位论文 基于 GPU 的 TSP 遗传算法 研究与实现 学位申请人姓名 欧阳陈华 导师姓名及职称 李肯立 教授 申亚宁 高级工程师 培 养 单 位 信息科学与工程学院 专 业 名 称 计算机技术 论 文 提 交 日 期 2012 年 4 月 25 日 论 文 答 辩 日 期 2012 年 5 月 24 日 答辩委员会主席 教授 Research and Implement on Genetic Algorithm for solving TSP with GPU by OUYANG Chenhua B E University of South China 2001 A thesis submitted in partial satisfaction of the requirements for the degree of Master of engineering in College of Information Science and Engineering in the Graduate School of Hunan University Supervisor Professor LI Kenli Mar 2012 基于 GPU 的 TSP 遗传算法研究与实现 I 学位论文原创性声明和学位论文版权使用授权书 湖 南 大 学 学位论文原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任何 其他个人或集体已经发表或撰写的 成果作品 对本文的研究做出重要贡献 的个人和集体 均已在文中以明确方式标明 本人完 全意识到本声明的法 律后果由本人承担 作者签名 日期 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学 校保留并向国家有 关部门或机构送交论文的复印件和电子版 允许论文被 查阅和借阅 本人授权湖南大学可以 将本学位论文的全部或部分内容编入 有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存和汇编 本学位论文 本学位论文属于 1 保密 在 年解密后适用本授权书 2 不保密 请在以上相应方框内打 作者签名 日期 年 月 日 导师签名 日期 年 月 日 工程硕士学位论文 II 摘 要 随着图形显示芯片 Graphic processing Unit GPU 的高速发展 GPU 越来越 强大 而且 GPU 为显示图像做了优化 在计算上已经超越了通用的 CPU 如此 强大的芯片如果只是作为显卡就太浪费了 开始有越来越多的开发与科研人员参 与到了基于 GPU 的通用计算的研究中来 这其中 并行计算是当前的一个热点课 题 本文以学习和研究基于 CUDA 的大规模并行通用计算为目标 选择对遗传算 法解决 TSP 问题进行研究 TSP 问题是一个典型的 易于描述却难以处理的 NP 完全问题 是很多复杂问题的集中体现 通过遗传算法能够获得 TSP 问题的最优 解和近似最优解 利用 CUDA 平台的 GPU 并行计算 将遗传算法中的算子问题 分配到 CUDA 中各个流处理器中并行执行 降低了遗传算法的运行时间 提高了 遗传算法的运行效率 本文主要对遗传算法进行了研究和分析 通过在 NVIDIA 提出的 CUDA 平台 上构建软件实现了 TSP 遗传算法的并行计算 首先 将 TSP 问题中的整个城市种 群初始化 然后分配到 GPU 的各个流处理器上 每个流处理器上分配一个初始种 群 这些分散的种群通过交叉 变异和选择操作 各自进化 从而得到初始种群 的最优进化个体 各流处理器将最优个体传回 CPU 进行比较 得出新一代的最优 个体 再将这个最优个体传回 GPU 的各个流处理器取代最差个体继续进行进化 当子代个体的适应度函数达到期望值 可认为获得了一个极优解 本文分别在 CPU 和 GPU 上对 TSP 遗传算法进行了测试 实验结果表明 通 过 GPU 并行加速后的遗传算法在运行速度和结果质量方面均优于传统的 CPU 算 法 关键词 GPU 并行计算 CUDA 遗传算法 TSP 问题 算子 基于 GPU 的 TSP 遗传算法研究与实现 III Abstract With the rapid development of graphics display chip Graphic processing Unit GPU GPU is more powerful GPU is optimized to display images has gone beyond the general purpose CPU in the calculation Such a powerful chip is too wasted if only as graphics more and more developers and researchers is participating in the study of the GPU based general purpose computing Parallel computing is currently a hot topic The genetic algorithm is a heuristic algorithm as a wide range of applications in the field of scientific research machine learning artificial intelligence Many traditional algorithms problems can obtain the optimal solution by genetic algorithm and the approximate optimal solution In this paper the problem to solve is the old TSP problem Traveling Salesman Problem TSP problem is a typical NP complete problem easy to describe but difficult to deal with a concentrated expression of the many complex issues Finally to solve these problems is the solution of the TSP problem When the number of cities is too large there is not a completely correct solution algorithm Only in a limited time the best individual of the best fitness can be obtained How to reduce the running time become a key factor to solve the TSP problem In this paper learning and research based on the CUDA massively parallel general purpose computing is the goal and choosing to study the genetic algorithm to solve TSP GPU parallel computing using CUDA platform operator in genetic algorithm allocated to each stream processors executing in parallel reduce the running time of the genetic algorithm and improve the efficiency of genetic algorithm to CUDA With researched and analysised of genetic algorithms parallel genetic algorithm was built on the NVIDIA CUDA platform First of all the entire population initialization and then assigned to each stream processors on the GPU through cross mutation and selection operations and evolution These dispersed populations was resulting in the optimal evolution of individuals of the initial population of each stream the best individual would be obtained by compareed of the best individual from each processor and was sent back to GPU instead of the worst individual to continue evolution In this paper Algorithm on the CPU and GPU respectively was tested It was testified that the parallel genetic algorithm through the acceleration of 工程硕士学位论文 IV the GPU exceed the CPU in speed and quality of results Keyword GPU parallel computing CUDA genetic algorithm TSP problem operator 基于 GPU 的 TSP 遗传算法研究与实现 V 目 录 学位论文原创性声明和学位论文版权使用授权书 I 摘 要 II Abstract III 插图索引 VII 附表索引 VIII 第 1 章 绪 论 1 1 1 本文的研究目的与意义 1 1 2 并行计算的国内外现状 水平与发展趋势 2 1 3 本文组织结构 3 第 2 章 CUDA 并行计算平台 4 2 1 CUDA 平台简介 4 2 2 CUDA 发展背景 6 2 3 CUDA 编程模型 7 2 3 CUDA 内存模型 8 2 3 1 寄存器 10 2 3 2 局部存储器 10 2 3 3 共享存储器 10 2 3 4 全局存储器 10 2 3 5 常数存储器 11 2 3 6 纹理存储器 11 2 4 小结 12 第 3 章 遗传算法 13 3 1 遗传算法简介 13 3 1 1 遗传算法的生物学基础 13 3 1 2 遗传算法的工作原理 14 3 2 遗传算法的理论基础 17 3 3 遗传算法的应用领域 18 3 4 小结 18 第 4 章 遗传算法解决 TSP 问题 19 4 1 旅行商问题 19 4 2 算子 19 工程硕士学位论文 VI 4 2 1 选择算子 19 4 2 2 交叉算子 20 4 2 3 变异算子 21 4 3 算法实现的流程图 22 4 4 算法的各个模块及其详细设计思路 23 4 4 1 地图选择模块 23 4 4 2 遗传算法解 TSP 的参数设置模块 23 4 4 3 选择算子模块 24 4 4 4 交叉算子选择模块 25 4 4 5 变异算子选择模块 27 4 5 设计中主要的类和函数的功能 28 4 5 1 Map 类 28 4 5 2 CGA 类 28 4 5 3 Control 类 29 4 5 4 Line 类 29 4 5 5 main cpp 29 4 6 基于 CUDA 的遗传算法解决 TSP 问题 30 4 6 1 CPU 端的执行步骤 32 4 6 2 GPU 端的执行步骤 32 4 6 3 算子的并行化 33 4 7 小结 34 第 5 章 实验与结果 35 总结与展望 38 参考文献 39 致 谢 43 基于 GPU 的 TSP 遗传算法研究与实现 VII 插图索引 图 2 1 CUDA 在多领域的应用 5 图 2 2 Tesla 系列 GPU 的成果 7 图 2 3 Cuda 软件架构图 7 图 2 4 CUDA 的内存模型 9 图 2 5 全局存储器示意图 11 图 3 1 遗传算法的运算过程 15 图 3 2 遗传算法的构造过程 16 图 4 1 求解 TSP 问题的算法流程图 22 图 4 2 基于 CUDA 求解 TSP 问题的流程图 31 图 5 1 TSP 问题测试结果图 36 图 5 2 500 个城市的初始化图 36 图 5 3 500 个城市的迭代结果图 37 工程硕士学位论文 VIII 附表索引 表 2 1 CUDA 存储器功能列表 9 表 5 1 TSP 问题测试结果表 36 工程硕士学位论文 1 第 1 章 绪 论 1 1 本文的研究目的与意义 传统上 GPU 的应用被局限于处理图形渲染计算任务 无疑是对计算资源的 极大浪费 随着 GPU 可编程性的不断提高 利用 GPU 完成通用计算的研究渐渐 活跃起来 将 GPU 用于图形渲染以外领域的计算称为 GPGPU General purpose computing on graphics processing units 基于 GPU 的通用计算 1 GPGPU 计算 通常采用 CPU GPU 异构模式 由 CPU 负责执行复杂逻辑处理和事物管理等不适 合数据并行的计算 由 GPU 负责计算密集型的大规模数据并行计算 这种利用 GPU 强大处理能力和高带宽弥补 CPU 性能不足的计算方式在发掘计算机潜在的 性能 在成本和性价比方面有显著优势 但是 传统的 GPGPU 受硬件可编程性 和开发方式的制约 应用领域受到了限制 开发难度也很大 2007 年 6 月 NVidia 推出了 CUDA Compute Unified Device Architecture 统一计算设备架构 2 CUDA 是一种将 GPU 作为数据并行计算设备的软硬件体 系 与以往的 GPU 相比 支持 CUDA 的 GPU 在架构上有了显著的改进 这两项 改进使 CUDA 架构更加适用于 GPU 通用计算 一是采用了统一处理架构 可以 更加有效地利用过去分布在顶点渲染器和像素渲染器的计算资源 二是引入了片 内共享存储器 支持随机写入 scatter 和线程间通信 CUDA 为开发人员有效利用 GPU 的强大性能提供了条件 自推出后 CUDA 被广泛应用于石油勘探 3 天文计算 流体力学模拟 4 分子动力学仿真 5 生物 计算 6 图像处理 音视频编解码 7 等领域 在很多应用中获得了几倍 几十倍 乃至上百倍的加速比 将 CUDA 应用于各种算法研究问题也成了当前的一个研发 热点 TSP Traveling Salesman Problem 旅行商问题 问题是一个组合优化的老问 题 该问题可以被证明具有 NP 计算复杂性 8 因此 任何能使该问题的求解得 以简化的方法 都将受到高度的评价和关注 遗传算法就是寻求满意解的最佳方 法之一 遗传算法是计算数学中用于解决最优化的全局概率搜索算法 是进化算法的 一种 9 进化算法最初是借鉴了进化生物学中的一些现象而发展起来的 这些现 象包括遗传 突变 自然选择以及杂交等 遗传算法通常实现为一种计算机模拟 对于一个最优化问题 一定数量的候 选解 称为个体 的抽象表示 称为染色体 的种群向更好的解进化 传统上 基于 GPU 的 TSP 遗传算法研究与实现 2 解用二进制表示 即 0 和 1 的串 但也可以用其他表示方法 进化从完全随机个 体的种群开始 之后一代一代发生 在每一代中 整个种群的适应度被评价 从 当前种群中随机地选择多个个体 基于它们的适应度 通过自然选择和突变产生 新的生命种群 该种群在算法的下一次迭代中成为当前种群 遗传算法在解决 TSP 问题时 具有非常高的计算密度 GPU 计算相对于 CPU 计算 更侧重于计算的吞吐量 9 10 将遗传算法在 CUDA 架构上进行优化 能够 缩减大量的计算时间 获得较高的加速比 因此 也证明了 CUDA 在生物计算领 域 具有实际的应用意义 1 2 并行计算的国内外现状 水平与发展趋势 并行计算 Parallel Computing 是由运行在多个部件上的小任务合作来求解 一个规模很大的计算问题的一种方法 它既是一种高性能计算 High Performance Computing 也是一种超级计算 Super Computing 11 面对需要大量计算的科 研问题 如天文计算 天气预测 空间对接等 并行计算是较好的一种解决方案 国防建设 物理科研 天文地理等领域的广泛需求推动了并行计算技术的迅猛发 展 当前流行的并行计算技术主要有两种 一种是大规模并行处理机 MPP Massively Parallel Processor 另 一 种 是 工 作 站 机 群COW Cluster of Workstation 12 其中 以 Cluster 架构来构建的超大规模并行计算机系统是高 性能计算机的主流 我国最新发布的神威蓝光高效能计算机就采用了这一架构 高性能计算机上的程序开发与传统串行程序开发不同 必须同时利用各处理 器中的所有可执行单元 才能充分发挥高性能计算机的最大性能 因此 并行程 序设计采用了两种编程模型 一种是 MPI Message Passing Interface 一种是 OpenMP 13 MPI MPI 是一个编程标准 有着不同的具体工具 比如 MPICH 等 是多主 机联网协同进行并行计算的工具 主要适用于机群系统 当然也可以用于单主机 上多核或者多 CPU 的并行计算 不过效率偏低 它能协调多台主机间的并行计算 因此在并行规模上具有很强的扩展性 能在从个人电脑到世界 TOP100 的超大型 计算机上使用 缺点是使用进程间通信的消息机制协调并行计算 这导致并行效 率低 内存开销大 不直观 编程麻烦 OpenMP 是针对单主机上的多核或者多 CPU 并行计算而设计的工具 也就是 说 OpenMP 更适合单台计算机上共享内存结构的并行计算 由于使用线程间共享 内存的方式协调并行计算 它在多核与多 CPU 结构上的效率很高 内存开销小 编程语句简洁直观 因此 OpenMP 具有编程容易 编译器容易实现 现在最新 版的 C C Fortran 等编译器基本上都内置 OpenMP 支持 的优点 不过 OpenMP 工程硕士学位论文 3 最大的缺点是只能在单台计算机上工作 不能用于集群的并行计算 2006 年 11 月 NVidia 公布了业界的第一个 DirectX 10 GPU 即 Geforce 8800 GTX 14 这是第一块基于 NVidia 的 CUDA 架构构建的 GPU CUDA 架构专门为 GPU 计算设计了一种全新的模块 目的是减轻 GPU 计算中存在的一些局限性 该 GPU 中拥有 128 个单独的 ALU Arithmetic Logic Unit 数学逻辑单元 14 因此非常适合并行计算 而且数值计算的速度远远优于 CPU 这是一个完整的 GPGPU 解决方案 提供了硬件的直接访问接口 而不必像传统方式一样必须依赖 图形 API 接口来实现 GPU 的访问 在架构上采用了一种全新的计算体系结构来 使用 GPU 提供的硬件资源 从而给大规模的数据计算应用提供了一种比 CPU 更 加强大的计算能力 CUDA 采用 C 语言作为编程语言提供大量的高性能计算指令 开发能力 使开发者能够在 GPU 的强大计算能力的基础上建立起一种效率更高的 密集数据计算解决方案 1 3 本文组织结构 第一章 绪论 主要简述研究的目的与意义 国内外研究现状及研究的内容 与目标 第二章 概述 CUDA 并行计算平台的相关知识 第三章 介绍遗传算法的相关知识和实现方法 第四章 介绍使用 CPU 串行编程通过遗传算法解决 TSP 问题 再将串行程 序改编为基于 CUDA 平台的 GPU 并行程序 将实验所得到的结果加以整理并进 行分析说明 第五章 总结全文 并对今后的研究工作做出展望 基于 GPU 的 TSP 遗传算法研究与实现 4 第 2 章 CUDA 并行计算平台 CUDA 表示为 Compute Unified Device Architecture 是一种由显卡厂商 NVIDIA 推出的通用并行计算架构 该架构使 GPU 能够代替 CPU 解决一些复杂 的计算问题 NVIDIA 的 GPU 具有多个流处理器 例如 GeForec 8800GTX 包含了 128 个流处理器 还包含了 CUDA 指令集架构 ISA 15 可以进行高性能的并行 化计算 虽然 CPU 的频率通常比较高 但是执行单元的数目则要少得多 利用 CUDA 并行计算平台 开发人员可以利用 GPU 进行及其复杂的密集运算 因此 在地质勘探 金融证券 天文气象 科学计算 图形图像处理 产品开发等领域 16 CUDA 都具有重要的应用价值 C 语言是应用最广泛的一种高级编程语言 CUDA 平台支持程序开发人员使用 C 语言编写程序 所编写出的程序可以在支持 CUDA 的处理器上以超高性能运行 在信号处理领域 Moreland 等人 17 利用常 规算法在 GPU 上实现了快速傅里叶变换 在有限元分析应用方面 Dimitrik 等 人将模拟地震造成的地震波传播移植至 GeForce 8800GTX 及 GTX 280 上 18 高 阶有限元的一种应用 最近 研究人员利用 GPU 集群实现大规模医学图像 19 整个集群系统包括 16 个节点 聚合计算能力超过 10 个 TFLOPS 本文研究了基于 CUDA 平台的遗传算法解决 TSP 问题 为解决 TSP 问题所 需的大量并行计算提供了一种潜在的选择方案 2 1 CUDA 平台简介 在有计算机帮助人类进行计算的历史中 运算的规模和计算速度每年都在成 几何级数增加 有统计数据表明 每经过 10 年 我们面对的一些应用 其数据规 模的增长和对计算速度的要求差不多会增长 100 倍 这些变化和要求使得人们不 遗余力的为生产出性能更加强大的处理器而孜孜以求 所以 CPU 处理器的主频 时钟速度也在狂飙猛进地提升 但是 随着制造工艺技术的制约以及 CPU 架构本身设计目标的局限 这种时 钟频率的提升很快就碰到了壁垒 从 2001 年至 2003 年 Pentium 4 处理器的时钟 频率从最初的 1 5GHz 提升到了 3GHz 然而从 2003 年到 2005 年 整整 2 年的时 间里 处理器的时钟频率提升的速度骤然放缓 只是从 3GHz 增加到 3 8GHz 处 理器的速度增长宛若已经到了强弩之末 与此同时 随着显卡的发展 GPU 越来越强大 而且 GPU 为显示图像做了 优化 在计算上已经超越了通用的 CPU 如此强大的芯片如果只是作为显卡就太 浪费了 因此 NVIDIA 在开发 GeForce8 系列架构的时候 同时开发了 CUDA 工程硕士学位论文 5 NVIDIA GeForce 8 GPU 开发的时候就考虑到了图形和并行计算两方面的需求 所 以 NVIDIA GeForce 8800 系列发布的时候就宣布了 CUDA 这是一种全新的 GPU 计算开发环境 目前只有 G80 G92 G94 G96 GT200 GF100 GF110 平台 即 Geforce 8 Gecorce GTX590 20 的 NVidia 显卡才能使用 CUDA 工具集的核心是一个 C 语言编译器 G80 中拥有 128 个单独的 ALU 因此非常适合并行计算 而且数值 计算的速度远远优于 CPU CUDA 的 SDK 中的编译器和开发平台支持 Windows Linux 系统 可以与 Visual Studio2005 集成在一起 Geforce8CUDA Compute Unified Device Architecture 是一个新的基础架构 这个架构可以使用 GPU 来解决商业 工业以及科学方面的复杂计算问题 它是一 个完整的 GPGPU 解决方案 提供了硬件的直接访问接口 而不必像传统方式一 样必须依赖图形 API 接口来实现 GPU 的访问 在架构上采用了一种全新的计算 体系结构来使用 GPU 提供的硬件资源 从而给大规模的数据计算应用提供了一种 比 CPU 更加强大的计算能力 CUDA 采用 C 语言作为编程语言提供大量的高性 能计算指令开发能力 使开发者能够在 GPU 的强大计算能力的基础上建立起一种 效率更高的密集数据计算解决方案 CUDA 相对于传统的服务器集群以及超级计算机在性价比 占地空间 功耗 等方面的优势非常明显 CUDA 对于行业的价值 通过 CUDA 和支持 CUDA GPU 两者结合在一起 所有的厂商很容易利用 GPU 强大的计算能力做各种各样的并行 计算工作 这就是最大的价值 这一切使得每个人都可以低成本的拥有自己的桌 面超级计算机成为可能 而不是大家来共享一台大型的超级计算机 正如 NVIDIA Tesla GPU 计算事业部高级产品经理 Sumit Gupta 所言 20 这不是简单的芯片的 性能提升 而是带来了一种全新的 具有革命性的计算模式 如图 2 1 图 2 1 CUDA 在多领域的应用 基于 GPU 的 TSP 遗传算法研究与实现 6 2 2 CUDA 发展背景 在硬件方面 包含 CUDA 架构的显卡已经有多款产品 传统的 OEM 厂商会 将 Tesla 产品整合在他们提供的解决方案中 除此以外 NVIDIA 也有自己专门的 CUDA 计算平台解决方案 如 Telsa S1070 1U 机架服务器 共有 4 个 GPU 卡 共 960 个内核 性能达到 4 万亿次每秒 功耗只有 700 瓦 而如果要达到相同计算 性能 需要一个小服务器集群才能实现 而功耗可能达到几万瓦 另一款产品是 Telsa C1060 可以用到普通的 PC 和工作站中 性能是 957Gflops 功耗只有 160 瓦 21 目前 适合于并行计算的应用已经越来越多 很多在 CPU 上面的应用 如视 频编码的效率非常低 把 H 264 的视频编码转移到 CUDA 上面以后 它的性能比 在 CPU 上快十几倍 这是非常典型的 CUDA 应用 H264 编码强度高 一是它的 编码效率很高 相同的码率 它可以获得更好的品质 二是它需要更多的计算 在这种情况下 原来用 CPU 实现实时 H 264 的编码是比较难的 现在使用 CUDA 可以加快编码的过程 像 IPOD 支持 H 264 的格式 要把一张 DVD 转换为 H 264 格式 用 CPU 来做 需要数个小时才能完成 改用 CUDA 来做 半个小时时间 就可以把一张 DVD 转换完 除此之外 还可以使用 CUDA 通过 PhysX 物理引 擎对物理效果加速 除了可以看见比较逼真的静态场景以外 还可以让动态场景 更加真实 通过物理加速引擎可以获得动态逼真 使很多虚拟场景中的事物动起 来与现实一样 例如水流 烟雾等等 物理加速如果仅仅靠 CPU 来做 是非常难 的 使用 GPU 可以做大规模的物理模拟 让虚拟场景变得栩栩如生 还有更多其 他方面的应用 例如图象 视频等正在开发中 预计不久以后有很多 GPU 计算方 面的应用不断的开发出来 对于企业计算领域 GPU 计算甚至超过了传统的计算机 让许多原来无法解 决的问题现在可以通过 GPU 计算来轻松实现 比如 针对新型流行性疾病如非典 禽流感等 人们总是希望新药物研制的时间越短越好 在天气预报方面 人们希 望预报的精度和准确度越高越好 在金融股票价格分析方面 人们在决定买卖股 票时总是希望越快越好 GPU 计算的出现 使得超级计算机在挑战这些领域极限 方面又进了一步 例如 美国国家癌症研究所通过 GPU 计算将模拟速度提升了 12 倍 等待结果的时间从原来的 2 个小时缩短到了 10 分钟 美国国家大气研究 中心的气象研究和预报模型 WRF 尽管仅仅将 1 通过 CUDA 来实现 但其总体 速度却提升了 20 节省了一个星期的分析时间 在评估整个美国期权市场时 Hanweck 原来计划用价值 26 2 万美元的 600 CPU 集群来处理 而实际采用三台 nvidia Telsa S870 后 机架空间节省了 9 倍 硬件成本节省了 6 倍 图 2 2 展示了 NVIDIA 的 CUDA 在某些领域获得了巨大成功 22 工程硕士学位论文 7 图 2 2 Tesla 系列 GPU 的成果 2 3 CUDA 编程模型 CUDA 是专门针对 GPU 来进行编程的平台 它最大的特点是 CUDA 如果在 GPU 计算方面来说 是所谓的异构计算系统 它和 CPU 有很大的不同 CPU 只 是针对一个处理器编程 CUDA 是针对 GPU 计算得的 但是它包含 GPU 和 CPU 两部分的代码 顺序计算和一些数据的管理等等代码在 CPU 上运行 而核心的并 行计算部分在 GPU 上运行 如图 2 3 在编辑的时候编译器会把 CPU 代码和 GPU 代码分开 GPU 代码会被编译成成 GPU 的目标代码 CPU 代码还是需要其他的 C 语言编译系统来编译 最新的 CUDA 版本也支持多核 CPU 这可能是最大的 不同 CUDA 一定是需要 CPU 来参与的 叫异构计算环节 所谓异构计算 就是 CPU 和 GPU 两个架构和指令集都是不一样的 但是他们共同协同动作来解决同 一个问题 至于说 CUDA 和 DirectX OpenGL 这些 3D API 的关系 对于 CUDA 来说 是不需要 3D API 的 但是 CUDA 可以很容易和 3D API 配合使用 23 图 2 3 Cuda 软件架构图 基于 GPU 的 TSP 遗传算法研究与实现 8 CUDA 提供了两种不同类型的 API 接口 一种是高级的 API CUDA 运行的 API 另一种是低级 API CUDA 的驱动 API 高级的 API 是在低级 API 之上所执行的 每一个调用的函数在运行的时候都 可以被驱动 API 细分为若干个基本的指令 驱动 API 结合了更多的管理功能 它会请求 GPU 做很多处理工作 但它的 好处是更加的灵活 它可以给程序员更多额外的控制 无论如何 这两种 API 都 可以沟通 OpenGL 和 Direct3D 的资源 CUDA 的软件层 目前 CUDA 的 2 0 版提供了两个标准的数学运算库 CUFFT 离散快速傅立叶变换 和 CUBLAS 离散基本线性计算 的实现 2 这两 个数学运算库所解决的是典型的大规模的并行计算问题 也是在密集数据计算中 非常常见的计算类型 开发人员在开发库的基础上可以快速 方便的建立起自己 的计算应用 此外 开发人员也可以在 CUDA 的技术基础上实现出更多的开发库 CUBLAS 是一套函数库 它是基于模块化的运行在 GPU 上的线性计算函数 库 它支持 NVIDIA 的 GPU 的计算资源 该库在 API 层次上是能够 自给自足 即不必与 CUDA 直接交互 应用程序使用 CUBLAS 库的基本模型是在 GPU 内存 空间中创建矩阵和矢量对象 使用数据填充它们 调用一定顺序的 CUBLAS 函数 最后把结果从 GPU 内存上载到主机 要实现这个过程 CUBLAS 提供了一些帮 助函数 用于在 GPU 空间中创建和销毁对象 以及对这些对象写入和读出数据 GPU 线程是非常轻量的 也就是说的创建和线程的切换 基本不需要系统开 销 线程的创建 撤销和切换几乎是立刻的 CPU 的程序多线程的创建和注销有 很多代码 GPU 线程和 CPU 程序的线程不太一样 即使是四核 CPU 如果跑非 常多线程的话 线程的管理就会成为严重的负担 GPU 计算 需要上千个甚至上 万个线程才可以把 GPU 填满 这是非常大的不同 所以大规模的并行计算特别适 用于 CUDA 的这种架构 2 3 CUDA 内存模型 除了编程模型 CUDA 也规定了存储器模型 即内存模型 在执行期间 CUDA 线程可能访问来自多个存储器空间的数据 如图 2 4 所示 工程硕士学位论文 9 图 2 4 CUDA 的内存模型 每一个线程拥有自己的私有存储器寄存器和局部存储器 每一个线程块拥有 一块共享存储器 shared memory 最后 grid 中所有的线程都可以访问同一块 全局存储器 global memory 除此以外 还有两种可以被所有线程访问的只读 存储器 常数存储器 constant memory 和纹理存储器 Texture memory 2 它 们分别为不同的应用进行了优化 全局存储器 常数存储器和纹理存储器中的值 在一个内核函数执行完成后将被继续保持 可以被同一程序中的其他内核函数调 用 表 2 1 给出了这 8 种存储器的位置 缓存情况 访问权限及生存域 表 2 1 CUDA 存储器功能列表 存储器 位置 拥有缓存访问权限 变量生存周期 register GPU 片内 N A Device 可读 写 与 thread 相同 Local memory 板载显存 无 Device 可读 写 与 thread 相同 Shared memory GPU 片内 N A Device 可读 写 与 block 相同 Constant memory 板载显存 有 Device 可读 host 可读 写 可在程序中保持 Texture memory 板载显存 有 Device 可读 host 可读 写 可在程序中保持 Global memory 板载显存 无 Device 可 读 写 host 可读 写 可在程序中保持 Host memory Host 内存 无 Host 可读 写 可在程序中保持 Pinned memory Host 内存 无 host 可读 写 可在程序中保持 注 N A Register 和 shared memory 都是 GPU 片上高速存储器 基于 GPU 的 TSP 遗传算法研究与实现 10 通过 mapped memory 实现的 zero copy 功能 某些 GPU 可以直接在 kernel 中 访问 page locked memory 2 3 1 寄存器 寄存器 register 是 GPU 片上告诉缓存器 执行单元可以以极低的延迟访问 寄存器 寄存器的基本单元是寄存器文件 register file 每个寄存器文件大小为 32bit 在 CUDA Toolkit 1 0 1 1 版本硬件中 每 SM 中寄存器文件数量为 8192 而在 CUDA Toolkit 1 2 1 3 硬件中 每 SM 中寄存器文件数量为 16384 寄存器文 件数量虽然可观 但平均分给并行执行的线程 每个线程拥有的数量就非常有限 了 编程时 不要为每个线程分配过多的私有变量 2 3 2 局部存储器 局部存储器 local memory 对于每个线程都是私有的 如果寄存器被消耗 完 数据将被存储在局部存储器中 如果每个线程使用了过多的寄存器 或声明 了大型结构体或数组 或者编译器无法确定数组的大小 线程的私有数据就有可 能会被分配到 local memory 中 一个线程的输入和中间变量将被保存在寄存器或 者局部存储器中 局部存储器中的数据被保存在显存中 而不是片上的寄存器或 者缓存中 因此对 local memory 的访问速度很慢 2 3 3 共享存储器 共享存储器 shared memory 也是 GPU 片内的高速存储器 它是一块可以 被同一 block 中的所有线程访问的可读写存储器 访问共享存储器的速度几乎和 访问寄存器一样快 是实现线程间通信的延迟最小的方法 共享存储器可用于实 现多种功能 如用于保存共用的计数器 例如计算循环迭代次数 或者 block 的 共用结果 例如归约运算的结果 2 3 4 全局存储器 全局存储器 global memory 位于显存 占据了显存的绝大部分 CPU GPU 都可以进行读写访问 整个网格中的任意线程都能读写全局存储器的任意位 置由于全局存储器是可写的 在目前的架构中 全局存储器没有缓存 Kernel 之 间的数据传递 可以通过 global memory 实现 如图 2 5 所示 工程硕士学位论文 11 图 2 5 全局存储器示意图 2 3 5 常数存储器 常数存储器 constant memory 是只读的地址空间 常数存储器中的数据位 于显存 但拥有缓存加速 常数存储器的空间较小 只有 64KB 在 CUDA 程序 中用于存储需要频繁访问的只读参数 当来自同一 half warp 的线程访问常数存储 器中的同一数据时 如果发生缓存命中 那么只需要一个周期就可以获得数据 2 3 6 纹理存储器 纹理存储器 texture memory 是一种只读存储器 由 GPU 用于纹理渲染的 图形专用单元发展而来 具备一些特殊功能 它并不是一块专门的存储器 而是 牵涉到显存 两级纹理缓存 纹理拾取单元的纹理流水线 纹理存储器中的数据 以一维 二维或者三维数组的形式存储在显存中 可以通过缓存加速访问 并且 可以声明大小比常数存储器要大得多 在通用计算中 纹理存储器非常适合实现 图像处理和查找表 对大量数据的随机访问或非对齐访问也有良好的加速效果 基于 GPU 的 TSP 遗传算法研究与实现 12 2 4 小结 本章对本文研究所涉及到的基本概念作了初步介绍 这些内容包括 CUDA 平台的简单介绍 CUDA 平台的编程模型和内存模型 以下各章将对本文的研究 结果详细介绍 工程硕士学位论文 13 第 3 章 遗传算法 3 1 遗传算法简介 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全 局优化概率搜索算法 它的优化过程是对生物进化机制的模仿 其基本思想源于 自然界的生物进化 由于自然界中的生物显示了它们对于环境的优异自适应能力 受其启发 人们开始研究生物生存的机理 模拟其行为 60 年代美国密执安大学 的 Holland 教授等通过研究自然和人工系统的自适应行为 模拟群体遗传选择和 自然淘汰的进化论观点创立了遗传算法 取得了令人瞩目的成果 24 70 年代 De Jong 用遗传算法的思想在计算机上进行了大量的纯数值函数计算试验 25 在一系 列工作基础上 80 年代 Goldberg 进行归纳总结形成了遗传算法的基本框架 26 下 面将首先介绍遗传算法的生物学基础 然后在它的基础之上 介绍遗传算法的工 作原理 3 1 1 遗传算法的生物学基础 在自然界中生物从其亲代继承特性或性状 这种现象称为遗传 Heredity 研究这种现象的科学叫遗传学 Genetics 27 在构成生物的细胞 Cell 中含有 染色体 Chromosome 生物的遗传信息都包含在染色体中 遗传信息由基因 Gene 组成 基因是 DNA Deoxyribonucleic Acid 或 RNA Ribonucleic Acid 中占有一定位置的基本遗传单位 在 DNA 中遗传信息在长链上按照一定模式排 列 即进行了遗传编码 遗传基因在染色体中占据的位置称为基因座 Locus 同一个基因座可能具有的全部基因称为等位基因 Allele 一个细胞核中所有染 色体携带的遗传信息的全体称为基因组 Genome 在细胞分裂的过程中遗传物质 DNA 通过复制 Reproduction 转移到新的细 胞中 但是在复制过程中有可能出现复制差错 虽然这种情况的概率很小 有性 繁殖生物在繁殖下一代时两个同源染色体通过交叉 Crossover 重组 形成两个 新的染色体 生物在其延续生存的过程中 逐渐适应生存环境使品质不断改良这种现象称 为进化 Evolution 生物进化是以集团的形式共同进行的 这样的一个团体称为 群体 Population 群体中的单个生物称为个体 Individual 每个个体对于生 存环境的适应能力称为适应度 通过自然选择 有利于生存环境的基因将增多 不利于生存环境的基因会减少 基于 GPU 的 TSP 遗传算法研究与实现 14 3 1 2 遗传算法的工作原理 前面论述了生物进化的原理 下面介绍遗传算法的工作原理 生物的进化是以集团为主体的 相应的遗传算法的运算对象是由 M 个个体 所组成的集合称为群体 与生物一代一代的自然进化过程相似 遗传算法的运算 过程也是一个反复迭代过程 第 t 代群体记做 P t 经过一代遗传和进化后得到 第 t 1 代群体 记为 P t 1 这个群体不断经过遗传和进化操作 并且每次都按 照优胜劣汰的规则将适应度较高的个体更多的遗传到下一代 最后就能得到一个 优良的个体 它达到或接近于问题的最优解 生物的进化过程主要是通过染色体的交叉和变异来完成的 在遗传算法中 从父代 P t 产生下一代 P t 1 主要通过选择 交叉 变异操作来实现 选择操作根据个体的适应度决定遗传到下一代的个体 交叉操作随机搭配群 体内的个体以某个概率交换他们的部分染色体 得到新的个体 变异操作就是对 于群体内的每个个体 以某个概率改变基因座上的基因值为其他等位基因 从而 产生新的个体 遗传算法的运算过程如图 3 1 所示 工程硕士学位论文 15 图 3 1 遗传算法的运算过程 遗传算法首先初始化种群 P 0 随机生成 M 个个体 将进化代数计数器 t 置 零 设置进化终止条件 然后进行个体评价 计算 P t 中个体适应度 将选择操 作作用于群体 P t 并得到输出的种群 将交叉操作作用于选择的输出种群 将 变异操作作用于交叉的输出种群 则得到下一代群体 P t 1 最后进行终止条件 判定 如果达到终止条件则停止进化 输出适应度最大个体为最优解 如果没有 达到终止条件 则对新的群体使用遗传操作 重复进行 一直到满足终止条件为 止 由于遗传算法都是通过对生物的遗传和进化过程中选择 交叉 变异机理的 模仿 来完成对问题最优解的自适应搜索过程 基于这个共同特点 Goldberg 总