Как сделать этот алгоритм параллельно с OpenMP?

Question

Еще раз я застрял при использовании openMP в C ++. На этот раз я пытаюсь реализовать параллельную Ханойскую башню.

sub Hanoi(n,D,A,I)
    if n =1 
    then 
        Move the disk D to A
    else              
        Hanoi(n-1,D,I,A)
        Move the disk D to A
        Hanoi(n-1,I,A,D)
    end
end-sub

как сделать этот алгоритм параллельным, используя инструкции OpenMp?

Answer 1

Я не думаю, что этот алгоритм может быть OpenMPed, и у меня есть сомнения, что есть много параллелизма в любых башнях алгоритма решения Ханоя. Хотя это решение является рекурсивным, в отличие от (скажем) быстрой сортировки, оно не поддается декомпозиции на основе задач; нет двух веток, которые вы можете сделать независимо. И я сомневаюсь, что написание алгоритма по-другому будет иметь большое значение; в любой момент вы хотите переместить один диск из одной стопки в другую (скажем, от 1 до 2). Вы не можете перемещать диски в куче 2, пока это происходит, и вы не можете перемещать диски внизу в куче 1, пока не будет перемещен верхний диск. В результате остается играть только с одним верхним диском в системе, с кучей 3, и перемещать его из стопки 3 в стопку 3 нельзя, поэтому я не вижу здесь никакого возможного параллелизма.

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

Answer 2

Используйте OpenMP tasks, которые были добавлены в спецификацию в версии 3.0.Если вы столкнулись с проблемами снова, опубликуйте свой код.