multithreading - 计算平方和的最并行算法？

Question

假设我需要计算一个大数组 A[n] 的平方和，其中 n 可能是数百万，并且我有 N 个线程要使用。任何人都可以指出一个很好的并行算法来做到这一点吗？谢谢!

Answer 1

这是一个算法:-

1. divide numbers in n/N blocks 
2. Compute for one block squares in parallel in O(1)
3. addition can be done in O(log(N)) for 1 block using adding pair at time

时间复杂度:- O(log(N)*(n/N))

注意:这个时间复杂度完全是理论上的，实际上您需要在并行操作结束后等待线程同步，这会增加延迟。

编辑:-

以下伪代码可能会解释线程的O(logN) 并行算法:-

void add(i,N) {

  int k = 1;

  while(i+k<N && i%k==0 && (i/k)%2==0) {

      arr[i] = arr[i]+arr[i+k];
      synchronize();
      k = 2*k;
   }


}

注意:-这是线程号 i 处理 N 大小块的 ith<​​ 索引的代码，请注意循环是 O(logN) 随着 k 每次迭代增加 2 倍，synchronize() 函数用于等待其他线程完成他们的迭代(如果它们不同步)。尝试解决这个例子你会明白，加法的最终答案将在 arr[0]