本书主要介绍并行计算相关的算法的设计和并行计算的性能优化技巧，涵盖现代处理器的特性、衡量程序性能的方法、串行代码性能优化、并行编程模型及其环境、并行算法设计、遗留代码的并行处理、并行编程模型、混合并行等核心技法与实践技巧。

并行计算领域著名专家撰写，百度深度学习研究院“杰出科学家”吴韧鼎力推荐
结合大量示例和伪代码，全面讲解如何通过并行算法设计实现单核/多核处理器、GPU和移动处理器的性能优化及相关的并行化秘技，并首次提出实现复杂度的全新性能度量标准

我一直认为，计算机科学就是计算的科学, 能写出正确而高效的代码是这个学科以及相关学科的基本功。高效的代码意味着代码作者对计算硬件细节和计算软件系统细节的充分及深入了解，对代码并行化以及代码性能优化的深刻认识。以近年极度火爆的深度学习为例，人们应该同样记住两位英雄人物：Alex Krizhevsky和Yangqing Jia。他们的优秀程序设计能力和代码优化能力让他们鹤立鸡群, 他们的工作让世人受益匪浅。本书的作者风辰也是一位优秀、务实的并行计算和代码性能优化人才，他将多年的并行计算实践和代码性能优化经验及感悟以全新并具有高度的视角集结成书，与众多程序员分享代码向量化和并行化的奥义。书中有大量风辰独有的真知灼见，当你购买这本书时, 恭喜你, 你已经找到了你正在寻找的、提高自身修为的一扇大门。
——　吴韧　百度深度学习研究院“杰出科学家”

近两三年来，在互联网企业中，GPU和并行计算越来越受到重视。无论是国外的Google、Facebook还是国内的百度、腾讯、阿里和360，都在使用代码优化、并行计算和GPU来完成以前不能完成的任务。而现在中小型企业也在使用代码优化和并行化技术来提升产品的使用体验。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
本书不但介绍了全新的代码性能优化的度量方法和标准，还介绍了常见的并行编程模型与环境、并行算法设计及编程模式的实践、遗留代码并行化和超级并行等读者最为关心的问题，使广大开发人员可以快速进入并行计算的实战工作。

本书亮点：
提出并解释了实现复杂度的概念及如何使用实现复杂度来分析程序性能。
介绍常见的串行代码优化方法。
提出了设计并行算法的步骤、方法和准则，以及如何将并行算法映射到硬件上以获得高性能。



本书是“并行计算与性能优化”系列的第1本，主要讲解了并行计算的核心理论、算法设计和实践，以及代码的性能优化，第2本和第3本则涵盖了并行编程方法与优化实践、科学计算与企业级应用的并行优化等重要主题，这些内容被许多顶级开发人员视为“不传之秘”。本书作者是国内顶尖的并行计算专家，曾任英伟达并行计算工程师和百度在线高级研发工程师，在该领域的经验和修为极为深厚，他毫不吝啬地将自己多年的积累呈现在这3本书中，得到了百度深度学习研究院“杰出科学家”吴韧的高度评价和强烈推荐。
本书结合大量示例和伪代码，详细介绍了单核代码的性能优化和向量化技术，在现代多核处理器上如何设计并行算法，以及基于GPU和移动处理器（ARM）的代码性能优化与并行化。
全书12章，逻辑上分为四大部分：
并行计算理论基础
主要介绍并行现状、与并行计算紧密相关的现代处理器的技术与特点，算法与程序性能的度量和分析的新旧标准及实用工具，以及代码依赖关系的分析和去除处理。
代码优化
首先从系统、应用、算法、函数、循环、语句和指令7大维度讲解了常见的串行代码优化手段，然后讲解了如何通过多种方式将现有的串行代码向量化和并行化，以提高效率和利用率。
并行算法设计考量
主要讲解了如何设计优良的并行算法以及将并行算法映射到具体硬件上，涵盖常见的并行编程环境、并行算法设计方法、并行算法的缺陷、编程模式实践、一般准则，等等。
遗留代码的并行化
主要讲解了如何找出软件的计算热点，如何合理地选择部分并行或者整体并行，然后将实现后的代码嵌入原软件，以提高企业现有代码的利用率，并以实例加以说明。

作者简介
刘文志　花名风辰，毕业于中国科学院研究生院，闻名于并行计算江湖，尤善异构并行计算（X86、ARM、GPU、APU、PHI）和大规模集群计算相关技术，有7年相关经验，涉及图像处理、计算机视觉、数据挖掘和石油勘探。曾任英伟达并行计算工程师（协助建立英伟达北京CUDA团队）、百度在线高级研发工程师（协助建立百度深度学习实验室异构计算团队）。

