Поиск на основе графического процессора всех возможных путей между двумя узлами на графике

Question

Моя работа широко использует алгоритм Migliore, Martorana и Sciortino для нахождения всех возможных простых путей, то есть тех, в которых ни один узел не встречается более одного раза, в графе, как описано в: Алгоритм для поискаВсе пути между двумя узлами в графике .(Хотя этот алгоритм по сути является поиском в глубину и интуитивно рекурсивен по своей природе, авторы также представляют нерекурсивную, основанную на стеке реализацию.) Я хотел бы знать, может ли такой алгоритм быть реализован на графическом процессоре.В данный момент я изо всех сил пытаюсь увидеть реальный параллелизм в этой проблеме.Например, затраты на мониторинг и диспетчеризацию потоков могут сделать поиск по кооперативному графу (по аппаратным потокам) непозволительным.Альтернативно, стратегия «разделяй и властвуй» может работать, если график разбит на части и назначен отдельным аппаратным потокам для поиска.Однако необходимо выяснить, как (1) разбить граф (2) сформулировать подзадачи и (3) объединить результаты поиска по разделам.

Answer 1

Немного ржавый на этом.Как насчет Дейкстры?

Boolean[] visited;              // [node] = true;
Boolean[][] connected;          // [node][i] = node
Vector<Vector<Integer>>[] path; // this should suck
Integer startNode;
Integer endNode;
Queue queue0; //for thread 0
Queue queue1; //for thread 1

while (queue0.hasNext()) {
   Integer node = queue.getNext();
   if visited[node] { 
      continue;
   } else {
      visited[node] = true;
   }

   for (nextNode: connected[node]) {
      for (i) {
         path[nextNode].append(path[node][i].clone().append(node));
      }
      if (nextNode%2 == 0) { queue0.add(nextNode); }
      if (nextNode%2 == 1) { queue1.add(nextNode); }
   }
}

path [endNode] [i] // i-й путь к endNode из startNode

разбиение: получено из узла% 2
подзадачи: найти место для переходаиз узла
объединение: у вас есть общая память, верно?

Answer 2

Я не думаю, что ваша проблема может быть легко перенесена на GPU, чтобы она работала быстрее. Программы с графическим процессором, которые используют большую часть графического процессора:

• Состоят из тысяч нитей, но их количество постоянно. Нет порождения новых тем или уничтожения предыдущих.
• Предпочитают доступ к объединенной памяти. Если соседние потоки обращаются к совершенно разным областям памяти (и обычно это делают графические алгоритмы), это будет медленно.
• Не нравится стеки с рекурсией и . Новейшие карты NVIDIA Fermi поддерживают вызовы функций, и потоки могут иметь стек, но из-за большого количества потоков стеки очень короткие (или занимают много памяти).

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