![科学计算与企业级应用的并行优化[按需印刷]](http://images.china-pub.com/ebook4725001-4730000/4729023/zcover.jpg)
基本信息
编辑推荐
国内并行计算领域知名专家风辰多年实践经验总结，兼具深度和高度基于大量示例，揭秘如何在主流硬件平台上通过向量化和并行化技术优化代码性能，涵盖线性代数、偏微分方程求解、分子动力学和机器学习领域常见算法优化案例近两三年来，在互联网企业中，代码性能优化、并行计算和GPU的使用越来越受到重视。无论是国外的Google、Facebook还是国内的百度、腾讯、阿里和360，都在使用代码性能优化、并行计算和GPU来完成以前不能完成的任务。而现在中小型企业也在使用代码性能优化和并行化技术来提升产品的使用体验。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。《科学计算与企业级应用的并行优化》不但包括如何使用SSE/AVX向量化扩展、OpenMP编译制导语句来优化运行在X86多核处理器上的代码性能，还包括使用NEON向量化扩展优化运行在移动处理器（ARM）的代码性能优化，以及使用CUDA优化运行在图形处理器（GPU）上的代码性能。笔者基于自身丰富的理论和实践经验，将大量“不传之秘”融入本书，主要体现在：使用AVX在Intel X86处理器上，使用CUDA在NVIDIA GPU上来优化线性代数运算（如稀疏矩阵向量乘、对称矩阵向量乘）；使用OpenMP和CUDA优化分子动力学算法，本质上分子动力学是nbody计算模式的一种具体表现，相关技巧也可应用到nbody模式中；展示了如何使用AVX、OpenMP和CUDA优化常见的数据挖掘算法（如k-means、KNN和卷积）和计算视觉算法（四维卷积）；简单展示了如何使用多GPU来优化主流的深度学习框架Caffe。
内容简介
书籍
计算机书籍
本书是“并行计算与性能优化”系列的第3本，此书的重点在于介绍如何利用目前主流的、基于C语言的各种特定硬件或平台的向量化扩展、并行化库来优化科学汁算和企业级应用的代码性能。而本系列的《并行算法设计与代码优化》关注并行优化和并行计算相关的理论、算法设计及高层次的实践经验；本系列的《并行编程方法与优化实践》关注于C程序没计语言的向量化和并行化扩展及算法到硬件的映射，以及如何在不同的硬件平台上优化代码以获得更好的性能：这些内容被许多顶级开发人员视为“不传之秘”。
本书作者是国内顶尖的并行计算专家，曾任英伟达并行计算下程师和百度在线高级研发工程师，在该领域的经验和修为极为深厚，他毫不吝啬地将自己多年的积累呈现在了这3本书中，得到了深度学习杰出科学家吴韧的高度评价和强烈推荐。
全书共5章。第1章介绍了常见的并行编程基于的多核／众核向量处理器的架构，OpenCL程序到平台的映射与运行差异。第2章介绍了如何在X86、ARM和GPU上优化常见的线性代数运算，如计算稀疏矩阵向量乘法，求解下三角线性方程组，计算矩阵乘法等：第3章以如何求解热传递问题和三维Stencil问题为例介绍厂如何在X86和GPU处理器上优化偏微分方程的求解。第4章介绍了如何在X86处理器和GPU上优化常见的分子动力学算法，如邻居搜索、范德华力计算、键长伸缩力计算和径向分布函数计算。第5章洋细介绍了如何在X86、ARM和GPU上优化常见的机器学习算法(如k-means、KNN、二维卷积和四维卷积)性能，最后给出利用多GPU并行卷积神经网络的常见方法，及如何基于数据并行、使用多GPU来优化Caffe的性能。
计算机书籍
本书是“并行计算与性能优化”系列的第3本，此书的重点在于介绍如何利用目前主流的、基于C语言的各种特定硬件或平台的向量化扩展、并行化库来优化科学汁算和企业级应用的代码性能。而本系列的《并行算法设计与代码优化》关注并行优化和并行计算相关的理论、算法设计及高层次的实践经验；本系列的《并行编程方法与优化实践》关注于C程序没计语言的向量化和并行化扩展及算法到硬件的映射，以及如何在不同的硬件平台上优化代码以获得更好的性能：这些内容被许多顶级开发人员视为“不传之秘”。
本书作者是国内顶尖的并行计算专家，曾任英伟达并行计算下程师和百度在线高级研发工程师，在该领域的经验和修为极为深厚，他毫不吝啬地将自己多年的积累呈现在了这3本书中，得到了深度学习杰出科学家吴韧的高度评价和强烈推荐。
全书共5章。第1章介绍了常见的并行编程基于的多核／众核向量处理器的架构，OpenCL程序到平台的映射与运行差异。第2章介绍了如何在X86、ARM和GPU上优化常见的线性代数运算，如计算稀疏矩阵向量乘法，求解下三角线性方程组，计算矩阵乘法等：第3章以如何求解热传递问题和三维Stencil问题为例介绍厂如何在X86和GPU处理器上优化偏微分方程的求解。第4章介绍了如何在X86处理器和GPU上优化常见的分子动力学算法，如邻居搜索、范德华力计算、键长伸缩力计算和径向分布函数计算。第5章洋细介绍了如何在X86、ARM和GPU上优化常见的机器学习算法(如k-means、KNN、二维卷积和四维卷积)性能，最后给出利用多GPU并行卷积神经网络的常见方法，及如何基于数据并行、使用多GPU来优化Caffe的性能。
作译者
刘文志，花名风辰，毕业于中国科学院研究生院，闻名于并行计算江湖，尤善异构并行计算（X86、ARM、GPU、APU、PHI）和大规模集群计算相关技术，有7年相关经验，涉及图像处理、计算机视觉、数据挖掘和石油勘探。曾任英伟达并行计算工程师（协助建立英伟达北京CUDA团队）、百度在线高级研发工程师（协助建立百度深度学习实验室异构计算团队）。
目录
序
前言
第1章 多核向量处理器架构 1
1.1 众核系统结构 2
1.2 众核架构的一致性 3
1.3 多核向量处理器架构 5
1.3.1 Intel Haswell CPU架构 6
1.3.2 ARM A15多核向量处理器架构 10
1.3.3 AMD GCN GPU架构 12
1.3.4 NVIDIA Kepler和Maxwell GPU架构 15
1.4 Intel MIC架构 21
1.4.1 整体架构 22
1.4.2 计算单元 22
1.4.3 存储器单元 24
1.4.4 MIC架构上一些容易成为瓶颈的设计 25
1.5 OpenCL程序在多核向量处理器上的映射 26
1.5.1 OpenCL程序在多核向量CPU上的映射 26
1.5.2 OpenCL程序在NVIDIA GPU上的映射 28
1.5.3 OpenCL程序在AMD GCN上的映射 34
1.6 OpenCL程序在各众核硬件上执行的区别 39
前言
第1章 多核向量处理器架构 1
1.1 众核系统结构 2
1.2 众核架构的一致性 3
1.3 多核向量处理器架构 5
1.3.1 Intel Haswell CPU架构 6
1.3.2 ARM A15多核向量处理器架构 10
1.3.3 AMD GCN GPU架构 12
1.3.4 NVIDIA Kepler和Maxwell GPU架构 15
1.4 Intel MIC架构 21
1.4.1 整体架构 22
1.4.2 计算单元 22
1.4.3 存储器单元 24
1.4.4 MIC架构上一些容易成为瓶颈的设计 25
1.5 OpenCL程序在多核向量处理器上的映射 26
1.5.1 OpenCL程序在多核向量CPU上的映射 26
1.5.2 OpenCL程序在NVIDIA GPU上的映射 28
1.5.3 OpenCL程序在AMD GCN上的映射 34
1.6 OpenCL程序在各众核硬件上执行的区别 39
前言
IT行业急需这本书
和本系列的前两本书一样，在解释为什么笔者认为软件工程师需要这本书之前，笔者先来介绍并行、并发和代码性能优化这3个概念，因为理解这3个概念是阅读本系列3本书的基础。
并行对应的英文单词是parallelism，是指在具有多个处理单元的系统上，通过将计算或数据划分为多个部分，将各个部分分配到不同的处理单元上，各处理单元相互协作，同时运行，以达到加快求解速度或者提高求解问题规模的目的。
并发对应的英文单词是concurrency，是指在一个处理单元上运行多个应用，各应用分时占用处理单元，是一种微观上串行、宏观上并行的模式，有时也称其为时间上串行、空间上并行。
代码性能优化是指通过调整源代码，使得其生成的机器指令能够更高效地执行，通常高效是指执行时间更少、使用的存储器更少或能够计算更大规模的问题。
从大的方面来说，并行和并发都是代码性能优化的一种方式，但是今天并行和并发已经是如此重要，以至于需要“开宗立派”。为了明晰并行、并发和代码性能优化的边界，在本书中，代码性能优化特指除了并行和并发以外的代码优化方法，比如向量化和提高指令流水线效率。在本书中，笔者将向量化独立出来解说。
2003年以前，在摩尔定律的作用下，单核标量处理器的性能持续提升，软件开发人员只需要写好软件，而性能的提升就等待下次硬件更新来解决，在2003年之前的几十年里，这种“免费午餐”模式一直在持续。2003年后，主要由于功耗的原因，这种“免费午餐”已经不复存在。为了生存，各硬件生产商不得不采用各种方式提高硬件的计算能力。目前最流行的3种方式如下：
1）让处理器在一个周期处理多条指令，多条指令可相同可不同。如Intel Haswell处理器一个周期可执行4条整数加法指令、两条浮点乘加指令，而访存和运算指令也可同时执行。
2）使用向量指令，主要是SIMD和VLIW技术。SIMD技术将处理器一次能够处理的数据位数从字长扩大到128或256位，也就提升了计算能力。
3）在同一个芯片中集成多个处理单元，根据集成方式的不同，相应地称为多核或多路处理器。多核处理器是如此重要，以至于现在即使是手机上的嵌入式ARM处理器都已经是四核或八核了。
目前绝大部分应用软件都是串行的，因为串行执行过程符合人类的思维习惯，易于理解、分析和验证。由于串行软件只能在多核CPU中的一个核上运行，和2003年以前的CPU没有多少区别，这意味着花多核CPU的价钱买到了单核的性能。通过多核技术，硬件生产商成功地将提高实际计算能力的任务转嫁给软件开发人员，而软件开发人员没有选择，只有直面挑战。
标量单核的计算能力没有办法继续大幅度提升，而应用对硬件计算能力的需求依旧在提升，这是个实实在在的矛盾。在可见的将来，要解决这个矛盾，软件开发人员只有代码性能优化和并行可以选择。代码性能优化并不能利用多核CPU的全部计算能力，它也不要求软件开发人员掌握并行开发技术，另外通常也无需对软件架构做改动，而且串行代码优化有时能够获得非常好的性能（如果原来的代码写得很差的话），因此相比采用并行技术，应当优先选择串行代码性能优化。一般来说，采用并行技术获得的性能加速不超过核数，这是一个非常大的限制，因为目前CPU硬件生产商最多只能集成十几、几十个核。
从2006年开始，可编程的GPU越来越得到大众的认可。GPU是图形处理单元（Graphics Processing Unit）的简称，最初主要用于图形渲染。自20世纪90年代开始，NVIDIA、AMD（ATI）等GPU生产商对硬件和软件加以改进，GPU的可编程能力不断提高，GPGPU（General-purpose computing on graphics processing units）比以前容易许多。另外由于GPU具有比CPU强大的峰值计算能力，近年来引起了许多科研人员和企业的兴趣。
近两三年来，在互联网企业中，GPU和并行计算越来越受到重视。无论是国外的Google、Facebook，还是国内的百度、腾讯、阿里和360，都在使用代码性能优化、并行计算和GPU来完成以前不能完成的任务。
10年前，并行计算还是实验室里教授们的研究对象，而今天多核处理器和GPU的普及已经使得普通人就可以研究它们。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
作为本系列的压轴之作，本书专注于领域相关的算法和应用的并行与性能优化。笔者介绍了如何优化线性代数、偏微分方程求解、分子动力学和机器学习领域的一些重要算法。
如果以武侠中的功夫来比喻的话，本系列的第一本书《并行算法设计与性能优化》专注于理论基础和实践的结合，是“内功”和“心法”的修炼；本系列的第二本书《并行编程方法与优化实践》专注于程序设计语言的核心内容的应用，是“招式”的学习；而本书则是“内功心法”和“招式”的具体运用。“内功心法”好意味着基础好、潜力大，以后发展空间广泛；“招式”好则能够通过“奇招”“怪招”解决问题；而只有将“内功心法”和“招式”完美融合，做到“心中无招而手中有招，无招胜有招，无招即有招”，才能成为异构并行计算这个领域真正的集大成者。愿读者和笔者一起向这个目标前进。
本书完全是“干货”，是一本真正将业界最佳实践和“只可意会，不可言传”的领域知识简洁明了地贡献出来的著作。为了帮助读者理解，本书使用了大量的示例。开发人员通常比较忙，因此本书力求简洁明了，点到为止。
读者对象
由于多核处理器和GPU已经非常便宜，而代码性能优化、向量化和并行已经深入IT行业的骨髓，所有IT行业的从业者都应当阅读本书。如果非要列一个读者清单，笔者认为下列人员应当阅读本书：
和本系列的前两本书一样，在解释为什么笔者认为软件工程师需要这本书之前，笔者先来介绍并行、并发和代码性能优化这3个概念，因为理解这3个概念是阅读本系列3本书的基础。
并行对应的英文单词是parallelism，是指在具有多个处理单元的系统上，通过将计算或数据划分为多个部分，将各个部分分配到不同的处理单元上，各处理单元相互协作，同时运行，以达到加快求解速度或者提高求解问题规模的目的。
并发对应的英文单词是concurrency，是指在一个处理单元上运行多个应用，各应用分时占用处理单元，是一种微观上串行、宏观上并行的模式，有时也称其为时间上串行、空间上并行。
代码性能优化是指通过调整源代码，使得其生成的机器指令能够更高效地执行，通常高效是指执行时间更少、使用的存储器更少或能够计算更大规模的问题。
从大的方面来说，并行和并发都是代码性能优化的一种方式，但是今天并行和并发已经是如此重要，以至于需要“开宗立派”。为了明晰并行、并发和代码性能优化的边界，在本书中，代码性能优化特指除了并行和并发以外的代码优化方法，比如向量化和提高指令流水线效率。在本书中，笔者将向量化独立出来解说。
2003年以前，在摩尔定律的作用下，单核标量处理器的性能持续提升，软件开发人员只需要写好软件，而性能的提升就等待下次硬件更新来解决，在2003年之前的几十年里，这种“免费午餐”模式一直在持续。2003年后，主要由于功耗的原因，这种“免费午餐”已经不复存在。为了生存，各硬件生产商不得不采用各种方式提高硬件的计算能力。目前最流行的3种方式如下：
1）让处理器在一个周期处理多条指令，多条指令可相同可不同。如Intel Haswell处理器一个周期可执行4条整数加法指令、两条浮点乘加指令，而访存和运算指令也可同时执行。
2）使用向量指令，主要是SIMD和VLIW技术。SIMD技术将处理器一次能够处理的数据位数从字长扩大到128或256位，也就提升了计算能力。
3）在同一个芯片中集成多个处理单元，根据集成方式的不同，相应地称为多核或多路处理器。多核处理器是如此重要，以至于现在即使是手机上的嵌入式ARM处理器都已经是四核或八核了。
目前绝大部分应用软件都是串行的，因为串行执行过程符合人类的思维习惯，易于理解、分析和验证。由于串行软件只能在多核CPU中的一个核上运行，和2003年以前的CPU没有多少区别，这意味着花多核CPU的价钱买到了单核的性能。通过多核技术，硬件生产商成功地将提高实际计算能力的任务转嫁给软件开发人员，而软件开发人员没有选择，只有直面挑战。
标量单核的计算能力没有办法继续大幅度提升，而应用对硬件计算能力的需求依旧在提升，这是个实实在在的矛盾。在可见的将来，要解决这个矛盾，软件开发人员只有代码性能优化和并行可以选择。代码性能优化并不能利用多核CPU的全部计算能力，它也不要求软件开发人员掌握并行开发技术，另外通常也无需对软件架构做改动，而且串行代码优化有时能够获得非常好的性能（如果原来的代码写得很差的话），因此相比采用并行技术，应当优先选择串行代码性能优化。一般来说，采用并行技术获得的性能加速不超过核数，这是一个非常大的限制，因为目前CPU硬件生产商最多只能集成十几、几十个核。
从2006年开始，可编程的GPU越来越得到大众的认可。GPU是图形处理单元（Graphics Processing Unit）的简称，最初主要用于图形渲染。自20世纪90年代开始，NVIDIA、AMD（ATI）等GPU生产商对硬件和软件加以改进，GPU的可编程能力不断提高，GPGPU（General-purpose computing on graphics processing units）比以前容易许多。另外由于GPU具有比CPU强大的峰值计算能力，近年来引起了许多科研人员和企业的兴趣。
近两三年来，在互联网企业中，GPU和并行计算越来越受到重视。无论是国外的Google、Facebook，还是国内的百度、腾讯、阿里和360，都在使用代码性能优化、并行计算和GPU来完成以前不能完成的任务。
10年前，并行计算还是实验室里教授们的研究对象，而今天多核处理器和GPU的普及已经使得普通人就可以研究它们。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
作为本系列的压轴之作，本书专注于领域相关的算法和应用的并行与性能优化。笔者介绍了如何优化线性代数、偏微分方程求解、分子动力学和机器学习领域的一些重要算法。
如果以武侠中的功夫来比喻的话，本系列的第一本书《并行算法设计与性能优化》专注于理论基础和实践的结合，是“内功”和“心法”的修炼；本系列的第二本书《并行编程方法与优化实践》专注于程序设计语言的核心内容的应用，是“招式”的学习；而本书则是“内功心法”和“招式”的具体运用。“内功心法”好意味着基础好、潜力大，以后发展空间广泛；“招式”好则能够通过“奇招”“怪招”解决问题；而只有将“内功心法”和“招式”完美融合，做到“心中无招而手中有招，无招胜有招，无招即有招”，才能成为异构并行计算这个领域真正的集大成者。愿读者和笔者一起向这个目标前进。
本书完全是“干货”，是一本真正将业界最佳实践和“只可意会，不可言传”的领域知识简洁明了地贡献出来的著作。为了帮助读者理解，本书使用了大量的示例。开发人员通常比较忙，因此本书力求简洁明了，点到为止。
读者对象
由于多核处理器和GPU已经非常便宜，而代码性能优化、向量化和并行已经深入IT行业的骨髓，所有IT行业的从业者都应当阅读本书。如果非要列一个读者清单，笔者认为下列人员应当阅读本书：
序言
到这里，终于可以松一口气了，一个持续多年的工作总算可以告一段落了。本系列起源于我2012年想写的《并行乱弹》一书，乱弹是乱弹琴的意思。按我的本意，并不想把它写成一本非常严谨的著作，当时更无意出版，因此并不是非常注意全书逻辑的严密性，虽然经过我和编辑的多次修改，但想必问题依旧难以避免，在此诚恳地请求读者谅解。
本系列的3本书相互之间有联系，也有其独立性：《并行算法设计与性能优化》介绍常见的串行代码优化方法和并行算法的设计；《并行编程方法与优化实践》介绍常见的向量化和并行编程环境及一些实例；《科学计算与企业级应用的并行优化》则介绍领域相关的算法与应用的性能优化。
如果说要写一本简短的武侠小说来描写主角是如何学习这3本“秘笈”的话，我想故事是这样的：在2015年，主角是某位内向宅男码农hpc，因为程序速度太慢天天被产品经理骂，受项目经理白眼，每天工作到晚上10点，遭到家人埋怨。在某个月黑风高的晚上，某条街道上那位江湖人称“风辰”的“HPC帮”护法长老收hpc为不记名弟子，并传授给hpc《并行算法设计与性能优化》《并行编程方法与优化实践》及《科学计算与企业级应用的并行优化》3本“秘笈”，“风辰”临走时收了传功费用1024万元。hpc如获至宝，休假一月潜心修炼。一月后出关，容光焕发，程序速度大幅度提升，产品经理天天请吃大餐，项目经理忙着加项目奖金。此后，hpc每天下午5点即下班回家，修身养性，陪家人一起吃饭、购物。
愿这3本书能够真正成为改变读者生活的良师益友！
风辰
2015年5月17日于深圳
本系列的3本书相互之间有联系，也有其独立性：《并行算法设计与性能优化》介绍常见的串行代码优化方法和并行算法的设计；《并行编程方法与优化实践》介绍常见的向量化和并行编程环境及一些实例；《科学计算与企业级应用的并行优化》则介绍领域相关的算法与应用的性能优化。
如果说要写一本简短的武侠小说来描写主角是如何学习这3本“秘笈”的话，我想故事是这样的：在2015年，主角是某位内向宅男码农hpc，因为程序速度太慢天天被产品经理骂，受项目经理白眼，每天工作到晚上10点，遭到家人埋怨。在某个月黑风高的晚上，某条街道上那位江湖人称“风辰”的“HPC帮”护法长老收hpc为不记名弟子，并传授给hpc《并行算法设计与性能优化》《并行编程方法与优化实践》及《科学计算与企业级应用的并行优化》3本“秘笈”，“风辰”临走时收了传功费用1024万元。hpc如获至宝，休假一月潜心修炼。一月后出关，容光焕发，程序速度大幅度提升，产品经理天天请吃大餐，项目经理忙着加项目奖金。此后，hpc每天下午5点即下班回家，修身养性，陪家人一起吃饭、购物。
愿这3本书能够真正成为改变读者生活的良师益友！
风辰
2015年5月17日于深圳
书摘
2.1.1 稀疏矩阵的存储格式
为了减少存储消耗和提高缓存利用以提升性能，稀疏矩阵通常采用只存储非零元的方式，显而易见还需要其他方式来保存行列结构关系。常用的稀疏矩阵存储格式主要有DIA、COO、ELL、CSR、HYB。
1） DIA格式依据对角线存储非零元。这种格式非常适合于对角线矩阵。
2） COO格式使用用3个数组：rowlndex、columnlndex、val，来表示原矩阵中的非零元素及索引，3个数组的长度都等于非零元素个数。rowlndex数组表示原矩阵中非零元素的行索引，columnlndex数组表示原矩阵中非零元素的列索引，val数组表示原矩阵中非零元素的值，即对原矩阵中每一个非零元都用一个三元组（行，列，值）来表示，即对原来矩阵中的第i个非零元素，其行索引为rowlndex（i），列索引为columnlndex（i），其值为val（i）。
3） ELL格式使用两个矩阵来保存非零元，其中一个存储每行的K个非零元，另一个存储非零元对应的列索引，故每个矩阵的大小都是K乘以矩阵行数，如果某一行的非零元数量小于K，则通过某种方式表示出来，如将其列索引指定为—1。在GPU上面，这种方式能够很好地满足GPU DRAM的合并访问要求，但是由于其要求K大于所有行中非零元数量的最大值，在每行非零元个数变化非常大的时候会引起存储空间和计算能力的浪费。
……
为了减少存储消耗和提高缓存利用以提升性能，稀疏矩阵通常采用只存储非零元的方式，显而易见还需要其他方式来保存行列结构关系。常用的稀疏矩阵存储格式主要有DIA、COO、ELL、CSR、HYB。
1） DIA格式依据对角线存储非零元。这种格式非常适合于对角线矩阵。
2） COO格式使用用3个数组：rowlndex、columnlndex、val，来表示原矩阵中的非零元素及索引，3个数组的长度都等于非零元素个数。rowlndex数组表示原矩阵中非零元素的行索引，columnlndex数组表示原矩阵中非零元素的列索引，val数组表示原矩阵中非零元素的值，即对原矩阵中每一个非零元都用一个三元组（行，列，值）来表示，即对原来矩阵中的第i个非零元素，其行索引为rowlndex（i），列索引为columnlndex（i），其值为val（i）。
3） ELL格式使用两个矩阵来保存非零元，其中一个存储每行的K个非零元，另一个存储非零元对应的列索引，故每个矩阵的大小都是K乘以矩阵行数，如果某一行的非零元数量小于K，则通过某种方式表示出来，如将其列索引指定为—1。在GPU上面，这种方式能够很好地满足GPU DRAM的合并访问要求，但是由于其要求K大于所有行中非零元数量的最大值，在每行非零元个数变化非常大的时候会引起存储空间和计算能力的浪费。
……