IT行业急需这本书
在解释为什么笔者认为IT行业急需这本书之前，先让笔者来介绍并行、并发和代码性能优化这三个概念，理解这三个概念是阅读本书的基础：
并行对应的英文单词是parallelism，是指在具有多个处理单元的系统上，通过将计算或数据划分为多个部分，将各个部分分配到不同的处理单元上，各处理单元相互协作，同时运行，以达到加快求解速度或者提高求解问题规模的目的。
并发对应的英文单词是concurrency，并发是指在一个处理单元上运行多个应用，各应用分时占用处理单元，是一种微观上串行、宏观上并行的模式，有时也称其为时间上串行、空间上并行。
代码性能优化是指通过调整源代码，使得其生成的机器指令能够更高效地执行，通常高效是指执行时间更少、使用的存储器更少或能够计算更大规模的问题。
从大的方面来说，并行和并发都是代码性能优化的一种方式，但是今天并行和并发已经是如此重要，需要“开宗立派”。为了清晰并行、并发和代码性能优化的边界，在本书中，代码性能优化特指除了并行和并发外的代码优化方法，比如向量化和提高指令流水线效率，在一些情况下，笔者也会将向量化独立来解说。
一般来说，并发是为了满足应用的功能需求，比如在计算的同时，用户界面能够响应用户；一个运行在16核处理器上的网络服务器需要同时支持64个用户而开启了64个线程。而并行更多的是为了提高速度或为了解决更大规模的问题。
人类生活的方方面面存在着并行或者并发，边吃饭边看电视，双手同时拔草，甚至吃饭时，嘴巴的动作和手的动作也是并行的。和人类社会广泛存在并行不同的是：计算机编程几乎一直都是串行的，绝大多数的程序只存在一个进程或线程（本书将它们统称为“控制流”）。对并行和向量化的研究可以追溯到20世纪60年代，但是直到近年来才得到广泛的关注，究其原因，主要是自2003年以来，能耗和散热问题限制了 X86 CPU频率的提高，从而导致多核和向量处理器的广泛使用。
2003年以前，在摩尔定律的作用下，单核标量处理器的性能持续提升，软件开发人员只需要写好软件，而性能就等待下次硬件的更新。在2003年之前的几十年里，这种“免费午餐”的模式一直在持续。2003年后，主要由于功耗的原因，这种“免费的午餐”已经不复存在。为了生存，各硬件生产商不得不采用各种方式以提高硬件的计算能力，以下是目前最流行的三种方式。
1）让处理器一个周期处理多条指令，这多条指令可相同可不同。如Intel Haswell处理器一个周期可执行4条整数加法指令、2条浮点乘加指令，同时访存和运算指令也可同时执行。
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的可编程能力不断提高，GPU通用计算比以前的GPGPU（General-Purpose Computing on Graphics Processing Units）容易许多，另外由于GPU具有比CPU强大的峰值计算能力，近来引起了许多科研人员和企业的兴趣。
近两三年来，在互联网企业中，GPU和并行计算越来越受到重视。无论是国外的Google、Facebook还是国内的百度、腾讯、阿里和360，都在使用代码优化、并行计算和GPU来完成以前不能完成的任务。
10年前，并行计算还是大实验室里面教授们的研究对象，而今天多核处理器和GPU的普及已经使得普通人就可以研究它们。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
代码性能优化和并行技术被许多顶级开发人员看成“不传之秘”或“只可意会，不可言传”的技术。本书将会把这些“不传之秘”一一展示在开发者面前，并且解释为什么。由于代码性能的具体细节非常难以解释清楚，笔者尽量在高层解释，避免陷入细节里。在写作此书时，我并没有查到世界上有类似的写给普通开发者的书籍，本书可算是第一本。
开发人员通常比较忙，因此本书力求简洁明了，点到为止即可。
读者对象
由于多核处理器和GPU已经非常便宜，而代码优化、向量化和并行已经深入IT行业的骨髓，所有IT行业的从业者都应当阅读本书，如果非要列一个清单，笔者认为下列人员应当阅读：
互联网及传统行业的IT从业者，尤其是希望将应用移植到多核向量处理器或GPU的开发人员。
大中专院校、研究所的学生和教授。
如何阅读本书
本系列包括三本书，此书是此系列的第一本，侧重于介绍与代码优化和并行计算相关的理论、算法设计及实践经验。
本书不但包括单核、多核代码的性能优化与并行化，还包括新出现的基于图形处理器（GPU）和移动处理器的代码性能优化及并行化。不但有实际的并行方式的介绍说明，还有理论的分析。笔者希望通过这种方式能够让阅读本文的软件开发人员掌握并行编程方法。
整体而言，本书分为如下几个部分：
理论基础，本部分主要介绍并行软件和硬件基础，并行算法设计思想以及一些软件优化方法。主要包括第1章、第2章、第3章、第5章。
代码优化，本部分主要介绍常见的串行代码优化手段（不包括向量化）。主要内容是第4章。
并行算法设计考量，本部分主要介绍如何设计优良的并行算法并将算法映射到硬件上。主要内容是第6章、第7章、第8章、第9章、第11章和第12章。
如何将现有的串行代码并行化，主要内容是第10章。
第1章　主要介绍并行化和向量化的相关概念，如并行和向量化的作用、为什么并行化和向量化、并行或向量化面临的现实困难。另外还介绍了一些不写代码也能够利用多核处理器性能的一些方法。
第2章　介绍了现代处理器的特性，如指令级并行、向量化并行、线程级并行、处理器缓存金字塔、虚拟存储器和NUMA（非一致内存访问）。
第3章　介绍了算法性能和程序性能的度量与分析。算法性能分析和度量的主要标准是时间复杂度、空间复杂度和笔者自己提出的实现复杂度。程序性能的度量标准主要有：时间、FLOPS、CPI、指令延迟和吞吐量。用来衡量优化一部分代码对程序整体性能的影响主要有：Amdahl定律和Gustafson定律。本章最后介绍了常见的用于程序性能分析的工具。
第4章　介绍了常见的串行代码优化方法。依据优化所涉及的尺度将优化方法归类并分为：系统级别、应用级别、算法级别、函数级别、循环级别、语句级别和指令级别。
第5章　简单介绍了指令级依赖和循环级依赖，并给出许多如何去除依赖的示例，最后以简单介绍处理器硬件支持的寄存器重命名结束。
第6章　介绍了常见的并行编程模型和目前主流的并行编程环境。
第7章　详细介绍了并行算法设计的基本步骤和主要内容：①划分；②通信；③结果归并；④负载均衡。
第8章　介绍了并行程序相比串行程序具有的一些可能的、天然的缺点，并分析了如何缓解某些缺点的方法。
第9章　介绍了如何使用SIMD向量指令、多核多线程和GPU来实现map、reduce、scan和流水线等并行实践模式。通过这些并行实践模式的介绍、解说，希望读者能够通过模式解决一系列相关的并行计算问题。
第10章　介绍了并行化遗留代码的基本步骤，并指出每个步骤的常用方法和需要注意的事项，最后以如何并行化word2vec做为示例结束。
第11章　介绍了常见的几种超级并行方式，并且以矩阵向量乘为例展示在各种超级并行模式下如何划分数据和计算。最后介绍如何在几种超级并行方式下优化矩阵乘运算。
第12章　给出了设计并行算法需要注意的一些准则，以方便读者随时查阅。
附录A　介绍了整数的运算规则和浮点数据的IEEE-754表示。
本书希望通过这种方式能够让读者渐进地、踏实地拥有并行思维，并且能够写出优良的并行代码。
对对并行和代码优化不太了解的人员，笔者希望你们按章节顺序仔细阅读。而对对并行或代码优化非常了解的人员，可按照需求选择章节阅读。
勘误和支持
由于笔者的水平有限、工作繁忙、编写时间仓促，而并行和代码优化又是一个正在高速发展的、影响因素非常多、博大精深且具有个人特色的领域，许多问题还没有统一的解决方案，虽然笔者已经努力确认每个细节，但书中难免会出现一些不准确的地方甚至是错误，恳请读者批评指正。你可以将书中的错误或写得不好的地方通过邮件发送到ily152832912@gmail.com或微信联系“风辰”，以便再版时修正，另外笔者会尽快回复邮件。如果你有更多的宝贵意见，也欢迎发送邮件，期待能够得到你们的真挚反馈。
致谢
首先要感谢我的老婆，她改变了我的人生轨迹，让我意识到人生有如此多的乐趣。
感谢中国地质大学（武汉）的图书馆，那是我对并行计算产生兴趣的地方。感谢中国科学院研究生院和中国科学院图书馆，在那里我奠定了从事并行计算事业的基础。
感谢我的朋友陈实富、赖俊杰、高洋等，如果没有你们，我还需要更多时间来提升水平。感谢我的老板王鹏、吴韧和汤晓欧，在这些技术大佬和“人生赢家”的指导下，我才会成长得如此迅速。
感谢机械工业出版社华章分社的高婧雅和杨福川，是你们引导我将这本书付梓成书，是你们帮我修改书稿，让它变得可读，是你们的鼓励、帮助以及引导使我顺利完成全部书稿。
最后感谢我的爸爸、妈妈、姥姥、姥爷、奶奶、爷爷，感谢你们将我培养成人，并时时刻刻为我提供精神力量！
谨以此书献给我最爱的家人，以及众多热爱代码优化、并行计算的朋友们！愿你们快乐地阅读本书！
风辰

