[РЕШЕНО] OpenMP и деление дерева

[Igors]

Добрый день

Использую OpenMP и весьма доволен этой библиотекой. Не могу сообразить как мне распараллелить деление дерева, алгоритм стандартный:

- Есть очередь нодов, (вначале только с 1 нодом).
- Извлекаем первый нод из очереди, делим его на 2 нода
- Подсчитываем приоритеты получившихся нодов, и, если надо, добавляем их в очередь
- Опять извлекаем первый нод (нод с наивысшим приоритетом) из очереди и.т.д

Нод хранит список примитивов которые его пересекают. Приоритет вычисляется как число примитивов в ноде помноженное на его размер. Все работает. Теперь как задействовать N ниток? Понятно что помещение в очередь и извлечение из нее должны быть защищены блокировками. Возможна ситуация когда очередь пуста, но это не значит "конец расчета" - нод(ы) делятся в др. нитках. Как бы мне это все организовать попроще и покрасивее?

Спасибо

[BlackTass]

бери в качестве условия окончания не просто опустошение очереди, а опустошение очереди и законченную работу всех потоков

[Igors]

бери в качестве условия окончания не просто опустошение очереди, а опустошение очереди и законченную работу всех потоков

Не очень понятно, что такое "законченная работа всех потоков"    Ведь пока хоть один нод делится - ни одну нитку мне заканчивать не резон.

[Авварон]

дык семафор. Начинаем работу, +1. Стопаемся -1. Когда 0 выходим.

[Igors]

дык семафор. Начинаем работу, +1. Стопаемся -1. Когда 0 выходим.

Мне это тоже казалось простым    Вот псевдокод для одно-ниточной версии. Для простоты полагаем что все ф-ции thread-safe (потокобезопасны). Прошу показать как сделать +1 и -1.

Код:

void DivideTree( void )
{
  while (true) {

// взяли нод для деления
// нет больше нодов - все сделано (для МП варианта это неверно)
   Node * theNode = GetNodeFromTree();  
   if (!theNode) break;                            

 // делим нод
   Node * child0, * child1;
   DivideNode(theNode, &child0, &child1);

// если получившиеся новые ноды еще достаточно велики - добавим их в дерево
   if (IsNodeBig(child0)) AddNodeToTree(child0);  
   if (IsNodeBig(child1)) AddNodeToTree(child1);  
  }
}

[Авварон]

Код:

void DivideTree( void )
{
#pragma parallel блабла // каким-то образом параллелим цикл
  while (true) {
   sem++; //открыли семафор

// взяли нод для деления
   Node * theNode = GetNodeFromTree(); // тредобезопасный пул нодов
   if (!theNode) {
       sem--; //нить "закончилась"
       bool end = sem.wait_for_zero(timeout); // ждем завершения остальных нитей
       if (end) break; else continue; // анализируем код возврата - если выпали по таймауту, идем на след виток, если дождались 0, работа закончена
   }
                   
 // делим нод
   Node * child0, * child1;
   DivideNode(theNode, &child0, &child1);

// если получившиеся новые ноды еще достаточно велики - добавим их в дерево
   if (IsNodeBig(child0)) AddNodeToTree(child0);  
   if (IsNodeBig(child1)) AddNodeToTree(child1);  
  }
  sem--; // закрыли семафор
}

несколько криво что два -- у семафора, но в случае 2х точек выхода из цикла, так и должно быть
надеюсь я не ошибся

[Igors]

Полагаем что sem++, sem--, sem.wait_for_zero есть атомарные операции, защищенные мутексом или др. блокировкой.
Рассмотрим ситуацию для 2-х ниток

Код:

