1

我有一个我想并行的 for 循环，但是线程必须共享 anunordered_map和 a vector。

因为 for 循环有点大，所以我将在这里发布它的简要概述，以便我可以清楚地说明我的主要问题。请阅读评论。

   unordered_map<string, vector<int>> sharedUM;

   /*
      here I call a function that updates the unordered_map with some
      initial data, however the unordered_map will need to be updated by
      the threads inside the for loop
   */

   vector<int> sharedVector;
  /* 
     the shared vector initially is empty, the threads will 
    fill it with integers, the order of these integers should be in ascending
    order, however I can simply sort the array after all the 
    threads finish executing so I guess we can assume that the order 
    does not matter
  */

   #pragma omp parallel for
   for(int i=0; i<N; i++){

      key = generate_a_key_value_according_to_an_algorithm();
      std::unordered_map<string, vector<int>::iterator it = sharedUM.find(key);

      /*
       according to the data inside it->second(the value), 
       the thread makes some conclusions which then
       uses in order to figure out whether 
       it should run a high complexity algorithm
       or not.
      */
       bool conclusion = make_conclusion();

       if(conclusion == true){

           results = run_expensive_algorithm();

          /*
             According to the results, 
             the thread updates some values of
             the key that it previously searched for inside the unordered_map
             this update may help other threads avoid running 
             the expensive algorithm
          */

       }

       sharedVector.push_back(i);

   }

最初我将代码保持原样，所以我只是#pragma在 for 循环中使用它，但是在更新sharedVector. 所以我决定使用简单的锁来强制线程在写入向量之前获取锁。所以在我的实现中，我有这样的事情：

      omp_lock_t sharedVectorLock;
      omp_init_lock(&sharedVectorLock);
      ...
      for(...)
      ...
       omp_set_lock(&sharedVectorLock);
       sharedVector.push_back(i);
       omp_unset_lock(&sharedVectorLock);
      ...
      omp_destroy_lock(&sharedVectorLock);

我已经多次运行我的应用程序，一切似乎都运行良好，直到我决定自动重新运行它太多次，直到我得到错误的结果。因为我对 OpenMP 世界和一般线程非常陌生，所以我不知道当编写器更新某些共享数据时我们应该锁定所有读取器这一事实。正如您在我的应用程序中看到的那样，线程总是从中读取一些数据unordered_map，以便得出一些结论并了解有关分配给它们的键的信息。如果两个线程必须使用同一个键，而其他线程试图读取这个键的值，而另一个线程已经达到更新这些值的地步，会发生什么？我相信这就是我的问题发生的地方。

但是，我现在的主要问题是我不确定避免此类事情发生的最佳方法是什么。就像我的系统在 99% 的时间里都在工作，但是这 1% 会破坏一切，因为两个线程很少分配有相同的键，这反过来又是因为我的 unordered_map 通常很大。

锁定 unordered_map 会做我的工作吗？最有可能，但这不会有效，因为A想要使用密钥x的线程必须等待B已经在使用密钥y的线程，而该线程可能与完成y不同x。

所以我的主要问题是，我应该如何解决这个问题？unordered_map当且仅当两个线程使用相同的密钥时，如何锁定？

先感谢您

4

3 回答 3

1

1关于使用锁和互斥锁。您必须在并行块之外（之前）声明和初始化锁变量#pragma omp parallel，然后在并行块内使用它们：（1）获取锁（如果另一个线程已锁定它，这可能会阻塞），（2）更改变量竞争条件，（3）释放锁。最后，在退出并行块后将其销毁。在并行块内声明的锁是线程本地的，因此无法提供同步。这可以解释你的问题。

2关于写入复杂的 C++ 容器。OpenMP 最初是为简单的 FORTRAN do 循环而设计的（类似于 C/C++ 的带有整数控制变量的循环）。一切更复杂的事情都会让你头疼。为了安全起见，对 C++ 容器的任何非常量操作都必须在锁（对同一容器上的任何此类操作使用相同的锁）或 omp 关键区域（对任何此类操作使用相同的名称）内执行同一个容器）。这包括pop()等等push()，除了简单的阅读。只有在这种非常量容器操作只花费一小部分时间的情况下，这才能保持高效。

3如果我是你，我不会为 openMP 烦恼（我用过，但现在后悔了）。使用 C++，您可以使用 TBB，它还带有一些线程安全但无锁的容器。它还允许您从递归执行的任务而非线程的角度进行思考（父任务产生子任务等），但 TBB 有一些简单的并行 for 循环实现，例如。

于 2013-04-06T22:34:54.913 回答
0

另一种方法是使用 TBB 的concurrent_unordered_map。

您不必使用 TBB 的其余并行性支持（尽管如果您从头开始使用 C++，它肯定比 OpenMP 更“c++-ish”）。

于 2013-04-08T08:53:33.453 回答
-1

这可能会有所帮助：

    vector<bool> sv(N);

代替

    sharedVector.push_back(i);

经过

    sv[i]=true;

这可以避免锁（非常耗时），并且可以轻松地对 sharedVector 进行排序，例如

    for(int i=0; i<N;i++){
        if(sv[i])sharedVector.push_back(i);
    }
于 2013-04-09T08:59:51.040 回答