本书主要介绍并行计算相关的算法的设计和并行计算的性能优化技巧，涵盖现代处理器的特性、衡量程序性能的方法、串行代码性能优化、并行编程模型及其环境、并行算法设计、遗留代码的并行处理、并行编程模型、混合并行等核心技法与实践技巧。
【前言】
Preface 前 言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（GeneralPurpose 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 介绍了整数的运算规则和浮点数据的IEEE754表示。
本书希望通过这种方式能够让读者渐进地、踏实地拥有并行思维，并且能够写出优良的并行代码。
对对并行和代码优化不太了解的人员，笔者希望你们按章节顺序仔细阅读。而对对并行或代码优化非常了解的人员，可按照需求选择章节阅读。
勘误和支持由于笔者的水平有限、工作繁忙、编写时间仓促，而并行和代码优化又是一个正在高速发展的、影响因素非常多、博大精深且具有个人特色的领域，许多问题还没有统一的解决方案，虽然笔者已经努力确认每个细节，但书中难免会出现一些不准确的地方甚至是错误，恳请读者批评指正。你可以将书中的错误或写得不好的地方通过邮件发送到ily152832912@gmail.com或微信联系“风辰”，以便再版时修正，另外笔者会尽快回复邮件。如果你有更多的宝贵意见，也欢迎发送邮件，期待能够得到你们的真挚反馈。
致谢首先要感谢我的老婆，她改变了我的人生轨迹，让我意识到人生有如此多的乐趣。
感谢中国地质大学（武汉）的图书馆，那是我对并行计算产生兴趣的地方。感谢中国科学院研究生院和中国科学院图书馆，在那里我奠定了从事并行计算事业的基础。
感谢我的朋友陈实富、赖俊杰、高洋等，如果没有你们，我还需要更多时间来提升水平。感谢我的老板王鹏、吴韧和汤晓欧，在这些技术大佬和“人生赢家”的指导下，我才会成长得如此迅速。
感谢机械工业出版社华章公司的高婧雅和杨福川，是你们引导我将这本书付梓成书，是你们帮我修改书稿，让它变得可读，是你们的鼓励、帮助以及引导使我顺利完成全部书稿。
后感谢我的爸爸、妈妈、姥姥、姥爷、奶奶、爷爷，感谢你们将我培养成人，并时时刻刻为我提供精神力量！
谨以此书献给我爱的家人，以及众多热爱代码优化、并行计算的朋友们！愿你们快乐地阅读本书！
风辰
【目录】
前言
第1章绪论
1.1并行和向量化的作用
1.2为什么要并行或向量化
1.3为什么向量化或并行难
1.4并行的替代方法
1.5进程、线程与处理器
1.6并行硬件平台
1.7向量化和多核技术不是的
1.8本章小结
第2章现代处理器特性
2.1指令级并行
2.1.1指令流水线
2.1.2乱序执行
2.1.3指令多发射
2.1.4分支预测
2.1.5VLIW
2.2向量化并行
2.2.1SIMD
2.2.2SIMT
2.3线程级并行
2.3.1内核线程和用户线程
2.3.2多线程编程库
2.3.3多核上多线程并行要注意的问题
2.3.4多线程程序在多核和单核上运行的不同
2.4缓存
2.4.1缓存层次结构
2.4.2缓存一致性
2.4.3缓冲不命中
2.4.4写缓存
2.4.5越过缓存
2.4.6硬件预取
2.4.7缓存结构
2.4.8映射策略
2.5虚拟存储器和TLB
2.6NUMA技术
2.7本章小结
第3章算法性能和程序性能的度量与分析
3.1算法分析的性能度量标准
3.1.1时间复杂度与空间复杂度
3.1.2实现复杂度
3.2程序和指令的性能度量标准
3.3程序性能优化的度量标准
3.3.1加速比与并行效率
3.3.2Amdahl定律和Gustafson定律
3.4程序性能分析实用工具
3.5本章小结
第4章串行代码性能优化
4.1系统级别
4.2应用级别
4.3算法级别
4.4函数级别
4.4.1函数调用参数
4.4.2内联小函数
4.5循环级别
4.5.1循环展开
4.5.2循环累积
4.5.3循环合并
4.5.4循环拆分
4.6语句级别
4.6.1减少内存读写
4.6.2选用尽量小的数据类型
4.6.3结构体对齐
4.6.4表达式移除
4.6.5分支优化
4.6.6优化交换性能
4.7指令级别
4.8本章小结
第5章依赖分析
5.1指令级依赖
5.1.1结构化依赖
5.1.2数据依赖
5.1.3控制依赖
5.2循环级依赖
5.2.1循环数据依赖
5.2.2循环控制依赖
5.3寄存器重命名
5.4本章小结
第6章并行编程模型及环境
6.1并行编程模型
6.1.1指令级并行
6.1.2向量化并行
6.1.3易并行
6.1.4任务并行
6.1.5数据并行
6.1.6循环并行化
6.1.7流水线并行
6.1.8区域分解并行
6.1.9隐式和显式并行化
6.1.10SPMD
6.1.11共享存储器并行
6.1.12分布式存储器并行
6.2常见并行编程环境
6.2.1MPI
6.2.2OpenMP
6.2.3fork/pthread
6.2.4CUDA
6.2.5OpenCL
6.2.6OpenACC
6.2.7NEON内置函数
6.2.8SSE/AVX内置函数
6.3本章小结
第7章并行算法设计方法
7.1划分
7.1.1分而治之
7.1.2划分原则
7.1.3常见划分方法
7.1.4并行性和局部性
7.2通信
7.2.1操作的原子性
7.2.2结果的可见性
7.2.3顺序一致性
7.2.4函数的可重入与线程安全
7.2.5volatile关键字
7.2.6锁
7.2.7临界区
7.2.8原子操作
7.2.9栅栏
7.3结果归并
7.4负载均衡
7.4.1静态负载均衡
7.4.2动态负载均衡
7.4.3动态负载均衡算法的一般步骤
7.5本章小结
第8章并行算法缺陷
8.1启动结束时间
8.2负载均衡
8.3竞写
8.4锁
8.4.1死锁
8.4.2活锁
8.5饿死
8.6伪共享
8.7原子操作
8.8存储器栅栏
8.9缓存一致性
8.10顺序一致性
8.11volatile同步错误
8.12本章小结
第9章并行编程模式实践
9.1map模式
9.2reduce模式
9.3结合map和reduce模式
9.4scan模式
9.5zip/unzip模式
9.6流水线模式
9.7本章小结
第10章如何并行遗留代码
10.1找出软件的计算热点
10.2判断是否并行化热点
10.3设计算法并实现
10.3.1选择何种工具进行向量化或并行化
10.3.2重构热点代码
10.3.3依据硬件实现算法
10.4将实现后的代码嵌入原软件
10.4.1混合编译
10.4.2动态链接库
10.5示例：如何并行化word2vec
10.6本章小结
第11章超级并行
11.1超级并行方式编程
11.1.1进程+线程
11.1.2进程+GPU线程
11.1.3线程+GPU线程
11.1.4线程+向量指令
11.1.5进程+线程+向量指令
11.1.6进程+线程+GPU线程
11.2矩阵乘法
11.2.1多机CPU矩阵乘法
11.2.2单机多GPU矩阵乘法
11.2.3多机多GPU矩阵乘法
11.3本章小结
第12章并行算法设计的一般准则
12.1并行算法设计14准则
12.2本章小结
附录A整型数据与浮点数据