计算机\程序设计

我一直认为，计算机科学就是计算的科学, 能写出正确而高效的代码是这个学科以及相关学科的基本功。高效的代码意味着代码作者对计算硬件细节和计算软件系统细节的充分及深入了解，对代码并行化以及代码性能优化的深刻认识。以近年极度火爆的深度学习为例，人们应该同样记住两位英雄人物：Alex Krizhevsky和Yangqin Jia。他们的优秀程序设计能力和代码优化能力让他们鹤立鸡群, 他们的工作让世人受益非浅。本书的作者风辰也是一位优秀、务实的并行计算、代码性能优化人才，他将多年的并行计算实践和代码性能优化经验及感悟以全新并具有高度的视角集结成书，与众多程序员分享代码向量化和并行化的奥义。书中有大量风辰独有的真知灼见，当你购买这本书时, 恭喜你, 你已经找到了你正在寻找的, 提高自身修为的一扇大门。
——吴韧，百度深度学习研究院“杰出科学家”
近两三年来，在互联网企业中，GPU和并行计算越来越受到重视。无论是国外的Google、Facebook还是国内的百度、腾讯、阿里和360，都在使用代码优化、并行计算和GPU来完成以前不能完成的任务。而现在中小型企业也在使用代码优化和并行化技术来提升产品的使用体验。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
本书不但介绍了恰当的、全新的代码性能优化的度量方法和标准，还介绍了常见的并行编程模型、编程环境、并行算法设计和编程模式的实践、遗留代码并行化和超级并行等读者最为关心的问题，使广大开发人员可以快速进入并行计算的实践工作。
本书亮点：
 提出并解释了实现复杂度的概念及如何使用实现复杂度来分析程序性能。
 介绍常见的串行代码优化方法。
 提出了设计并行算法的步骤、方法和准则，以及如何将并行算法映射到硬件上以获得高性能。

