基本概念
- 并行（parallelism）：在多处理单元系统上，将计算或数据划分为多部分，各部分在不同处理单元上执行，各处理单元相互协作，同时运行。
- 并发（concurrency）：在一个处理单元上运行多个应用，各应用分时占用处理单元，有时称其为时间上串行、空间上并行。
- 代码性能优化：通过调整源代码，生成更高效的机器指令（执行时间和使用存储器更少）。
并行和并发都是代码性能优化的方式。通常代码性能优化特指除了并行和并发之外的优化方法。
硬件生产商采用各种方式提高硬件计算能力，目前最流行的三种方式：
- 指令并行：处理器一个周期执行多条相同或不同的指令，比如：Intel Haswell处理器一个周期可执行4条整数加法指令、2条浮点乘加指令，同时访存和运算指令也可同时执行。
- 数据并行：使用向量指令，向量化是指同一条指令同时操作多个数据，主要是SIMD和VLIW技术。SIMD技术将处理器一次处理的数据位数扩大到了128或256位。
- 多核并行：同一个芯片集成多个处理单元，根据集成方式不同，分为多核处理器或多路处理器（集成多个多核处理器称为多路）。
图形处理单元（GPU）通过将几百、几千核心集成在一块硅片上以满足图形图像及视频对性能的需求，这称为众核。一方面：众核处理器集成的核心数量远远超过多核；另一方面：众核处理器将更高比例的晶体管用于计算，因此其原生性能也超过多核。
目前绝大部分应用软件是串行的，只能在多核CPU中的一个核上运行。通过多核技术，硬件生产商成功地将提高实际计算能力的任务转嫁给软件开发人员。
代码优化并不利用多核CPU的全部计算能力，也不要求软件开发人员掌握并行开发技术，应当优先选择串行代码优化。采用并行技术的加速比通常不超过核数。
Intel Haswell I3-4130处理器使用256位的向量，集成了2个核心。在其上运行32位浮点计算的标量串行代码，最多能够发挥峰值性能的1/16。标量计算意味着只能发挥向量运算性能的1/8，而串行代码只能发挥2核中1核的性能。
进程与线程
进程的概念简化了程序设计、存储器管理等，并且提供了一种大粒度的并行方法。线程存在进程之中，进程中的所有线程共享进程的资源并独享某些资源，因此更易于通信。进程可调度到一台机器中的一个或多个处理器核心上执行，而线程会调度到一个核心上执行，向量化的代码则会映射到一个核心内的向量单元上执行。由于操作系统调度策略的不同，并不能保证进程和线程会一直在相同的核心上执行。通常基于进程的是类似MPI的分布式存储器编程模式，基于线程的是类似pthread、OpenMP等基于共享存储器的编程模式。由于分布式计算的各节点有其独立的存储器，因此基于进程的消息传递通信更适合，而多核等由于共享存储器，所以基于线程的共享存储器更易于通信。
进程是对操作系统正在运行的程序的一种抽象。系统内的多个进程通过时间片轮转并发执行，保存一个进程的状态切换到另一个进程的过程称为上下文切换。在任何一个无限精度时刻，一个处理器核心最多只能运行一个进程或一个线程，当操作系统需要在某个核心上运行另一个进程时，就会进行上下文切换。上下文切换和通信较耗时，基于进程的并发往往只适合于大粒度的任务并行。进程是资源拥有的独立单位，不同的进程拥有不同的虚拟地址空间，不能够直接访问其它进程的上下文资源。
进程之中可以有许多线程，这些线程共享进程的上下文，如虚拟地址空间和文件，但独立执行且可通过存储器通信。当进程终止时，进程内的所有线程也同时终止。另外线程也有其私有逻辑寄存器、栈和指令指针PC。由于线程共享进程资源，因此线程的建立、销毁比进程的建立、销毁更高效。目前基于GPU的并行编程也使用基于线程的开发环境，这是一种硬件线程，其线程的创建、调度和销毁开销接近0。多线程程序在多核和单核上执行时具有明显的差别。由于在单核上多线程通过分时共享执行，这使得一些长延迟的操作如锁、IO访问不会导致核心空闲。网络服务器就是通过多线程技术来提升系统的吞吐量的。
由于进程的存储器资源是独立的，而线程的存储器资源是共享的，因此通常基于进程的并行编程更简单，但是基于线程的并行在多核处理器上通常更高效。在节点间使用进程级并行，在节点内的多核上使用线程级并行，这称为混合或超级并行。
超线程（hyper-threading）通过双倍增加一些资源（PC和寄存器）减少线程的切换代价，但是只有一份执行单元，因此其峰值计算能力并没有提高。超线程技术将一个物理处理器核模拟成两个逻辑核，可并行执行两个线程，能够在单个时针周期内在两个线程间切换，让单核都能使用线程级并行计算，减少了CPU的闲置时间，提高CPU的运行效率。
如果一个操作并不阻碍进程或线程，接着执行代码，称这个操作为非阻塞，反之则为阻塞。相对非阻塞来说，阻塞更为常见，因为非阻塞要求开发人员手动保证操作的完成，这可能会带来数据一致性问题。同步或异步则是针对通信的多个进程或线程，如果一个进程或线程与其他进程与线程通信时，不需要其他线程做好准备，称之为异步，反之则为同步。在某些文献中，阻塞与同步、非阻塞与异步的含义是一样的。
并行硬件平台
###机群
通过使用网线依据某种拓扑方式将多台微机互连以获取更大的计算能力，这种系统通常称为机群，而每台微机称为节点。目前几乎所有的超级计算机都是机群系统。显式的消息传递编程接口MPI是这类平台上的标准和首选。
###X86多核向量处理器
相比超线程，多核是真正的线程级并行设备。多核与超线程技术相结合，可进一步提高系统的吞吐量。多核的每个核心里面具有独立的一级缓存，共享的或独立的二级缓存，有些机器还有独立或共享的三级/四级缓存，所有核心共享内存DRAM。多线程/多进程程序时可利用这些每个核心独享的缓存，这是超线性加速（多核处理器上获得的性能收益超过核数）的原因之一。发挥多核处理器多个核心性能的编程方式通常是使用OpenMP和pthread等线程级并行工具，容易产生的性能问题主要是伪共享和负载均衡。
SSE是X86多核向量处理器支持的向量指令，具有16个长度为128位（16个字节）的向量寄存器，处理器能够同时操作向量寄存器中的16个字节。AVX将SSE的向量长度延长为256位（32字节），并支持浮点乘加。由于采用显式的SIMD编程模型，SSE/AVX的使用比较困难。
为了减小使用SIMD指令的复杂度，Intel寄希望于编译器。Intel的编译器向量化能力非常不错，但通常手工编写的向量代码性能更好。在MIC（Intel 的众核架构）上编程时，软件开发人员的工作由显式使用向量指令转化为改写C代码和增加编译制导语句，让编译器产生更好的向量指令。要发挥X86向量处理器的向量计算能力，可以使用三种编程方式：
- 使用串行C语言，让编译器产生向量指令，或使用编译制导语句（如OpenMP 4.0）。这种方代码的可移植性通常最好，但能够发挥的性能也最差。
- 使用Intel规定的内置函数。
- 使用汇编语言。
###CPU+GPU
由于现代GPU强大的并行处理能力和可编程流水线，可处理非图形数据。特别在面对单指令流多数据流（SIMD），且数据处理的运算量远大于数据调度和传输的需要时，GPGPU在性能上大大超越了传统的CPU应用程序。由于GPU将更大比例的晶体管用于计算，相对来说用于缓存的比例就比CPU小，因此通常局部性满足CPU要求而不满足GPU要求的应用不适合GPU。CPU+GPU异构计算需要在GPU和CPU之间传输数据，而这个带宽比内存的访问带宽还要小，因此那种需要在GPU和CPU之间进行大量、频繁数据交互的解决方案不适合在GPU上实现。
###移动设备
而由于电池容量和功耗的原因，移动端不可能使用桌面或服务器高性能处理器，因此其对性能优化具有很高需求。ARM支持的向量指令集称为NEON，大多数移动GPU已支持使用OpenCL进行并行计算。
现代处理器
现代处理器利用了指令级并行技术，同一时刻存在着多条指令同时执行。处理器执行指令的顺序无须和汇编代码给出的指令顺序完全一致，编译器和处理器只需要保证最终结果一致，这类处理器称为乱序执行处理器。目前主流的CPU和GPU基本上都已经是乱序执行处理器。严格按照顺序一次执行一条指令，只有前一条执行完才开始执行后一条指令的处理器，称为按序处理器。
现代乱序执行多核向量处理器，具有许多和代码性能优化相关的特点：
- 指令级并行：主要有流水线、多发射、VLIW、乱序执行、分支预测等技术；
- 向量化并行（矢量化）：主要有SIMT、SIMD技术；
- 线程级并行：多核支持的线程级并行是目前处理器性能提升的主要手段；
- 缓存层次结构：包括缓存组织、缓存特点以及NUMA。
##优化方法
程序优化主要分两类：（串行）算法优化和硬件相关优化（向量化、并行化）。算法优化通常独立于硬件，比较复杂，常通过$\mathbf O$度量复杂度比较性能。硬件相关优化根据硬件体系结构，设计相应算法，主要考虑硬件的存储和计算特性，通常包括：
- Cache优化；
- 流水线优化；
- 指令集优化；
- 多核并行化；
- GPU优化；
- 多机并行化。
Cache优化的目的是提高Cache命中率，通过减少数据存取时间，提升程序性能。流水线技术是为了充分利用有限的硬件资源，尽可能让所有硬件都忙起来，减少等待时间。多核优化是将任务分配给多个处理器执行。GPU的处理核通常会比CPU多得多，并且有自己的存储器。
DSP优化主要包括Cache优化、流水线优化和指令集优化。
算法优化通常主要考虑计算代价，这和处理器相关。对于硬件相关的优化，存储器和总线结构是不可忽视的重要因素。
参考资料
- 刘文志：《并行算法设计与性能优化》。
