3

考虑以下串行函数。当我并行化我的代码时,每个线程都会从并行区域内调用这个函数(未显示)。我正在尝试使这个线程安全高效(快速)。

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”的存储值(无论它是什么)。每隔一段时间,当调用“新 A”时,必须计算和存储一个值。

那么我应该把它放在#pragma omp critical哪里?

虽然很容易,但是将所有这些都放在一个非常低效#pragma omp critical的地方,因为每个线程都会不断地这样做,而且它通常是只读的情况。

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

我希望我说得通。谢谢你。

4

3 回答 3

2

根据Stack Overflow 上的这个链接,插入 anstd::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;
}

编辑:编辑以纠正早期版本中的错误。

于 2012-05-09T18:56:10.597 回答
1

OpenMP 是用于自动循环并行化的编译器“工具”,而不是线程通信或同步库;所以它没有复杂的互斥锁,比如读/写互斥锁:在写入时获取锁,但在读取时获取锁。

这是一个实现示例

无论如何,克里斯 A. 的回答比我的要好 :)

于 2012-05-09T19:01:40.637 回答
1

虽然@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 atomicand#pragma omp flush指令也可能有用。

atomic导致对内存位置(指令前面的表达式中的左值)的写入始终是原子的。

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

于 2012-05-09T18:55:34.100 回答