18,20. Распараллеливание рекуррентных соотношений. Распараллеливание рекурсий первого порядка. Метод каскадных сумм.

Р

* В этом методе набор из n процессорных элементов (ПЭ) загружается данными, которые должны суммироваться. Существует возможность сдвига данных таким образом, что значение i-го ПЭ помещается в i+1-й, а 1-й ПЭ заполняется нулевым значением. Данные, выдвигаемые из n-го ПЭ, теряются. Метод каскадных сумм реализуется, как показано на рис.3. Здесь реализован случай n=8. Содержимое ПЭ сдвигается на одну позицию вправо и суммируется с несдвинутой копией. Если этот процесс повторять log2n раз, на каждом ярусе увеличивая сдвиг в два раза, то в результате в несдвинутой копии ПЭ сформируется требуемая последовательность Xi. Если требуется получить только полную сумму (Х8), то достаточно выполнить операции, обведенные кружком. (из лаб. практикума)

екурсия - это последовательность вычислений, при котором значения очередного вычисляемого терма зависит от одного или нескольких ранее вычисленных термов. Под термом понимается результаты вычислений на очередном шаге. Если это значение зависит только от предыдущего терма – то рекурсия 1-го порядка. Исп. при решении систем уравнений, преобразовании матриц и других задач.

Общая линейная рекурсия первого порядка.

X_j = a_jX_j-1+d_j, где j = 1,2,…,n

Частный случай:

X_j = d_k, где j = 1,2,…,n

Рассмотрим традиционную схему вычислений.

ПРИМЕР: n = 8.

0	X1	X2	X3	X4	X5	X6	X7	X8
	d1	d2	d3	d4	d5	d6	d7	d8
	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6	Шаг 7	Шаг 8

В этом алгоритме:

n-1 операция сложения со степенью параллелизма единица, n-1 операция сдвига со степенью параллелизма 1.

Шаги:

1. Сначала n аккумуляторов загружаются исходными данными di.

2. Затем на первом уровне производится сдвиг содержимого аккумуляторов на одну позицию вправо и сложение содержимого каждого аккумулятора со сдвинутыми значениями.

3. На втором уровне содержимое аккумуляторов сдвигается на две позиции, на третьем - на четыре и так далее.

В результате на уровне L* = log₂n каждый аккумулятор содержит соответствующую частичную сумму.

В полученном алгоритме log₂n “+” операций сложения со степенью параллелизма n и n-1 операция сдвига (маршрутизации) со степенью параллелизма n. Таким образом, по сравнению с обычной схемой общее кол-во операций сложения увеличивается, общее количество операций сложения выполнены за три шага. Если смещение по индексу выводит соответствующее значение из заданного диапазона, то это значение заполняется нулями. Если этот метод применить для получения конечной суммы элементов, не вычисляя всех частных сумм, то общее число сложений получается таким же, как и при последовательном вычислении, а количество шагов равно трем. (Если этот метод выполняется методом конечных сумм, то выполняются операции, обведенные в кружочки и число операций равно 7. Метод каскадных сумм хорошо работает, если n – степень 2.)

Этот алгоритм может быть реализован фрагментом программы на языке Fortran:

X=D

DO 1 L=1, LOG2(N)

X=X+SHIFTR(X, 2**(L-1))

1 CONTINUE

где, X и D – векторы из n элементов, «+» - параллельное сложение, SHIFTR – векторная функция, которая помещает копию вектора X со смещением на указное количество позиций (2**(L-1), т.е. 2 в степени (L-1)) вправо, в вектор SHIFTR.

Если вернуться к общей линейной рекурсии первого порядка, то при последовательном вычислении требуется 2n арифметических операций со степенью параллелизма «1» и n сдвигов со степенью параллелизма 1.

Предложенный метод называется методом «каскадных сумм», а соответствующий метод распараллеливания общий рекурсии первого порядка называется «циклической редукцией». На языке Fortran циклическая редукция может быть реализована следующим кодом:

X=D

DO 1 L, LOG 2(N)

X=A*SHIFTR (X, 2**(L-1)) + X

A=A*SHIFTR (A, 2**(L-1))

1

где X, D и A – векторы.

Предложенный метод каскадных сумм может быть использован для вычисления нелинейных рекурсий первого порядка. Например, n!=(n-1)!*n – вот рекурсия первого порядка.

Для циклической редукции существуют прикидки времени выполнения при больших n: нужно выполнить ≈3log₂n со степенью параллелизма n² и 2 операциями сдвига со степенью параллелизма n.