Вступление
В предыдущем посте я обсуждал инфраструктуру fork / join, представленную в Java SE 7, и ее использование для простого параллелизма некоторых типов задач; то есть те, которые работают в одной JVM и включают в себя большую часть работы, которую можно разбить на более мелкие части с помощью стратегии «разделяй и властвуй». Чтобы проиллюстрировать это, я представил пример использования fork / join для симуляции Монте-Карло чистой приведенной стоимости инвестиций с неопределенной прибылью и ставкой дисконтирования. В этом посте я приведу пошаговое описание примера приложения. Это пошаговое руководство обеспечит основу для некоторых изменений реализации, которые мы обсудим в следующем посте. Полный код для примера приложения доступен на GitHub под лицензией Apache 2.0.
Обзор приложения
Некоторые из классов приложения связаны со спецификой расчета чистой приведенной стоимости и генерации случайных значений для моделирования по методу Монте-Карло:
NetPresentValueКласс полезности, который с учетом известного набора годовых прибылей или затрат и ставки дисконтирования возвращает чистую приведенную стоимость по известной формуле.Distribution: Интерфейс Java, представляющий статистическое распределение; Реализаторы предоставляют метод для возврата значений выборки, которые соответствуют распределению.SingleValueDistribution: «Распределение», которое на самом деле не случайно, но каждый раз возвращает одно и то же значение.TriangleDistribution: Распространенное распределение, которое подходит для случаев, когда полная «форма» случайной величины неизвестна, но можно оценить минимальное, максимальное и «наиболее вероятное» значение.StatsCollector: Класс для сбора статистики из прогонов симуляции по мере их выполнения. В терминах параллельного программирования это выполняет роль редуктора (например, в MapReduce или в Cilk Plus ).MonteCarloNpv: Основной класс, который устанавливает пример инвестиционной и печатной статистики.
Оставшийся класс NpvTask— это класс, который связывает инфраструктуру форка / соединения Java с вычислениями Монте-Карло и Чистой приведенной стоимости. NpvTask Класс расширяет RecursiveTask, общий, абстрактный класс , который требует своих детей для реализации compute(). compute() Метод не принимает никаких параметров и возвращает любой типа был использован для параметрирования родового (в данном случае StatsCollector).
Расширяя RecursiveTask, NpvTask делает себя доступным для отправки в ForkJoinPool, как это делается в основном методе. Сама задача должна быть облегченной и избегать других форм синхронизации потоков (поскольку задач может быть намного больше, чем потоков в пуле, было бы очень неразумно захватывать блокировку внутри задачи). Взамен, задача имеет возможность форкнуть другие задачи, которые затем будут запланированы для асинхронного запуска в пуле.
Ключевая часть NpvTask выглядит следующим образом:
protected StatsCollector compute() {
StatsCollector collector = new StatsCollector(min, max, numBuckets);
if (numIterations < minChunkSize) {
for (int i = 0; i < numIterations; i++) {
collector.addObs(NetPresentValue.npv(sampleFlows(),
rate.sample()));
}
} else {
List<NpvTask> subTasks = new ArrayList<>(numChunks);
for (int i = 0; i < numChunks; i++) {
NpvTask subTask = new NpvTask(min, max, numBuckets,
numIterations / numChunks, rate, flows);
subTasks.add(subTask);
}
invokeAll(subTasks);
for (NpvTask subTask : subTasks) {
collector.combine(subTask.join());
}
}
return collector;
}
Каждый вызов задачи объявляет свой собственный экземпляр StatsCollector. Это позволяет задачам работать параллельно, не синхронизируя доступ к одному экземпляру. Статистика собирается при повторном объединении задач.
Затем метод сравнивает количество итераций, которые он должен выполнить, с минимальным размером порции. Поскольку с созданием новой задачи связаны затраты, существует размер, ниже которого разделение работы становится неэффективным. Сделав этот настраиваемый параметр, можно протестировать различные значения для повышения производительности. «Лучший» размер будет зависеть от выполняемых вычислений и доступного оборудования для обработки.
Если оставшийся размер достаточно велик, и его имеет смысл разделить, метод создает несколько экземпляров NpvTask и передает часть оставшейся работы. Задачи хранятся в списке, так что их статистика может быть объединена. Затем вызываются задачи, а потом родитель ожидает завершения всех задач и собирает результаты.
Это одна из возможных реализаций «разделяй и властвуй». Это нечто среднее между разделением работы на две части и выполнением истинной «параллельной работы», когда работа будет сразу разделена на достаточное количество частей, и дальнейшее разделение не потребуется. В следующем посте я покажу несколько альтернативных способов разделения работы и производительности.
Производительность
Существует много различных вариантов разделения работы, которые влияют на производительность. Однако мы можем сравнить простой случай, когда все прогоны выполняются последовательно, с множеством случаев с разными параметрами:
StopWatch 'Monte Carlo NPV': running time (millis) = 4902 ----------------------------------------- ms % Task name ----------------------------------------- 00861 018% Sequential 00282 006% Parallel (children=2, min fork size=100) 00234 005% Parallel (children=2, min fork size=500) 00200 004% Parallel (children=2, min fork size=1000) 00186 004% Parallel (children=2, min fork size=2000) 00181 004% Parallel (children=3, min fork size=100) 00182 004% Parallel (children=3, min fork size=500) 00188 004% Parallel (children=3, min fork size=1000) 00192 004% Parallel (children=3, min fork size=2000) 00197 004% Parallel (children=4, min fork size=100) 00203 004% Parallel (children=4, min fork size=500) 00211 004% Parallel (children=4, min fork size=1000) 00182 004% Parallel (children=4, min fork size=2000) 00194 004% Parallel (children=5, min fork size=100) 00203 004% Parallel (children=5, min fork size=500) 00189 004% Parallel (children=5, min fork size=1000) 00207 004% Parallel (children=5, min fork size=2000) 00194 004% Parallel (children=6, min fork size=100) 00208 004% Parallel (children=6, min fork size=500) 00206 004% Parallel (children=6, min fork size=1000) 00202 004% Parallel (children=6, min fork size=2000)
Существуют некоторые незначительные различия в производительности с различными настраиваемыми параметрами, хотя они могут не быть статистически значимыми и, безусловно, зависят от машины. Все параллельные случаи имеют существенное преимущество перед последовательным (около 4х).
Эта распечатка получена из превосходного StopWatch класса, который является частью библиотеки утилит Spring Framework. StopWatch хорош в регулярных тестах, таких как этот, где задача занимает достаточно много времени, поэтому разрешение системных часов не имеет значения. Микробенчмарки, использующие библиотеку Caliper , см. В моем посте о производительности коллекции Java .
Заметки
Один из наиболее раздражающих аспектов «разделяй и властвуй» заключается в том, что нам обычно нужно разделить работу на целые куски (не имеет смысла выполнять половину цикла моделирования), но работа не всегда аккуратно делится на количество заданий. В этом примере это нормально, так как мы можем выполнить несколько прогонов больше или меньше, не сильно влияя на статистику, которую мы создаем. Но реальный пример, вероятно, должен был бы решить эту проблему, разделив работу на несколько неравные куски.
Другая ключевая проблема с разделяй и властвуй — это способ, которым мы рекомбинируем собранные данные. В этом примере мы собираем базовую статистику, и наш combine() метод StatsCollector прост. Это работает, потому что операции, которые мы выполняем, являются ассоциативными и коммутативными; если мы собираем статистику в три отдельных сегмента, то не имеет значения, в каком порядке мы их объединяем. Если бы операции были ассоциативными, но не коммутативными, мы должны были бы быть более осторожными, как мы объединяли данные и где мы генерировали новые (пустые) StatsCollector экземпляров.