作者：刘文志
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
并行算法设计与性能优化试读：
前言
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或微信联系“风辰”，以便再版时修正，另外笔者会尽快回复邮件。如果你有更多的宝贵意见，也欢迎发送邮件，期待能够得到你们的真挚反馈。
致谢
首先要感谢我的老婆，她改变了我的人生轨迹，让我意识到人生有如此多的乐趣。
感谢中国地质大学（武汉）的图书馆，那是我对并行计算产生兴趣的地方。感谢中国科学院研究生院和中国科学院图书馆，在那里我奠定了从事并行计算事业的基础。
感谢我的朋友陈实富、赖俊杰、高洋等，如果没有你们，我还需要更多时间来提升水平。感谢我的老板王鹏、吴韧和汤晓欧，在这些技术大佬和“人生赢家”的指导下，我才会成长得如此迅速。
感谢机械工业出版社华章公司的高婧雅和杨福川，是你们引导我将这本书付梓成书，是你们帮我修改书稿，让它变得可读，是你们的鼓励、帮助以及引导使我顺利完成全部书稿。
最后感谢我的爸爸、妈妈、姥姥、姥爷、奶奶、爷爷，感谢你们将我培养成人，并时时刻刻为我提供精神力量！
谨以此书献给我最爱的家人，以及众多热爱代码优化、并行计算的朋友们！愿你们快乐地阅读本书！风辰
第1章 绪论
在2003年以前，计算机性能的提升主要依赖CPU主频的提升，科研人员只要写好程序，几乎用不着优化，因为下一代CPU主频的提升会轻易地提升软件的性能，这使得计算机行业进入一个良性循环：由于性能的提升，人们能够使用计算机做更多的事，当人们习惯当前计算机的速度后，又会提出新的性能要求，让计算机以更快的速度做更多的事；CPU生产商也乐于升级硬件以赚取更多的利润。计算机行业在这种良性互动下发展了几十年，但是由于CPU的功耗与频率的三次方近似成正比，无限制地提升频率已不可能。到2003年，CPU频率的提升接近停止，为了能够卖出自己的产品，各CPU生产商纷纷通过各种方式提升计算能力，如提高指令级并行能力、在一个时钟周期内执行更多指令、向量指令、多核和超线程技术等。从长远来看，最有可能引领未来的是向量化和多核技术：向量化是指使用同一条指令同时操作多个数据；多核技术是采用在同一个芯片上集成多个核心的办法。而高端的服务器版本则会集成多个多核处理器，这称为“多路”。相比CPU从单核到多核、多路，从标量到向量的发展，图形处理单元（GPU）一出世即通过将几百、几千核心集成在一块硅片上以满足图形图像及视频对性能的需求，这称为“众核”。一方面：众核处理器集成的核心数量远远超过多核；另一方面：众核处理器将更高比例的晶体管用于计算，因此其原生性能也超过多核。
作为本书的绪论，本章会从并行和性能优化的作用及为什么需要并行开始，既而介绍并行和代码性能优化面临的现实困难；然后针对某些特殊情况，介绍一些不修改代码也能利用多核处理器性能的几种替代方法；再介绍与多核技术息息相关的进程、线程等相关概念；最后介绍目前主流的向量和多核计算平台；最后本章以笔者对多核和向量化的点评结束。
1.1 并行和向量化的作用
并行和向量化的首要作用是尽量发挥硬件提供的全部计算能力，以减少延迟（更快地完成计算任务）或提高吞吐量（在相同的时间内完成更多任务）。目前绝大多数软件都是标量且串行的，虽然目前CPU使用乱序执行、指令流水线等指令级并行技术提升了处理器效率，这些技术的使用使得从指令级来看程序的执行并不完全和串行的代码系列一致，但是软件依旧只有一个标量控制流。以Intel Haswell I3-4130处理器为例，它使用了256位的向量，集成了2个核心，那么在其上运行的、使用32位浮点计算的标量串行代码最多能够发挥峰值性能的1/16，其中标量计算意味着只能发挥向量运算性能的1/8，而串行代码只能发挥2核中1核的性能。标量串行软件只能利用多核向量处理器提供的部分计算能力，为了利用多核向量处理器提供的全部计算能力，必须采用向量化和并行化的思维方式编写软件代码，而现有的串行软件必须修改才能利用多核向量处理器的全部计算能力。
并行/并发的另一个作用是实现功能和同时满足多个用户请求：比如需要软件在计算的同时能够响应用户的交互，此时就必须使用并行/并发，因为存在两个或多个控制流；假设一个用户请求需要100ms完成，那么如果使用单线程服务的话，1秒钟可以满足10个用户请求，但是如果使用20个线程的话，每个用户请求的满足时间可能只需要150ms，甚至更少。
在科学计算中，物理模拟需要长时间的运行以获得更精确的结果，因此并行和向量化技术应用比较广泛。在这个领域，并行和向量化主要提供以下两方面的作用：
❏让程序运算得更快，以节约时间。假设程序原来需要一年才能模拟一次，通过使用并行和向量技术，现在一个月就能够完成一次模拟，缩短的11个月时间就可以多做实验、提前发论文、提前毕业或陪女朋友逛街等。
❏让程序能够计算更大规模的体系。大规模体系要求更大的计算能力，因此对并行和向量化的需求更为迫切，而且大规模意味着可以更真实地模拟现实系统。假设一个二维域分解问题的计算量和区域的大小成比，假设使用并行和向量化技术获得的计算能力是原来的36倍，那么可以将模拟区域两个方向都扩大为原来的6倍。
1.2 为什么要并行或向量化
从2003年开始，CPU频率的提升接近停止，那种每次硬件的更新都会提升标量串行软件的性能的“免费午餐”已经结束，为了提升软件的性能，软件开发人员不得不使用并行或向量化技术。除了现实世界中的硬件已经完全是并行硬件外，还有几个原因要求我们必须使用并行或/和向量化：现在的编译器不能很好地自动向量化或并行串行软件（一些编译器能够自动向量化和并行简单程序）；现实世界中人类对计算能力的需求永无止境。
有些编译器公司和组织（如Intel、GNU、PGI、CAPS）想让编译器自动向量化或并行串行程序，这一直是人们奋斗的目标。20世纪80年代中期，基于依赖分析的自动向量化工具已经基本可用，可以帮助程序员将Fortran语言代码移植到向量计算机上进行并行计算。现代的GCC能够向量化和并行一些非常简单的代码，但是对于复杂一些的程序基本上无能为力。实际上，即使是简单的代码，自动向量化或并行的性能也很难做到完美（通常性能比手工编写的要差很多）。其他的一些相关的研究，包括共享存储的MIMD（Multi instruction Multi Data，多指令多数据）和分布式存储结构的自动并行化，到目前为止，这些方法都少有进展。实际上，自动向量化或并行的主要难点在于编译器没有办法收集/分析向量化或并行所需的数据相关性和控制相关性等信息，必须需要程序开发人员干预。现在，研究的重点转向基于编程语言的策略研究，即从开发人员那里获得更多有关逻辑控制和数据相关性的描述，同时利用自动向量化或并行技术来减轻程序设计的负担。OpenMP、OpenACC、CUDA和OpenCL就是其中的典型代表。
由于标量单核的性能已经不能大幅度提升，以及向量多核/众核技术的普及，只有向量化或并行才能充分利用多核/众核技术带来的性能提升，而研发人员总能发掘出要求更高计算能力的应用（希望程序能够运行得更快或者能够计算更大规模的问题），这些应用对计算能力的需求推动着硬件和软件技术向前发展。一旦软硬件技术的发展暂时满足了应用对计算能力的需求，科研人员又会提出更高的要求。这种良性互动推动着科学发展。只是其中的一方由硬件厂商变成了硬件厂商和软件开发人员的结合，而硬件厂商通常只管卖出产品，发挥多核向量处理器性能的实现责任落在了开发人员肩上，而开发人员没有选择。
1.3 为什么向量化或并行难
向量化或并行编程方式和目前通行的标量串行软件开发方式并不一样，它要求开发人员显式地编码以处理多核向量代码中向量内的多个元素、多个控制流之间的依赖关系，这使得向量化或并行软件的设计和开发难度远超标量串行软件，主要原因有人为的，也有技术方面的。本节将会介绍这些原因和可能的解决办法。
由于多核与并行技术的流行只是近十年的事情，虽然向量化技术已经使用了多年，但是过去软件开发人员没有动力去采用它们，因此目前的大多数软件开发人员没有足够的经验来应对向量化或并行的挑战。而初学者也没有很好的资料及成熟的项目代码学习，另外向量化或并行编译器的低能以及向量化和并行调试工具的匮乏也增加了并行化与向量化编程的难度，这种现象和计算机编程早期一样。在计算机编程的早期，只有科学家才能编程，一方面那个时代只有科学家才能接触到计算机，另一方面那个时代还没有高级程序设计语言，必须要使用机器语言编程，而今天几乎人人都能编程。随着未来向量化和并行化技术的流行，最终向量化或并行编程将会越来越简单，成为软件开发人员的必备技能。
综合分析，笔者以为向量化或并行化难的主要技术原因有以下几个。
❏没有很好的设计方法学：向量化和并行的本质在某种意义上和现行的面向对象程序设计方法学冲突。
❏遗留代码：过去几十年积累下来的代码是企业的巨大财富，没有人会放弃。但是向量化或并行它们将面临现实的挑战。
❏可扩展性：如果代码能够发挥双核的计算能力，那么4核、8核、16核呢？是否能够线性扩展？如果处理器拥有上百核心呢？何况并行程序在上百核心的处理器上会发生什么事情也是个未知数。
❏可维护性：向量化或并行代码的可读性通常不如标量串行代码，如何在原来的开发人员离开后，接管的开发人员也能够维护就变得异常重要。
❏任务/数据划分：并行意味着多个控制流同时执行，而向量化意味着同时操作多个数据，并行需要在各个控制流之间划分任务和数据并去除依赖，向量化则需要处理向量内要处理的数据的依赖关系。数据/任务的划分方式不但决定了编程时的难易程度，而且划分带来的负载均衡和通信问题往往也会对程序的最终性能产生决定性的影响。
❏并发访问控制：多个控制流需要访问不同的或相同的资源，如何协调对这些资源的访问就变得非常重要，这也成为并行编程的一大难点。
❏资源划分：资源划分方法不但关系到编程的难易，还关系到最终的性能。
❏与硬件交互：为了最好地发挥性能，软件开发人员通常会应用硬件的特性。
❏对软件开发人员的过高要求，开发工具不够智能，且市场不愿付出相应的薪水。下面笔者将详细解释各个方面。
1.并行程序设计方法学
面向对象设计方法主导了今天大型软件项目的开发，面向对象设计方法指导设计人员通过分离问题中涉及的对象将大问题分解成小问题，然后通过对对象编码以解决小问题，通过利用对象之间的通信来解决的小问题，进而解决大问题。面向对象设计方法学完全没有考虑向量化或并行必须考虑去除的数据和控制的依赖关系，而对象之间的通信本质上来讲是一种依赖关系，因此在某种程度上来说，面向对象设计方法学在本质理念上和向量化或并行冲突。
面向对象方法鼓励隐藏对象拥有的数据，而向量化或并行化需要分析作用在数据上的操作的依赖关系。分析一个对象内拥有的原生数据的依赖关系可能会比较容易，但是如果对象内调用了其他对象，那么可能还需要分析被调用对象的依赖关系，直到所有对象之间的依赖都已经弄清楚。
如果使用一张有向图来表示对象间的引用关系的话，分析对象间依赖的难易程度和有向图中非零元的数量近似成正比。读者可以想象一下：如果代码有成百个对象，且对象之间都有联系，那么分析它们之间的依赖关系将会相当复杂。
对于向量化或并行来说，最合适的设计方法应当是过程化的设计方法加上以数据为中心。面向对象方法习惯将数据隐藏在对象内部，而向量化或并行本质上是以数据为中心的，显式的数据传递对于向量化或并行来说更为适用。通过过程化的设计方法来设计程序流程，以数据为中心来向量化或并行已经是主流的设计方法。
在实践中，开发人员可以通过分析指导的方式来分析面向对象软件中的最耗时代码（也称为热点）。如果程序的热点很集中，那么只需要采用过程化的方法加上数据为中心的方式并行化热点即可；如果程序的热点很分散，那么可能需要重新设计软件。
2.遗留代码
一些大的软件项目拥有成千上万，甚至百万行代码，而通常大项目对性能的要求又更为急迫。如何向量化或并行这些代码却比较难，因为向量化或并行的难度和代码的长度呈线性关系，而且当前维护这些代码的人员通常并非原始的开发人员，这使得向量化或并行的代价和风险都很大。
对于遗留代码来说，基于编译制导的编译器（如OpenMP和OpenACC）会是一个比较安全的选择。编译制导方法基于原来的串行代码，加入指导向量化和并行的伪指令语句。在向量化或并行的过程中，整个代码还能够运行，允许软件开发人员逐步地向量化或并行现有代码，便于调试和验证正确性。
3.可扩展性
现在16核的机器已经开始普及，编写的程序在16核上可扩展性可能会比较好，但是如果把程序放到32核、64核上会发生什么事情，或许此时需要重新改写代码，甚至需要更改向量化或并行方法。
Amdal定律告诉我们：在计算规模一定的前提条件下，只要代码有不能并行的部分，程序是不太可能完全线性加速的。在处理器核心增多的条件下，并行性不好的部分代码可能会成为限制可扩展性的瓶颈。最终程序或者硬件会达到一个核心数量的极限，在这个极限上，再增加核心数量就不会再提升性能了。
可扩展性的问题基本上没有解决办法，因为开发人员不能完全正确地预测在目前还不存在的硬件上发生的事情。通常的缓解方法是要求在开发项目时，留下足够的设计文档，使源码有足够的、准确的注释。这样在核心数增多可扩展性出现问题时，开发人员能够尽快定位问题，找到可能的解决办法。
4.可维护性
由于在原有的标量串行逻辑中加入了向量化和多个控制流的调度内容，而人脑能够同时维护的状态数量是有限的，这使得向量化或并行代码比标量串行代码更加难以维护。
一些项目同时维护一个标量串行版本和一个向量并行版本，这带来一个问题：如何让两者保持一致。
5.任务/数据划分
由于并行需要将多个工作划分成几个小部分，然后每个控制流处理一个或多个部分。任务/数据划分时需要十分小心，划分方式不但影响编程的难易，还影响程序最终的性能。比如，不均匀的划分会导致负载不均衡。（负载均衡用于在控制流之间重新分配任务/数据，以获得更好的性能。）而某些划分方式会导致程序的很多代码顺序执行。另外，划分可能导致某些全局处理变得复杂，此时可能需要同步，以安全地处理这些全局数据。
依据对任务和数据的划分方式的不同，可将并行编程划分为不同的编程模式，本书会在第6章详细分析。
通常划分后各个控制流之间需要一些通信（易并行可能无须通信）。由于通信会引起开销，不成熟的划分方式可能使得通信的开销过大而导致性能的极端下降。
基于CPU的并行编程中，控制流的数量必须加以控制，因为每个控制流都会占用一些资源，比如缓存、虚拟存储器。如果过多的控制流同时在一个处理器核心上执行，那么每个控制流使用的资源数量就会减少，这可能会引起缓存命中率过低，从而降低性能。另一方面，大量的线程可能会带来大量冗余计算和IO操作。
最后，并行会大量增加程序的状态空间，导致人脑难以理解，降低生产率。这一点通常可以通过采用成熟的软件工程方法予以克服。
6.并发访问控制
并行程序的多个控制流需要协调对某个资源的访问，比如打印机，如果不加以控制的话，并行程序打印出来的可能就是“天书”。
基于消息传递的编程模式允许各控制流拥有自己独立的存储器内容，此时数据的交流通过传递消息实现。需要注意由于资源访问导致的死锁、活锁、饿死等问题。
基于共享存储器的编程模式只有一个存储器空间，这样各个控制流访问同一存储器地址时就有可能产生冲突，常见的有“读后写”、“写后读”和“写后写”等问题。这类问题通常通过互斥（互斥是指某一时刻只允许一个控制流访问）资源的访问解决。
并行编程中，最常见的并发访问控制是文件，如果多个控制流同时读一个文件，那么就有可能读到错误的数据，常见的解决方法有：
❏由一个控制流读取文件，然后分发数据；
❏将文件分成多个子文件，每个控制流读取自己的子文件。
前一种方式编程简单，但是由于分发数据操作完全是串行的，有可能会导致过大的性能开销。而后一种则相反。
关于并发资源的访问，比较明智的做法是将访问分为写和读，由于不同的控制流可以同时读一个数据，因此此时无须访问控制。而多个控制流要写的数据必须要特殊处理。需要提醒读者的是，当对一个数据有些控制流读、有些控制流写时，也必须进行特殊处理。
7.资源划分
如何在不同的控制流之间分配计算资源一直是并行的难题，这往往和负载均衡关联，如果分配给某个控制流的资源多，就可能要让其他的控制流等待它计算完成。在基于X86的处理器上，这往往只涉及内存、共享文件的划分。在基于GPU的并行计算环境上，这个问题往往更加复杂。
资源划分与并发访问控制、通信密切相关，好的资源划分方式能够既减少通信又保证资源访问的局部性，这通常意味着优秀的性能和可扩展性。
资源划分通常依赖于应用。数值计算频繁地将矩阵按行、列或子矩阵进行划分。控制流可能会静态地分割数据，或者每个控制流处理的数据量会随时间改变。资源划分是常见的向量化和并行化方式，事实证明它非常有效，但是随之而来的复杂的数据结构的处理也非常有挑战性。
8.与硬件交互
向量化或并行编程要求软件开发人员对机器的配置比较了解，只有这样才能避开硬件的缺陷，编写出高效的代码。涉及新的硬件特性时，经常需要直接与这些硬件打交道。当需要榨取系统的最后一点性能时，通常需要直接访问硬件。
由于不同硬件的设计方法、发挥硬件性能的编程方式及硬件设计上容易造成性能瓶颈的地方都不相同，这些因素可能会导致在某一硬件上性能很好的算法，在另一硬件上性能却非常差。
基于多机系统编程时，网络的拓扑结构和网线的传输速度非常重要；基于多核编程时，核心和缓存之间的组织比较重要（这个方面经常出现的是伪共享问题）；基于GPU编程时，GPU硬件的组织更为重要，如核心之间缓存的组织、DRAM的组织、核心的组织以及程序如何映射到硬件上执行。在这些情况下，软件开发人员需要根据目标硬件，协调程序各个方面的设计。
9.对软件开发人员的要求
目前编译器及开发环境对向量化或并行的支持能力比较差，主要包括以下三个方面：
❏只能自动向量化一些简单的代码，即使能自动向量化代码，通常也不是最优的；
❏只能自动并行化简单代码，编译器在自动并行化方面做得通常比自动向量化还要差；
❏不能找出并行冲突的地方；
❏不能协调资源访问。
Intel的并行工具系列能够发掘出程序简单的并行性并识别读写冲突，另外其具有简单的自动并行化能力（能够自己决定是否使用SSE指令及OpenMP），但是对于优秀的开发人员来说，这远远不够。
由于编译器缺乏相应的功能，软件开发人员不得不自己来做。软件开发人员需要自己发掘应用的并行性，并且处理共享资源的访问冲突。另外由于不同的并行化方法可能利用了硬件/软件不同的特性，因此其性能更难以把握。
目前的调试器对向量化或并行的支持非常差且不可靠，软件开发人员缺乏工具导致生产率上不去，这就导致了雇主不愿使用并行开发。
由于硬件生产商极力地、不负责任地吹嘘向量化或并行编程是如此简单（实际上并行化和并行化代码这种责任也是硬件生产商转嫁给软件开发人员的），使得很多雇主认为只要付给并行软件开发人员和串行软件开发人员一样的工资就够了，而且一般而言并行软件的开发周期比串行软件开发要长得多，这也导致了软件开发人员不愿意使用向量化或并行技术。个人认为市场应当给经验丰富、能力强的并行软件开发人员2倍以上的工资（与同等能力的标量串行软件开发人员比），否则开发优秀的并行软件通常是一句空话。
1.4 并行的替代方法
由于向量化和并行编程的难度和软件开发周期长，很多人不愿意使用它们，但这并不意味着他们不能享有向量多核并行处理器的好处，另外一些方法也能够像并行一样发挥向量多核处理器性能。下面给出了几种简单方法：
❏运行同一程序的多个实例；
❏利用已有的并行库；
❏优化串行程序。
1.运行同一程序的多个实例
如果需要计算同一条件作用在不同的数据集上的效果，或者要计算同一数据集在不同的配置条件下的运行结果。软件开发人员可以在多核处理器上同时为每个数据集运行一次串行程序，这样多个进程可同时占用多个计算核心上的资源。或者为每一种配置条件运行串行程序的一个实例，这样运行每个配置条件的一个实例可占用一个计算核心上的资源，多个不同的实例就可以同时占用多个核心。这些方法并没有减少一次运行的时间（由于资源共享，甚至有可能增加一次运行的时间），但是系统整体的吞吐量会得到提升。
在进行基于深度学习的卷积神经网络实验优化时，经常需要在不同的配置条件下（假设有三个配置，记为A、B、C）学习参数模型，以从多个可选的模型中获得最优的模型。可以分别配置A、B、C运行三个优化实例a、b、c，那么a、b、c可分别在一个核心上运行，这样系统上便有三个核心在运行计算任务，相比只有一个核心在运算，这会提高吞吐量。
如果同时在一个单核机器上运行多个程序，或者在多核处理器上同时运行远超过核心数量的控制流，这可能会既增加单个程序的运行时间，又减少多核处理器整体的吞吐量。
2.利用已有的并行库
目前已经有许多函数库实现了并行，如Intel的MKL、IPP、TBB，以及NVIDIA开发的基于其CUDA计算环境的CUDNN、NPP、CUFFT、CUBLAS等，这些库简化了向量化或并行的设计，使用这些库能够方便地利用多核向量处理器的性能。
NVIDIA的nvblas库使用NVIDIA GPU加速计算密集的blas三级函数。对于原先使用CPU blas三级库函数的应用来说，只需要在编译时链接nvblas库即可利用NVIDIA GPU加速。对于在Linux上运行的调用了blas的应用来说，还可以不用重新编译，只需要在运行程序前使用LD_PRELOAD环境变量让应用使用nvblas中的GPU实现代码即可实现加速。
使用已有的并行库通常比自行编写并行代码要便利，但是要避免由于使用不当，导致性能反而不如标量串行代码的情形。
3.优化串行程序
优化标量串行程序通常应当在向量化或并行之前进行，结果通常会更吸引人。
优化标量串行代码获得的性能提升与向量的长度和核心的数量没有直接的关系，其后还可以利用向量化和并行进一步提升性能。
相比向量化和并行，优化串行代码在操作上通常更容易一些，代码的可扩展性和可维护性通常也更好。
算法的改进获得的性能提升可能是指数级，而向量化或并行带来的性能提升通常和向量长度及核心的数量成正比。
1.5 进程、线程与处理器
现代处理器和进程、线程两个概念紧密关联。进程的概念简化了程序设计、存储器管理等，并且提供了一种大粒度并行的方法。线程存在进程之中，进程中的所有线程共享进程的资源并独享某些资源，因此更易于通信。本节介绍与此相关的进程、线程、超线程和处理器等概念及关系。
在实践中，进程可调度到一台机器中的一个或多个处理器核心上执行，而线程会调度到一个核心上执行，向量化的代码则会映射到一个核心内的向量单元上执行。由于操作系统调度策略的不同，并不能保证进程和线程会一直在相同的核心上执行。
通常基于进程的是像MPI一样的分布式存储器编程模式，基于线程的是像pthread、OpenMP等这样基于共享存储器的编程模式。由于分布式计算的各节点有其独立的存储器，因此基于进程的消息传递通信更适合，而多核等由于共享存储器，所以基于线程的共享存储器更易于通信。
1.进程
当程序在系统上运行时，操作系统会提供一种假象，就好像系统中只有这个程序在运行，只有该程序在使用核心、DRAM和设备。如果真的只有这个程序一直在使用核心的话，在单核心的系统上，用户就必须得等待当前正在执行的程序运行完才能输入下一条指令。现代操作系统并非这样，这是通过进程的概念实现的。
进程是对操作系统正在运行的程序的一种抽象。多个进程可以并发运行在一个核心上，通过时间片轮转，就好像进程一直在使用核心。系统内的多个进程通过时间片轮转并发执行，这就要求有一种机制能够在时间片到期时保存正在运行的进程的状态，并运行另一个等待运行的进程。这种保存一个进程的状态切换到另一个进程的过程称为“上下文切换”。
上下文是指保持进程运行所需要的寄存器、缓存和DRAM等资源。在任何一个无限精度的时刻，一个处理器核心最多只能运行一个进程或一个线程，当操作系统需要在某个核心上运行另一个进程时，就会进行上下文切换。
通过上下文切换进程获得了并发的特性，而运行在多个核心上的多个进程又获得了并行的特性，由于进程的上下文切换和通信比较耗时，因此基于进程的并发往往只适合于大粒度的任务并行。
进程和程序有关系也有不同，程序是静态指令的集合，进程是程序正在运行的状态。进程是资源拥有的独立单位，不同的进程拥有不同的虚拟地址空间，不能够直接访问其他进程的上下文资源。
2.线程
进程之中可以有许多线程，这些线程共享进程的上下文，如虚拟地址空间和文件，但是独立执行且可通过存储器进行通信。当进程终止时，进程内的所有线程也会同时终止。另外线程也有其私有逻辑寄存器、栈和指令指针PC。
由于线程共享进程资源，因此线程的建立、销毁比进程的建立、销毁更高效，在多核处理器上逐渐比进程更引人关注。
由于进程的存储器资源是独立的，而线程的存储器资源是共享的，因此通常基于进程的并行编程更简单，但是基于线程的并行在多核处理器上通常更高效。在多机系统中，不同的计算机天然适合多进程。因此在多核处理器上应优先选择线程级并行，而多机系统应选择进程级并行。实际上，许多现代系统及大规模程序充分利用这两种优势：在节点间使用进程级并行，在节点内的多核上使用线程级并行，这称为混合或超级并行。
目前基于GPU的并行编程也使用基于线程的开发环境，这是一种“硬件线程”，其线程的创建、调度和销毁开销接近0。
多线程程序在多核和单核上执行时具有明显的差别。由于在单核上多线程通过分时共享执行，这使得一些长延迟的操作如锁、IO访问不会导致核心空闲。事实上，网络服务器就是通过多线程技术来提升系统的吞吐量的。
3.超线程
Intel的一些高端机器支持称为“超线程”（Hyper-Threading, HT）的技术，超线程通过双倍增加一些资源（PC和寄存器）来减少线程的切换代价，但是只有一份执行单元，因此其峰值计算能力并没有提高。对于那些指令类型丰富且多的应用，超线程能够很好地提升性能。但是超线程不是万能的，在某些应用上性能可能会下降，而在绝大多数应用上提升不会超过20%。
超线程技术将一个物理处理器核模拟成两个逻辑核，可并行执行两个线程，能够在单个时针周期内在两个线程间切换，让单核都能使用线程级并行计算，减少了CPU的闲置时间，提高CPU的运行效率。采用超线程，应用程序可在同一时间里使用芯片的不同功能单元。单线程核心在任一时刻只能够对一条指令进行操作，而超线程技术可以让一个核心同时进行两个线程处理。
Intel表示，超线程技术让（P4）处理器在只增加5%芯片面积的情况下，就可以换来15%至30%的效能提升（实际上，对某些程序或非多线程程序而言，超线程反而会降低性能）。超线程技术需要主板芯片组和操作系统的配合，才能充分发挥效能。
4.阻塞和同步
在并行编程中，进程或线程的阻塞和非阻塞、同步和异步是非常常见的名词。准确地说，这4个名词有非常明显的区别，但是在某些文献中，阻塞与同步、非阻塞与异步的含义是一样的。
具体来说，阻塞是相对于进程或线程本身而言，如果一个操作并不阻碍进程或线程，接着执行代码，称这个操作为“非阻塞”，反之则为“阻塞”。相对非阻塞来说，阻塞更为常见，因为非阻塞要求开发人员手动保证操作的完成，这可能会带来数据一致性问题。
同步或异步则是针对通信的多个进程或线程，如果一个进程或线程与其他进程与线程通信时，不需要其他线程做好准备，称之为“异步”，反之则为“同步”。
阻塞和同步的具体含义可能会依据不同的编程环境、语言等有微小的不同。比如对于某些MPI异步数据传输函数实现来说，数据传输时传输的缓冲区和结果在异步操作返回时是否立即可用。
1.6 并行硬件平台
不同的并行计算平台适合不同的并行编程模式，对于某个具体的并行应用来说，如果选对了并行硬件平台，实现后的性能通常会比较好，编程也会简单。下面列出一些常用的并行硬件平台，并说明其适合的编程方式及特点。
1.机群
通过使用网线依据某种拓扑方式将多台微机互连以获取更大的计算能力，这种系统通常称为机群，而每台微机称为节点。目前几乎所有的超级计算机都是机群系统。
通常机群通过TCP/IP协议通信，使用物理网络互连，为了提高通信效率，一些超级计算机也会使用特有的协议和网络硬件。
目前常用于机群通信的网线主要有万兆以太网和InfiniBand网卡，其中万兆以太网的最高速度为1.25 GB/s，而InfiniBand可达7 GB/s，映射到处理32位浮点数据时的速度，这大约是现在的多核向量处理器速度的千分之一，极易在计算时成为瓶颈。
将多台机器联结在一起的方式称为网络互连，目前流行的互连方式有星形、环形、树形、网格和超立方。由于不同的互连方式可能导致程序运行时信息的路由路径不同，其对数据传输的延迟影响非常大，如网格就适合具有二维局部性的数据传输应用。
由于节点具有独立的处理器和存储器，在机群上编程需要使用显式或隐式的机制指定数据何时需要在不同的节点间传输和接收。在程序运行时，程序需要通过网络互连在各个节点间交换数据，那么数据的传输路径就会影响传输延迟和带宽，因此显式的消息传递编程接口MPI成为这类平台上的标准和首选。
使用MPI在机群系统上编程时，需要提前处理好输入数据和输出数据在节点间的分布，以利用各个节点能提供的带宽。
2.X86多核向量处理器
多核向量处理器指将两个或更多独立单核向量处理器核封装在一个集成电路（IC）芯片中。多核向量处理器既可以执行向量运算，又可以执行线程级并行处理。由于生产商大量生产这种集成多个向量核心的芯片，因此硬件随处可得，近年来越来越受到开发人员的重视。（1）X86多核
相比超线程，多核是真正的线程级并行设备。多核与超线程技术相结合，可能会进一步提高系统的吞吐量。
多核的每个核心里面具有独立的一级缓存，共享的或独立的二级缓存，有些机器还有独立或共享的三级/四级缓存，所有核心共享内存DRAM。通常第一级缓存是多核处理器的一个核心独享的，而最后一级缓存（Last Level Cache, LLC）是多核处理器的所有核心共享的，大多数多核处理器的中间各层也是独享的。如Intel Core i7处理器具有4～8个核，一些版本支持超线程，其中每个核心具有独立的一级数据缓存和指令缓存、统一的二级缓存，并且所有的核心共享统一的三级缓存。
由于共享LLC，因此多线程或多进程程序在多核处理器上运行时，平均每个进程或线程占用的LLC缓存比使用单线程时要小，这使得某些LLC或内存限制的应用的可扩展性看起来没那么好。
由于多核处理器的每个核心都有独立的一级缓存，有时还有独立的二级缓存，使用多线程/多进程程序时可利用这些每个核心独享的缓存，这是超线性加速（指在多核处理器上获得的性能收益超过核数）的原因之一。
图1-1展示了某个AMD多核处理器的缓存组织结构。
硬件生产商还将多个多核芯片封装在一起，称之为多路，多路之间以一种介于共享和独享之间的方式访问内存。由于多路之间缺乏缓存，因此其通信代价通常不比DRAM低。一些多核也将内存控制器封装进多核之中，直接和内存相连，以提供更高的访存带宽。
多路上还有两个和内存访问相关的概念：UMA（均匀内存访问）和NUMA（非均匀内存访问）。UMA是指多个核心访问内存中的任何一个位置的延迟是一样的，NUMA和UMA相对，核心访问离其近（指访问时要经过的中间节点数量少）的内存其延迟要小。如果程序的局部性很好，应当开启硬件的NUMA支持。图1-1 多核结构示意（图片来自Internet）
发挥多核处理器多个核心性能的编程方式通常是使用OpenMP和pthread等线程级并行工具，容易产生的性能问题主要是伪共享和负载均衡。（2）X86向量指令
SSE是X86多核向量处理器支持的向量指令，具有16个长度为128位（16个字节）的向量寄存器，处理器能够同时操作向量寄存器中的16个字节，因此具有更高的带宽和计算性能。AVX将SSE的向量长度延长为256位（32字节），并支持浮点乘加。在不久的将来，Intel会将向量长度增加到512位。由于采用显式的SIMD编程模型，SSE/AVX的使用比较困难，范围比较有限，使用其编程实在是一件痛苦的事情。
MIC是Intel的众核架构，它拥有大约60个X86核，每个核心包括向量单元和标量单元。向量单元包括32个长度为512位（64字节）的向量寄存器，支持16个32位或8个64位数的同时运算。目前MIC的核为按序的，因此其性能优化方法和基于乱序执行的X86处理器核心有很大不同。
为了减小使用SIMD指令的复杂度，Intel寄希望于编译器，实际上Intel的编译器向量化能力非常不错，但是通常手工编写的向量代码性能会更好。在MIC上编程时，软件开发人员的工作由显式使用向量指令转化为改写C代码和增加编译制导语句以让编译器产生更好的向量指令。
要发挥X86向量处理器的向量计算能力，可以使用三种编程方式：
1）使用串行C语言，让编译器产生向量指令，或使用编译制导语句（如OpenMP 4.0）。这种方式最为简单，代码的可移植性通常也最好，但是给予软件开发人员的控制力最差，通常能够发挥的性能也最差。
2）使用Intel规定的内置函数。使用这种方式需要软件开发人员显式地、使用C函数来指定如何向量化操作，使用向量指令来加载数据。使用内置函数时，需要注意哪些内置函数被处理器支持，哪些不被支持（尤其是在开发机和线上机架构不同的情况下）。
3）使用汇编语言。当编译器生成了不够优化或不需要的指令时，就需要使用汇编语言来榨取系统的最后一点性能。使用汇编语言编程相当不便，代码也难以调试，故应当作为不得已的选择。
另外，现代64位CPU还利用SSE指令执行标量浮点运算。
3.GPU+CPU
近年来GPU（Graphics Processing Unit，图形处理器）的晶体管集成度和（向量多核并行）处理能力的发展速度都远远快于CPU（Central Processing Unit，中央处理器），CPU与GPU的融合是芯片技术发展的一种大趋势。Intel和AMD都在其CPU中集成GPU，而NVIDIA和ATI（AMD）则增强其GPU的编程能力，使得GPU越来越易于满足通用计算的需求。
GPGPU是一种利用处理图形任务的GPU来完成原本由CPU处理（与图形处理无关的）的通用计算任务。由于现代GPU强大的并行处理能力和可编程流水线，令其可以处理非图形数据。特别在面对单指令流多数据流（SIMD），且数据处理的运算量远大于数据调度和传输的需要时，GPGPU在性能上大大超越了传统的CPU应用程序。
NVIDIA和AMD持续改进GPU的编程能力，尤其是CUDA和OpenCL推出后，基于CPU+GPU的异构并行计算越来越得到大家的重视。
GPU是为了渲染大量像素而设计的，并不关心某个像素的处理时间，而关注单位时间内能够处理的像素数量，因此带宽比延迟更重要。考虑到渲染的大量像素之间通常并不相关，因此GPU将大量的晶体管用于并行计算，故在同样数目的晶体管上，具有比CPU更高的计算能力。
CPU和GPU的硬件架构设计思路有很多不同，因此其编程方法很不相同，很多使用CUDA的开发人员有机会重新回顾学习汇编语言的痛苦经历。GPU的编程能力还不够强，因此必须要对GPU特点有详细了解，知道哪些能做，哪些不能做，才不会出现在项目开发中发觉有一个功能无法实现或实现后性能很差，从而导致项目中止的情况。
由于GPU将更大比例的晶体管用于计算，相对来说用于缓存的比例就比CPU小，因此通常局部性满足CPU要求而不满足GPU要求的应用不适合GPU。由于GPU通过大量线程的并行来隐藏访存延迟，一些数据局部性非常差的应用反而能够在GPU上获得很好的收益。另外一些计算访存比低的应用在GPU上很难获得非常高的性能收益，但是这并不意味着在GPU实现会比在CPU上实现差。CPU+GPU异构计算需要在GPU和CPU之间传输数据，而这个带宽比内存的访问带宽还要小，因此那种需要在GPU和CPU之间进行大量、频繁数据交互的解决方案可能不适合在GPU上实现。
4.移动设备
目前高端的智能手机、平板使用多个ARM核心和多个GPU核心，运行在移动设备上的应用对计算性能需求越来越大，而由于电池容量和功耗的原因，移动端不可能使用桌面或服务器高性能处理器，因此其对性能优化具有很高需求。
现在移动设备主要使用基于ARM的处理器，目前市场上的高性能ARM处理器主要是32位的A7/A9/A15。ARM A15 MP是一个多核向量处理器，它具有4个核心，每个核心具有64 KB一级缓存，4个核心最大可共享2 MB的二级缓存。ARM支持的向量指令集称为NEON。NEON具有16个长度为128位的向量寄存器（这些寄存器以q开头，也可表示为32个64位寄存器，以d开头），可同时操作向量寄存器的16个字节，因此使用向量指令可获得更高的性能和带宽。
现在移动设备上的GPU主要是高通的Adreno系列和Imagination的PowerVR系列，这两家厂商的大多数移动GPU已支持使用OpenCL进行并行计算，笔者也使用OpenCL在两家的移动GPU上编写过一些并行代码。
1.7 向量化和多核技术不是万能的
在2003年，Intel曾经预测能够在2010年采用10纳米或更小的制作工艺开发出30 GHz的计算机，实现万亿指令级别的性能（即每秒钟处理一万亿条指令）。但是现在Intel和其他的生产商在使用14 nm技术生产主频低于5 GHz的处理器，虽然Intel和AMD的超频技术使得计算机的瞬间主频远远超过5 GHz，但是这不可持续且会降低硬件寿命。
由发热和能量消耗带来的问题，使得硬件生产商采用向量化和多核技术，并且宣称向量化和多核技术延续了摩尔定律。向量化和多核技术部分解决了发热和能耗问题，但是这种解决方案也引来一个棘手的软件问题：如何编程以发挥向量多核处理器的计算能力。
由于应用和硬件中串行运算部分的存在，随着处理器数量的增加和向量宽度的增加，并行程序的效率就会降低一些。对于某个应用，当使用的核心数量达到一定程度时，增加核心反而会减慢应用的速度，硬件上也存在这种问题。可能在制造几百个长向量核心的处理器前，多核向量处理器已经达到了实际限制。
对于软件开发人员来说，一些问题很容易向量化和并行，但是也有一些不行；有些问题适合向量化和并行，但是程序却不容易编写。很难将算法划分为几百、几千个控制流，因为人脑很难维护这些控制流的状态空间。实际上自动向量化和自动并行化是解决这些问题的首选（软件开发人员编写串行代码，编译器或硬件给多个处理器有效地分发指令），但是现在的自动向量化和自动并行化工具仍旧非常弱。
抽象是软件开发中的有效技术。但是，编写并行程序的时候，抽象就不太好用。抽象要求隐藏程序处理的数据对象，而并行必须要处理数据的依赖关系，两者之间存在天然的冲突。
1.8 本章小结
本章是全书所涉及的基础知识的简单介绍，介绍了许多与并行和向量化相关的重要内容，包括但不限于本节内容。
并行和性能优化的两大作用：①发挥硬件的计算性能，提升程序的吞吐量、增加计算规模或减少计算时间；②为了满足某些功能性需求。
为什么需要向量化和并行：①依靠硬件厂商提升性能的“免费”时代已经结束；②自动向量化工具已经可用，但是只能向量化简单代码，并且性能往往并不理想；③应用对性能的需求依旧在提高，软件开发人员没有选择。
并行和代码性能优化面临的现实困难；①没有很好的向量化和并行设计方法学；②向量化和并行化遗留代码并不容易；③向量化或并行代码的可扩展性和可维护性差；④任务、数据划分及并发访问控制难；⑤对开发人员的过高要求。
一些不修改代码也能利用多核处理器的性能的几种替代方法：①同时运行程序的多个实例；②利用已有的并行库；③优化串行代码。
目前主流的向量和多核计算平台：X86 CPU、GPU和ARM。
处理器是程序的运行平台，不同的现代处理器具有许多相同和不同的特性，在编写代码时如果能够很好地利用这些特性，那么就可以很好地发挥硬件的性能，下一章笔者介绍现代处理器具有的一些典型特性。
第2章 现代处理器特性
现代处理器是向量化或并行程序的运行平台，程序的最终性能由运行它的处理器实现，只有了解了目标处理器的特性，才能写出高效的代码。
从系统启动到终止，处理器一条接着一条地执行内存中的指令，就好像是前一条指令执行完之后下一条指令才开始执行。实际上，现代处理器利用了指令级并行技术，同一时刻存在着多条指令同时执行，并且处理器执行指令的顺序无须和汇编代码给出的指令顺序完全一致，编译器和处理器只需要保证最终结果一致，这类处理器称为“乱序执行处理器”。而严格按照顺序一次执行一条指令，只有前一条执行完才开始执行后一条指令的处理器，称为“按序处理器”。目前主流的CPU和GPU，无论是服务器端，还是移动端基本上都已经是乱序执行处理器。
处理器的处理速度远快于内存读写速度，为了减少访问数据时的延迟，现代主流处理器主要采用了两种方式：
❏利用程序的局部性特点，采用了一系列小而快的缓存以保存正在访问和将要被访问的数据，以近似于内存的价格获得近似于缓存的速度；
❏利用并行性，在一个控制流由于高延迟的操作而阻塞时，执行另一个控制流。
简单来说，前一种方法是将经常访问的数据保存在低延迟的缓存中，以减少延迟，主要由目前主流的CPU所采用。而后一种方法则尽量保证运算单元一直在忙碌，以提高硬件的吞吐量，这种方法目前主要由主流的GPU所采用。这两种办法没有天然的壁垒，无论是CPU还是GPU都采用了这两种的方法，区别只是更偏重于使用哪一种。
现代乱序执行多核向量处理器具有许多和代码性能优化相关的特点，本章主要介绍以下部分：
❏指令级并行，主要有流水线、多发射、VLIW、乱序执行、分支预测等技术；
❏矢量化，主要有SIMT和SIMD技术；
❏线程级并行，多核支持的线程级并行是目前处理器性能提升的主要手段；
❏缓存层次结构，包括缓存组织，缓存特点以及NUMA。
上述特点的存在增大了现代处理器的实际处理数据的速度。本章会详细解析这些技术，并分析其如何影响程序的性能。软件开发人员如果了解现代多核向量处理器的这些特性，就能写出性能效率超过一般开发人员的代码。
2.1 指令级并行
表面上看，处理器是一条又一条串行的执行指令，实际上可以同时对多条指令求值，这称为指令级并行。指令级并行要求同时执行的指令之间没有数据或控制依赖。指令级并行相关的技术主要有：指令流水线、乱序执行、多发射、VLIW和分支预测。
通过指令级并行，处理器可以调整程序中指令在该处理器上的执行顺序，能够处理某些在编译阶段无法知道的相关关系（如涉及内存引用时）；在指令集兼容的条件下，能够允许一个流水线机器上编译的指令，在另一个流水线机器上也能有效运行。
指令级并行能够利用处理器上的不同组件同时工作，如果程序具有类型丰富的运算，指令级并行能使处理器性能迅速提高。
2.1.1 指令流水线
处理器有许多不同的功能单元，如果能够利用它们可以同时执行的特点，就可以提高执行速度。现代处理器将指令操作划分为许多不同的阶段，每个阶段由某个单元执行，这样存在多个操作在处理器的多个单元上像多个水流一样向前流动，这称为“流水线执行”，而每个水流就称为一个流水线。流水线（pipeline）是一串操作的集合，其中前一个操作的输出是下一个操作的输入。流水线执行允许在同一时钟周期内重叠执行多个指令。图2-1是一个取指令、指令解码、数据加载、操作和写回的经典5阶段流水线示意图。图2-1 流水线示意图
为了充分利用流水线的好处，一些处理器将一些复杂的指令划分为许多更小的指令以增加流水线的长度。流水线系统中存在许多正在执行且还没有执行完的指令，现代处理器能够允许上百条流水线指令同时执行，而每条指令的延迟可能长达几个甚至几十个时钟，而最终的结果是某些指令的吞吐量达到每时钟周期几个。（如果能够达到每时钟周期超过一条指令的吞吐量，称之为超标量。）通常一条指令的计算和另一条指令的访存同时进行，这样能够更好地利用流水线的好处。
为了更好地利用指令流水线，现代处理器升级通常会增加指令流水线的长度，但是代码中指令级并行是有限的，一旦达到此限制，再增加流水线长度就不会有好处。如ARM A9的指令流水线长度为8，而A15为13。
带有长流水线的处理器想要达到最佳性能，需要程序给出高度可预测的控制流。代码主要在紧凑循环中执行的程序，可以提供恰当的控制流，比如大型矩阵或者在向量中做算术计算的程序。此时在大多数情况下处理器可以正确预测代码循环结束后的分支走向。在这种程序中，流水线可以一直保持在满状态，处理器高速运行。
2.1.2 乱序执行
对于按序处理器来说，一旦一条指令因为需要等待前面指令的结果，那么该指令之后的所有指令都需要等待。为了充分利用指令流水线或多个执行单元的好处，处理器引入了乱序执行的概念，乱序执行是指后一条指令比前一条指令先开始执行，但要求这两条指令没有数据及控制依赖。由于在很多情况下，处理器比较难以判断指令的数据相关性，编译器也引入了类似的功能，主要有指令重排和变量重命名。通常还需要软件开发人员以处理器和编译器友好的方式编写代码，以充分发掘应用具有的并行性，利用处理器的乱序执行功能。
乱序执行需要在执行指令前知道指令之间的依赖关系，如果两条指令之间有依赖，那么这两条指令就不能乱序执行。现代处理器对乱序执行有不同程度的支持，比如大多数的Intel X86桌面处理器和服务器处理器上都具有重排缓冲区（ReOrder Buffer, ROB），并且具有远多于逻辑寄存器数量的物理寄存器以支持寄存器重命名。
乱序执行会重排指令的执行顺序，这要求处理器的发射能力大于其执行能力。如果处理器的发射能力和指令的执行能力一致，那么ROB中就不会有指令等待重新排列执行顺序。由于处理器执行不同指令的速度并不相同，因此其发射能力并不一定比执行最快的指令的吞吐量大，比如主流X86 CPU一个周期能够处理4条整数加法指令，但是其指令发射能力也是一个周期4条。
2.1.3 指令多发射
从乱序执行的角度来说，处理器的发射能力最好要大于指令执行能力。而从处理器具有多个执行单元、每个执行单元能够在一个周期内同时执行多条指令的角度来看，如果指令发射单元每个周期只能发射一条指令，那么必定有些单元空闲。从这个角度来说，只要是具有多个执行单元的处理器，无论是否支持乱序执行，都要求其指令发射能力大于执行能力。
指令发射单元一个周期内会发射多条指令，通常指令发射单元的发射能力会超过单一硬件单元的处理能力，如在NVIDIA Kepler GPU上，SMX一个周期可以发射8条指令，但是SMX本身却最多能消耗6条乘加指令；如在主流的Intel X86 Haswell CPU上，一个周期可发射4条指令，但是只能消耗2条乘加指令。
许多处理器支持一个周期发射2条或多条指令，但是多条指令要满足一条条的条件，比如有些处理器要求没有依赖关系、有些处理器只允许访存指令和计算指令同时发射，而Intel Xeon PHI处理器两个周期可以为一个线程发射两条指令，但是这两条指令要没有背靠背的依赖。
指令多发射增加了硬件的复杂度，提高了处理器的指令级并行能力。
2.1.4 分支预测
当处理器遇上分支指令（判断指令，如if）的时候，有两种选择：
❏直接执行下一条指令，如果分支是循环的判断条件，则这很有可能造成流水线中断；
❏选择某条分支执行，一旦选择错误，处理器就需要丢弃已经执行的结果，且从正确的分支开始执行。
目前几乎所有的处理器都采用了后者，而选择哪个分支的过程称为“分支预测”，很多生产商宣称分支预测正确率达到90%以上（关于这一点，聪明的软件开发人员各有各的观点）。
如果程序中带有许多循环，且循环计数都比较小，或者面向对象的程序中带有许多虚函数的对象（每个对象都可以引用不同的虚函数实现），此时处理器很难或者完全不可能预测某个分支的走向。由于此时程序的控制流不可预测，因此处理器常常猜错。处理器需要频繁等待流水线被清空或等待被新指令填充，这将大幅降低处理器的性能。
关于分支预测，不同的处理器展现出完全不同的态度，比如X86就极力地优化其分支预测器的性能，而ARM和主流的GPU则要保守得多。
为了帮助处理器更好地进行分支预测，软件开发人员需要依据某些原则编写分支代码，可参考本书的第4章。
2.1.5 VLIW
乱序执行和分支预测增加了硬件的复杂性。在并行执行任何操作之前，处理器必须确认这些指令间没有相互依赖。乱序执行处理器增加了硬件资源用于调度指令和决定依赖。
而VLIW（Very Long Instruction Word）通过另外一种方法来实现指令级并行。VLIW的并行指令执行基于编译时已经确定好的调度。由于决定同时执行的工作是由编译器来完成的，处理器不再需要调度硬件。结果VLIW处理器相比其他多数的超标量处理器提供了更加强大的处理能力且更少的硬件复杂性。（硬件的复杂性降低了，但编译器的复杂性提高了。）
VLIW对于一些向量操作非常有效，并且能够组合某些不相关的指令以同时执行，但是VLIW对编译器提出了过高的要求，故实际性能通常并不是很理想。早期的AMD GPU大量使用了VLIW，现在已经全面转向使用SIMT。目前主要是移动端GPU和一些过时的AMD GPU/APU在使用VLIW。
2.2 向量化并行
向量化并行是现代处理器提升性能的重要方法，和多核一样，它通常要求软件开发人员显示编写向量化的代码。大多数编译器提供了内置函数来避免直接使用汇编指令编写向量化代码，如X86的SSE/AVX、ARM的NEON，它们都是SIMD（单指令，多数据）模式。而主流的GPU则采用了SIMT（单指令，多线程）。
向量化主要指一条向量指令操作向量寄存器中的多个元素，这是一种数据并行模式。在本书中，向量化并行是数据并行的一个子集。
2.2.1 SIMD
SIMD是指一条指令作用在多个数据上面，目前Intel X86提供了SSE/AVX指令，向量寄存器长度分别为128位、256位。利用SSE/AVX指令可显著提高处理能力，但是由于SSE/AVX指令缺乏灵活性和性能的可扩展性，开发人员需要比较长的时间才能熟练使用它们，因此目前应用范围有限。
目前在X86上有多种办法可以使用SIMD指令，比如汇编语言、内置函数（Intrinsic）和OpenMP 4.0。从编程难度来看，使用汇编语言最难，使用OpenMP 4.0最容易，但是大多数时候使用内置函数也可接近或者达到手工使用汇编优化的性能。
虽然SSE/AVX指令集是由Intel设计的，但是AMD的处理器也支持它们，因此在处理器都支持AVX指令集的条件下，使用SSE/AXV指令编写的程序在Intel和AMD的X86处理器之间可移植。
使用SIMD指令要求开发人员非常熟悉指令的类型、吞吐量和延迟。因为不同的处理器对SIMD指令的支持程度不同，这不但表现在指令类型很不相同，还表现在同一指令在不同的架构处理器上的延迟和吞吐量可能也不相同，或者某些指令存在某些未公开的性能缺陷。
2.2.2 SIMT
SIMT是NVIDIA GPU和AMD GCN GPU采用的向量化方法，SIMT也是数据并行的一个子集，但是去掉了SIMD的一些限制，具有先天的优势。相比SIMD所具有的限制，SIMT具有的优势主要有以下几个方面。
❏SIMT指定了逻辑向量宽度，而隐藏了物理向量宽度，软件开发人员依据逻辑向量宽度来编写代码，这提高了代码性能的可移植性。比如AMD GCN，其逻辑向量宽度为256字节，而物理向量宽度为64字节，如果AMD为了性能将其物理向量宽度改为128字节（不改变其他条件），那么为AMD GCN架构编写的代码不用修改，在物理向量长度增加后的架构上其性能也会得到相应的提升。而在支持AVX指令集的硬件上运行使用SSE指令集编写的程序却不能得到相应的性能提升。
❏SIMT无须显式地编写向量化代码，其向量化代码逻辑隐藏在了多核代码中。软件开发人员只需要编写一份CUDA或OpenCL代码就可以利用GPU这种多核向量处理器的全部性能，而X86多核向量处理器则需要同时使用向量指令和多线程两种编码方式才能发挥全部性能。虽然Intel也提供了基于其X86多核向量处理器的OpenCL编程环境，但是本质上硬件的向量化方式依旧是SIMD，而且软件开发人员需要自己保存编译器生成的向量指令。
❏OpenCL和CUDA比内置函数（Intrinsic）要简单直接，更易于调试、验证和维护。
由于相比SIMD向量化方式具有以上优点，用于图形处理的GPU才能够在Intel X86处理器的围剿下杀出一条血路，并且其应用场景正在不断扩大。
2.3 线程级并行
线程级并行将处理器内部的并行由指令级和向量级上升到线程级，旨在通过线程级的并行来增加指令吞吐量，提高处理器的资源利用率。线程级并行的思想是：
1）在多核处理器上，使用多个线程使得多个核心同时执行多条流水线；在多核处理器上使用多线程技术，使得多核处理器的多个核心上有多个流水线同时执行，以利用多个核心的计算能力；
2）在单核处理器上，当某一个线程由于等待数据到达而空闲时，可以立刻导入其他的就绪线程来运行。在单核处理器上使用多线程技术，使核心能够始终处于忙碌的状态。
使用线程级并行使得系统的处理能力提高了，吞吐量也相应提升。除了提高处理能力和吞吐量，线程级并行也经常用来提高用户的使用体验，如果使用单线程，那么网络服务器在一段时间内只能满足一个用户的请求，而多线程则可能满足多个用户的请求，虽然这可能增加了单个请求的延迟，但是提高了整体的吞吐量。使用多线程技术，网络服务器能够同时满足多个用户的请求，也不会使得某个用户因等待过长而抱怨。
2.3.1 内核线程和用户线程
运行在用户空间（运行时）的线程称为用户线程，同理运行在内核空间（操作系统）的线程称为内核线程。用户线程由库管理，无须操作系统支持，因此其创建、调度无须干扰操作系统的运行，故消耗少。内核线程的创建、调度和销毁都由操作系统负责，操作系统了解内核线程的运行情况。操作系统不知用户线程的存在，因此无法将其映射到核心上，当一个用户线程由于资源分配而阻塞时，操作系统无法切换。
由于操作系统内核和物理硬件的限制，一个进程支持的线程数量是有限的，在Linux下可以通过sysconf函数查询得到，通常其值不小于64。
很明显的是，用户线程的缺点刚好是内核线程的优点，而内核线程的缺点又正好是用户线程的优点，如果能够合理地将用户线程映射到内核线程上，就有可能综合两者的优点，因此现代库和操作系统将用户线程映射到内核线程。存在4种映射方式：一对多，一对一，多对一，多对多。现在很多多线程库都使用多对多的映射方式，实际在核心上执行的线程数量可能远少于声明或创建的线程数量。
pthread是用户级线程库，但是Linux使用了内核级线程实现（一对一映射方式），因此pthread线程和GCC的OpenMP线程都是内核线程。
2.3.2 多线程编程库
目前硬件和编译器还无法自己产生高效的线程级并行代码（自动并行化），软件开发人员需要自己丰衣足食。由于线程级并行和传统的串行很不一样，因此很多机构和组织想设计一种全新的语言来满足线程级并行的挑战，但是几乎所有的努力都失败了，而还没有失败的那些正在苦苦挣扎。现在，通行的做法是在串行语言的基础上增加多线程库或通过编译制导语句给予编译器额外的并行信息，然后由编译器生成代码以达到并行目的。以下是目前常用的多线程库和编译制导语句标准。
❏pthread, POSIX标准规定了UNIX及Linux实现的线程库接口pthread。pthread目前在所有的Linux下可用，在业界被广泛使用。
❏win32 thread，是Windows系统内置的线程API。由于本书不包含Windows的内容，故也不包含win32 thread。
❏OpenMP，是一个开放的、基于编译制导语句的API，目前在各大操作系统上均可用，由于其与具体系统平台无关，提供了比较好的可移植性，因此应当优先使用。
❏C/C++标准线程，新的C/C++标准都已经引入了线程API，只是在本书编写时，编译器还不支持。
❏OpenCL和CUDA，它们是基于GPU（OpenCL也正用于在FPGA上编程）的并行计算的架构、语言和API，由于在某些问题上能够比CPU更快地解决问题，目前正在被广泛使用，使用范围正在逐渐扩大。
❏OpenACC是一个基于加速器的编译制导标准，通常用于GPU、FPGA等的并行编程，目前提供编译器的主要厂商有Cray和PGI。
2.3.3 多核上多线程并行要注意的问题
多核处理器上的所有核心共享内存，可以有各自的一、二级缓存和寄存器。由于资源共享，在多核处理器上使用线程级并行需要注意的问题有以下几个。
❏线程过多：如果系统上的线程数量远远超过核心的数量，那么就会导致频繁的上下文切换，进而降低性能，如缓存污染。通常支持超线程的多核处理器能够使用的线程数最多是物理核心数的2倍（即逻辑核心数），再增加就有可能降低程序的性能。
❏数据竞争：当多个线程读写同一共享数据时，便会产生竞争，需要同步，比如两个线程对同一个共享数据执行操作时，就需要同步以保证结果是一致的。一方面，同步通常会导致线程之间相互等待，潜在地降低了性能；另一方面，如果不使用同步程序可能无法并行，这可能提升程序的并行性。
❏死锁：线程发生死锁时，处理器都在操作（一直在询问需要的资源是否可用），但是线程都在相互等待其他线程释放资源，谁也无法前进一步，处于一种“僵死”的状态。
❏饿死：当一个或多个线程永远没有机会调度到处理器上执行，而陷入永远的等待的状态。
❏伪共享：当多个线程读写的数据映射到同一条缓存线上时，如果一个线程更改了数据，那么其他线程对该数据的缓存就要被失效，如果线程频繁地更改数据，硬件就需要不停地更新缓存线，这使性能从独享缓存的水平降低到共享缓存或内存的水平。
2.3.4 多线程程序在多核和单核上运行的不同
多线程程序在单核和多核上运行具有不同的特点。
❏锁：在单核上，多个线程执行锁或者临界区时，实际上只有一个线程在执行临界区代码，而核心也只支持一个线程执行，因此不存在冲突。如果某个线程持有锁，那么只是其他线程不会被调度到CPU上执行，影响的只是持有和释放锁的时间，处理器时刻在运行着。但是在多核上运行时，锁或临界区会导致其余处理器空闲而只允许一个处理器执行持有锁的那个线程，这是一个串行的过程，会影响性能。
❏负载均衡：在单核上不用考虑负载均衡，因为各个线程轮流执行，当一个线程执行完时，便会执行另一个线程，不存在线程等待问题。即使各个线程的任务非常不平衡，也不会影响总执行时间。而在多核上执行时，此时最终时间由运行时间最长的线程决定。
❏任务调度：单核上，任务调度完全是操作系统的工作，无须软件开发人员干预，通常有时间片轮转、优先级算法等。而在多核上运行时，软件开发人员要合理地在核心间分配任务，以尽量同时结束计算（此时任务调度的工作已经从操作系统转移到了软件开发人员）。
❏程序终止：在多线程环境中，何时终止程序就变得复杂，因为程序终止时需要确定各个线程都已经计算完成。幸运的是，多线程库通常都提供了对应的函数。在多机编程上，这个问题可能会变得非常复杂。
2.4 缓存
现代X86 Haswell处理器的吞吐量是一个时钟周期内4次整形加法、2次单精度浮点乘加。从延迟上看，做一次乘法也只要3个周期，一次除法也就十几个周期。而一次内存访问却需要200周期以上，并且随着技术的发展，内存容量变得越来越大，带宽也在增加（但是增加的幅度比处理器的吞吐量要小），但延迟并没有减少而是越来越大。处理器吞吐量与内存吞吐量和延迟的差异越来越大，这称为内存墙。现代处理器通过几种方式来减小这种差距实际产生的影响：
❏每次内存访问、读取周围的多个数据，因为这些数据随后极有可能会被用到；
❏采用容量小但更快的存储器（称为缓存）缓存内存访问，如果访问的数据在缓存中，那么就无须去访问内存；
❏支持向量访问和同时处理多个访问请求，通过大量并行访问来掩盖延迟。
程序在一段时间内访问的数据通常具有局部性，比如对一维数组来说，访问了地址x上的元素，那么以后访问地址x+1、x+2上元素的可能性就比较高；现在访问的数据，在不久之后再次被访问的可能性也比较高。局部性分为“时间局部性”和“空间局部性”，时间局部性是指当前被访问的数据随后有可能访问到；空间局部性是指当前访问地址附近的地址可能随后被访问。现代处理器通过在内存和核心之间增加缓存以利用局部性增强程序性能，这样可以用远低于缓存的价格换取接近缓存的速度。
现代处理器缓存的带宽很高，比如Intel Haswell一级缓存的带宽为每时钟周期每核心64字节，要发挥其峰值必须要使用向量指令。而内存的延迟很高，要隐藏内存的高延迟，则需要发起多个访问请求以让流水线始终在满负荷运行。
软件开发人员应当意识到：对于性能限制在内存/缓存上的程序来说，缓存能够显著增加程序的实际性能，因此要编写缓存友好的代码，同时在多核的条件下要注意避免伪共享问题导致的性能损失。
2.4.1 缓存层次结构
为了更好地利用程序访问内存/缓存的局部性，现代处理器采用了多层次的、容量不同和性能不同的缓存，其中上一级缓存容量比下一级缓存小，但是延迟更小、带宽更大。比如Intel Haswell CPU一级缓存大小为32KB，延迟为3个周期，读吞吐量为每周期64字节；其二级缓存大小为256KB，延迟为11个周期，读吞吐量为每周期64字节。
现代处理器至少具有二级缓存，某些高端的多核处理器还具有三级缓存。通常都采用上一级缓存缓存下一级缓存的访问的方式。如寄存器缓存一级缓存访问，一级缓存缓存二级缓存访问，二级缓存缓存三级缓存访问，三级缓存缓存内存访问。当然一些处理器有微小的不同，比如AMD A10 APU中CPU的一级缓存就不缓存来自寄存器的写操作。
不同的缓存层次组织成一个类似于金字塔的结构，上一级缓存容量小、速度快，下一级缓存容量大、速度慢，上一级缓存下一级。如图2-2所示，寄存器缓存level 1缓存，level 1缓存level 2，而level 2缓存RAM, RAM缓存硬盘、网络等，而硬盘缓存远程请求等等。图2-2 缓存金字塔
由于这种金字塔的保存方式，某些数据可能同时被缓存在某个核心的多个缓存层次上（也有可能只缓存在某个层次上），如同时被L1和L2缓存。在多核处理器上，某个数据还可能同时被多个核心上的缓存所缓存。
一次内存访问，如果访问的数据在缓存中，则称为缓存命中，如果不在，则称为缓存不命中，为了衡量缓存命中的概率，提出了缓存命中率的概念，其指程序执行过程中缓存命中的次数占总访存次数的百分比。通常程序的缓存优化过程就是提高缓存命中率的过程。
2.4.2 缓存一致性
由于处理器具有多级缓存，那么如何保证缓存中的数据和内存中的数据是一致的，这由处理器的缓存一致性协议来保证。
对于单核处理器来说，其缓存一致性协议要保证，某个地址上读得到的数据一定是最近（一般指处理器视角）写进去的。比如，某条指令更改了地址0x0100上的内容，那么核心对0x0100的缓存需要失效。
多核处理器上还存在一个和单核处理器不同的缓存一致性问题，即多个核心缓存了同一个内存地址的数据，那么一个核心更改了某个地址的数据，其他的核心就需要对该地址数据的缓存失效。一些简单的多核处理器缓存一致性协议使得缓存一致性的代价和处理器的数目成正比，如Intel Xeon PHI。
为了正确性，一旦一个核心更新了内存中的内容，硬件就必须要保证其他的核心能够读到更新后的数据。目前大多数硬件采用的策略或协议是MESI或基于MESI的变种：
❏M代表更改（modified），表示缓存中的数据已经更改，在未来的某个时刻将会写入内存；
❏E代表排除（exclusive），表示缓存的数据只被当前的核心所缓存；
❏S代表共享（shared），表示缓存的数据还被其他核心缓存；
❏I代表无效（invalid），表示缓存中的数据已经失效，即其他核心更改了数据。
一旦某个核心更新了内存中的数据，那么硬件便会使其他核心对该数据的缓存失效。实际上更新的缓存数据何时被写回内存，各个处理器的策略也不相同。
多核系统的存储器具有缓存一致性并不代表多个控制流同时读写一个变量不会产生问题，主要是因为：①现在的编译器和编程语言几乎都采用弱一致性协议；②多个控制流执行的先后顺序通常没有办法控制；③缓存一致性并不保证顺序一致性。
对于开发人员来说，缓存一致性是透明的，就如同缓存一样，因此无须过多关注。
缓存失效是一个长延迟的操作，不能完全流水线化，故很多处理器都提供了失效队列来保存缓存失效操作。伪共享本质上也是一种缓存一致性问题。
2.4.3 缓冲不命中
如果处理器无法在某级缓存中得到需要的数据，那么就会向下一级缓存请求数据，这称为缓存不命中。不命中意味着从上一级缓存的性能下降到下一级缓存的性能，因此知道什么情况下会导致缓存不命中就非常重要。通常缓存不命中有以下几种情况。
❏冷不命中，所谓“冷不命中”是指程序开始执行时，由于缓存里根本没有数据，因此无论请求任何数据，都会不命中。通常程序无须特别关注这种情况，但是在测试缓存性能、大小或结构时，要注意这点。
❏满不命中，满不命中是指如果缓存已经完全被占用，那么请求的数据如果不在缓存中，就需要将其中的某个已缓存的数据x覆盖为新请求的数据。如果随后又要请求x，那么x不命中，这称为“满不命中”。如果数据存在局部性，但是访问的数据的大小超过了缓存大小就会存在满不命中的情况。
❏冲突不命中，新读取的数据将会被放入缓存中的某个地址a,a并不是任意的，而是由某些算法决定（由于内存比缓存大得多，因此多个内存地址会被映射到同一个缓存地址）。如果a中原始数据在随后被访问，那么也不会命中，这称为“冲突不命中”。冲突不命中和缓存的组织有关，比如缓存线长度，每组里面有多少缓存线。
实际上，如果只是为了正确性，软件开发人员并不需要关注这几种不命中的情况是否发生。然而为了提高性能，软件开发人员就必须知道硬件缓存不命中的机制和原因。
2.4.4 写缓存
当程序将数据从寄存器写入内存时，这涉及一个是直接写入内存，还是写入到下一层缓存中的选择问题，依据写是否命中来说，各有两种基本策略。
如果要写的数据已经存在缓存中，即写命中时，有如下两种策略。
❏写回（write back），指仅当一个缓存线需要被替换回内存时（缓存已满，或者多线程时，其他线程需要访问这个数据），才将其内容写入内存或下一级缓存。如果缓存命中，则总是不用更新内存。为了减少耗时的内存写操作，缓存线通常还设有一个脏位（dirty bit），用以标识该缓存线在被载入之后是否发生过更新。如果一个缓存线在被置换回内存之前从未被写入过，就不用写回内存。
❏写直达（write through），指每当缓存接收到写数据指令，都直接将数据写回到内存或下一级缓存。如果此数据也在缓存中，则必须同时更新缓存。
无论是写回还是写直达，如果更新的地址被其他核心缓存，那么其他核心对此地址的缓存必须失效。写回的优点是节省了大量的写操作。因为，对一个缓存线内多个不同地址的更新只需一次写操作即可完成，这节省了内存带宽和功耗。写直达比写回更易于实现，并且能更简单地维护数据一致性。
无论是写回还是写直达都需要多个周期，不能完全流水线化，因此现代处理器核心上通常都有一个缓冲区用于临时保存等待写回内存的数据，这称为写缓冲。只要写缓冲中的数据不在随后被访问或更新，那么写操作就可以完全流水线化。但是某些写后读或写后写会导致串行化问题（读时必须等待前面的写操作完成），如代码清单2-1的前缀和代码：代码清单2-1 需要检查写缓冲的前缀和代码
由于下一次循环需要使用前一次循环写入的数据，因此硬件必须检查写缓冲中的操作是否完成，这导致延迟增加，不能完全流水线化，聪明一些的编译器会将其改写为代码清单2-2的代码：代码清单2-2 不需要检查写缓冲的前缀和代码
如果需要被写的数据不在缓存中，即写不命中的话，那么现代处理器会执行两种处理方法中的一种：
❏写分配（write allocate）。写分配是指，如果要写的数据没有被缓存，那么就在缓存中分配一条缓存线，这类似于大多数处理器对读的处理。如果被写入的数据的局部性很好（在随后会被读），那么写分配就很适合。
❏写不分配（write no-allocate）。写不分配是指，如果要写的数据没有缓存，那么数据就直接写入内存，而不占用缓存线，这有点类似于越过缓存。如果被写入的数据的局部性很差（在随后不会被再次使用），那么写不分配就很适合。
2.4.5 越过缓存
对于某些应用来说，其代码只具有空间局部性而没有时间局部性，即某个数据只被访问一次，其后其相邻的数据会被访问，但是其本身不会被再次访问。如果在访问这类数据的时候，能够做到既不占用缓存，又能够利用到其空间局部性，那么就能够将缓存留给更需要缓存的数据访问。实际上只需要硬件为读写分配几条长度和缓存线长度相同的缓冲区即可。某些现代X86处理器使用流加载或流存储的概念，如SSE/AVX中的__mm_stream_load、__mm256_stream_load和__mm_stream_store、__mm256_stream_store。
通常使用流加载和流存储指令要求数据访问的步长为1，如下面的代码所示：
由于现代X86处理器为编程的常见情况做了许多优化，流加载和流存储并不总是能够提升性能。
2.4.6 硬件预取
为了利用空间局部性，同时也为了掩盖传输延迟，可以投机性地在数据被用到之前就将其取入缓存。这一技术称为预取（Prefetch）。本质上讲，处理器每次加载一条缓存线即是一种预取，即预取了这条缓存线上的其他数据。
预取可以通过硬件或软件控制。典型的硬件指令预取会在缓存因失效而从内存载入一个缓存线的同时，请求紧随其后的另一个缓存线。某些Intel的处理器需要通过启用BIOS的选项来启用硬件预取，因为如果程序的局部性不好，则硬件预取反而会降低性能。
如果程序访问数据能够很好地满足局部性要求，硬件和软件预取几乎总能提高性能，但是如果程序的局部性很差，则预取反而会降低性能。预取降低性能的原因主要有以下几个：
❏如果预取的数据在随后没有被访问，那么预取的数据就不会被使用（完全浪费掉了），还不如不预取；
❏如果预取过早的话，可能会出现冲突不命中（预取的数据有可能会被替换出缓存）；
❏有可能导致满不命中，如果缓存已满，那么预取的数据需要换出缓存中数据，如果被换出缓存的数据在随后被访问，那么就增加了缓存访问次数。
X86和ARM处理器支持软件预取技术，如SSE和NEON中的prefetch指令。
2.4.7 缓存结构
缓存以缓存线为基本单位读写，每条缓存线可保存L（现代机器上L一般为64）个字节。数据在缓存间上下移动时以缓存线为单位，即不可能出现只加载半条缓存线的情况。对于软件开发人员来说，缓存的总量和缓存线的大小相当重要，另外缓存的层次结构、缓存映射策略也需要了解。
目前内存的容量越来越大，根据机械定律，内存容量越大则其访问延迟就越长，为了弥补访问时间的损失，缓存会越来越大且层次会越来越多。目前大多数机器具有三级缓存，不久的将来，四级缓存也会出现。
1.缓存线
缓存线是缓存中数据交互的最小单位，即读写数据时，每次会读写一个或多个缓存线，不会存在读取半个缓存线（不包括寄存器从一级缓存中读）的情况。
通常缓存线的长度是2的幂，主流的CPU上缓存线长度为64B；主流的GPU上，缓存线长度为128B。缓存线会映射到连续的地址，通常读取数据时，如果能够对齐到缓存线长度，可以有效减少访存的次数。
在缓存总量一定的条件下，增加缓存线长度会增加访问延迟，但是有可能减少访存次数以提高带宽。
2.缓存组
为了减少读取多个映射到同一个缓存的内存地址时造成的存储器访问“抖动”的影响（即冲突不命中），通常将多个缓存线组成一组，每个对齐到缓存线的内存地址可映射到一组中的某一条缓存线。在读取时，具体读入到组中的哪一条缓存线则由其替换策略决定，常见的替换策略是最近最少使用、随机策略等。通常组的大小为8或16条缓存线。
在缓存容量固定且缓存线大小固定的前提下，如果增加缓存组内缓存线的数量，那么缓存组的数量就会减少。缓存组数量越少，出现满不命中的可能性就越大。
2.4.8 映射策略
当缓存被数据占满时，哪些缓存的内容要被替换、从下一级缓存取出的数据要放到上一级缓存的什么地方等，这些行为都和映射策略相关。
常见的缓存映射策略是：直接相联、组相联和全相联。
组相联是指缓存组中的缓存线数量大于1，即一个内存地址可映射到缓存组中的多条缓存线。而直接相联是指每个缓存组中只存在一条缓存线；而全相联是指所有的缓存线都属于同一个组；直接相联和全相联都可视为组相联的特殊情况。
以Intel X86 CPU的一级数据缓存为例，通常其大小为32KB，缓存线长度为64B，每个缓存组中有8条缓存线，故共有64组，这样地址相差64×64=4KB的数据就会映射到同一组中，如果该组中的所有缓存线都已经被使用，那么就需要将某条缓存线的数据空出来（即冲突不命中）。
2.5 虚拟存储器和TLB
虚拟存储器是对内存和IO设备（包括硬盘）的抽象，通过将内存中的数据切换到硬盘，它使得进程好像拥有了比整个内存容量大得多的内存空间。虚拟存储器的设计同时简化了操作系统和编译器设计，比如可以假设进程的可执行代码的起始地址都是0x00400000，而具体的物理地址是多少则由映射机制解决，那么操作系统只需要从地址0x00400000处加载程序代码，而不必关心代码保存在哪个位置。通过虚拟存储器这种抽象，Windows和Linux都将存储器抽象为按字节寻址的线性存储器，这称为平面存储器模型。在虚拟存储器抽象下，软件开发人员无须了解存储器组织细节就可以编写高性能程序。
虚拟存储器使用虚拟地址寻址，而物理存储器使用物理地址寻址，因此硬件执行访存操作时需要将虚拟地址翻译成物理地址，操作系统和存储器管理单元（Memory Management Unit, MMU）硬件配合来完成这一工作。由于从虚拟地址到物理地址的转换非常耗时，处理器和操作系统主要使用了两个优化来减少转换次数。
❏分页机制，虚拟存储器和物理存储器被划分为大小相等的页，虚拟存储器和物理存储器之间的每次交换都以页为单位，通常页大小为4KB、64KB或4MB（Linux下页的默认大小即为4KB），这远大于缓存线的大小，处理器通过每次载入一页的方式（相当于一次转换可完成一页而不是一个数据）减少载入单位数据时从虚拟地址到物理地址转换的消耗。
❏TLB,TLB用于缓存已经翻译的虚拟地址，通过利用访问页的局部性来减少翻译次数。由于虚拟地址和物理地址之间的转换非常耗时且TLB不命中的代价很大，因此TLB的映射策略通常设计为全相联。实际上，在一些硬件上，缓存层次中也使用多层TLB来减少地址翻译代价。一些需要对多维数据进行访问的程序在大数据量的情况下，通常存在TLB不命中的情况。
解决程序TLB不命中而导致的性能问题的方法主要有如下几个：
❏增大页的大小。比如以前使用了4KB大小的页，现在改成使用64KB、甚至2MB大小的页；
❏对于重复多次使用且局部性很好的多维数据，临时分配数据空间来保存数据的一部分，然后重复使用该临时数据空间，此时TLB只需要保存这一部分临时数据空间的地址即可；
❏对数据进行分块优化。如果数据被多次使用，只是由于其大小超过TLB能够缓存的范围，即满不命中。此时可将数据分块，操作完一块后接着操作另一块。
对代码优化人员来说，无须了解虚拟存储器和TLB的实现细节，只需要依据其抽象就可以编写高性能的代码。
2.6 NUMA技术
随着多路系统中多核处理器数目的增多，内存带宽和多路系统计算能力之间的差距越来越大。为了提高多路系统中多核处理器之间通信的带宽，NUMA应运而生。
对Intel的处理器来说，多路处理器之间通过QPI总线通信；而AMD的处理器则通过HT总线通信。QPI和HT的带宽比内存带宽小，而延迟则大于访问内存的延迟，这是NUMA存在的根本原因。
对NUMA架构上的每个处理器来说，访问各个存储器的速度是不一样的。访问“靠近”处理器自身的存储器速度要比访问“远”的存储器快，如图2-3所示。图2-3 处理器和存储器连接
要利用NUMA的优点，控制流分配存储器时要保证分配的存储器离自身所在的处理器比较“近”，这需要保证两点：
❏控制流分配存储器时分配在离自己近的物理内存上，这可以通过在线程内使用malloc分配办到，如代码清单2-3的OpenMP代码所示。但是如果控制流在运行时迁移到另一个物理核心上，这点就可能失效。这引出了下一点：代码清单2-3 分配
❏控制流不能在核心间迁移。为了使得处理器核心能够公平地得到任务，操作系统会在核心间迁移控制流，一旦出现线程迁移到其他处理器上的情况，那么此线程访问存储器就可以不满足NUMA要求。可以通过线程亲和性保证线程不会在核心间迁移，如gcc环境变量GOMP_CPU_AFFINITY。GOMP_CPU_AFFINITY使用（s-e：span）格式表示如何将线程固定在CPU上，其中s表示起始线程固定到的CPU编号，e表示最后一个CPU编号，span表示相邻线程间隔的CPU编号距离，需要提示的是：CPU从0开始编号。如GOMP_CPU_AFFINITY=“0-3 4-10：2”表示：线程0固定到0号CPU、线程1固定到1号CPU、线程2固定到2号CPU、线程3固定到3号CPU、线程4固定到4号CPU、线程5固定到6号CPU、线程6固定到8号CPU、线程7固定到10号CPU。
异构并行计算引入了GPU和FPGA等加速器，这些加速器目前通过PCI-E连接到IOHub, IOHub再连接到CPU。如果主板支持多个socket，那么GPU和GPU之间，GPU和CPU之间也存在NUMA。
Linux系统提供了numactl工具来设置NUMA特性，而pthread和OpenMP实现提供了设定线程亲和性的函数。代码清单2-4就使用pthread将线程t1固定到处理器0上。代码清单2-4 numactl使用示例
cpu_set_t是一个掩码向量（目前长度为1024位），每一位对应着一个CPU核心，__CPU_ZERO宏将掩码向量cpu_info全部清零，__CPU_SET宏将掩码向量的某一位设置为1，如代码清单2-4就将掩码向量cpu_info中第一位设置为1，而函数pthread_setaffinity_np则将线程固定到掩码指定编号的CPU上，如代码清单2-4就将线程t1固定到CPU 0上。
2.7 本章小结
本章主要介绍了现代处理器的主要特性，包括但不限于如下内容：
现代处理器使用的指令级并行技术有：指令流水线、乱序执行、指令多发射、分支预测和VLIW。
现代处理器主要使用两种向量化并行技术：SIMD和SIMT，其中CPU主要使用SIMD，而GPU主要使用SIMT。
本章还介绍了线程级并行的基础知识：用户线程和内核线程、常见的多线程编程库等。
关于现代处理器的存储器系统，本章介绍了：缓存层次结构、缓存一致性、缓存不命中的分类、缓存结构及缓存的映射策略，另外还介绍虚拟存储器和TLB及NUMA技术。
现代处理器特性是代码优化和并行的基础之一，而另外一个基础是如何衡量算法和程序的性能，只有知道如何衡量算法和程序的性能才能评价算法和程序的优劣。下章笔者将会介绍目前常见的衡量算法和程序性能的一些标准和概念。
第3章 算法性能和程序性能的度量与分析
通过分析算法或程序的性能，能够说明优化是否产生效果。最重要的是分析程序的性能，告诉代码优化人员程序发掘了计算机的多少计算能力，即程序还有多少潜在的优化空间。算法的性能分析能够指导算法设计，而算法或程序性能的度量是分析的基础。目前常用的表达算法性能的量有时间复杂度和空间复杂度，而表达程序性能的量有：时间、FLOPS、CPE、IPC等。
由于时间复杂度和空间复杂度无法准确衡量算法实现的复杂度，因此本章提出了实现复杂度的概念。时间复杂度和空间复杂度关注抽象算法的性能，而实现复杂度更关注于如何估计算法的具体实现性能。即使是同一个算法，不同的开发人员、基于不同的平台实现，其最终的性能通常也差别巨大，相比时间复杂度，实现复杂度提供了一种更好的比较算法实现后优劣的途径。
本章首先介绍算法的性能度量标准，通过算法度量标准可以大致分出算法的优劣；其次介绍如何表达一个程序在某个平台上运行时的性能；再次介绍对程序的一部分代码向量化或并行化对整个程序而言的性能收益；最后介绍一些常见的程序性能分析工具。笔者希望通过这种方式让读者了解：如何衡量算法和程序的性能，如何通过工具获得程序的性能，为性能优化打好基础。
3.1 算法分析的性能度量标准
对于代码性能优化和并行化来说，如何衡量算法的性能非常重要。如果能够在编写代码前就依据某些标准选择最优算法，那么就会节约大量算法选择时间。
通常使用时间复杂度来度量算法运行的性能，使用空间复杂度来度量算法要使用的存储器空间大小。时间复杂度和空间复杂度用得如此广泛，几乎每一本关于算法的教科书都会使用一定的篇幅来介绍它们，故本章只予以简单介绍。
对于代码性能优化来说，时间复杂度和空间复杂度存在很多缺陷。为了更好地指导代码性能优化和并行化，本章提出了实现复杂度的概念，并将其进一步细分为计算复杂度、访存复杂度和指令复杂度。由于初次提出实现复杂度的概念，故在一些细节上可能存在不足，还请读者原谅。
3.1.1 时间复杂度与空间复杂度
时间复杂度和空间复杂度是常见的衡量算法性能的度量标准。由于大学教科书中花大量的篇幅介绍，故本节只简单介绍其作用。
1.时间复杂度
通常使用时间复杂度来衡量算法需要的大致计算时间尺度，比如算法需要操作n个数据，每个数据大约要运算2n次，则时间复杂度为O（n2）。
以下列伪代码所示的矩阵向量乘法为例：
其中外层循环执行次数为nRows，内层循环执行次数为nCols，循环内计算次数为4，外加对累加器temp赋值为零和更新结果product的两次计算，故其总的计算量为nRows×（4×nCols+2），假设矩阵为方阵，即nRows==nCols=n，则总的计算量为4×n2+2×n，时间复杂度忽略低阶和常数的影响，故上述算法的时间复杂度为O（n2）。
从上面计算矩阵向量乘法的时间复杂度的过程我们可以得知，时间复杂度有以下几个方面需要特别注意：
1）只关注计算对性能的影响，而不关注访存；
2）只关注最高阶计算量对性能的影响，而忽略低阶计算量对算法性能的影响；
3）只关注运算量的阶，而忽略阶的比例常数对算法性能的影响；
4）不关注不同的计算对性能的影响。
再比如如下的矩阵加法算法代码，nRows==nCols=n，其计算量为5n2，和矩阵向量乘的例子相比，它们的时间复杂度均为O（n2），即时间复杂度分析的结果是一样的，而在性能分析实践中，这两者的性能必然存在比较大的差距。
虽然本节后面会解释两者性能差别的原因，但是感兴趣的读者可以先自行分析一下。
时间复杂度是一个很好的大致评价算法优劣的标准，但不是一个很好的性能优化度量标准，主要原因如下。
❏时间复杂度只考虑计算对性能的影响，而不考虑数据读写对性能的影响。从冯氏架构来看，数据读写为计算提供运算所需的输入/输出，不考虑数据读写明显忽略了影响性能的一个重要方面；从计算机架构的进展来说，目前数据读写越来越成为多核向量处理器性能的瓶颈（内存墙）。这意味着大部分时间花费在访问存储器上面的算法都不适合使用时间复杂度来估计性能，比如上面提到的矩阵加法。
❏不同的算法具有不同的限制因素。有些算法的大部分性能限制在读取网络数据上，有些算法限制在TLB上，对于这些算法来说，只有时间复杂度是不够的。一个典型的极端例子就是：从来没有优秀的开发人员使用时间复杂度来衡量网络服务器或数据库服务器的性能。
❏不考虑处理器执行不同指令的速度差异。处理器生产商需要考虑处理器将来要运行哪些软件，这些软件的主要运算是什么，如何能够在不大量增加晶体管的情况下提升这些软件的性能，故并不是对所有指令一视同仁。通常生产商将更多的晶体管用于更常见指令，以提高这些指令的性能，这导致同一处理器上不同指令的性能并不相同。比如Intel Haswell处理器一个周期可执行4次整数加法，而对于浮点加法一个周期只能执行1次。
❏忽略常数和低阶运算对性能的影响。由于时间复杂度忽略常数和低阶运算对性能的影响，因此常常出现一些时间复杂度为O（n）的算法，在某些问题规模上，性能比时间复杂度为O（n2）的算法要差的情况。比如计算复杂度为O（n log n）快速排序算法在实践中通常比时间复杂度为O（n）的基数排序要快。
❏不能很好地度量并行算法。并行算法需要的数据/任务划分、通信等都超出了时间复杂度的范围。一旦并行算法的这些特性成为了影响性能的重要因素，时间复杂度分析通常会得出与实际不符的结论。
在大的尺度上，用时间复杂度分析抽象算法的性能非常有用，但是某些具体算法的实现则需要特别留意是否有上面列出的情况。
2.空间复杂度
空间复杂度用来表示算法运行需要的存储器空间，比如某算法需要使用一个长度为n的空间作为输入，使用另一个长度为n的空间作为输出，则空间复杂度为O（n）。
和时间复杂度类似，空间复杂度也忽略低阶和常数的影响。如上一小节的矩阵向量乘法算法，输入矩阵占用空间大小为n2，输入向量和输出向量大小俱为n，其使用的空间大小为n2+2×n，其空间复杂度为O（n2）。而上一小节所示的矩阵加法算法，输入矩阵和输出矩阵大小俱为n2，其使用的空间大小为3×n2，其空间复杂度为O（n2）。两个算法的空间复杂度俱为O（n2），但是很明显它们运行时需要占用的空间大小并不相同。
空间复杂度能够衡量程序运行时需要的大致数据量，因此与性能优化没有过多联系。表面上看空间复杂度与程序的性能关系很大，如果算法设计不好，运行时需要消耗大量内存，这样就会影响整个系统的性能。持有这种观点的人简单地把程序在真实系统上运行时需要的空间大小等价于算法分析时的空间复杂度。另外决定现实系统运行速度的是算法在现实系统上运行时的瓶颈，这并不由算法本身独立决定。
空间复杂度也忽略常数的影响，且无法衡量程序运行时要访问多少次存储器，更没有考虑缓存层次结构的影响。
空间复杂度的定义侧重于表示算法要使用的存储器空间，其相对意义大于绝对意义，即使其相对意义也并不非常实用。我们无法估计一个空间复杂度为O（n）的算法其在某个平台上实现时需要的内存空间大小，也无法说空间复杂度为O（n）的算法在某个平台上实现时需要的具体空间就一定比空间复杂度为O（n2）的算法小。
3.1.2 实现复杂度
无论时间复杂度还是空间复杂度，都是理论上或“纸面上”的东西。在某个特定的处理器上，程序的实际性能基本上由运行时的计算、访存和指令决定，因此本文提出了计算复杂度、访存复杂度和指令复杂度的概念。为了便于区分时间复杂度和空间复杂度，本文将计算复杂度、访存复杂度和指令复杂度统称为实现复杂度。
相比时间复杂度和空间复杂度，实现复杂度更贴近硬件，对程序性能的度量通常也更为准确。将实现复杂度作为优化代码性能的标准是一个更好、更实际的选择。
对于具体的代码而言，依据在某种处理器上运行的性能瓶颈不同而采用实现复杂度的不同方面来度量。对于一个计算限制的算法，应当使用计算复杂度和指令复杂度；而对于一个存储器限制的算法，应当使用访存复杂度来分析。
1.计算复杂度
计算复杂度可用来衡量每一个控制流的计算数量，不但计算加载存储指令，还需要考虑指令的吞吐量或延迟，通过加权平均来表示计算性能。由于各种现代向量多核处理器具有不同的特点，比如X86 CPU是为延迟优化的，在考虑计算复杂度时权重应该以延迟为准；而GPU是为吞吐量优化的，考虑计算复杂度时权重应当以吞吐量倒数为准。但这并不绝对，一些优化良好的X86 CPU代码有很好的指令级并行能力，也应当从吞吐量倒数考虑。
以输入两个长度为n的32位浮点数组a、b，对两个数组中的每个元素a[i]、b[i]做加法，并以保存结果这一简单运算为例（为叙述方便，标记为例1）。其计算复杂度公式为：O（2n×a+b×n+g×n）
其中：
❏a表示加载的吞吐量倒数，即加载指令的吞吐量倒数；
❏b表示加法指令的吞吐量倒数；
❏g表示存储指令的吞吐量倒数。
如果代码运行在一台为延迟优化的处理器上，只需将a、b、g替换成延迟时钟周期数即可。以Intel Haswell架构为例，假设数据都在一级缓存中，此时a为3，表示从一级缓存中加载数据的延迟为3个周期；b为0.25，表示加法指令的吞吐量为4；g为3，表示从存储数据到一级缓存的延迟为3个周期，故计算复杂度为O（9n+0.25×n），从中可以看出：绝大部分计算复杂度是由访存带来的，这意味着这个算法的瓶颈是访存。
计算复杂度还和硬件的架构相关，如果算法的某种指令可以被SIMD单元处理且程序的确会使用SIMD指令，那么其吞吐量倒数就会考虑一次可SIMD处理的操作数量。以例1为例，如果使用128 SSE指令的话，其计算复杂度为O（0.5n×a+0.25b×n+0.25g×n）。如果某条分支指令需要被SIMD单元执行两次，则需要对相应的吞吐量倒数除以2。
在并行算法上应用计算复杂度分析时，如果控制流之间的计算量并不均衡，那么需要同时考虑控制流之间的最大计算复杂度和最小计算复杂度，它们的比例就可大致估计负载不均衡的程度，进而估计优化负载后，最大可提升的性能比例。假设一个有两个线程的并行算法，两个线程的计算复杂度分别为O（0.5n）和O（2n），故计算时间由O（2n）决定，应用负载均衡算法后，最好的性能提升是2×2/（2+0.5）=1.6倍。
2.访存复杂度
访存复杂度衡量算法访问缓存层次的字节数量，通常不是直接地加和，而是由瓶颈在缓存层次的哪一级决定。比如，如果算法是内存密集型的，只需要分析其内存访问字节数量；如果算法是一级缓存密集型，则需要分析一级缓存访问字节数量；如果算法是多核心共享缓存密集型，则需要分析所有处理器核心访问共享缓存的总数量。
计算访存复杂度时，由于缓存容量大小、替换策略和缓存线大小导致的额外开销也应当计算在内。
对于访存复杂度，通常使用缓存层次的带宽来表示，比如算法发挥的一级缓存的带宽是多少，二级缓存带宽多少。
由于访存复杂度要考虑存储器层次结构，因此对于一些复杂的算法需要处理器提供硬件计数器支持，可喜的是，现在大多数主流的处理器都已经提供了该项支持。
对于某一个具体的程序来说，通常有以下几种带宽定义：
1）存储器的峰值带宽：该值由硬件规格决定，通常可由硬件参数计算出来。如双路双通道DDR3-2333内存，其峰值带宽为：2（双路）×2（双通道）×2.333（内存等效频率）×8（64位内存控制器）=74.6 GB/s。
2）可获得的存储器带宽：该值亦由硬件决定，不过其大小由程序测试获得。由于硬件设计方面可能存在不足，可获得的存储器带宽通常要小于存储器的峰值带宽。如NVIDIA K20c GPU的峰值显存带宽大约200 GB/s，但是可获得的显存带宽大约175 GB/s。
3）程序发挥的存储器带宽：此值是硬件为某个特定程序发挥的带宽，一般而言，此值可通过硬件计数器获得，但是某些顶级的软件开发人员也能够手工计算出来。
4）程序的有效访存带宽：此值由算法计算获得，其表示程序最小要访问的数据量与程序计算时间的比值。其还表示访存优化能够达到的上限，对程序访问带宽的优化不可能比程序的有效访存带宽还小。
访存复杂度分析的是程序发挥的存储器带宽，因为其值是程序在硬件的存储器上执行时的实际访存字节数。
可获得的存储器带宽与存储器的峰值带宽的比例可以反映存储器处理存储器访问的效率，比如Intel Xeon Phi处理器的峰值显存带宽大约350 GB/s，而可获得的显存带宽大约170 GB/s，这就是一个典型的存储器硬件存在不足的例子。对于主流的GPU而言，此值在70%～80%，而在Intel X86处理器上，此值通常能够超过90%。
程序发挥的存储器带宽与可获得的存储器带宽的比例表示程序已经发挥了硬件能够提供的带宽的比例，它意味着存储器还能够提供的带宽的比例，如果值接近1，则表示存储器的带宽已经被耗尽，下一步的优化应当考虑如何减少访存次数和浪费的存储器带宽。
程序的有效访存带宽和程序发挥的存储器的比例表示程序访问存
试读结束[说明：试读内容隐藏了图片]