![并行算法设计与性能优化[按需印刷]](http://images.china-pub.com/ebook4705001-4710000/4706195/zcover.jpg)
基本信息
编辑推荐
并行计算领域著名专家撰写，百度深度学习研究院“杰出科学家”吴韧鼎力推荐
结合大量示例和伪代码，全面讲解如何通过并行算法设计实现单核/多核处理器、CPU和移动处理器的性能优化及相关的并行化秘技，并首次提出实现复杂度的全新性能度量标准。
内容简介
书籍
计算机书籍
本书是"并行计算与性能优化"系列的第1本，主要讲解了并行计算的核心理论、算法设计和实践，以及代码的性能优化，第2本和第3本则涵盖了并行编程方法与优化实践、科学计算与企业级应用的并行优化等重要主题，这些内容被许多顶级开发人员视为"不传之秘"。本书作者是国内顶尖的并行计算专家，曾任英伟达并行计算工程师和百度在线高级研发工程师，在该领域的经验和修为极为深厚，他毫不吝啬地将自己多年的积累呈现在这3本书中，得到了百度深度学习研究院"杰出科学家"吴韧的高度评价和强烈推荐。
本书结合大量示例和伪代码，详细介绍了单核代码的性能优化和向量化技术，在现代多核处理器上如何设计并行算法，以及基于GPU和移动处理器（ARM）的代码性能优化与并行化。
全书12章，逻辑上分为四大部分：
·并行计算理论基础
主要介绍并行现状、与并行计算紧密相关的现代处理器的技术与特点，算法与程序性能的度量和分析的新旧标准及实用工具，以及代码依赖关系的分析和去除处理。
·代码优化
首先从系统、应用、算法、函数、循环、语句和指令7大维度讲解了常见的串行代码优化手段，然后讲解了如何通过多种方式将现有的串行代码向量化和并行化，以提高效率和利用率。
·并行算法设计考量
主要讲解了如何设计优良的并行算法以及将并行算法映射到具体硬件上，涵盖常见的并行编程环境、并行算法设计方法、并行算法的缺陷、编程模式实践、一般准则，等等。
·遗留代码的并行化
主要讲解了如何找出软件的计算热点，如何合理地选择部分并行或者整体并行，然后将实现后的代码嵌入原软件，以提高企业现有代码的利用率，并以实例加以说明。
计算机书籍
本书是"并行计算与性能优化"系列的第1本，主要讲解了并行计算的核心理论、算法设计和实践，以及代码的性能优化，第2本和第3本则涵盖了并行编程方法与优化实践、科学计算与企业级应用的并行优化等重要主题，这些内容被许多顶级开发人员视为"不传之秘"。本书作者是国内顶尖的并行计算专家，曾任英伟达并行计算工程师和百度在线高级研发工程师，在该领域的经验和修为极为深厚，他毫不吝啬地将自己多年的积累呈现在这3本书中，得到了百度深度学习研究院"杰出科学家"吴韧的高度评价和强烈推荐。
本书结合大量示例和伪代码，详细介绍了单核代码的性能优化和向量化技术，在现代多核处理器上如何设计并行算法，以及基于GPU和移动处理器（ARM）的代码性能优化与并行化。
全书12章，逻辑上分为四大部分：
·并行计算理论基础
主要介绍并行现状、与并行计算紧密相关的现代处理器的技术与特点，算法与程序性能的度量和分析的新旧标准及实用工具，以及代码依赖关系的分析和去除处理。
·代码优化
首先从系统、应用、算法、函数、循环、语句和指令7大维度讲解了常见的串行代码优化手段，然后讲解了如何通过多种方式将现有的串行代码向量化和并行化，以提高效率和利用率。
·并行算法设计考量
主要讲解了如何设计优良的并行算法以及将并行算法映射到具体硬件上，涵盖常见的并行编程环境、并行算法设计方法、并行算法的缺陷、编程模式实践、一般准则，等等。
·遗留代码的并行化
主要讲解了如何找出软件的计算热点，如何合理地选择部分并行或者整体并行，然后将实现后的代码嵌入原软件，以提高企业现有代码的利用率，并以实例加以说明。
作译者
刘文志 花名风辰，毕业于中国科学院研究生院，闻名于并行计算江湖，尤善异构并行计算（X86、ARM、GPU、APU、PHI）和大规模集群计算相关技术，有7年相关经验，涉及图像处理、计算机视觉、数据挖掘和石油勘探。曾任英伟达并行计算工程师（协助建立英伟达北京CUDA团队）、百度在线高级研发工程师（协助建立百度深度学习实验室异构计算团队）。
目录
前言
第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
第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
前言
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的普及已经使得普通人就可以研究它们。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
代码性能优化和并行技术被许多顶级开发人员看成“不传之秘”或“只可意会，不可言传”的技术。本书将会把这些“不传之秘”一一展示在开发者面前，并且解释为什么。由于代码性能的具体细节非常难以解释清楚，笔者尽量在高层解释，避免陷入细节里。在写作此书时，我并没有查到世界上有类似的写给普通开发者的书籍，本书可算是第一本。
开发人员通常比较忙，因此本书力求简洁明了，点到为止即可。
读者对象
在解释为什么笔者认为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的普及已经使得普通人就可以研究它们。对于软件开发人员来说，如果不掌握并行计算和代码性能优化技术，在不久的将来就会被淘汰。
代码性能优化和并行技术被许多顶级开发人员看成“不传之秘”或“只可意会，不可言传”的技术。本书将会把这些“不传之秘”一一展示在开发者面前，并且解释为什么。由于代码性能的具体细节非常难以解释清楚，笔者尽量在高层解释，避免陷入细节里。在写作此书时，我并没有查到世界上有类似的写给普通开发者的书籍，本书可算是第一本。
开发人员通常比较忙，因此本书力求简洁明了，点到为止即可。
读者对象
媒体评论
我一直认为，计算机科学就是计算的科学, 能写出正确而高效的代码是这个学科以及相关学科的基本功。高效的代码意味着代码作者对计算硬件细节和计算软件系统细节的充分及深入了解，对代码并行化以及代码性能优化的深刻认识。以近年极度火爆的深度学习为例，人们应该同样记住两位英雄人物：Alex Krizhevsky和Yangqing Jia。他们的优秀程序设计能力和代码优化能力让他们鹤立鸡群, 他们的工作让世人受益匪浅。本书的作者风辰也是一位优秀、务实的并行计算和代码性能优化人才，他将多年的并行计算实践和代码性能优化经验及感悟以全新并具有高度的视角集结成书，与众多程序员分享代码向量化和并行化的奥义。书中有大量风辰独有的真知灼见，当你购买这本书时, 恭喜你, 你已经找到了你正在寻找的、提高自身修为的一扇大门。
--吴韧百度深度学习研究院"杰出科学家"
--吴韧百度深度学习研究院"杰出科学家"
