对一个数组并行求和

Question

我有以下算法来求和数组中的元素:

// global
index = 0
array = [...]
total_sum = 0 // this is what we're interested in
// per thread
thread_sum = 0
mutex.lock()
while (index < array.size) {
  mutex.unlock()
  thread_sum += array[index]
  mutex.lock()
  index++
}
total_sum += thread_sum
mutex.unlock()

每个线程都运行相同的代码，并且它们在完成后立即与主线程连接。问题是，有时不止一个线程添加相同的数字。这是怎么发生的?

原始代码是c++，使用std::vector/thread/mutex/ref.

Answer 1

在释放锁之前增加index，否则多个线程可能会看到相同的值:

// per thread
thread_sum = 0
mutex.lock()
while (index < array.size) {
  i = index++
  mutex.unlock()
  thread_sum += array[i]
  mutex.lock()
}
total_sum += thread_sum
mutex.unlock()

然后，如果使用原子整数，可以更有效地自动更改整数的值。

最后，当单个工作负载很小或非常可预测时，考虑批处理，以减少同步的开销。