计算奇数的 PRAM CREW 算法

Question

所以我尝试解决以下任务：

开发一个 CREW PRAM 算法来计算整数序列的奇数 x_1,x_2,...x_n.

n 是处理器的数量 - 复杂度应该是 O(log n) 并且 log_2 n 是一个自然数

目前我的解决方案：

Input: A:={x_1,x_2,...,x_n} Output:=oddCount
begin 
1. global_read(A(n),a)
2. if(a mod 2 != 0) then
       oddCount += 1

问题是，由于CREW不允许我同时使用多条写指令oddCount += 1是读取oddCount然后写入oddCount + 1，所以会出现多次写入。

我必须做这样的事情吗

Input: A:={x_1,x_2,...,x_n} Output:=oddCount
begin 
1. global_read(A(n),a)
2. if(a mod 2 != 0) then
       global_write(1, B(n))
3. if(n = A.length - 1) then
      for i = 0 to B.length do
         oddCount += B(i)

所以首先每个进程确定它是奇数还是偶数，最后一个进程计算总和？但是这对复杂度有什么影响，有没有更好的解决方案？

感谢 libik，我找到了这个解决方案：（n 以 0 开头）

Input: A:={x_1,x_2,...,x_n} Output:=A(0):=number off odd numbers
begin 
1. if(A(n) mod 2 != 0) then
       A(n) = 1
   else
       A(n) = 0
2. for i = 1 to log_2(n) do
       if (n*(2^i)+2^(i-1) < A.length)
           A(n*(2^i)) += A(n*(2^i) + (2^(i-1)))
end

i = 1 --> A(n * 2): 0 2 4 6 8 10 ... A(n*2 + 2^0): 1 3 5 7 ...

i = 2 --> A(n * 4): 0 4 8 12 16 ... A(n*4 + 2^1): 2 6 10 14 18 ...

i = 3 --> A(n * 8): 0 8 16 24 32 ... A(n*8 + 2^2): 4 12 20 28 36 ...

所以第一个 if 是第一步，for 代表 log_2(n)-1 个步骤，所以总共有 log_2(n) 个步骤。解应该在 A(0).

Answer 1

您的解决方案是 O(n)，因为循环必须遍历所有数字（这意味着您根本不使用多个处理器）

CREW 意味着您不能写入同一个单元（在您的示例中单元=处理器内存），但您可以一次写入多个单元。

那么如何才能尽快完成呢？

初始化时所有处理器都以 1 或 0 开头（有无奇数）

在第一轮中，只需将邻居 x_2 与 x_1 相加，然后将 x_4 与 x_3 相加，等等。它将在 O(1) 中完成，因为每个第二个处理器 "p_x" 并行查看 "p_x+1" 处理器并添加 0 或 1（是否有奇数）

然后在处理器 p1、p3、p5、p7...中，您有部分解决方案。让我们再做一次，但现在 p1 查找 p3，p5 查找 p7，p_x 查找 o_x+2

那么您只有处理器 p1、p5、p9 等中的部分解决方案

重复该过程。每一步处理器数量减半，所以你需要 log_2(n) 步。

如果这是现实生活中的例子，通常会计算同步成本。基本上在每一步之后，所有处理器都必须同步自己，这样他们现在就可以执行第二步（因为你运行每个处理器中描述的代码，但是你怎么知道你是否已经可以从处理器添加数字 p_x，因为你可以在 p_x 完成工作后进行。

您需要某种 "clock" 或同步。

在此示例中，最终的复杂度为 log(n)*k，其中 k 是同步的复杂度。

成本取决于机器或定义。如何通知处理者您已完成的一种方法与此处描述的计算奇数的方法基本相同。那么它也将花费 k=log(n) 这将导致 log^2(n)

计算奇数的 PRAM CREW 算法

PRAM CREW algorithm for counting odd numbers

algorithm

parallel-processing

complexity-theory

big-o