存档

文章标签 ‘并行程序’

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也没出来,之后就直接停止了研发)。

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

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

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

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