前言

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或微信联系“风辰”，以便再版时修正，另外笔者会尽快回复邮件。如果你有更多的宝贵意见，也欢迎发送邮件，期待能够得到你们的真挚反馈。

致谢

首先要感谢我的老婆，她改变了我的人生轨迹，让我意识到人生有如此多的乐趣。

感谢中国地质大学（武汉）的图书馆，那是我对并行计算产生兴趣的地方。感谢中国科学院研究生院和中国科学院图书馆，在那里我奠定了从事并行计算事业的基础。

感谢我的朋友陈实富、赖俊杰、高洋等，如果没有你们，我还需要更多时间来提升水平。感谢我的老板王鹏、吴韧和汤晓欧，在这些技术大佬和“人生赢家”的指导下，我才会成长得如此迅速。

感谢机械工业出版社华章公司的高婧雅和杨福川，是你们引导我将这本书付梓成书，是你们帮我修改书稿，让它变得可读，是你们的鼓励、帮助以及引导使我顺利完成全部书稿。

最后感谢我的爸爸、妈妈、姥姥、姥爷、奶奶、爷爷，感谢你们将我培养成人，并时时刻刻为我提供精神力量！

谨以此书献给我最爱的家人，以及众多热爱代码优化、并行计算的朋友们！愿你们快乐地阅读本书！

风辰