CREW PRAM奇数计数O(log n)算法设计及优化咨询

你一开始遇到的问题非常典型——CREW PRAM的写冲突限制确实会直接否决“共享变量累加”这种直观思路，而后来的单进程求和又会把复杂度拉回线性，所以我们需要用并行归约的思路来实现O(log n)的复杂度。

先复盘下你之前的方案问题 #

• 第一个方案里直接操作共享的oddCount：多个处理器同时执行oddCount +=1属于“读-改-写”操作，会触发多写冲突，违反CREW PRAM的规则（只允许并发读，不允许多处理器同时写同一单元）。
• 第二个“标记后单进程求和”方案：最后单个处理器遍历所有标记的复杂度是O(n)，直接让整体复杂度变成了线性，达不到O(log n)的要求。

最终的O(log n)复杂度CREW PRAM算法 #

下面是符合要求的实现，核心思路是先做0-1标记，再通过分治式的并行归约求和：

伪代码（处理器索引n从0开始，总处理器数N=2^k，k为自然数）

Input: A:={x₀,x₁,...,x_{N-1}}  // 调整索引与处理器一一对应
Output: A(0) = 奇数的总数
begin
    // 步骤1：并行转换为0-1标记数组
    if(A(n) mod 2 != 0) then A(n) = 1 else A(n) = 0
    
    // 步骤2：log₂N轮并行归约求和
    for i = 1 to log₂N do
        offset = 2^(i-1)
        block_size = 2^i
        // 每个处理器负责合并一对相邻子块的结果
        if (n * block_size + offset) < N then
            A(n * block_size) += A(n * block_size + offset)
end

步骤详解

1. 0-1标记阶段（O(1)并行步）：
   所有处理器同时读取自己负责的数组元素，判断奇偶后写入0或1到原位置——每个处理器只操作自己对应的存储单元，完全没有写冲突，符合CREW规则。
2. 并行归约求和阶段（O(log n)并行步）：
   这是算法的核心，每一轮都让处理器并行合并相邻的子结果：
   • 第1轮：每个处理器合并相邻的2个元素（比如处理器0合并A(0)和A(1)，处理器1合并A(2)和A(3)，以此类推）；
   • 第2轮：每个处理器合并相邻的2个“双元素块”（处理器0合并A(0)和A(2)，处理器1合并A(4)和A(6)）；
   • 每一轮的块大小翻倍，经过log₂N轮后，所有结果会被聚合到A(0)中。
     每一轮中，不同处理器的写入位置互不重叠，所以不会产生任何写冲突。

复杂度验证

整个算法的并行总步数是1（标记） + log₂N（归约）= O(log N)，完全满足题目要求的时间复杂度，且每一步都严格遵循CREW PRAM的读写规则。

内容的提问来源于stack exchange，提问作者Dubbox