多核编程的几个难题及其应对策略

发布时间:2008/6/5 0:00:00 访问次数:313

　　随着多核 cpu的出世，多核编程方面的问题将摆上了程序员的日程，有许多老的程序员以为早就有多cpu的机器，业界在多cpu机器上的编程已经积累了很多经验，多核cpu上的编程应该差不多，只要借鉴以前的多任务编程、并行编程和并行算法方面的经验就足够了。

　　我想说的是，多核机器和以前的多cpu机器有很大的不同，以前的多cpu机器都是用在特定领域，比如服务器，或者一些可以进行大型并行计算的领域，这些领域很容易发挥出多cpu的优势，而现在多核机器则是应用到普通用户的各个层面，特别是客户端机器要使用多核cpu，而很多客户端软件要想发挥出多核的并行优势恐怕没有服务器和可以进行大型并行计算的特定领域简单。

　　串行化方面的难题

　　1）加速系数

　　衡量多处理器系统的性能时，通常要用到的一个指标叫做加速系数，定义如下：s(p) = 使用单处理器执行时间（最好的顺序算法）/ 使用具有p个处理器所需执行时间

　　2）阿姆尔达定律

　　并行处理时有一个阿姆尔达定律，用方程式表示如下：

　　s(p) = p / (1 + (p-1)*f)

　　其中 s(p)表示加速系数

　　p表示处理
器的个数

　　f表示串行部分所占整个程序执行时间的比例

　　当f = 5%, p = 20时, s(p) = 10.256左右

　　当f = 5%, p = 100时, s(p) = 16.8左右

　　也就是说只要有5%的串行部分，当处理器个数从20个增加到100个时，加速系数只能从10.256增加到16.8左右，处理器个数增加了5倍，速度只增加了60%多一点。即使处理器个数增加到无穷多个，加速系数的极限值也只有20。

　　如果按照阿姆尔达定律的话，可以说多核方面几乎没有任何发展前景，即使软件中只有1%的不可并行化部分，那么最大加速系统也只能到达100，再多的cpu也无法提升速度性能。按照这个定律，可以说多核cpu的发展让摩尔定律延续不了多少年就会到达极限。

　　3）gustafson定律

　　gustafson提出了和阿姆尔达定律不同的假设来证明加速系数是可以超越阿姆尔达定律的限制的，gustafson认为软件中的串行部分是固定的，不会随规模的增大而增大，并假设并行处理部分的执行时间是固定的（服务器软件可能就是这样）。gustafson定律用公式描述如下：

　　s(p) = p + (1-p)*fts

　　其中fts表示串行执行所占的比例

　　如果串行比例为5%，处理器个数为20个，那么加速系数为20＋(1-20)*5%=19.05

　　如果串行比例为5%，处理器个数为100个，那么加速系数为100＋(1-100)*5%=95.05

　　gustafson定律中的加速系数几乎跟处理器个数成正比，如果现实情况符合gustafson定律的假设前提的话，那么软件的性能将可以随着处理个数的增加而增加。

　　4）实际情况中的串行化分析

　　阿姆尔达定律和gustafson定律的计算结果差距如此之大，那么现实情况到底是符合那一个定律呢？我个人认为现实情况中既不会象阿姆尔达定律那么悲观，但也不会象gustafson定律那么乐观。为什么这样说呢？还是进行一下简单的分析吧。

　　首先需要确定软件中到底有那么内容不能并行化，才能估计出串行部分所占的比例，20世纪60年代时，bernstein就给出了不能进行并行计算的三个条件：

　　条件1：c1写某一存储单元后，c2读该单元的数据。称为“写后读”竞争

　　条件2：c1读某一存储单元数据后，c2写该单元。称为“读后写”竞争

　　条件1：c1写某一存储单元后，c2写该单元。称为“写后写”竞争

　　满足以上三个条件中的任何一个都不能进行并行执行。不幸的是在实际的软件中大量存在满足上述情况的现象，也就是我们常说的共享数据要加锁保护的问题。

　　加锁保护导致的串行化问题如果在任务数量固定的前提下，串行化所占的比例是随软件规模的增大而减小的，但不幸的是它会随任务数量的增加而增加，也就是说处理器个数越多，锁竞争导致的串行化将越严重，从而使得串行化所占的比例随处理器个数的增加而急剧增加。（关于锁竞争导致的串行化加剧情况我会在另一篇文章中讲解）。所以串行化