《科学计算与企业级应用的并行优化.html.pdf》由会员分享,可在线阅读,更多相关《科学计算与企业级应用的并行优化.html.pdf(23页珍藏版)》请在三一文库上搜索。
1、序 到这里,终于可以松一口气了,一个持续多年的工作总算可以告一段落了。本系列起源于我2012年想写的并行乱弹一 书,乱弹是乱弹琴的意思。按我的本意,并不想把它写成一本非常严谨的著作,当时更无意出版,因此并不是非常注意全书逻辑 的严密性,虽然经过我和编辑的多次修改,但想必问题依旧难以避免,在此诚恳地请求读者谅解。 本系列的3本书相互之间有联系,也有其独立性:并行算法设计与性能优化介绍常见的串行代码优化方法和并行算法的 设计;并行编程方法与优化实践介绍常见的向量化和并行编程环境及一些实例;科学计算与企业级应用的并行优化则介 绍领域相关的算法与应用的性能优化。 如果说要写一本简短的武侠小说来描写主角
2、是如何学习这3本“秘笈”的话,我想故事是这样的:在2015年,主角是某位内 向宅男码农hpc,因为程序速度太慢天天被产品经理骂,受项目经理白眼,每天工作到晚上10点,遭到家人埋怨。在某个月黑风 高的晚上,某条街道上那位江湖人称“风辰”的“HPC帮”护法长老收hpc为不记名弟子,并传授给hpc并行算法设计与性能 优化并行编程方法与优化实践及科学计算与企业级应用的并行优化3本“秘笈”,“风辰”临走时收了传功费用1024 万元。hpc如获至宝,休假一月潜心修炼。一月后出关,容光焕发,程序速度大幅度提升,产品经理天天请吃大餐,项目经理忙 着加项目奖金。此后,hpc每天下午5点即下班回家,修身养性,陪家
3、人一起吃饭、购物。 愿这3本书能够真正成为改变读者生活的良师益友! 风辰 2015年5月17日于深圳 前言 IT行业急需这本书 和本系列的前两本书一样,在解释为什么笔者认为软件工程师需要这本书之前,笔者先来介绍并行、并发和代码性能优化这 3个概念,因为理解这3个概念是阅读本系列3本书的基础。 并行对应的英文单词是parallelism,是指在具有多个处理单元的系统上,通过将计算或数据划分为多个部分,将各个部分 分配到不同的处理单元上,各处理单元相互协作,同时运行,以达到加快求解速度或者提高求解问题规模的目的。 并发对应的英文单词是concurrency,是指在一个处理单元上运行多个应用,各应用
4、分时占用处理单元,是一种微观上串 行、宏观上并行的模式,有时也称其为时间上串行、空间上并行。 代码性能优化是指通过调整源代码,使得其生成的机器指令能够更高效地执行,通常高效是指执行时间更少、使用的存储 器更少或能够计算更大规模的问题。 从大的方面来说,并行和并发都是代码性能优化的一种方式,但是今天并行和并发已经是如此重要,以至于需要“开宗立 派”。为了明晰并行、并发和代码性能优化的边界,在本书中,代码性能优化特指除了并行和并发以外的代码优化方法,比如向 量化和提高指令流水线效率。在本书中,笔者将向量化独立出来解说。 2003年以前,在摩尔定律的作用下,单核标量处理器的性能持续提升,软件开发人员
5、只需要写好软件,而性能的提升就等 待下次硬件更新来解决,在2003年之前的几十年里,这种“免费午餐”模式一直在持续。2003年后,主要由于功耗的原因,这 种“免费午餐”已经不复存在。为了生存,各硬件生产商不得不采用各种方式提高硬件的计算能力。目前最流行的3种方式如 下: 1)让处理器在一个周期处理多条指令,多条指令可相同可不同。如Intel Haswell处理器一个周期可执行4条整数加法指 令、两条浮点乘加指令,而访存和运算指令也可同时执行。 2)使用向量指令,主要是SIMD和VLIW技术。SIMD技术将处理器一次能够处理的数据位数从字长扩大到128或256位,也 就提升了计算能力。 3)在同
6、一个芯片中集成多个处理单元,根据集成方式的不同,相应地称为多核或多路处理器。多核处理器是如此重要,以 至于现在即使是手机上的嵌入式ARM处理器都已经是四核或八核了。 目前绝大部分应用软件都是串行的,因为串行执行过程符合人类的思维习惯,易于理解、分析和验证。由于串行软件只能在 多核CPU中的一个核上运行,和2003年以前的CPU没有多少区别,这意味着花多核CPU的价钱买到了单核的性能。通过多核技 术,硬件生产商成功地将提高实际计算能力的任务转嫁给软件开发人员,而软件开发人员没有选择,只有直面挑战。 标量单核的计算能力没有办法继续大幅度提升,而应用对硬件计算能力的需求依旧在提升,这是个实实在在的矛
7、盾。在可见 的将来,要解决这个矛盾,软件开发人员只有代码性能优化和并行可以选择。代码性能优化并不能利用多核CPU的全部计算能 力,它也不要求软件开发人员掌握并行开发技术,另外通常也无需对软件架构做改动,而且串行代码优化有时能够获得非常好的 性能(如果原来的代码写得很差的话),因此相比采用并行技术,应当优先选择串行代码性能优化。一般来说,采用并行技术获 得的性能加速不超过核数,这是一个非常大的限制,因为目前CPU硬件生产商最多只能集成十几、几十个核。 从2006年开始,可编程的GPU越来越得到大众的认可。GPU是图形处理单元(Graphics Processing Unit)的简称,最初 主要用
8、于图形渲染。自20世纪90年代开始,NVIDIA、AMD(ATI)等GPU生产商对硬件和软件加以改进,GPU的可编程能力 不断提高,GPGPU(General-purpose computing on graphics processing units)比以前容易许多。另外由于GPU具有比 CPU强大的峰值计算能力,近年来引起了许多科研人员和企业的兴趣。 近两三年来,在互联网企业中,GPU和并行计算越来越受到重视。无论是国外的Google、Facebook,还是国内的百度、 腾讯、阿里和360,都在使用代码性能优化、并行计算和GPU来完成以前不能完成的任务。 10年前,并行计算还是实验室里教授
9、们的研究对象,而今天多核处理器和GPU的普及已经使得普通人就可以研究它们。对 于软件开发人员来说,如果不掌握并行计算和代码性能优化技术,在不久的将来就会被淘汰。 作为本系列的压轴之作,本书专注于领域相关的算法和应用的并行与性能优化。笔者介绍了如何优化线性代数、偏微分方程 求解、分子动力学和机器学习领域的一些重要算法。 如果以武侠中的功夫来比喻的话,本系列的第一本书并行算法设计与性能优化专注于理论基础和实践的结合,是“内 功”和“心法”的修炼;本系列的第二本书并行编程方法与优化实践专注于程序设计语言的核心内容的应用,是“招式”的 学习;而本书则是“内功心法”和“招式”的具体运用。“内功心法”好意
10、味着基础好、潜力大,以后发展空间广泛;“招 式”好则能够通过“奇招”“怪招”解决问题;而只有将“内功心法”和“招式”完美融合,做到“心中无招而手中有招,无招 胜有招,无招即有招”,才能成为异构并行计算这个领域真正的集大成者。愿读者和笔者一起向这个目标前进。 本书完全是“干货”,是一本真正将业界最佳实践和“只可意会,不可言传”的领域知识简洁明了地贡献出来的著作。为了 帮助读者理解,本书使用了大量的示例。开发人员通常比较忙,因此本书力求简洁明了,点到为止。 读者对象 由于多核处理器和GPU已经非常便宜,而代码性能优化、向量化和并行已经深入IT行业的骨髓,所有IT行业的从业者都应当 阅读本书。如果非
11、要列一个读者清单,笔者认为下列人员应当阅读本书: 互联网及传统行业的IT从业者,尤其是希望将应用移植到多核向量处理器的软件开发人员; 对向量化和并行化感兴趣的职业工作者; 线性代数、偏微分方程、分子动力学和机器学习相关领域的科技工作者; 大中专院校及研究所的学生、教师; 关注异构并行计算和高性能计算的人们。 如何阅读本书 本系列包括3本书,本书是此系列的第三本。本书重点介绍如何利用目前主流的C语言的各种特定硬件或平台的向量化扩 展、并行化库,来设计性能优良的向量化和并行代码。而本系列的第一本并行算法设计与代码优化关注并行优化和并行计算 相关的理论、算法设计及高层次的实践经验;本系列第二本并行编
12、程方法与优化实践关注C程序设计语言的向量化和并行化 扩展及算法到硬件的映射;本书则关注如何将线性代数、偏微分方程求解、分子动力学和机器学习领域的常见算法优良地实现出 来。 本书不但包括如何使用SSE/AVX向量化扩展、OpenMP编译制导语句来优化运行在X86多核处理器上的代码性能,还包括 使用NEON向量化扩展、OpenMP编译制导语句优化运行在移动处理器(ARM)的代码性能,以及使用CUDA和OpenCL优化 运行在图形处理器(GPU)的代码性能。笔者希望通过这种方式能够让阅读本书的软件开发人员了解和掌握如何将常见算法映 射到具体硬件上以获得高性能,以及如何依据硬件和算法的特点进行代码性能
13、优化。 本书分为以下几章: 第1章 介绍常见的并行编程基于的多核/众核向量处理器的架构、OpenCL程序如何映射到这些平台上执行及OpenCL程序 在这些硬件上运行时具有哪些不同。先介绍Intel Haswell、ARM A15、Intel MIC、AMD GCN GPU和NVIDIA Kepler/Maxwell GPU的架构。然后介绍OpenCL程序如何映射到Intel Haswell处理器、AMD GCN GPU和NVIDIA Kepler/Maxwell GPU上执行。最后介绍OpenCL程序在这些处理器上运行时的细微区别。 第2章 介绍如何在X86、ARM和GPU上优化常见的线性代数
14、运算,如计算稀疏矩阵向量乘法,求解下三角线性方程组,计 算矩阵乘法等。对于电子电路模拟、计算流体力学相关的领域来说,稀疏矩阵向量乘法是非常重要的。本章还介绍如何在主流的 X86、ARM和NVIDIA GPU上优化稀疏矩阵向量乘法运算。 第3章 介绍如何在X86和GPU处理器上优化偏微分方程的求解,主要介绍如何求解热传递问题和三维Stencil问题。 第4章 介绍如何在X86处理器和GPU上优化常见的分子动力学算法,如邻居搜索、范德华力计算、键长伸缩力计算和径向 分布函数计算。 第5章 介绍如何在X86、ARM和GPU上优化常见的机器学习算法,如k-means、KNN、二维卷积和四维卷积的计算性
15、 能。最后介绍多GPU并行卷积神经网络的常见方法,以及如何使用数据并行来使用多GPU并行优化Caffe。 对于对并行和代码性能优化不太了解的人员,笔者建议先阅读本系列的第一本书并行算法设计与性能优化1和第二本书 并行编程方法与优化实践2。对于对并行或代码性能优化非常了解的人员,可按照自己相关的领域选择对应的章节阅读。 勘误和支持 由于笔者的水平有限、工作繁忙、编写时间仓促,而向量化、并行和代码性能优化又是一个正在高速发展的、和硬件及算法 密切相关的、影响因素非常多、博大精深、兼具个人特色的领域,许多问题还没有统一的解决方案,虽然笔者已经努力确认很多 细节,但书中难免会出现一些不准确的地方,甚至
16、是错误,恳请读者批评指正。你可以将书中的错误或写得不好的地方通过邮件 发送到,微博联系“异构并行计算-风辰”或微信联系“风辰”,以便再版时修正,笔者会尽快回复大 家。如果有更多的宝贵意见,也欢迎发送邮件,期待能够得到读者朋友们真挚的反馈。 致谢 首先要感谢我的老婆,她改变了我的人生轨迹,让我意识到人生有如此多的乐趣。如果不是她容忍我晚上10点下班回家后 还要接着写书,此系列的出版估计得晚个两三年。 感谢我的母校中国地质大学(武汉)的图书馆,那是我对并行计算产生兴趣的地方。感谢我的母校中国科学院研究生院和中 国科学院图书馆,在那里我奠定了从事并行计算事业的基础。 感谢我的朋友陈实富、高洋等,如果
17、没有你们,我还需要更多时间来提升水平。感谢我的老板王鹏、吴韧和汤晓欧,在这些 技术大佬和“人生赢家”的指导下,我才会成长得如此迅速。 感谢我在英伟达(NVIDIA)时的实习生、百度时的实习生和我现在的同事及下属,如果不是你们的努力工作,我没有时间 来写这个系列。 感谢机械工业出版社华章公司的高婧雅和杨福川老师,我本无意出版此书,是你们引导我将这本书付梓成书,是你们帮我修 改书稿,让它变得可读、可理解,是你们帮我修正错误,是你们的鼓励和帮助使得我顺利完成全部书稿。 最后感谢我的爸爸、妈妈、姥姥、姥爷、奶奶、爷爷,感谢你们将我培养成人,并时时刻刻为我提供精神力量! 谨以此书献给我最爱的家人,以及众
18、多热爱代码性能优化、向量化、并行计算的朋友们!愿你们快乐地阅读本书! 风辰 1 本书由机械工业出版社华章公司出版,书号978-7-111-50102-2。 2 本书由机械工业出版社华章公司出版,书号978-7-111-50194-7。 第1章 多核向量处理器架构 多核向量处理器的出现是为了更好地提供程序所需的性能,而处理器的峰值性能、程序代码能够实现的性能则与硬件的特 性、组织结构紧密相关。 硬件的性能最终由程序代码实现。代码中的各个部分(如访存、计算)如何在硬件上执行,在硬件上执行时,其具体行为如 何;这些问题的答案都影响了代码的最终性能。目前看来只有OpenCL才有可能在主流的多核向量处理
19、器(CPU、MIC、GPU、 FPGA等)上都得到支持(即一份代码可以在这些平台上运行),故本章只介绍OpenCL程序如何映射到CPU和GPU上执行。 处理器和程序是两个相互独立、而又相互联系的事物。在计算机编程的发展史上,有些看起来相互矛盾的几个现象一直在共 同发展,即: 1)程序要独立于硬件,不能过分依赖硬件。为了更好地达到这一目标,有解释型编程语言、运行时编译(Just In Time,JIT)等技术支持,如CUDA的JIT驱动能够编译PTX为可执行代码,Python和Bash会解释执行代码,Java虚拟机和C#的 CRT则上升到另外一个层面。 2)依据硬件的特性设计程序。为了发挥硬件的
20、性能,许多软件开发人员不得不依据硬件的特性来设计程序,比如X86处理 器是否支持popcount(用来计算二进制表示的数据中1的数量)就可能导致完全不同的算法设计;在基于GPU的异构并行计算 平台上,PCI-E的带宽在很大程度上影响了算法的设计策略。 3)依据程序来设计硬件。为了让程序在自家的处理器上运行得更快,硬件生产商会依据一些典型的应用的计算特点来设计 处理器,让处理器在这些典型的应用上性能非常好。这类典型的应用有Stencil、矩阵乘等。 从某种程度上说,这些现象是相互矛盾的,一方面要求独立于硬件,另一方面又要求依赖硬件;从另外一方面来说,这些现 象又是相互融合的,软件开发人员依据硬件
21、设计程序和硬件生产商依据典型应用程序来设计硬件都是为了让应用的计算性能更 优;而不同的编程语言希望独立于硬件则是为了让使用该语言编写的应用能够运行在更多的平台上。 本章将介绍目前市场上的主流多核向量处理器(如AMD GPU、NVIDIA GPU、Intel MIC、ARM A15 CPU和Intel Haswell)的硬件组织架构,以及OpenCL程序如何映射到这些硬件上执行。为简单起见,本章只介绍和性能优化相关的部分。 1.1 众核系统结构 众核是指处理器核数比较多,通常指处理器核心数量在几十个或以上。目前主流的众核处理器都是多核向量处理器,如 NVIDIA和AMD的GPU、Intel的MI
22、C等。 目前的众核处理器都是通过PCI-E总线连到主板上,作为CPU控制的一个硬件加速器使用。Sandy Bridge已经完全集成了内 存控制器和IOH,这意味着连接到不同的CPU上的众核处理器会连接到不同的IOH(I/O Hub)。如图1-1所示为一种简单的两 个GPU连到两个处理器的情形。 在目前的Intel和AMD的X86处理器之间,分别通过QPI总线和HT总线连接多个X86多核向量处理器。由于处理器集成了内 存控制器,因此在多路处理器上编程时最好启用NUMA特性,编程时要考虑NUMA的影响。 图1-1 多GPU多socket组织结构图 在某些版本的Intel主板上,由于QPI总线的原因
23、,多个众核处理器之间通过QPI交换数据时,必须通过内存而不能使用 DMA传输。 在Sandy Bridge处理器上由于IOH的原因,连接的同一IOH上的众核处理器之间通过DMA传输的带宽有可能比通过内存中 转的带宽要差。 通常GPU操作显存而不是内存,而程序开始执行时数据通常保存在内存上,这就需要将数据从CPU内存传入GPU显存。目 前这类数据传输由PCI-E总线(不包括APU的Fusion Compute Link总线)负责,如图1-1所示。PCI-E 2.0规范中,每个通道的 数据传输速度达到了500.0 MB/s,这样PCI-E 2.016插槽能够提供8 GB/s(0.516 GB/s)
24、的带宽,即有效带宽为8 GB/s。但 是由于PCI-E数据封包及运行时操作系统的影响,实际可用的带宽最多为5 GB/s6 GB/s,慢的可能为2 GB/s3 GB/s(PCI-E 2.016)。PCI-E 3.0规范的上下行数据带宽均为16 GB/s,实测最高传输速度可达近12 GB/s。 1.2 众核架构的一致性 不同的厂家生产的众核产品具有不同的架构名词、编程环境名词,但是从架构的某些抽象上来说,几乎都是一致的,这称为 众核架构的一致性。众核架构的一致性非常重要,如果每种众核架构都是完全不相同的,那么程序开发人员和优化人员就需要了 解每一种众核架构的特点才能在上面开发应用,以及优化运行在某
25、种众核处理器架构上的应用,这种代价的巨大可想而知。同时 众核架构的一致性也为OpenCL这种通用的众核架构编程环境的存在提供了土壤,而OpenCL的出现减少了在不同的众核架构间 移植程序的代价。 不同的处理器生产商采用的这种众核架构的一致性既有现实应用的特点,又由计算机体系结构的理论所决定。 1)从应用来说:不同的应用具有不同的特点,有的是计算密集型,有的是数据访问密集型。有的拥有复杂的逻辑控制结 构;有的逻辑结构简单,但是数据量或计算量大。今天人类产生的数据的数量已经越来越大,这些数据由大量人类产生,因此其 天生具有并行性,非常适合多核处理;数据通常具有不同的特点,也有维度,故适合向量化。
26、2)从计算机体系结构来说:不同架构的计算机适合处理的工作负载具有不同类型,但是计算机本质上是利用应用中不同层 次的并行性,如指令级并行、数据并行和线程级并行。另外现代计算机设计中提升单机硬件性能的两大主要手段就是多核并行和 SIMD并行,多核并行编程通常需要使用线程级并行API,而SIMD并行则需要利用应用中的数据并行。 无论是从应用特点的角度,还是从计算机体系结构的角度来说,线程并行和SIMD并行是所有众核架构必须具有的特性。而 一种处理器架构很难处理不同类型的负载,因此异构并行计算架构已经越来越得到业界的重视。 1.异构并行计算架构 异构并行计算架构包含两个方面的内容:异构和并行。异构是指
27、计算系统上具有两种或两种以上不同特点的处理器。目前来 说,异构主要是指CPU+加速器;CPU主要指X86、Power、ARM等,现代的X86和Power处理器已经能够支持多种加速器;加 速器主要指GPU、Cell和FPGA等众核处理器。并行是指无论是要发挥CPU的峰值性能,还是要发挥加速器的峰值性能,都要使 用并行的编程方式,因为绝大多数的加速器都是众核处理器。 由于异构系统具有多种不同架构的处理器,不同架构处理器具有不同的特点,因此如果要发挥处理器的峰值性能,编程时算 法映射也会有所不同。由于异构系统的出现时间比较短,目前编译器方面的研究也不多,这些都增加了软件设计人员的负担。 2.多核并行
28、+SIMD并行 由于制造工艺和提升主频遇到的挑战,目前计算机提升性能的方式主要是将多个单核的处理器集成在一起,这称为多核。为 了增加多个单核处理器间协作的性能,集成起来的多个单核处理器会共享一些组件,比如缓存、执行单元等,这种特点反映在多 个层次上。由于协作导致的通信消耗,使得不能无休止地集成处理器。在多核X86上,目前能够集成的单核处理器数量为8左右 (单socket)。为了进一步提升性能,生产商又改造主板,使得一个主板上能够安装多个多核处理器,通常称为多路。 在通过多核提升性能的同时,生产商还在单核中集成多个向量处理单元来提升性能,每个向量中的不同处理单元必须执行相 同的逻辑路径,这称为S
29、IMD。 对多核处理器来说,每个处理器可独立执行不同的任务,而SIMD单元却必须共同执行同一操作。故要发挥多核向量处理器 的性能,则必须同时考虑多核并行和SIMD并行。 现代的GPU具有多个计算单元(SM,CU),而每个计算单元又是一个SIMD处理器。GPU和X86 CPU的不同在于:在基于 GPU编程时无需知道SIMD单元的宽度。 1.3 多核向量处理器架构 计算机架构可简单分为两个部分: 1)指令集架构(Instruction Set Architecture,ISA)。指令集架构确定了处理器原生支持哪些指令(功能),如支持哪 些寻址方式、哪些计算指令等。 2)实现。实现也被称为微架构(m
30、icroarchitecture),描述了处理器的硬件如何组织,各个组件的数量。比如处理器具有 几级缓存,每级缓存的容量、吞吐量、映射策略、替换策略及缓存结构等。计算机体系结构中的实现决定了硬件的峰值性能和程 序是否容易发挥硬件性能。 本节主要介绍主流多核向量处理器的实现,比如多核处理器如何组织、缓存层次结构、核心的计算性能等。 1.4 Intel MIC架构 由于GPU给予Intel太多的压力,长期没有对应的竞争产品,Intel在高性能计算方面的收入下降,为了保证利润,Intel的 MIC项目给予了回应。 MIC又称为Xeon Phi,它和GPU一样,也是安装在PCI-E总线上,并且使用GD
31、DR5显存。另外,MIC基于Intel以前的显卡 项目Larrabee。 对MIC来说,架构上基于1993年的奔腾CPU架构,但是加入了64位支持,并且每核心使用4个硬件线程,通过线程的切换来 隐藏延时。 1.5 OpenCL程序在多核向量处理器上的映射 硬件的架构决定了程序最终如何执行,这包括CUDA和OpenCL的抽象如何映射到现实的设备上。对于传统的基于高级语言 的CPU编程而言,硬件是完全透明的,软件开发除了优化性能时需要了解一些高层的抽象外,几乎不关心底层的硬件如何运 作。而在使用OpenCL或CUDA进行基于GPU的编程时,开发人员需要了解一些底层的抽象,这一方面能够帮助理解程序的
32、行 为;另一方面能够让他们明白CUDA和OpenCL能够做什么,不能够做什么,而最重要的一点是能够写出可扩展的、稳定的高性 能程序。 OpenCL程序无论是在不同的CPU上执行,还是在不同的GPU上执行,它们都有相似的地方。笔者尝试过把这些细节融合在 一起介绍,最终发现结果比较混乱和模糊,因此推倒重来,采用了现在这种分别介绍的模式。分别介绍会增加篇幅,但是却能够 让关注某一方面的读者只阅读感兴趣的内容。 1.6 OpenCL程序在各众核硬件上执行的区别 虽然OpenCL是平台中立的,但是为了获得好的性能,需要了解不同的生产商的产品的特点,同时在编译时利用宏也可以获 得很好的可移植性。本节将以提
33、升性能为目的介绍AMD和NVIDIA的OpenCL实现的不同点。 1.索引空间、工作组和工作项的映射 在AMD和NVIDIA的GPU上,索引空间内的所有线程映射到一个GPU上,索引空间内的线程划分为工作组,每个工作组在 一个CU(NVIDIA GPU上为Streaming Multiprocessor,AMD GPU上为SIMD引擎)上执行,工作组内的工作项映射为一个 PE。由于Intel和AMD的X86 CPU具有SIMD单元,每个工作项可能映射到SIMD单元的一个槽中。 在Intel和AMD的CPU上,索引空间内的线程映射到所有的核心上,但是一个工作组只映射到一个核心上,因此工作项并不 一
34、定代表一个线程,很多时候多个工作项映射到一个SSE向量指令上。 为了发挥X86 CPU的性能,显式地使用向量数据类型可能更好。 2.数据传输 GPU具有独立的显存,因此计算时需要将数据从GPU上传输到CPU上,这个过程可以利用DMA加速。NVIDIA的OpenCL 实现显式地提供了这一功能,而AMD的实现会在运行时自动调用。 基于CPU的OpenCL不使用显存,无需数据复制,因此最好使用OpenCL的存储器映射,这样就免掉了内存复制的消耗。 3.任务并行 CPU天生适合任务并行,而GPU适合数据并行,应当合理的安排两者的计算,以达到整体最优。但在某些情况下这是一个 非常难的问题。 另外CPU也
35、支持数据并行,如SSE/AVX指令就是为了这一目的设计的。同时GPU也可以实现任务并行,只要一个kernel使 用一个工作项即可,由于只使用了一个PE,其性能也会相当差。 4.全局存储器读写 由于GPU读写全局存储器要满足合并访问的要求才能够很好地发挥硬件的带宽,目前AMD GPU和NVIDIA GPU的合并访问 要求基本上是一致的(都要求一个执行单元的工作项访问相邻的地址且有对齐要求),而CPU的数据访问要尽量具有局部性以 发挥缓存的能力,同时对齐的内存访问也易于编译器使用SSE指令优化。 5.局部存储器 AMD某些系列的GPU使用全局存储器模拟局部存储器,因此其局部存储器的性能很差。而CP
36、U上根本无需存在局部存储 器,因此它们都是内存模拟的,故为CPU进行OpenCL编程时最好不要使用局部存储器。 不同的GPU的局部存储器的数量是不一样的,如NVIDIA的G80/GT200上每个SM的局部存储器大小为16KB,Fermi上可配 置为48KB,而AMD GPU中,每个SIMD引擎具有32KB。 在基于GPU的OpenCL平台编程时,使用局部存储器要考虑每个工作组使用的局部存储器大小,因为这会影响硬件的占用 率。 6.工作组声明 在OpenCL中,工作组的大小可以显式指定,也可以由编译器决定,这和CUDA不同。 在NVIDIA的GPU上,warp的大小是32,因此工作组大小应当是3
37、2的倍数,但是笔者建议至少是64的倍数。AMD的GPU 上,wavefront的大小是64,故工作组大小应当是64的倍数。目前无论是在AMD的GPU上,还是NVIDIA的GPU上,一开始将 工作组大小设置为128256是比较好的选择。 在基于CPU的OpenCL平台上编程时,工作组的大小一般选择32128比较好,并且要尽量保证工作组的大小和SSE指令的 大小是对齐的,如工作组访问char数组,那么工作组大小最好为64或128。 7.上下文切换 由于GPU上切换执行单元执行时,不会保存或重启上下文的内容,因此这是零消耗的,利用这点可以隐藏访存或其他计算 的延迟。 在CPU上,上下文切换需要保存和
38、重启上下文,因此其代价非常高,在某些编程语言中(如CUDA)有设置是切换上下文还 是忙等待的函数。此时编程要注意上下文切换与其他操作的时间长短,才能知道进行上下文切换是否值得。一般在网络服务应用 中,使用上下文切换是值得的。 8.分支 由于GPU的分支单元相对比较少而且缺乏分支预测能力,因此分支会减弱性能。而CPU天生就适合控制指令执行,因此在 进行OpenCL编程时,应尽量将分支移到kernel外面让CPU来负责它的执行。 1.7 众核编程模式 对于CPU+GPU的异构系统来说,常见的编程方式是:使用CPU来完成逻辑控制,而使用GPU来处理计算密集的数据并行 运算。 Intel宣称MIC支持
39、4种编程模式。 1)至强(Xeon)本地模式:所有的进程和线程都在主机上,此时MIC不干任何事情,处于休息状态。通常使用这种模式以 更好地调试。 2)至强为主机,MIC为协处理器:串行代码在主机上运行,并行代码在MIC上运行,这种模式和GPU没有任何区别。这也 是目前最常见的模式,通常使用Intel OpenMP扩展来编写程序。 3)对称模式:并行代码同时在主机和MIC上运行,这种模式可以利用主机和MIC上的所有计算能力,但是由于架构的不 同,对某些应用来说,如何在主机和MIC之间分配任务并保证负载均衡变得非常困难。对于另外一些应用,使用动态负载均衡策 略可能会获得好的结果。 4)MIC本地模
40、式:所有的进程都运行在MIC上面,就将MIC看成一个多核处理器。在这种模式下,也许只需要重新编译原 来的MPI程序即可,非常有利于入门学习。由于MIC单核心的性能比Xeon要差很多,因此原来的串行运行时间会成倍增加,在 某些应用上,会成为瓶颈。另外,目前MIC最多只有8GB内存,进程数多的话,平均到每个进程占用的内存就很少了。 目前适用于CPU+GPU架构的编程语言有NVIDIA CUDA和开放的OpenCL,两者基本概念的设计一致。 Intel自己的MPI/OpenMP/OpenCL/cilk/Fortran都支持MIC。另外基于GPU设计的OpenACC也支持MIC。 1.8 众核性能优化
41、 每个MIC核心支持4个硬件线程,多个硬件线程间的切换能够隐藏延迟,但是MIC上线程的切换不是免费的,因此需要在线 程切换时间、问题规模和线程数量上权衡。这没有固定的公式或规则可以应用,通常的做法是试验。 MIC的主要性能来自于VPU,如何保证代码能够被向量化就非常重要。通常向量化代码要求地址对齐、访问地址不相关, 一个常见的实践是将对多维数组变化最快的维上的数据的处理留给VPU。 编写缓存友好的代码,必要时使用缓存分块、非一致内存访问及预取技术。在必要时,可转换数据,如将由结构体组成的数 组改成由数组组成的结构体。 1.9 MIC和GPU编程比较 Intel宣称MIC是兼容X86的,实际上目
42、前MIC只兼容没有使用SSE/AVX指令的代码(在64位机器上,浮点运算即使用SSE指 令实现),而且这种兼容是源码的兼容而非二进制兼容。不过不管怎么样,这总比移植到GPU上时,需要将部分代码完全重写 要好。 对于某些应用,重新编译可能能够通过,但是这通常不能发挥硬件的性能,因为要利用VPU,代码必须要向量化。 Intel宣称MIC使用OpenMP编程,因此其编程应当会简单一些。但是这个前提是默认GPU编程使用CUDA,如果使用 OpenACC的话,两者的难度就相差不大。另外,对于高性能计算来说,通常计算性能优化比入门更重要,而GPU的计算性能优 化比MIC要容易很多。 1.10 本章小结 本
43、章介绍了主流的多核向量处理器架构,主要是处理器核心组织和缓存金字塔,包括Intel Haswell、ARM A15、Intel MIC、AMD GCN和NVIDIA Kepler架构。 本章还介绍了OpenCL程序如何在多核处理器上执行,其工作项和工作组如何映射到硬件上,以及OpenCL程序如何在多核 向量CPU、NVIDIA Kepler GPU和AMD GCN GPU上执行,并且比较了OpenCL程序在各种不同处理器上执行时的区别。 第2章 常见线性代数算法优化 线性代数中的许多操作是其他算法和应用的基础,如矩阵向量乘法广泛应用在图论、有限元和有限差分求解器中。矩阵乘法 则大量应用在数据挖
44、掘、计算机视觉算法中,并且已经成为很多硬件厂商用来衡量现代计算机性能的标准之一。 本章提出了许多优秀的计算方法,例如:笔者提出的使用一个工作组计算稀疏矩阵多行与向量乘积;使用自适应方法计算稀 疏矩阵与向量乘积;如何向量化下三角方程组求解等。另外,本章提出的在X86、ARM和GPU上实现的、简单的矩阵乘法的性 能也是非常不错的(已经接近一些库的性能)。 本章介绍如何优化常见的线性代数算法,包括稀疏矩阵向量乘法、对称矩阵向量乘法、矩阵乘法及下三角线性方程组求解。 2.1 稀疏矩阵与向量乘法 现实应用中,很多矩阵都是稀疏的,如许多使用图论来解决的问题都可以转化为对稀疏矩阵的操作。以北京市地铁站点图为
45、 例,以每个站点为一个节点且以整数索引为其编号,那么站点间的连接关系就可以以一个稀疏矩阵来表示,矩阵的值可以表示不 同的量,以表示在具体应用场景下不同的物理含义,可以表示站点间的运行时间、表示票价等。可以依据Floyd/迪杰思特最短路 径算法求得两站间的最短换乘距离/最少票价等。 有限元计算时通常需要对偏微分方程进行离散化处理,离散后会形成一个线性方程组,方程组的系数矩阵很多时候是稀疏 的。求解稀疏系数线性方程组常见的有两种办法:直接法和间接法。直接法是指类似LU分解类方法,而间接法通常指迭代法。 在使用各种迭代法求解稀疏系数线性方程组时,最主要的操作是计算稀疏矩阵向量乘法。 2.2 对称矩阵
46、与向量乘积 对于对称矩阵来说,只需要保存左下角的一半即可,这可减少存储器使用量。假设以一维数组保存对称矩阵左下角(包括对 角线)的元素,那么原来行列索引为(i,j)的元素在一维数组中的索引为: 只保存对称矩阵一半的方式减少了存储量,潜在地提升了缓存的利用率,却对并行化和向量化运算带来了挑战。本节简要说 明如何并行化和向量化对称矩阵向量乘法。 2.3 三角线性方程组的解法 在使用直接法解线性方程组时,计算步骤可分成两个部分:其一,将系数矩阵分解成上三角矩阵和下三角矩阵,即LU分 解;其二,求解上三角线性方程组和下三角线性方程组。关于使用直接法求解线性方程组的内容,感兴趣的读者可以参考相关的 教科
47、书。最后一步(矩阵分解成上三角和下三角矩阵之后)是要求解上/下三角方程组,尤其是在只需在初始化时进行一次矩阵 分解然后多次求解的情况下,上/下三角方程组的计算更为重要。本节以下三角方程组为例,说明如何优化。 2.4 矩阵乘法 实际的许多工程应用都涉及或可转化为矩阵乘法,因此其常成为衡量硬件性能的标准。如NVIDIA和AMD发布新的GPU处 理器时,经常就宣称其sgemm(单精度稠密矩阵乘法)或dgemm(双精度稠密矩阵乘法)性能达到多少FLOPS。因此如何高 效地将矩阵乘法映射到硬件上就非常重要,这成为衡量硬件性能的实际标准之一,同时也应当成为衡量软件开发人员代码性能优 化水平的标准之一。 将
48、一个大小为MK的矩阵与一个大小为KN的矩阵相乘,其结果为一个大小为MN的矩阵。在最理想情况下,其计算访 存比例为,假设都是方阵,即M=K=N,那么计算访存比可简化为。但是由于现代处理器的缓存大小是有限的,因此计算访存比 上限通常受限于寄存器数量和缓存容量。 在现代多核向量处理器上实现矩阵乘法时,需要注意以下几点: 1)对全局存储器(DRAM)的访问是否高效。比如在X86、ARM架构上实现时是否能够使用向量加载和存储指令;在GPU 上实现时是否满足合并访问的要求。 2)是否能很好地使用处理器核心上的缓存。比如在X86、ARM架构上是否能有效地利用一级缓存,在GPU上实现时是否能 很好地利用了局部
49、存储器带宽。 3)是否很好地使用了寄存器分块算法。无论是在X86、ARM处理器上,还是在GPU上,如果不考虑寄存器数据重用的话, 一级缓存或局部存储器的带宽和延迟无法满足矩阵乘法计算的要求。 4)是否考虑到生成的指令能足够好。在支持乘加指令的处理器上就不应当生成乘或加指令。 5)是否考虑到如何掩盖指令和访存延迟。需要有足够的计算和访存并行度以利用处理器计算单元和访存单元的带宽。 本节将实现基于AVX、ARM NEON指令集和GPU的矩阵乘法。 2.5 本章小结 本章详细介绍了如何在X86、ARM和GPU处理器上优化常见的线性代数算法,这些算法非常常见,比如计算不同保存格式 的稀疏矩阵向量乘法,不同特征的矩阵和向量乘法。最后本章以如何在X86、ARM和GPU上实现性能强大的矩阵乘法算法结 尾。 第3章 优化偏微分方程的数值解法 偏微分方程广泛应用于科学计算的方方面面,计算流体力学和空气动力学模拟飞行器试飞中的气流对飞行器影响时,需要求 解空气动力学方程和流体方程来模拟流体的流动,这些方程都是偏微分方程离散所得。石油勘探中利用方程偏微分求解来模拟地 下的形状,进而判断是否有油气田,常见的算法如RTM(Reverse Time Migration,
链接地址:https://www.31doc.com/p-5518984.html