Skip to content

Lesson14：并行算法

Parallel Random Access Machine (PRAM)

alt text

三种处理矛盾的方法： + Exclusive-Read Exclusive-Write (EREW)：限制读写 + Concurrent-Read Exclusive-Write (CREW)：限制写，可以随便读 + Concurrent-Read Concurrent-Write (CRCW)：可以随便读写 然而并不是真的随便写 + Arbitrary rule：埃及吧咋写咋写，随便挑一个(可以值不同) + Priority rule：优先级高的写(可以值不同) + Common rule (if all the processors are trying to write the same value) 写入相同值才可以，不然不行

alt text

alt text

alt text

alt text

一个例题及针对它的分析：

alt text

alt text

缺点就在于，每个处理器在处理时间内都需要被调用指令有人钢枪，有人伏地并不能区分被赋予的指令的重要性(比方说那个递归树的题目，就有很多处理器只是在旁边喊666stay idle，这对于资源是浪费)

WD(work-depth)

alt text

横向对比一下其实很明显，就是WD模型是需要处理器了才拉出去，不会出现空闲喊666的情况。

忘记说了，for ... pardo表示的是使某处理器被调用。

Measuring the performance

  • Work load – total number of operations: W(n)
  • Worst-case running time: T(n)
    • W(n) operations and T(n) time 用于双重评估算法
    • P(n) = W(n)/T(n) processors and T(n) time (on a PRAM) 与上面是渐进等价的
    • W(n)/p time using any number of p ≤ W(n)/T(n) processors (on a PRAM)
    • W(n)/p + T(n) time using any number of p processors (on a PRAM)

前缀和问题

alt text

思路就是先自下而上求B(h,i)，再自上而下求C(h,i)。

对于所有右儿子的C都与其父节点相同。

代码实现：

alt text

归并排序：分割法