Вычислительные методы алгебры и оценивания. Семушин И.В. - 61 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

3.4 Параллельное LU-разложение
модифицировать алгоритм, чтобы устранить задержку, вызванную записью
в память (3.7). Идея состоит в том, чтобы выполнять необходимую обра-
ботку для j-го столбца полностью, прежде чем переходить к (j + 1)-му
столбцу. При этом обработка каждого из остальных столбцов матрицы A
откладывается до тех пор, пока не наступит время придать этому ст о лбцу
окончате льный вид. Псе в докод данного алгоритма приведен на рис. 3.6.
Для j = 2 до n
Для s = j до n
l
s,j−1
= a
s,j−1
/a
j−1,j−1
Для k = 1 до j − 1
Для i = k + 1 до n
a
ij
= a
ij
− l
ik
a
kj
Рис. 3.6. Столбцово ориентированная схема
¯
LU-разложения с отложенными моди-
фикациями (jki-алгоритм, см. с. 64) [8]
Опишем несколько первых операций j-го шага вычислений, показ ывая
таким образом характер обменов с памятью:
Загрузить первый столбец матрицы L .
Загрузить j-й столбец матрицы A.
(
Модифицировать j-й столбец матрицы A;
загрузить второй столбец мат рицы L.
(
Модифицировать j-й столбец матрицы A;
загрузить третий столбец мат рицы L.
. . . . . . . . . . . . . . . . . .
(3.9)
Заметим, что в а лгоритме (3.9) не производится за писей в память, пока
вся рабо та с j-м сто лбцом матрицы A не з а в ершена. Столбцы матрицы L
все время должны загружа ть ся в регистры, но эти загрузки идут на фоне
вычислений. Только в начале и в конце каждого шага происходят задержки
для загрузок и(или) записей. Вполне вероятно, что транслятор не сумеет
распознать возможности оставить текущий j-й столбец в регис тре; в этом
случае результат, требуемый от алгоритма на рис. 3. 6 , либо достигается с
переходом к программированию на языке ассемблера, либо аппроксимиру-
ется путем развертывания циклов. Еще одна потенциальная проблема при
реализации данного алгоритма заключается в том, что длины векторов при
61

Страницы