Ответ 1
Как объяснено в ответе Erans, эта операция использует свойство ассоциативности функции.
Тогда есть два фундаментальных шага. Первая - это фактическая операция с префиксом (в смысле требования к предыдущему элементу (элементам) для оценки), применяемая параллельно к частям массива. Результатом каждой частичной операции (идентичной результирующему последнему элементу) является смещение для оставшегося массива.
Например, для следующего массива с использованием суммы в качестве операции префикса и четырех процессоров
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 для второй, для операции потребуется всего ¼n (где 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, что дает общее количество, что по-прежнему является преимуществом, если массив достаточно большой.
В качестве дополнительного примечания вы можете заметить, что смещения, рассчитанные при подготовке второго этапа, идентичны результату для последнего элемента фрагмента. Таким образом, вы можете уменьшить необходимое количество операций на одну на блок, просто назначив это значение. Но типичный сценарий состоит в том, чтобы иметь только несколько блоков (масштабируемых с количеством процессоров) с большим количеством элементов, поэтому сохранение одной операции на блок не имеет значения.