Эта статья продолжает серию, в которой обсуждаются новые функции разветвления / объединения, добавленные в Java SE 7. В частях 1 и 2 представлен пример приложения, которое выполняет моделирование методом Монте-Карло чистой приведенной стоимости инвестиций с неопределенной прибылью и ставкой дисконтирования. Пример приложения доступен на GitHub .
В предыдущем посте был скрыт важный вопрос: каков «правильный» способ разделить работу? Конечно, ответ зависит от типа выполняемой работы и машины, на которой она выполняется. Но есть несколько альтернатив, которые мы можем рассмотреть.
Во-первых, напомним, что мы начинаем с большого объема работы (в этом случае многие прогоны симуляции являются независимыми). Ниже определенного размера мы выполняем «базовый случай», где мы запускаем как обычную последовательную программу. Размер «базового случая» сам по себе является настраиваемым параметром.
Выше этого минимального размера мы работаем, разделяя работу, создавая задачи для выполнения каждой части работы и собирая результаты, когда задачи завершены. Каждая подзадача может сама порождать задачи для дальнейшего разделения работы до достижения базового размера. Поэтому имеет смысл поговорить о том, сколько будет уровней, что называется «глубиной» реализации.
Глубина указывается с использованием нотации «Большой О», поскольку нас больше всего интересует, как глубина будет расти по мере изменения размера проблемы. Конечно, подход, который мы выбрали для разделения работы, повлияет на эту глубину. В общем, чем меньше глубина, тем выше теоретическое значение, которое мы можем получить, добавив больше процессоров, поскольку теоретическое максимальное ускорение — это общая выполненная работа, деленная на глубину. (Это интуитивно понятно; если бы у нас была общая работа, O(n) и мы могли бы выполнять все эти шаги параллельно, так что при такой глубине O(1)мы могли бы теоретически выполнить весь расчет за один шаг, если бы у нас были nпроцессоры.)
На самом деле получить линейное ускорение обычно невозможно, но типичные подходы достаточно хороши для большинства проблемных размеров и машин.
Первый подход делит работу на постоянный фактор. Частным случаем этого является разделение работы на количество доступных процессоров.
Другой подход заключается в выборе количества детей в зависимости от размера ввода. Этот расчет выполняется на каждом уровне рекурсии. Общий выбор заключается в использовании sqrt(n) в качестве числа детей, так как это уменьшает рост
Третий подход немедленно разделяет работу на достаточное количество частей, поэтому дальнейшее разделение не требуется. В таких языках, как Cilk Plus , есть параллельное for выражение для указания этого. Конечно, количество задач, которые могут фактически выполняться параллельно, намного меньше, поэтому в реализации это похоже на разделение работы на основе количества процессоров.
Пример приложения предоставляет средства для проверки вышеуказанных подходов. Вот пример выходных данных при запуске на четырехъядерном i7 с использованием 10 миллионов итераций.
StopWatch 'Monte Carlo NPV': running time (millis) = 40192 ----------------------------------------- ms % Task name ----------------------------------------- 10149 025% Sequential 02413 006% DivideByTwo (children=2, min fork size=100) 02350 006% DivideByTwo (children=2, min fork size=500) 02418 006% DivideByTwo (children=2, min fork size=1000) 02448 006% DivideByTwo (children=2, min fork size=2000) 02271 006% DivideByP (children=8, min fork size=100) 02260 006% DivideByP (children=8, min fork size=500) 02263 006% DivideByP (children=8, min fork size=1000) 02281 006% DivideByP (children=8, min fork size=2000) 02271 006% Sqrt(n) (children=-1, min fork size=100) 02270 006% Sqrt(n) (children=-1, min fork size=500) 02271 006% Sqrt(n) (children=-1, min fork size=1000) 02268 006% Sqrt(n) (children=-1, min fork size=2000) 02259 006% Parfor (children=20000, min fork size=500)
Различия в основном не значительны; другой прогон показывает разные результаты, причем меняется не только число, но и порядок от самого быстрого до самого медленного:
StopWatch 'Monte Carlo NPV': running time (millis) = 44836 ----------------------------------------- ms % Task name ----------------------------------------- 10162 023% Sequential 02841 006% DivideByTwo (children=2, min fork size=100) 02712 006% DivideByTwo (children=2, min fork size=500) 02734 006% DivideByTwo (children=2, min fork size=1000) 02839 006% DivideByTwo (children=2, min fork size=2000) 02621 006% DivideByP (children=8, min fork size=100) 02586 006% DivideByP (children=8, min fork size=500) 02617 006% DivideByP (children=8, min fork size=1000) 02620 006% DivideByP (children=8, min fork size=2000) 02612 006% Sqrt(n) (children=-1, min fork size=100) 02619 006% Sqrt(n) (children=-1, min fork size=500) 02620 006% Sqrt(n) (children=-1, min fork size=1000) 02639 006% Sqrt(n) (children=-1, min fork size=2000) 02614 006% Parfor (children=20000, min fork size=500)
Результаты позволяют нам сделать некоторые разумные выводы об использовании Java fork / join:
- Параллельная лучше, чем последовательная. Все наши параллельные методы работали значительно лучше. Обратите внимание, что на четырехъядерном процессоре скорость была близка к 4х.
- Простое лучше, чем сложное. По крайней мере, для такого рода примера не так много реальной ценности, которую можно извлечь из более сложных расчетов того, как следует разделять работу. В литературе по высокопроизводительным вычислениям есть много хорошей работы, будь то разделение задач, представление разреженных матриц или использование пользовательских параллельных алгоритмов. Большая часть этой работы относится к действительно большим задачам или действительно большим кластерам. Если вы не работаете с триллионами строк или временами выполнения, измеренными в днях, читаемость, вероятно, важнее.
- Производительность не всегда интуитивно понятна. Реализация «Parfor» создает 20 000 задач, что кажется много. Но реализация «DivideByTwo» с размером «базовый случай», равным 100, создает 262 142 задания и выполняется примерно за то же время.
- Javadoc говорят правду, когда говорят, что задачи fork / join гораздо легче, чем обычные потоки. Сомнительно, чтобы приложение Java, которое породило 262 142 потока, было бы пригодным (или все еще живым) на обычном оборудовании.
- Одиночные ошибки — это проклятие параллельного программирования, и вы в них попадете. В моей первоначальной реализации
NpvTaskбыла ошибка, которая порождала детей, если число запрашиваемых итераций было равно размеру «базового случая». Это означает, что каждое из 20 000 заданий в моем «Парфоре» порождает 20 000 детей, на выполнение которых уходит 15 секунд. Я заметил это, когда яStatsCollectorтакже отслеживал, сколько всего экземпляров было создано и достигло 4 миллиардов.
Надеюсь, это было полезное введение в fork / join в Java. Ключевым моментом является то, что для вычислений, включающих большой объем работы, который можно подразделить, fork / join может обеспечить параллельное ускорение с помощью компактного кода.