存档

文章标签 ‘顺序一致性’

存储一致性之顺序一致性(Sequential consistency)

2011年5月6日 sigma 没有评论 23,439 views

定义(Lamport ,1979):

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program

中译为:

任意一次执行的结果都像所有处理器的操作以某种顺序的次序执行所得到的一样,而且各处理器的操作都按照各自程序所指定的次序出现在这个顺序中。

这个定义意味着,当程序在各个机器上并行运行时,任何一种有效的交错存储器访问顺序都是可认可的行为,但所有处理器必须看见的是同样的访问顺序。如果一个进程(处理器)看见的是一种交错,另一进程看见的是另一种交错,则这样的存储器不是一个顺序一致性的存储器。然而,同一程序再次并行运行,其存储器访问的交错次序会不同于上次的交错次序,这是允许的。在一块存储器中,若一个进程(或处理机)看到一种交错,另一进程看到另一个交错,这就不是顺序一致存储器。注意,这与时间无关,没有最近存入的概念。在这里,进程可以看到所有进程写,但只能看到本进程读。

在顺序一致性中衍生了一个可线性化概念:

线性化是一种弱于严格一致性但又强于顺序一致性的一致性模型。这种模型假设操作具有一个全局的时间戳。设TSop(x)表示在x上的操作op执行时的时间戳, op可以是读操作,也可以是写操作。如果TSop1(x)< TSop2(y),则在顺序一致性模型中的读/写操作顺序下,操作op1(x)必须在操作op2(y)之前。

线性化的数据存储也是顺序一致的。它们的区别在于:线性化是根据时间戳确定操作顺序的。在实际应用中,线性化主要用于并发算法的形式验证。线性化的实现比顺序一致性的实现开销更大。

最后,给一张顺序一致性的示意图:

CMP读书笔记五:通过并行加速程序

2011年4月10日 sigma 9 条评论 4,952 views

前一篇关于降低单任务延时的文章,主要讲的都是在现有的编程模式下,不改变现有串行程序代码下,通过编译器,操作系统,以及处理器自动给程序加速,降低延时。但是,这种加速方法加速很有限,不具有可升级性(scalable):辅助线程(helper thread)受限于只有一个主线程,一个辅助线程,加速比很难超过2;猜测多线程(TLS)受限于原来串行程序上下文的依赖性,可拆解的部分有限,加速比也不理想。

为了解决程序在多核系统加速受限的问题,出现了串行程序不同的编程模式,并行编程。和串行程序不同,并行程序设计要求程序员显示的声明程序的那些部分是可以并行的。因此,对于一个习惯于串行程序编写的程序员来说,写并行程序难度要大。

对于串行程序,只需要输入相同,每次执行的结果是一样的,是确定的。而对于并行程序,执行的结果每次都可能不一样。在这些所有的执行结果中,只需要能够把并行程序串成某个串行程序,并且该串行程序的执行结果和该次并行程序执行结果一致,则认为程序在顺序一致性模型(sequential consistency,SC)下是正确的。顺序一致性的严格定义如下:

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

意译成中文如下:

并行程序的任何一个执行结果都和某个顺序执行相同,该顺序执行符合:①该顺序执行是将所有处理器执行的并行操作(指令)串起来的。②对于原来任何一个处理器上的并行执行操作,其排序在改顺序执行上的排序一直。(通俗的将,在并行执行中,对于同一个核心的执行A,B,倘若A在B前,在最后的串起来的顺序执行,A还是要在B前)

因为这个一致性模型要求太强了,要保证并行执行符合该模型对硬件要求很高,并且会带来极大的性能损耗,因此,出现了很多弱的一致性模型。

另外,由于并行程序可能出现的符合一致性要求的结果不止一个,而事实上程序员希望的执行结果可能只有一个或几个,为了解决这个问题,对于要放到不同处理器核心执行的代码,就需要程序员显式的标记那段代码在那段代码之前执行,既需要通过一些barrier来同步不同处理器核心的执行。

另外,并行执行还涉及到对一些临界资源的访问,对于这些共享的资源,往往只能一个处理器访问,这是就会出现互斥,这时需要一些机制来保证互斥访问,于是出现了锁的机制。但锁很容易导致死锁活锁问题,导致性能极大下降。为了解决这个问题,受数据库启发,出现了事务内存(transaction memory,TM)的概念,但是TM对硬件的改动极大,现在还没有商业的处理器能够实现(之前sun公司的Rock处理器号称要实现,但是直到sun落下,rock也没出来,之后就直接停止了研发)。

写到这里,突然这个关于并行的题目有点大,有太多的东西需要讲,有太多的东西需要介绍,有种剪不断理还乱,不知从何处下手的感觉。好吧,这篇就先扯到这,让他虎头蛇尾好。

有空的话,我再写些东西把各种一致性,各种编程模型以及事务内存,以及其他的并行相关的东西介绍下~

最后,秉承每文一图的习惯,附一张顺序一致性的示意图(上面是符合的并行执行,下面是不符合的并行执行):

无觅相关文章插件,快速提升流量