关于并行编程的笔记(一)

撰写于 2017-04-23 修改于 2018-12-15 标签 笔记

一、影响并行编程的硬件特性

1.1 CPU流水线(Pipelined CPUs)

CPU流水线,是CPU填充接下来将要执行的指令的地方。

现代CPU每个核心都有多条流水线。例如,ARM Cortex-A73架构就是3发射设计。这样就意味着,串行编写的程序代码,在实际执行过程中,往往是乱序执行的。

CPU采用了预测分支技术,可以在程序执行到关键点位置之前,预测一个结果,并将接下来的指令提前填充到流水线中。如果预测成功,程序的执行效率非常高。但是如果预测失败,流水线中的指令就必须替换为正确的指令。这就构成了很大的一笔性能开销。

gcc编译过程中,如果使用了-O2或者-O3选项,都会将实际代码的顺序打乱,以提高实际执行速度。

1.2 内存引用(Memory References)

现代CPU的计算速度发展很快,导致即使是内存IO也成为耗时操作。即使CPU的L1~L3缓存容量越来越大,但对于常见的操作,例如链表遍历,仍然作用有限。

1.3 原子操作(Atomic Operations)

使用锁结构或者其他方案,可以将一组指令绑定成不可分割的操作,也就是原子化。然而,原子化的指令组合内部,也有可能存在流水线冲刷的可能性。如果每条线程都要冲刷流水线,那性能开销就大了。

1.4 内存屏障(Memory Barriers)

内存屏障,就是为了防止顺序指令被错误地乱序执行。因此,它的存在绝对会对程序性能造成影响。

1.5 缓存不命中(Cache Miss)

在多核CPU系统中,如果一条线程修改了一个数据结构,而另一个线程同时也在修改它,此时会发生缓存不命中。而CPU的控制机制将会保证这两步操作顺序执行,降低性能。

考虑一个八核CPU。

线程A运行在核1上,修改了一个数据结构。CPU的控制机制会将该数据结构标记为脏。当运行在核7上的线程B请求修改同一个数据结构时,发现已经存入的数据被标记为脏:

  1. 向自身的二级互联模块发送查询请求,
  2. 核6回应没有修改,
  3. 向总互联模块发送查询请求
  4. 核0、核1的二级互联模块,做出回应
  5. 核0、核1的二级互联模块向所属的核心发出查询请求,然后得到核1的响应。
  6. 核1将自己的缓存,依次发给二级互联模块、总互联模块然后是核7的二级互联模块,最后发到核7的缓存里。

1.6 IO操作(I/O Operations)

无论是向本地磁盘,还是向网络请求数据,IO操作都会对程序性能构成很大的影响。

二、常见的同步结构

POSIX提供了fork()等API可以创建进程。但是进程过于重量级,而且消息传递比较麻烦。

因此,作为线程库,pthread的使用更为广泛。

pthread的详细教程可以参考man手册和Multithreaded Programming Guide

2.1 互斥锁

pthread库中提供一种mutex锁。这把锁,只能有一个线程同时持有,其他竞争线程只能被阻塞进入休眠状态。

2.2 自旋锁

spin锁和mutex锁类似,只能有一个线程同时持有。但是,没有得到锁的线程不会休眠,而是进入轮询状态。

自旋锁适用于锁每次持有时间较短的情况。

2.3 读写锁

对于多读少写的数据结构,pthread提供一种读写锁rwlock。rwlock允许线程并发读取数据,但只能有一个线程修改数据。修改期间,无法读取数据。

也即是说r锁之间不会排斥,但会排斥w锁;而w锁之间是相互排斥的。

2.4 RCU

自旋锁是Linux内核中的一种锁机制。和读写锁类似,适用于多读少些的数据结构。不同的是,r锁和w锁不会互斥。也就是读写可以同时执行。如果读取动作执行在修改之前,可能会重新读取,取决于是否注册通知事件。而读取动作执行在修改之后的,可以立即拿到正确的数据。

2.5 gcc原语

gcc编译器还提供了原子化访问内存的原语。具体可以看文档:6.52 Built-in Functions for Memory Model Aware Atomic Operations

2.6 风险指针

风险指针(Hazardous Pointer)是一种无锁结构(Lock-free)。

它的思想起源于多线程gc机制。每一个线程维护一组风险指针,其中指向的是全局公共变量。gc机制会扫描所有线程的风险指针,如果有某个公共变量不存在于任何一个线程的风险指针中,那就会被回收。

三、并行算法设计

并行算法的一个重要的设计指标就是“可拓展性”(Scalability),也就是尽量保证并发线程和程序性能正相关。

然而,真实情况并非那样美好。如果算法需要频繁地访问公共变量,那么很多线程就会阻塞在锁的获取上。线程越多,被阻塞的就越多,性能就会越差。

解决这个问题,可以从这几个方向考虑:

  1. 尽量使用原子化访问内存的原语,减少对锁的依赖。
  2. 减小锁的粒度。也就是,如果需要修改的数据不同,尽量获取不同的锁,例如:哈希锁、层级锁。
  3. 设计一组线程内部变量。将小幅度的修改控制在线程内部,从而减少对公共变量的修改,降低获取锁的频率。
Site by Zhang,Xin using Hexo & Random

Hide