Parallelize Depth First Search C++

Question

Я писал программу для HiQ, и я использовал этот цикл Depth First Search. Однако я хотел сделать это параллельно с MPI, но что я могу сделать, чтобы сделать параллельный поиск по глубине?

bool FindSolution(ConfigType PuzzleConfig) // Depth-First Search for sol to puzzle 
{ 

if (PuzzleConfig == SolutionConfig) return true;  

bool SolutionFound = false; 

Mark(PuzzleConfig); 

// For all configurations adjacent to current Puzzle Configuration (uses brute-force) 
for (short from=1; !SolutionFound && from<=NUMHOLES; from++) 
{ 
    for (short to=1; !SolutionFound && to<=NUMHOLES; to++) 
    { 
     JumpType jump = {from,to}; 
     if (ValidJump(jump, PuzzleConfig)) 
     { 
      ConfigType NewConfig = FindNewConfig(jump, PuzzleConfig); 
      if (!Marked(NewConfig)) 
      { 
       SolutionFound = FindSolution(NewConfig); // Recursive call for Depth-First Search 
       if (SolutionFound) 
        JumpStack.push(jump); 
      } 
     } 
    } 
} 

return SolutionFound; 
} 

Answer 1

MPI полезен, когда вы можете определить конкретную топологию параллельных вычислительных элементов заранее, и может разделить работу через вычислительные элементы во многом заранее исполнения. Затем каждый элемент «знает», где находятся другие элементы, и примерно то, что они делают, и, следовательно, может решить, для чего он должен отправлять сообщения, чтобы отправить сообщение MPI. Аналогично, принимающие элементы должны «знать», что они получают сообщение, чтобы получить MPI.

Глубокий первый поиск, возможно, подобен дереву, поэтому вы знаете абстрактную топологию ... но вы не знаете фактической формы дерева, и, следовательно, никакой процессор не знает, с каким узлом он связан заранее. Поэтому очень сложно выяснить, какие процессоры должны отправлять, и какие должны получить. Я не думаю, что MPI - ваш друг.

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

Для того, Таким образом, самые глубокие узлы сначала разворачиваются процессорами, придавая глубину первому аромату.

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

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