如何让不同的线程一起填充数组？

Question

假设我有一些要并行运行的任务（Monte Carlo模拟）。我想完成给定数量的任务，但是任务要花费不同的时间，因此要在线程上平均分配工作并不容易。另外：最后，我需要在单个向量（或数组）中所有模拟的结果。

所以我想出了以下方法：

 int Max{1000000};
 //SimResult is some struct with well-defined default value.
 std::vector<SimResult> vec(/*length*/Max);//Initialize with default values of SimResult
 int LastAdded{0};
 void fill(int RandSeed)
 { 
      Simulator sim{RandSeed};
      while(LastAdded < Max)
      {
           // Do some work to bring foo to the desired state
           //The duration of this work is subject to randomness
           vec[LastAdded++] 
                 = sim.GetResult();//Produces SimResult. 
      }
 }
 main()
 { 
       //launch a bunch of std::async that start
       auto fut1 = std::async(fill,1);
       auto fut2 = std::async(fill,2);
       //maybe some more tasks.


      fut1.get();
      fut2.get();
      //do something with the results in vec. 
 }

上面的代码将给出我想知道的竞争条件。我正在寻找一种高效的方法来避免这种情况。要求：避免比赛条件（填满整个数组，不跳过）；最终结果立即排列;表演者。

阅读各种方法，似乎原子是一个不错的选择，但是我不确定哪种设置对我来说是最有效的？而且甚至不确定原子是否会削减它。也许需要一个互斥锁来保护LastAdded？

Answer 1

因为您已经知道要使用多少个元素并且从不更改向量的大小，所以最简单的解决方案是让每个线程都在向量的自身部分上工作。例如

void fill(int RandSeed, size_t partitionStart, size_t partitionEnd)
{ 
      Simulator sim{RandSeed};
      for(size_t i = partitionStart; i < partitionEnd; i++)
      {
           // Do some work to bring foo to the desired state
           // The duration of this work is subject to randomness
           vec[i] = sim.GetResult();//Produces SimResult. 
      }
 }

main()
{ 
    //launch a bunch of std::async that start
    auto fut1 = std::async(fill,1, 0, Max / 2);
    auto fut2 = std::async(fill,2, Max / 2, Max);

    // ...
}

Answer 2

我想说的一件事是，您需要对标准库随机数函数非常小心。如果您的“ Simulator”类创建了一个生成器的实例，则不应使用同一对象并行运行Monte Carlo模拟，因为在运行之间您可能会得到重复的随机数模式，这将给您带来不准确的结果。

此领域的最佳做法是创建N个具有相同属性的Simulator对象，并为每个对象提供不同的随机种子。然后，您可以使用OpenMP将这些对象集中到多个线程中，OpenMP是用于科学软件开发的常见并行编程模型。

std::vector<SimResult> generateResults(size_t N_runs, double seed) 
{
    std::vector<SimResult> results(N_runs);
    #pragma omp parallel for
    for(auto i = 0; i < N_runs; i++)
    {
        auto sim = Simulator(seed + i);
        results[i] = sim.GetResult();
    }
}

编辑：使用OpenMP，您可以选择不同的调度模型，例如在线程之间动态拆分工作。您可以执行以下操作：

#pragma omp parallel for schedule(dynamic, 16)

这将使每个线程一次包含16个项目的块。