C++ OpenMP关键字：critical：“单向”锁定？

Question

考虑以下串行函数。当我并行化我的代码时，每个线程将从并行区域内调用此函数（未显示）。我试图使这个函数既线程安全又高效（快速）。

float get_stored_value__or__calculate_if_does_not_yet_exist( int A )
{    
    static std::map<int, float> my_map;

    std::map::iterator it_find = my_map.find(A);  //many threads do this often.

    bool found_A =   it_find != my_map.end();

    if (found_A)
    {
        return it_find->second;
    } 
    else
    {
      float result_for_A = calculate_value(A);  //should only be done once, really.
      my_map[A] = result_for_A;
      return result_for_A;
    }    
}

几乎每次调用此函数时，线程都会成功“查找”其“A”（不管它是什么）的存储值。偶尔，在调用“new A”时，将需要计算并存储一个值。

那么我应该在哪里放置#pragma omp critical？

虽然容易，但在这一切周围放置#pragma omp critical非常低效，因为每个线程将经常执行这个操作，并且通常是只读情况。

有没有办法实现“单向”critical或“单向”锁定例程？也就是说，涉及迭代器的上述操作仅在“else”语句中写入my_map时才“锁定”。但是多个线程应该能够同时执行.find调用。

希望我表达清楚。谢谢。

- cmo

Answer 1

根据Stack Overflow上的这篇文章，插入std::map不会使迭代器失效。对于end()迭代器也是同样的情况。这里有一篇相关链接。 不幸的是，如果您不使用临界区，就可能发生多次插入。此外，由于您的calculate_value程序可能计算量很大，因此必须锁定以避免该else子句在相同的A值下被重复执行并插入两次。

以下是一个示例函数，您可以在其中复制此错误的多次插入：

void testFunc(std::map<int,float> &theMap, int i)
{
    std::map<int,float>::iterator ite = theMap.find(i);

    if(ite == theMap.end())
    {
         theMap[i] = 3.14 * i * i;
     }
}

然后这样调用：

std::map<int,float> myMap;

int i;
#pragma omp parallel for
for(i=1;i<=100000;++i)
{
    testFunc(myMap,i % 100);
}

if(myMap.size() != 100)
{
    std::cout << "Problem!" << std::endl;
}

编辑：已编辑以更正之前版本中的错误。

- Chris A.

---

即使在“mid-find”时发生.insert，这也是真的吗？（即，在此线程处于.find调用内部时）。 - cmo

虽然插入操作可能会被调用多次，但实际的写入次数取决于您使用的插入运算符。例如，使用operator[]，如myMap[i] = 3.14*i*i将导致多次写入。然而，myMap.insert(std::pair<int, float>(i, 3.14*i*i))实际上只会写入一次。 - cmo

Answer 2

OpenMP是一个编译器的“工具”，用于自动循环并行化，而不是线程通信或同步库；因此它没有像读/写互斥锁那样复杂的互斥锁：在写入时获取锁，但在读取时不获取锁。

这里有一个实现示例。

无论如何，Chris A.的答案比我的好 :)

- CharlesB

Answer 3

虽然@ChrisA的答案可能解决了你的问题，但我会在这里留下我的答案，以防未来的搜索者发现它有用。

如果您愿意，您可以给#pragma omp critical部分一个name。然后，具有该名称的任何部分都被视为相同的关键部分。如果这是您想要做的事情，您可以轻松地使您方法的仅有一小部分成为关键部分。

#pragma omp critical map_protect
{
    std::map::iterator it_find = my_map.find(A);  //many threads do this often.

    bool found_A =   it_find != my_map.end();
}

...

#pragma omp critical map_protect
{
    float result_for_A = calculate_value(A);  //should only be done once, really.
    my_map[A] = result_for_A;
}

#pragma omp atomic和#pragma omp flush指令也可能很有用。

atomic会使得对内存位置（由该指令前的表达式中的左值表示）的写入操作始终是原子性的。

flush确保任何预期对所有线程可用的内存都实际上被写入到了所有线程中，而不是存储在处理器缓存中并且在应该可用的地方不可用。

- Sam DeHaan

---

但是你使用 critical 是我担心的低效率 - 由于 critical，多个线程无法同时读取地图。 - cmo

“atomic”虽然是个好主意。那么我只需要在写入区域周围放置“atomic”和“flush”吗？而读取区域需要指令吗？ - cmo

@CycoMatto 我知道。我以为我在使用atomic和flush时做了一些聪明的事情，后来意识到我的错误并编辑了我的回答。它提供了可能对其他遇到类似问题的人有用的信息，但肯定不会提供你想要的写入时锁定的行为。 - Sam DeHaan

@CycoMatto atomic 只保护语句，而不是块，这就是为什么我的聪明才智失败的原因。在任何尝试读取（.find）之前，应该放置 flush。 - Sam DeHaan