разница разделяй и властвуй, виляй и присоединяйся

В C++, в чем разница между divide и conquer & fork и join? Это вилка и вступить в конкретном случае "разделяй и властвуй", потому что ветвления и соединения применяется только в параллельности? Спасибо!

2 3
c++ language-agnostic parallel-processing fork-join

2 ответа:

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

  Result solve(Problem problem) 
  {
        if (problem is small)
            directly solve problem
        else 
             {
            split problem into independent parts
            fork new subtasks to solve each part
            join all subtasks
            compose result from subresults
          }
  }

C++14 имеет некоторые проблемы, связанные с fork & join , вы можете прочитать больше на этом сайте ( http://www.meetingcpp.com/index.php/br/items/a-look-at-c14-papers-part-2.html )

1

"Разделяй и властвуй" -это общий метод программирования для разбиения более крупной задачи на более разрешимые подзадачи, решения их по отдельности (а иногда и рекурсивно), наконец, получения ответа на большую задачу путем объединения ответов на подзадачи. Это идея, не специфичная для C++.

"Fork" и "Join" называют конкретные примитивы параллелизма, доступные во многих языках. "Вилка" вызывает другой поток выполнения должен быть запущен; "присоединиться" заставляет текущий поток ожидать для завершения и синхронизации другого потока. Я считаю, что стандарт C++14 имеет такие встроенные примитивы. Многие другие языки не имеют этого встроенного модуля, но он часто доступен через библиотеки (включая более ранние версии C++).

Можно использовать " Fork "и" Join "для реализации" Divide and conquer", усиленного параллелизмом. Используемый таким образом," fork "отправляет потоки на отдельные подзадачи, а" join " необходим как шаг, чтобы сигнализировать о завершении подзадач. Но "присоединиться" не получается в частности, вычислить комбинированный ответ на "большую" проблему. Вам, вероятно, потребуется больше кода, чем просто вилка и соединение.

2