Thread-Level Paralellism 线程级并行
Thread-Level Paralellism (线程级并行)
目录(Page1~2)
并行计算(硬件)(Page3~12)
多核心
- 在一个芯片上有多个分离的处理器
- 多个处理器如何保持主存一致性
超线程
- 有效地让多个线程在同一个核心上执行
线程级并行(软件)(Page13~结束)
把程序切分为独立的任务块
- 譬如并行求和
分治并行
- 譬如并行快排
并行计算(硬件)
利用并行计算(Page3)
迄今为止,在我们已经讲过的内容中,我们使用多线程来处理I/O延迟。
譬如:在Web应用中,给每一个client都开一个线程,那么就可以避免一个client被另一个client阻塞。
多核心的CPU提供了额外的机遇
把工作分发到多个线程上工作,在N个核心上并行执行。
如果有很多独立的工作的话,那么这些可以自动并行。
- 例如在电脑上运行多个应用,或者服务器同时服务多个client。这些独立的(互相之间不会影响的)工作,是可以自动并行的。
当然,我们也可以专门写出并行的代码,让一个单独的大型的任务运行地更快。
- 这需要把这个任务分解成可并行的子任务。
Shark machine 可以同时运行16个线程
8核心,每个核心有两个超线程
理论上限是16倍的加速。
- 当然这是“理论上限”,实际运行中是难以达到的。
多核处理器的硬件形态(Page4~12)
(主要是《高等计算机体系结构》讲的东西,给学生一个大概行的了解即可)
多核心处理器(Page4)
图示为多核心处理器的形态,一共有n个处理器核心,编号分别是0~n-1。
每个核心都有自己独立的L1缓存和L2缓存,其中L1缓存又分为数据缓存和指令缓存。
所有的核心共享L3缓存,再由L3缓存连接主存。
三级缓存的出现,是为了弥补存储访问速度跟不上处理器运行速度的不足。
利用计算机科学的“局部性原理”,给处理器架设多级缓存,可以提升处理器的执行效率。
多级缓存是有很大的好处,但是也带来了重大的问题:“一致性”。
所谓的一致性,就是说对于不同的CPU核心,需要它们看到的是同样的主存内容。
缓存的本质还是对主存内容的一个映射,对于同一个地址,在CPU0的cache中的值如果和CPU1的cache中的值不一样,那么程序就会出现问题。
主存的一致性(Page5~7)
这里有一段代码的例子。thread1写入a并输出b,thread2写入b并输出a。
最终输出的内容,取决于代码的执行顺序,但是对于线程内部来说,绝不能乱序。即代码Wa一定要在Rb之前执行,同时Wb一定要在Ra之前执行。
Page6列举了所有的执行的可能性。
如果输出100,1或者1,100那么就是错误的结果,是不应该出现的。
但是如Page7所示。
首先main函数设置a为1,b为100,thread1和thread2都把a、b放到了自己的cache中。
对于thread1来说,它把a写成2,然后thread2把b写成了200.
这个时候,它们只是保存了自己cache的内容,在没有确保一致性的机制的情况下,他们认为cache中的a、b的值都是正确的,于是使用print输出,就会输出1、100。
这就是采用Cache机制有可能出现的错误的结果。这个结果是不满足“主存一致性”的。它的解决方法就是SNOOPY Caches
Snoopy Caches(Page8~9)
把每个cache block标注一个状态。
有三种状态可以标注
- Invalid 不可用的值
- Shared 只读的拷贝
- Exclusive 可写的拷贝
这一页的执行顺序,动画可以表述地很清楚。
首先假设cache中是空的,thread1写入了a,那么就把a设为exclusive,(如果其他的cache中a的状态是shared,那么就强制把它们的状态设置为invalid,这个是动画所没有展示出来的)说明cache1中的a是独占的,是只有这里的a的值是正确的;同样地,thread2写入了b,那么b在cache2中也是独占的,只有这里是正确的。
thread1要想读取b,自己的cache中是没有(或者Invalid),那么就会通知其他的cache查找,找到之后,存入b的值的信息,然后status都变成shared。同理thread2也得到了shared的a的值。因此最终可以获得符合一致性的结果。
超线程
乱序执行处理器架构(Page10)
指令译码器从指令cache中读取内容后,动态地生成一个执行序列,然后再映射到不同的功能单元上。
乱序执行的目的是为了最大化处理单元的利用率。不同的功能单元的处理速度不一样,浮点慢,整数很快。浮点计算需要的时间有时是整数计算的几十倍。
1 | double a = 1.3; |
在这段代码的例子中,sum+=1的指令不必去等待浮点乘法计算完成,这可以让功能单元最大程度地利用,同时节约大量的时间。
超线程的实现(Page11)
一个核心内部,有两个PC,两个执行序列和两个寄存器堆,采用同样一套执行单元,通过指令译码器进行分配。这样可以更好地利用执行单元,提高执行效率。
一些机器(Page12)
Shark Machines 和 GHC Cluster Machines
这里只是说使用了这两种机器作为实验机器。
对于Shark Machine,它是八核心十六线程,相当于有十六个可以并行的核心,这也是为什么Parallel Sums #1~#4这些图的横坐标轴Threads的数量最大是16。
线程级并行(软件)
求和的例子(Page13~27)
这个例子的目标是从0加到N-1。
1 | Sum = 0 + 1 + 2 + 3 + 4 + ... + (N-1) |
最终Sum应该等于(N-1)*N/2
这里为了说明“线程级并行”,所以才使用这些数字一个一个加总。
加总并行:为了让整个加总过程可以并行,把N个数字划分为K个区间,每个区间N/K个数字(向下取整),最后再把余数加起来。
Page13~27总览:
- 求和的方法 #1:划分为K块,分给K个线程,每个线程都去不断更新一个全局变量Sum。
- 1-A (Race)不使用同步机制——(结果错误)
- 1-B (Semaphore)使用信号量——(特别慢)
- 1-C (Mutex)使用互斥锁——(特别慢)
- 求和的方法 #2:划分为K块,分给K个线程,每个线程只去计算自己的sum,最后汇总。
- 2-A (Adjacent memory acc)加总到一个连续的数组元素——(效果还可以)
- 2-B (Spaced memory acc)加总到有一定间隔的数组元素——(效果更好)
- 2-C (Register acc)加总到自己的寄存器——(效果最好)
Page14(1-A、1-B、1-C)
1 | typedef unsigned long data_t; // 设置data_t类型为无符号的long |
Page15(1-A、1-B、1-C)
1 |
|
Page16~17(1-A)
1-A不加同步保护的代码:
1 | void *sum_race(void *vargp) |
多核心性能如17页图示,最优加速2.86倍,但是当thread数量大于1的时候,就会出错!
Page18~19
加入同步的内容,信号量or互斥锁。代码很简单,只是在1-A的基础上,在global_sum上增加了互斥而已。
运行性能如19所示。非常差的性能!对于信号量法1-B来说,本来单线程2.5秒结束的工作,信号量法会需要10分钟,耗费时间变成了原来的几百倍。
互斥锁比信号量好三倍,运行速度只慢了一百多倍。
但是显然这些方法都是失败的!
Page20
这里就是上述方法2的2-A、 2-B、 2-C。
1 | /* Partial sum computed by each thread | 每个线程求出的部分的总和*/ |
Page21
1 | nelems_per_thread = nelems / nthreads; // 每个线程需要处理的长度 |
Page22(子线程的代码)
1 | void *sum_global(void *vargp) |
Page23
性能比较。2-A相邻数组存储的方法比一个一个相加,快了5倍,但是2-B间隔数组方法快乐13.3倍。
从程序语言的方法上没有任何区别,操作次数也一样,为什么这两者有这么大的差距?答案在Page24
Page24
因为错误的分享False Sharing。
Cache的一致性不是以字节作为单位,而是以cache block作为单位。
当更新psum[i]的时候,那么整个block就是独占的。当访问psum[0]的时候psum[1]、psum[2]、…、psum[7]就不能同时访问了。
Page24
当间隔拉大,false sharing的影响就越来越小。
在本例子中,机器的缓存block大小是64,而变量的长度是8,因此一个block中有8个。
当spacing是1的时候,thread1会影响thread2thread8;thread4;
当spacing是2的时候,thread1会影响thread2
当spacing是4的时候,thread1会影响thread2;
当spacing >= 8 就再也没有区别了。
这也是为什么图中S8和S16基本上是重合的。
Page26
1 | void *sum_local(void *vargp) |
这就是2-C的代码。这个sum是一个局部变量,因此在加总过程中线程之间不会有“任何”影响!
因为sum非常常用,所以sum很可能常驻寄存器,所以最终可以达到7.5倍的加速比,比2-B还要快两倍。
快速排序(Page28~45)
###Page 28~31
目标:排序N个数字
方法:使用快排的并行版本
算法:
- 选择轴值pivot
- 把X个数字分为两个L、R部分,L代表小于等于p的数字的集合,R表示大于等于p的数字的集合。
- 递归地排序L,得到排序后的L’。
- 递归地排序R,得到排序后的R’。
- 返回L’ : p : R’
算法的演示如图29~30所示。
1 | void qsort_serial(data_t *base, size_t nele) { |
以上代码是最基础的快排代码,采用了“分治法”的思想。
Page32 并行快排
进行并行快排的算法:
- 如果数组长度小于等于阈值,那么就采用普通的顺序快速排序。
- 否则,首先找到轴值pivot,得到L和R,然后启用两个线程,并行地排序L和R。
上述算法如图Page33所示。
Page34
任务:排序数据的一个子集
表示方式:使用base和nele来表示。base代表数组起始位置,nele代表元素数目。
特点:作为分离的线程运行。
Page35
对于很短的小任务,采用顺序快排即可。对于很小的片段内容,如果使用多线程,反而造成资源浪费。
Page36
把一个任务切分为两个任务的示意图。
原本一个thread来处理,得到轴值应在的位置以后,递归地排序L和R,会分离为两个新的threads,分别处理。
Page37 顶级函数(简化版)
1 | void tqsort(data_t *base, size_t nele) { |
Page38
1 | /* Multi-threaded quicksort | 多线程快排*/ |
Page39
1 | /* Thread routine for many-threaded quicksort */ |
Page40~41 并行快排的性能
Serial Fraction是指进行顺序排序的部分所占输入的比例。
Serail Fraction = 1 意味着100%的输入,都是用qsort_serial,即不使用多线程。
排序2^37个数字,大约134M个。
最佳的加速是6.84倍。
大多数的fraction都有着比较好的performance,极端情况除外。
当F太小的时候,并行度不够,所以比较慢。
当F太大的时候,Thread太多产生很多的负载,而且内存吃紧,造成运行缓慢。
阿姆达尔定律(Page42)
描述一个问题:
T 表示顺序执行总时间
p 代表可以加速部分的比例(p介于0~1之间)
k 代表加速比
那么公式为:
Tk = pT/k + (1-p)T
其中Tk表示在加速比为k的时候,新的顺序执行时间T。
极值
当k等于无穷大,Tk = (1-p)T
Example(Page43)
计算一下加速效果。
阿姆达尔定律和并行快排
- 顺序执行瓶颈
- 最顶层的分割环节,不会有任何加速
- 第二层,最多最多只有两倍加速
- 第k层,最多可以有2^k-1次方的加速
- 意义
- 小规模的并行效果好
- 大规模的如果想要并行,就必须让partition(分割)阶段并行
Page45是分割阶段并行的例子。
首先选取轴值p,然后划分的四个部分同时划分为L和R两个部分。
最后把所有的L聚集在左边,R聚集在右边。
这看起来是可以并行的,但是实际上在计算机中是不能加速的。
把四个部分划分为L和R可以,但是把多个L都放在数组左边,把多个R都放在数组右边,这意味着大量的拷贝操作。
而且很难直接在source array中直接操作,还需要额外的临时空间。
总结(Page47)
- 必须要有并行的策略
- 分割成k个独立的部分
- 使用分治法
- 循环内部不要使用同步机制
- 使用同步机制的代价很高
- 关心硬件
- 需要了解处理器和存储的架构
- 关心全局数据的sharing和false sharing
- 关心阿姆达尔定律
- 顺序代码会成为瓶颈
- 你可以做到的!
- 进行温和的并行并不难
- 建立试验框架,测试多种策略。