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倍以上的工资（与同等能力的标量串行软件开发人员比），否则开发优秀的并行软件通常是一句空话。