又有人投入Erlang的怀抱了:37Signals Campfire loves Erlang

p 处理器 求 大小为 n 的数组 的向前和：

p == 1 时
  做 n-1 次加法，耗时 n

p > 1 时
  1.由于 n 很大，先均匀分 p 块，求 块内向前和，耗时 n/p
  2.再求 块外向前和，耗时不超过 p
  3.最后把 块内向前和 与 块外向前和 加起来，耗时 n/p

  最后是 2n/p + p
  处理器数目巨大时，第 2 步耗时可以更少，设为 f(p)，由 f(n) 和 f(p) 的关系列出方程，选择适当的 p 可以求得 f 最小值……
  既然题目说数组巨大，那么相比之下处理器数目不巨大，就不考虑了 ……

-----------------

处理器充分多时，求 n 个数的和，可以用二叉把耗时降低至 log(n)/log(2)，不过“向前和”貌似有点不一样 -_-

这个算法若不考虑通讯开销,最快是O(nlogn)的.只会慢不会快.

不是啊，p == sqrt(2n) 时，能达到 O(sqrt(n)) 的

并行算法的一个前提条件是假定处理器数量固定.假定你现在4个处理器


1 2 | 3 4 | 5 6 | 7 8|9 10|11 12|13 14| 15 16 

1 3 | 3 7 | 5 11 | 7 15|9 19|11 23|13 27| 15 31    8/4

1 3  6 10 | 5 11  18 26|9 19 30 33|13 27 42 58    8/4

1 3  6 10  15 21  28 36|9 19 30 33 46 60 75 71    8/4

1 3  6 10  15 21  28 36 9 19 30 33 46 60 75 71    8/4


你的算法是这样的？
刚才说错了复杂度应该是O(nlogn/p)
只有当处理器数目和元素数目相等时，才能跑到O(logn)
当然一般的情况下,元素数目远大于处理器数目

排版好痛苦…… 改了好几遍

这样应该清晰？ 设有 4 个处理器。（p=4）

 

1 2 | 3  4 |  5 6  | 7  8     运算次数 / 本轮用到的处理器个数

第一步：块内向前和
1 3 | 3  7 |  5 11 | 7  15          1 / 4

 

第二步：块外向前和（结果存于前一块的最后一个元素）
1 3                               
      3 10                          1 / 1 (10 = 3+7)
              5 21                  1 / 1 (21 = 10+11)
                     7  36          1 / 1 (36 = 21+15)

 

第三步：内外向前和相加
1 3 | 6 10 | 15 21 | 28 36          1 / 3

 

既然处理器数量是小小的常数，O(2n/p + p) = O(n/2) = O(n)，怎么弄都是 O(n) ……

第一步 n/2p

第二步 n/2-1 (bottle neck)

第三步 (n-1)/2p

n/2p+n/2+(n-1)/2p

按照比单线程算法快的要求，的确已经不错了，不过speed up不可能高于50%.意味着你无论加多少cpu都不会快过单线程算法的一半.

假定现在4个处理器

1  2  3  4 |  5  6  7  8 |  9 10 11 12 | 13 14  15  16    总运算/处理器个数

1  3  6 10 |  5 11 18 26 |  9 19 30 42 | 13 27  42  58       12/4

1  3  6 10 |  5 11 18 36 |  9 19 30 78 | 13 27  42  136       3/1

1  3  6 10 | 15 21 28 36 | 45 55 66 78 | 91 105 120 136       9/3

 

第二步等价于 大小为4（分块数）的数组向前和问题，既然处理器数量是常数，那么就可以常数时间解决，并不是 bottle neck。

其实加速的方法是比较经典的算法.可以往这方面考虑
另外,还可以加一个两个限制条件,就不那么简单了.
1.数组中的某些随机数可能太小,因此我们可以设一个阈值k,使得前向加前的所有元素都大于k
2.再进一步元素的值也不能过大,设一阈值l,使得前向加前的所有元素都在k和l之间.

根据同学说的 xiaonei现在也转向Erlang了

这个算法串行仍然是O(nLogn)的,很简单每一步都需要n/2,总共需要logn步。

只有当处理器达到log2n时,才可能是O(n)的,即可以在n/2内完成,但是再多的处理器也只能比串行算法快一半.比如你处理100万个元素,需要将近20个处理器才能比串行算法快一半.

其实,这个算法可以在串行时就达到O(n).并行时可以达到O(n/p).