OpenMP-распараллеливание

Question

Я пишу программу на C++ с научными целями. Программа работает хорошо, и она возвращает хорошие результаты,, поэтому я решил улучшить ее производительность с помощью OpenMP. Цикл, который я хочу оптимизировать, следующий:

 //== #pragma omp parallel for private(i,j) 
     for (k=0; k < number; k++) 
     { 

     for (i=0; i < L; i++) 
     {  
       for (j=0; j < L; j++) 
       {  
         red[i][j] = UNDEFINED; 
       } 
     } 


     Point inicial = {L/2, L/2, OCCUPIED}; 
     red[L/2][L/2] = OCCUPIED; 
     addToList(inicial, red, list, L,f); 
     oc.push_back(inicial); 

     while (list.size() > 0 && L > 0) 
     {  
       punto = selectPoint(red, list, generator, prob, p); 

       if (punto.state == OCCUPIED) 
       {  
         addToList(punto, red, list, L,f); 

         oc.push_back(punto); 
       }  
       else 
       { 
         out.push_back(punto); 
       } 


     } 

     L = auxL; 

     oc.clear(); 
     out.clear(); 
     list.clear(); 

     } 

f = f*1.0/(number*1.0); 

     if (f > 0.5) 
     { 
       inta = inta; 
       intb = p; 
       p = (inta + intb)/2.0; 
     } 
     else if (f < 0.5) 
     { 
       intb = intb; 
       inta = p; 
       p = (inta + intb)/2.0; 
     } 

     cout << p << endl; 


     } 

Моя попытка с OpenMP прокомментирована выше. Как вы можете видеть Я объявил i и j как приватные, потому что они объявлены перед параллельным разделом. Я также пытался сделать L приватным, без результатов. Только ошибки сегментации и плохие указатели повсюду. Я думаю, проблема в том, что while петля вложена внутри. Мои вопросы: Правильно ли в этом случае omp parallel for? или я должен попытаться оптимизировать только этот цикл while? Являются ли std::vector мешающими OpenMP?

Примечание: list, oc и out являются std::vector<Point> и Point является простой структурой, состоящей из трех ИНТ свойств. addToList - функция, в которой нет петель.

Answer 1

Возможно, вы захотите ознакомиться с учебником OpenMP. Когда вы смотрите на OpenMP-код, вам нужно представить, что может произойти параллельно. Take

oc.push_back(inicial); 

Может ли две нити попытаться сделать это одновременно? Да. Поддерживает ли std::vector параллелизм? №

Этот код полон этих вещей.

---

Если вы хотите использовать структуры данных в вашей OpenMP оды, вам нужно to use locks. Из моего личного опыта, когда это происходит, гораздо лучше реорганизовать алгоритм, чем фактически использовать их. Хотя блокировки OpenMP + возможны, это, как правило, указывает на то, что есть проблема с идеей (= возможно субъективное представление).

Answer 2

В текущем ответе указывается на параллелизм в коде, но учтите, что не все структуры данных должны быть реализованы с помощью замков для обеспечения безопасности потоков. Существуют также структуры данных lock-free. В этом конкретном случае мы могли бы заблокировать свободный список Harris: https://timharris.uk/papers/2001-disc.pdf

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