Реализация параллельного поиска в ширину с использованием openmp - PullRequest
Новая
       16

Реализация параллельного поиска в ширину с использованием openmp

0 голосов
/ 06 ноября 2019

Я хочу реализовать параллельный обход в ширину, используя openmp.

Я читаю Распараллеливание поиска в ширину . Я просто пытаюсь напечатать обход в ширину. Но код в приведенной выше ссылке содержит почти весь код обхода в критической секции.

Если в критической секции не может быть двух потоков одновременно, то это займет столько же времени, сколько ипоследовательная программа (может занять еще больше времени). Как я могу использовать OpenMP для параллельного запуска алгоритма?

1 Ответ

1 голос
/ 06 ноября 2019

Ваша предпосылка вводит в заблуждение:

код [...] содержит почти весь код обхода в критической секции. 

std::queue<node*> q;
q.push(head);
while (!q.empty()) {
  qSize = q.size();
  #pragma omp parallel for
  for (int i = 0; i < qSize; i++) {
    node* currNode;
    #pragma omp critical
    {
      currNode = q.front();
      q.pop();
    }
    doStuff(currNode);
    #pragma omp critical
    q.push(currNode);
  }
}

Конечно,Сам по себе обход фактически находится в критической секции, как и должно быть, если вы используете не-потокобезопасную структуру данных. Тем не менее, предпосылка этого вопроса была:

Функция обработки doStuff() довольно дорогая

Пока это верно, проблема не в том, чтооставшийся код находится в критическом разделе. Например, вы можете использовать закон Амдала для вычисления теоретически достижимого ускорения.

Все это говорит о том, что если ваш doStuff очень дешев, ваше наблюдение, конечно, верно. Затем я бы рекомендовал использовать поиск, который не требует общей очереди, такой как поиск в глубину или итеративный поиск в глубину.

...