并行算法设计与性能优化总结

时间:2022-11-07 05:55:33

与其说是总结,不如说是查漏补缺。因此,可能对别人来说,看起来语无伦次,毫无章法,仅作为自己的记录:

1.并行和并发的区别在于并发是在单核上执行多线程,即为满足用户应用需求,并行才是为了加速。

2.一般来说,并行相对串行的加速比,不会超过核数。Amdal定律告诉我们,在计算规模一定的前提下,只要代码中有不能并行的部分,程序是不太可能完全线性加速的,在处理器核心增多的情况下,并行不好的部分,可能会成为加速的瓶颈,最终程序或硬件达到一定的核心数量的极限,再增加核心不会增加性能了。

3.CPU的功耗与频率的三次方近似成正比,这导致无限制的提升CPU频率已经无可能,因此才出现多核,GPU等满足性能要求。

4.将多个多核集成在一起,叫多路,而GPU将几百,几千个核心集成在一起,叫众核。

5.在实践中,进程可以调度到一台机器中的一个核心或者多个处理器核心上,而线程会调度到一个核心上执行,向量化的代码则会映射到一个核心内的向量单元上执行。由于操作系统的调度策略不同,并不会保证进程和线程一直在相同的核心上执行。通常基于进程的是像MPI一样的分布式存储器编程模式,基于线程的是像OpenMP,pthread等基于共享存储器的编程模式。基于分布式计算的各节点有独立的存储器,因此,基于进程的消息传递通信更合适,而多核等由于共享存储器,基于线程的共享存储器更合适。

6.所谓超线程,是芯片厂商提供了切换线程的代价。一般应用加速比不超过20%。

7.GPGPU是一种利用处理图像任务的GPU来完成本来有CPU处理(与图像处理无关的)的通用计算任务。

8.指令级并行方法有:指令流水线,乱序执行,多发射,VLIW和分支预测。

9.向量级并行方法有:SIMD,SIMT

10.线程级并行:多线 程并行。

      10.1运行在用户空间的线程叫用户线程,运行在内核的线程叫内核线程,用户线程由库管理,无需操作系统支持,因此创建和调度无需干扰操作系统的运行,消耗少,操作系统不知用户线程的存在,因此无法将用户线程映射到核心上,当用户线程由于资源分配而阻塞时,操作系统无法切换。为了将用户线程和内核线程的优点同时发挥出来,现代库和操作系统将用户线程映射到内核线程,通常有一对一,一对多,多对多,多对一,多数为多对多的方式,实际在核心上执行的线程数量可能远少于声明和创建的线程数。

       10.2常见的多线程编程库有:pthread,win32 thread,OpenMP,C/C++新标准,OpenCL和CUDA,OpenACC

       10.3通常,支持超线程的多核处理器能够使用的线程数最多是物理核心的2倍,还要防止数据竞争,死锁,饿死,内存伪共享等问题。所谓数据竞争就是在多个线程访问相同数据时,由于同步等原因,需要让步等待其他线程访问结束,导致性能降低,所谓伪共享,是多个线程读写数据映射在一个cache线上时,如果一个线程更改了数据,那么其他线程对该数据的缓存就失效,如果线程频繁的更改数据,硬件就需要不停的更新cache线,这使得性能从独享cache降低到共享cache或者内存的水平。

       10.4多核和单核上多线程运行的不同。

       10.4.1单核上,多线程就是并发,多个线程执行锁或者临界区,实际上是一个线程在执行,而核心也只支持一个线程在运行,线程调度影响的只是持有和释放锁的时间,多核上,锁或者临界区会导致其余的处理器空闲而只允许一个处理器执行持有锁的那个线程,这中串行会影响性能。

       10.4.2单核上,负载均衡不用考虑,多核上,此时最终运行时间由运行最长的线程决定。

       10.4.3单核上,任务调度完全由操作系统执行,无须开发人员干预,而多核上,需要人为合理分配核心计算任务,以尽量同时结束计算。

11.cache,虚拟内存TLB,NUMA等内存访问加速技术。NUMA技术的使用,需要保证控制流(线程或者进程等)分配存储器时分配在离自己近的物理内存上,这可以通过线程内使用malloc分配来办到。同时要保证控制流不能核心间迁移。即绑核。如GCC的环境变量GOMP_CPU_AFFINITY=“0-3 4-10:2”,Linux系统有numactl工具设置NUMA特性,以及pthread提供API,OpenMP也是提供API。

11.串行代码优化从 以下几个角度分析:
    11.1系统级,需要分析出性能控制因素,例如网速,利用率,负载均衡。如果CPU使用率不高且很稳定,则需要优化内存带宽,若CPU使用率忽上忽下,则需要考虑其他进程占用CPU。当然,CPU大多时候空闲,说明没有很大程度上发挥硬件计算能力,或者,访问带宽太小,或者CPU在等待其他进程,线程释放资源等。
     11.2应用级别,通常有编译选项,调用高性能库,去掉全局变量等、
     11.3算法级,函数级,循环级,语句级,指令级