刘文志　著：暂无简介

前言
第1章　绪论 1
1.1　并行和向量化的作用 2
1.2　为什么要并行或向量化 3
1.3　为什么向量化或并行难 4
1.4　并行的替代方法 9
1.5　进程、线程与处理器 10
1.6　并行硬件平台 13
1.7　向量化和多核技术不是万能的 17
1.8　本章小结 18
第2章　现代处理器特性 19
2.1　指令级并行 20
2.1.1　指令流水线 20
2.1.2　乱序执行 22
2.1.3　指令多发射 22
2.1.4　分支预测 23
2.1.5　VLIW 23
2.2　向量化并行 24
2.2.1　SIMD 24
2.2.2　SIMT 25
2.3　线程级并行 25
2.3.1　内核线程和用户线程 26
2.3.2　多线程编程库 26
2.3.3　多核上多线程并行要注意的问题 27
2.3.4　多线程程序在多核和单核上运行的不同 28
2.4　缓存 28
2.4.1　缓存层次结构 29
2.4.2　缓存一致性 30
2.4.3　缓冲不命中 31
2.4.4　写缓存 32
2.4.5　越过缓存 33
2.4.6　硬件预取 34
2.4.7　缓存结构 34
2.4.8　映射策略 35
2.5　虚拟存储器和TLB 36
2.6　NUMA技术 37
2.7　本章小结 39
第3章　算法性能和程序性能的度量与分析 40
3.1　算法分析的性能度量标准 40
3.1.1　时间复杂度与空间复杂度 41
3.1.2　实现复杂度 43
3.2　程序和指令的性能度量标准 47
3.3　程序性能优化的度量标准 52
3.3.1　加速比与并行效率 52
3.3.2　Amdahl定律和Gustafson定律 53
3.4　程序性能分析实用工具 54
3.5　本章小结 60
第4章　串行代码性能优化 61
4.1　系统级别 62
4.2　应用级别 65
4.3　算法级别 68
4.4　函数级别 71
4.4.1　函数调用参数 71
4.4.2　内联小函数 72
4.5　循环级别 72
4.5.1　循环展开 72
4.5.2　循环累积 73
4.5.3　循环合并 74
4.5.4　循环拆分 74
4.6　语句级别 75
4.6.1　减少内存读写 75
4.6.2　选用尽量小的数据类型 76
4.6.3　结构体对齐 77
4.6.4　表达式移除 78
4.6.5　分支优化 78
4.6.6　优化交换性能 82
4.7　指令级别 83
4.8　本章小结 84
第5章　依赖分析 86
5.1　指令级依赖 87
5.1.1　结构化依赖 87
5.1.2　数据依赖 88
5.1.3　控制依赖 89
5.2　循环级依赖 90
5.2.1　循环数据依赖 90
5.2.2　循环控制依赖 92
5.3　寄存器重命名 93
5.4　本章小结 94
第6章　并行编程模型及环境 95
6.1　并行编程模型 95
6.1.1　指令级并行 96
6.1.2　向量化并行 97
6.1.3　易并行 98
6.1.4　任务并行 99
6.1.5　数据并行 100
6.1.6　循环并行化 101
6.1.7　流水线并行 102
6.1.8　区域分解并行 103
6.1.9　隐式和显式并行化 104
6.1.10　SPMD 104
6.1.11　共享存储器并行 105
6.1.12　分布式存储器并行 105
6.2　常见并行编程环境 105
6.2.1　MPI 106
6.2.2　OpenMP 108
6.2.3　fork/pthread 108
6.2.4　CUDA 109
6.2.5　OpenCL 109
6.2.6　OpenACC 110
6.2.7　NEON内置函数 111
6.2.8　SSE/AVX内置函数 111
6.3　本章小结 111
第7章　并行算法设计方法 114
7.1　划分 114
7.1.1　分而治之 115
7.1.2　划分原则 116
7.1.3　常见划分方法 116
7.1.4　并行性和局部性 117
7.2　通信 118
7.2.1　操作的原子性 119
7.2.2　结果的可见性 120
7.2.3　顺序一致性 121
7.2.4　函数的可重入与线程安全 122
7.2.5　volatile关键字 122
7.2.6　锁 123
7.2.7　临界区 126
7.2.8　原子操作 127
7.2.9　栅栏 128
7.3　结果归并 129
7.4　负载均衡 129
7.4.1　静态负载均衡 130
7.4.2　动态负载均衡 130
7.4.3　动态负载均衡算法的一般步骤 131
7.5　本章小结 133
第8章　并行算法缺陷 134
8.1　启动结束时间 134
8.2　负载均衡 135
8.3　竞写 136
8.4　锁 136
8.4.1　死锁 137
8.4.2　活锁 139
8.5　饿死 140
8.6　伪共享 140
8.7　原子操作 141
8.8　存储器栅栏 142
8.9　缓存一致性 142
8.10　顺序一致性 143
8.11　volatile同步错误 143
8.12　本章小结 144
第9章　并行编程模式实践 146
9.1　map模式 147
9.2　reduce模式 149
9.3　结合map和reduce模式 152
9.4　scan模式 155
9.5　zip/unzip 模式 156
9.6　流水线模式 159
9.7　本章小结 161
第10章　如何并行遗留代码 162
10.1　找出软件的计算热点 163
10.2　判断是否并行化热点 164
10.3　设计算法并实现 166
10.3.1　选择何种工具进行向量化或并行化 166
10.3.2　重构热点代码 167
10.3.3　依据硬件实现算法 168
10.4　将实现后的代码嵌入原软件 169
10.4.1　混合编译 169
10.4.2　动态链接库 170
10.5　示例：如何并行化word2vec 171
10.6　本章小结 174
第11章　超级并行 176
11.1　超级并行方式编程 176
11.1.1　进程+线程 177
11.1.2　进程+GPU线程 178
11.1.3　线程+GPU线程 181
11.1.4　线程+向量指令 181
11.1.5　进程+线程+向量指令 182
11.1.6　进程+线程+GPU线程 183
11.2　矩阵乘法 184
11.2.1　多机CPU矩阵乘法 184
11.2.2　单机多GPU矩阵乘法 187
11.2.3　多机多GPU矩阵乘法 188
11.3　本章小结 189
第12章　并行算法设计的一般准则 190
12.1　并行算法设计14准则 190
12.2　本章小结 194
附录A　整型数据与浮点数据 195