Как работает недавно представленный Arrays.parallelPrefix (...) в Java 8?

Question

Я сталкивался с Arrays.parallelPrefix , представленным в Java 8.

Этот перегруженный метод выполняет операции с каждым элементом входного массива в совокупности.Например, из документов:

Параллельно накапливает каждый элемент заданного массива, используя предоставленную функцию.Например, если массив изначально содержит [2, 1, 0, 3] и операция выполняет сложение, то по возвращении массив содержит [2, 3, 3, 6].Вычисление параллельного префикса обычно более эффективно, чем последовательные циклы для больших массивов.

Итак, как Java выполняет эту задачу в parallel, когда операция над членом зависит от результата операции в предыдущемтермин, и так далее?

Я пытался пройтись по коду сам, и они действительно используют ForkJoinTasks, но это не так просто, как объединить результат, чтобы получить окончательный массив.

Answer 1

Как объяснено в Ответ Эрана , эта операция использует свойство ассоциативности функции.

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

Например, для следующего массива с использованием суммы в качестве операции префикса и четырех процессоров

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  

мы получаем

  4 → 13 → 18 → 19    0 →  5 →  6 → 12    6 → 10 → 16 → 21    1 →  7 → 16 → 19  
                 ↓                   ↓                   ↓                   ↓  
                19                  12                  21                  19  

Теперь мы используем ассоциативность, чтобы сначала применить операцию префикса к смещениям

                 ↓                   ↓                   ↓                   ↓  
                19         →        31         →        52         →        71  

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

                     19   19   19   19   31   31   31   31   52   52   52   52  
                      ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

Когда мы используем один и тот же пример для восьми потоков,

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  

  4 → 13    5 →  6    0 →  5    1 →  7    6 → 10    6 → 11    1 →  7    9 → 12  
       ↓         ↓         ↓         ↓         ↓         ↓         ↓         ↓  
      13         6         5         7        10        11         7        12  

       ↓         ↓         ↓         ↓         ↓         ↓         ↓         ↓  
      13    →   19    →   24    →   31    →   41    →   52    →   59    →   71  

           13   13   19   19   24   24   31   31   41   41   52   52   59   59  
            ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

мы видим, что будет явное преимущество, даже если мы будем использовать более простую стратегию сохранения рабочих блоков одинаковыми для обоих этапов, другими словами, принять один свободный рабочий поток во второй фазе,Нам понадобится около ⅛n для первой фазы и ⅛n для второй, для операции потребуется totaln total (где n - стоимость оценки последовательного префикса всего массива).Конечно, только приблизительно и в лучшем случае.

Напротив, когда у нас есть только два процессора

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  


  4 → 13 → 18 → 19 → 19 → 24 → 25 → 31    6 → 10 → 16 → 21 → 22 → 28 → 37 → 40  
                                     ↓                                       ↓  
                                    31                                      40  

                                     ↓                                       ↓  
                                    31                   →                  71  

                                         31   31   31   31   31   31   31   31  
                                          ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

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

Когда мы разделяем работу второй фазы между обоими процессорами, первой фазе требуется около ½n, а второй потребуется¼n, получая totaln total, что по-прежнему является преимуществом, если массив достаточно большой.

В качестве дополнительного примечания вы можете заметить, что смещения, рассчитанные при подготовке второго этапа, идентичны результату дляпоследний элемент куска.Таким образом, вы можете уменьшить необходимое количество операций на одну на блок, просто назначив это значение.Но типичный сценарий состоит в том, чтобы иметь только несколько блоков (масштабируемых с количеством процессоров) с большим количеством элементов, поэтому сохранение одной операции на блок не имеет значения.

Answer 2

Я прочитал оба ответа и все еще не мог полностью понять, как это делается, поэтому решил вместо этого привести пример.Вот то, что я придумал, предположим, что это массив, с которого мы начинаем (с 3 процессорами):

7, 9, 6, 1, 8, 7, 3, 4, 9

Таким образом, каждый из 3 потоков получит свой кусок для работы:

Thread 1:  7, 9, 6
Thread 2:  1, 8, 7
Thread 3:  3, 4, 9

Поскольку документация обязывает ассоциативную функцию , мы можем вычислить сумму в первом потоке и некоторые частичные суммы в тех, а когда известна первая - все они будут.Давайте посмотрим, что станет 7, 9, 6:

7, 9, 6  -> 7, 16, 22

Таким образом, сумма в первом потоке равна 22 - но другие потоки об этом пока не знают, поэтому вместо этого они работают какx например.Таким образом, поток 2 будет:

1, 8, 7 -> 1 (+x), 9 (+x), 16(+x) 

Таким образом, сумма из второго потока будет x + 16, поэтому в Thread 3 мы будем иметь:

3, 4, 9 -> 3 (+ x + 16), 7 (+ x + 16), 16 (+ x + 16)

3, 4, 9 -> x + 19, x + 23, x + 32

Таким образом, как только я знаю x, я знаю и все остальные результаты.

Отказ от ответственности: я не уверен, что именно так это реализовано (и я попытался посмотреть на код - но это слишком сложно).

Answer 3

Суть в том, что оператор является

без побочных эффектов, ассоциативной функцией

Это означает, что

(a op b) op c == a op (b op c)

Следовательно, если вы разбите массив на две половины и примените метод parallelPrefix к каждой половине рекурсивно, вы сможете позже объединить частичные результаты, применив операцию к каждому элементу второй половины массива с помощьюпоследний элемент первой половины.

Рассмотрим [2, 1, 0, 3] с примером сложения.Если вы разделите массив на две половины и выполните операцию для каждой половины, вы получите:

[2, 3]    and    [0, 3]

Затем, чтобы объединить их, вы добавляете 3 (последний элемент первой половины) к каждомуэлемент второй половины, и получить:

[2, 3, 3, 6]

РЕДАКТИРОВАТЬ: Этот ответ предлагает один способ параллельного вычисления префиксов массива.Это не обязательно самый эффективный способ и не обязательно способ, используемый реализацией JDK.Далее вы можете прочитать о параллельных алгоритмах решения этой проблемы здесь .