void DivideTree( void )
{
  while (true) {
                         <---- нитка 2 сейчас здесь
   sem++; 

   Node * theNode = GetNodeFromTree(); 
   if (!theNode) {
       sem--; 
       bool end = sem.wait_for_zero(timeout);  <---- нитка 1 сейчас здесь, end = true
...
}

Alas, poor Yorick 

[Авварон]

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

added: все равно фигня получается... видимо мьютексы, мьютексы и еще раз мьютексы:(

[Igors]

added: все равно фигня получается... видимо мьютексы, мьютексы и еще раз мьютексы:(

Не расстраивайтесь, это действительно трудно. Я сделал вариант, работает прилично, но все же иногда нитки крутятся вхолостую. Вот "принципиальная схема" (как это называлось в мое время)

Код:

void DivideTree( void )
{
  while (true) {

    LOCK_TREE;
    Node * theNode = GetNodeFromTree();  
    if (!theNode) {
      if (!theTaskActive) {
        UNLOCK_TREE;
        break;
      }
      else {
        UNLOCK_TREE;
        continue;
      }
    }                            
    ++theTaskActive;
    UNLOCK_TREE;

    Node * child0, * child1;
    DivideNode(theNode, &child0, &child1);

    LOCK_TREE;
    if (IsNodeBig(child0)) AddNodeToTree(child0);  
    if (IsNodeBig(child1)) AddNodeToTree(child1);  
    --theTaskActive;
    UNLOCK_TREE;
  }
}

[Авварон]

ну в данном варианте очень много while(1) крутится, пока мы ожидаем новых нодов. Я пытался этого избежать таймаутом.

[Igors]

ну в данном варианте очень много while(1) крутится, пока мы ожидаем новых нодов.

Согласен и я избегаю большинства таких прокруток (хотя и не всех): если после взятия нода очередь пуста - то делать UNLOCK_TREE не сразу а в конце цикла. Это заставляет остальные нитки ждать на первом LOCK_TREE т.к. все равно им нечего делать пока данная нитка не создаст новые ноды. К сожалению, текст получается очень навороченный и приводить его нет смысла.

[spectre71]

Более простой пример с семафором.
Нет никаких лишних блокировок и прокруток цикла!
Привожу пример на QSemaphore, легко переделать на нативный.

Код:

QSemaphore sem(1); //изначально имеем 1 ноду

void startThreads( void ) {
  for(i=0; i<MaxThreadCount; ++i) {
    // создаем и запускаем Потоки;
  }
}

void DivideTree( void ) {
  while (true) {  
    // счетчик у семафора соответствует кол-ву доступных Node в списке
    // если он 0, то будем отдыхать на семафоре
    sem.acquire();
    Node * theNode = GetNodeFromTree();  //потокобезопасна
    if (!theNode) {
     // не получили Node - их больше не будет, 
     // разблокируем остальные Threads они тоже не получат Node и выйдут
      sem.release();
      break;
    }

 // делим нод
    Node * child0, * child1;
    DivideNode(theNode, &child0, &child1);

// если получившиеся новые ноды еще достаточно велики - добавим их в дерево
    if (IsNodeBig(child0)) {
      AddNodeToTree(child0);  //потокобезопасна 
      // увеличиваем счетчик семафора, добавился нод в список
      sem.release();
    }
    if (IsNodeBig(child1)) {
      AddNodeToTree(child1);  //потокобезопасна
      // увеличиваем счетчик семафора, добавился нод в список
      sem.release();
    }  
  }
}

[spectre71]

Ошибся!
В итоге(когда список опустеет) все потоки встанут на семафор.
Надо еще подумать.

[Igors]

Более простой пример с семафором.
Нет никаких лишних блокировок и прокруток цикла!

Пример: имеем 1 нод. Поделили его, оба "осколка" оказались малы (IsNodeBig вернула false). Все нитки ждут на семафоре forever  

Edit: опоздал - отправил, и только потом увидел Ваш новый ответ 

[spectre71]

Вроде так правильно.
GetNodeCount - возвращает текущее кол-во нод в списке

GetNodeCount, GetNodeFromTree, AddNodeToTree. Защищать внутри не требуется!

Код:

QSemaphore sem(1); //изначально имеем 1 ноду
QMutex locker;
int ActiveThreadCount = 0;

void startThreads( void ) {
  for(i=0; i<MaxThreadCount; ++i) {
    locker.lock();
    ActiveThreadCount++;  
    locker.unlock();
    // создаем и запускаем Поток;
  }
}

void DivideTree( void ) {
  while (true) {  
    // счетчик у семафора соответствует кол-ву доступных Node в списке
    // если он 0, то будем отдыхать на семафоре
    
    locker.lock();
    --ActiveThreadCount; 
    if(!sem.tryAcquire()) {
      if(!ActiveThreadCount && !GetNodeCount()) {
        locker.unlock();
        sem.release();
        break;                 
      } else {
        locker.unlock();
        sem.acquire();
        locker.lock();
      }
    }
    
    ++ActiveThreadCount;
    Node * theNode = GetNodeFromTree(); 
    locker.unlock();

    if (!theNode) {
     // не получили Node - их больше не будет, 
     // разблокируем остальные Threads они тоже не получат Node и выйдут
      sem.release();
      break;
    }

 // делим нод
    Node * child0, * child1;
    DivideNode(theNode, &child0, &child1);

// если получившиеся новые ноды еще достаточно велики - добавим их в дерево
    if (IsNodeBig(child0)) {
      locker.lock();
      AddNodeToTree(child0); 
      locker.unlock();
      // увеличиваем счетчик семафора, добавился нод в список
      sem.release();
    }
    if (IsNodeBig(child1)) {
      locker.lock();
      AddNodeToTree(child1); 
      locker.unlock();
      // увеличиваем счетчик семафора, добавился нод в список
      sem.release();
    }  
    
  }
}