3月
29
2013

流水线中的大冒险

上一节说到,流水线中的分支预测本身是为了提高整条流水线的并行度,为此,CPU做了很多努力,例如乱序执行,甚至于流水线本身也是为了这个目的而诞生的。

和我们编写一般程序一样,顺序执行总是最简单、最安全的,指令被一条接着一条地顺序执行,没有人会思考任何有关并发的隐患。但是一旦踏入并发编程的范畴,似乎就开始变得一团糟,你需要考虑数据竞争、锁、内存等等一系列问题。和分支预测一样,有时候你会采用一些试探性的方法去处理并发中产生的问题,例如经典的CAS(Compare And Swap)算法,可能成功可能失败,喜忧参半。

在流水线中也存在着类似的大冒险,典型的有三种:

数据冒险

结构冒险

控制冒险

对应的,也有一些方法去辅助CPU在这些冒险的过程中,尽可能地达到我们期望的结果。

一、数据冒险

数据冒险源于在流水线的乱序执行中,读写之间产生的数据依赖,例如写后读,如果在一条指令的读之前,刚好有另一条指令完成了对相同位置的写,那么按常理来说,读的指令读到的数据必须是刚被写入的那个值。

看起来是不是很眼熟?是的,这跟Java中的Happens-Before法则是一致的,扩展开的话,数据库中的一致性以及Java中的volatile,本质上都是在确保同样的效果。

我们知道经典的CPU是通过ALU进行计算的,而数据的输入则在通用寄存器中,事实上为了支持流水线,在ALU和通用寄存器之间,还有一些额外的寄存器,这些寄存器对程序员不可见,被称作流水线寄存器,它们的作用也很简单,保存在流水线的执行过程中,各个时钟周期的结果暂存。

对于经典的五级流水线来说,一条指令的执行周期要经过以下过程:

IF: Instruction Fetch – 取址

ID: Instruction Decode and register fetch – 译码

EX: Execution and effective address calculation – 执行

MEM:  Memory access – 内存访问

WB:  Write Back – 写回通用寄存器

那么试想一下,假设现在有两条指令的执行路径如下:

I1: IF – ID – EX – MEM – WB

I2:       IF – ID –   EX   – MEM – WB

I1的结果在EX之后被写入流水线寄存器暂存,此时还没写入内存,也没写入通用寄存器。

这个时候I2在EX阶段要取I1的结果,按道理是拿不到的。

最简单的,I2等待2个时钟周期,等I1把结果写入通用寄存器后,再去读取。这是一种解决方式。

CPU还可能会采用被称作Register Forwarding的机制获取数据,简单来说就是I1的流水线寄存器中的数据直接转发作为I2的EX的输入,此时I2的EX就不会受到影响,并且避免了等待造成的浪费。

二、结构冒险

结构冒险是当CPU同时有多条指令要访问同一个硬件资源时造成的冲突。例如同时对内存的访问,但同时只能提供一条指令的访问。

结构冒险在早期的冯·诺依曼架构中是个问题,因为数据和指令是存在一起的,IF和MEM就会发生冲突。而现代处理器在L1 Cache层将指令和数据分开,分为L1 Cache(I)和L1 Cache(D),避免了这个竞态问题。

三、控制冒险

控制冒险和上一节说到的分支预测关系密切。

首先想象一下如果没有分支预测,那么当流水线遇到跳转语句时,它会认为跳转这个时间点开始进入新的起点,所有事先被执行的指令都不对。这时CPU需要插入若干个停顿周期,直到一切恢复原点。

某些处理器会通过插入NOP指令的方式来停顿若干个时钟周期,而某些处理器干脆排空所有的当前指令(被称作流水线冲刷(Pipeline Flush)。

除了分支预测,另一种优化方式是将插入的等待NOP指令改为不相关的乱序执行的有效指令,利用等待时间的开销。

Written by Hesey Wang in: 并发,技术 |

没有评论 »

RSS feed for comments on this post. TrackBack URL

Leave a comment

©2006 - 2016 Hesey (舒)