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

UptoLike

ВУЗ: 

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

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

Рубрика: 

3.4 Параллельное LU-разложение
y
i
= 0
Для i = 1 до m
Для j = 1 до n
y
i
= y
i
+ a
ij
x
j
y
i
= 0
Для j = 1 до n
Для i = 1 до m
y
i
= y
i
+ a
ij
x
j
Рис. 3.4. ij (слева) и ji (справа) формы матрично-векторного умножения [8]
Как выше (в подразд. 3.1) говорилось, такая опе рация типа «вектор плюс
произведение вектора на число», называется триадой (или операцией saxpy);
некото рые векторные компьютеры выполняют ее особенно эффективно.
Сравнение приведенных способов умножения матрицы на вектор пока-
зывает, что на одних векторных компьютерах предпочтителен один способ,
на других — другой; многое определяется также и способом хранения дан-
ных в памяти. Предположим, что матрица A хранится по столбцам; такое
соглашение в отношении двумерных массивов принято в Фортране. (В дру-
гих языках, например в Паскале, двумерные массивы хранятся по строкам.)
Тогда векторы, требуемые для алгоритма (3.5), располагаются в последо-
вательно адресуемых ячейках памяти, в то время как для алгоритма (3. 5 )
строки будут представля т ь ве кторы с шагом m. Однако в векторных ком-
пьютерах часто существует ограничение на доступ к векторам: в качестве
операндов для векторных команд допускаются только векторы с шагом 1
(т. е. такие, которые располагаются в последовательно адресуемых ячейках
памяти). Поэтому, если матрица A хранится по столбцам, т о эти сообра-
жения, связанные с памят ь ю, усиливают аргументацию в пользу алгоритма
(3.5). Если же матрица A хранится по строкам, то предпочтительней может
оказаться алгоритм (3.4). Только детальный анализ может показать, какой
выбор следует сделать для конкретной машины.
3.4 Параллельное LU-разложение
Для распараллеленных вычислений нужны соответ ствующие параллель-
ные или векторые компьютеры. С сере дины 70-х годов 20-го столетия фирма
CRAY Research, Inc. производит векторные компьютеры, которые могут слу-
жить примером процесс о ров типа «регистр–регистр». Под эт им подразуме-
вается, что существуют в екторные команды, для которых операндами явля-
ются векторы. Эти команды получают свои операнды из очень быстрой па-
мяти, именуемой векторными регистрами, и запоминают результаты опять-
59

Страницы