C ++ OpenMP критично: односторонняя блокировка?

Рассмотрим следующую последовательную функцию. Когда я распараллеливаю свой код, каждый поток будет вызывать эту функцию из параллельной области (не показано). Я пытаюсь сделать это потокобезопасным и эффективным (быстрым).

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», значение должно быть вычислено и сохранено.

Так куда же мне положить #pragma omp critical?

Хотя это легко, очень неэффективно ставить #pragma omp critical вокруг всего этого, поскольку каждый поток будет делать это постоянно, и это часто будет только для чтения.

Есть ли способ реализовать «одностороннюю» critical или «одностороннюю» lock процедуру? То есть вышеупомянутые операции с использованием итератора должны быть «заблокированы» только при записи в my_map в операторе else. Но несколько потоков должны иметь возможность выполнять вызов .find одновременно.

Надеюсь, я понимаю. Спасибо.


c++ openmp parallel-processing critical-section
person cmo    schedule 09.05.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Согласно этой ссылке на 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;
}

Изменить: отредактировано для исправления ошибки в более ранней версии.

person Chris A.    schedule 09.05.2012
comment
Верно ли это, даже если .insert происходит в середине поиска? (т.е. пока этот поток находится внутри вызова .find). - person cmo; 09.05.2012
comment
Хотя операция вставки может вызываться несколько раз, фактическая запись может происходить один или несколько раз в зависимости от того, какой оператор вставки вы используете. Используя operator[], например myMap[i] = 3.14*i*i приведет к многократной записи. Однако myMap.insert(std::pair<int, float>(i, 3.14*i*i)) напишет только один раз. - person cmo; 10.05.2012

arrow_upward
1
arrow_downward

OpenMP - это компиляторный «инструмент» для автоматического распараллеливания цикла, а не библиотека потокового взаимодействия или синхронизации; поэтому у него нет сложных мьютексов, таких как мьютекс чтения / записи: блокировка устанавливается при записи, но не при чтении.

Вот пример реализации.

В любом случае ответ Криса А. лучше, чем мой :)

person CharlesB    schedule 09.05.2012

arrow_upward
1
arrow_downward

Хотя ответ @CrisA может решить вашу проблему, я оставлю свой ответ здесь на тот случай, если будущие поисковики сочтут его полезным.

Если хотите, можете присвоить разделам #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 и _ 6_.

atomic заставляет запись в ячейку памяти (lvalue в выражении, которому предшествует директива) всегда быть атомарной.

flush гарантирует, что любая память, которая должна быть доступна для всех потоков, фактически записывается во все потоки, а не хранится в кэше процессора и недоступна там, где должна быть.

person Sam DeHaan    schedule 09.05.2012
comment
Но ваше использование critical - это неэффективность, о которой я беспокоился - несколько потоков не могут одновременно читать карту из-за critical. - person cmo; 09.05.2012
comment
Однако atomic - хорошая идея. Так что мне нужно только разместить atomic и flush вокруг области записи? - а читаемый регион нужен директиве? - person cmo; 09.05.2012
comment
@CycoMatto Я знаю. Я подумал, что сделал что-то умное с atomic и flush, понял свою ошибку и отредактировал свой ответ. Он предоставляет информацию, которая может быть полезна кому-то еще, кто наткнется на вашу проблему, но определенно не обеспечивает желаемого поведения блокировки при записи. - person Sam DeHaan; 09.05.2012
comment
@CycoMatto atomic защищает только утверждение, а не блок, вот почему моя сообразительность потерпела неудачу. flush будет исправлен перед любой попыткой чтения (.find). - person Sam DeHaan; 09.05.2012