Букатов А.А., Дацюк В.Н., Жегуло А.И. Программирование многопроцессорных вычислительных систем
Подождите немного. Документ загружается.
191
Глава 15.
Использование библиотеки параллельных подпрограмм Aztec
15.1. Общая организация библиотеки Aztec
Множество задач, решаемых на многопроцессорных системах,
требуют решения больших систем линейных уравнений с разреженными
матрицами
A*Х = В, (15.1)
где A – задаваемая пользователем разреженная матрица n × n,
В – задаваемый пользователем вектор длины n,
Х – вектор длины n, который должен быть вычислен.
В исследовательской лаборатории параллельных вычислений
Сандии (США) разработан достаточно эффективный и удобный в
использовании пакет подпрограмм Aztec [18] для решения
итерационными методами системы уравнений (15.1). Пакет изначально
разрабатывался для того, чтобы облегчить перенос приложений с
однопроцессорных вычислительных систем на многопроцессорные.
Предоставляемые средства трансформации данных позволяют легко
создавать разреженные неструктурированные матрицы для решения как на
однопроцессорных, так и на многопроцессорных системах. В
суперкомпьютерном центре ЮГИНФО РГУ эта библиотека установлена на
всех высокопроизводительных вычислительных системах (nCUBE2, SUN
Ultra 60, Alpha DS20E, Linux-кластер), и программы, разработанные с
использованием этой библиотеки, без какой-либо модификации
выполняются на любой из этих систем.
Aztec включает в себя процедуры, реализующие ряд итерационных
методов Крылова:
•
•
•
•
•
метод сопряженных градиентов (CG),
обобщенный метод минимальных невязок (GMRES),
квадратичный метод сопряженных градиентов (CGS),
метод квазиминимальных невязок (TFQMR),
метод бисопряженного градиента (BiCGSTAB) со стабилизацией.
192
Все методы используются совместно с различными переобуслав-
ливателями (полиномиальный метод и метод декомпозиции областей,
использующий как прямой метод LU, так и неполное LU разложение в
подобластях). Хотя матрица A может быть общего вида, пакет
ориентирован на матрицы, возникающие при конечно-разностной
аппроксимации дифференциальных уравнений в частных производных
(Partial Differential Equations – PDE). Наконец, Aztec может
использовать одно из двух представлений разреженных матриц:
поэлементный формат модифицированной разреженной строки (MSR) или
блочный формат переменной блочной строки (VBR). Полный комплект
документации можно найти на сервере [19]. В данном пособии приводится
краткая инструкция по использованию пакета.
15.2. Конфигурационные параметры библиотеки Aztec
Для использования библиотеки Aztec в текст программы должен
быть включен include-файл, в котором определен набор необходимых
переменных:
С:
#include <az_aztec.h>
FORTRAN:
include ‘az_aztecf.h’
Пакет написан на языке C, поэтому все используемые при вызове
подпрограмм массивы должны быть описаны индексируемыми от 0 (в том
числе и на Фортране). Вызов различных подпрограмм решения систем
линейных алгебраических уравнений выполняется через драйверную
подпрограмму AZ_solve. Управление режимами работы решателя
осуществляется с помощью двух массивов:
•
•
массива целого типа options(0:AZ_OPTIONS_SIZE);
массива вещественного двойной точности
params(0:AZ_PARAMS_SIZE).
193
Возвращаемая информация помещается в массив двойной точности
status(0:AZ_STATUS_SIZE).
Приведем список наиболее важных опций. Значения констант,
используемых в качестве индексов элементов массивов options, params,
status и в качестве значений, присваиваемых этим элементам, определены
в include-файлах.
options[AZ_solver]
Специфицирует алгоритм решения.
Возможные значения задаются либо в виде
именованных констант, либо числовых значений,
которые приведены в скобках:
AZ_cg (0)
Метод сопряженных градиентов (применяется
только к симметричным, положительно
определенным матрицам).
AZ_gmres (1)
Обобщенный метод минимальных невязок.
AZ_cgs (2)
Квадратичный метод сопряженных градиентов.
AZ_tfqmr (3)
Метод квазиминимальных невязок.
AZ_bicgstab (4)
Метод бисопряженного градиента со
стабилизацией.
AZ_lu (5)
Прямой LU метод решения (только на одном
процессоре).
По умолчанию: AZ_gmres
options[AZ_scaling]
Определяет алгоритм масштабирования.
Масштабируется вся матрица (запись идет на место
старой). Кроме того, при необходимости
масштабируются правая часть, начальные данные и
полученное решение.
Возможные значения:
AZ_none
Без масштабирования.
AZ_Jacobi
Точечное масштабирование Якоби.
AZ_BJacobi
Блочное масштабирование Якоби, где размер
блоков соответствует VBR блокам. Точечное
масштабирование Якоби применяют, когда
используется MSR формат.
AZ_row_sum
Масштабирование каждой строки такое, что
сумма ее элементов равна 1.
AZ_sym_diag
Симметричное масштабирование такое, что
диагональные элементы равны 1.
AZ_sym_row_sum
Симметричное масштабирование
с использованием суммы элементов строки.
По умолчанию: AZ_none.
194
options[AZ_precond]
Специфицирует переобуславливатель.
Возможные значения:
AZ_none
Переобуславливания нет.
AZ_Jacobi
k шаговый метод Якоби. Число k шагов Якоби
задается через options[AZ_poly_ord].
AZ_Neumann
Ряд полиномов Неймана, где степень полинома
задается через options[AZ_poly_ord].
AZ_ls
Полином наименьших квадратов, где степень
полинома задается через options[AZ_poly_ord].
AZ_lu
Метод декомпозиции областей (аддитивная
процедура Шварца), использующий неполную LU
факторизацию с величиной допустимого
отклонения params[AZ_drop] на подматрице
каждого процессора. Обработка внешних
переменных в подматрице определяется с
помощью options[AZ_overlap].
AZ_ilu
Подобно AZ_lu, но используется ilu(0) вместо
LU.
AZ_bilu
Подобно AZ_lu, но используется bilu(0) вместо
LU, где каждый блок соответствует VBR блоку.
AZ_sym_GS
k-шаговый симметричный метод Гаусса-Зейделя
для неперекрывающейся декомпозиции области
(аддитивная процедура Шварца). Симметричная
процедура Гаусса-Зейделя декомпозиции области
используется тогда, когда каждый процессор
независимо выполняет один шаг симметричного
метода Гаусса-Зейделя на его локальной
подматрице, после чего с помощью
межпроцессорных коммуникаций обновляются
граничные значения, требуемые на следующем
локальном шаге метода Гаусса-Зейделя. Число
шагов k задается через options[AZ_poly_ord].
По умолчанию: AZ_none.
options[AZ_conv]
Определяет выражение невязки, используемое для
подтверждения сходимости. Итерационное решение
завершается, если соответствующее выражение
невязки меньше, чем params[AZ_tol].
Возможные значения:
AZ_r0
AZ_rhs
AZ_Anorm
195
AZ_sol
AZ_weighted
, где , n – общее число
неизвестных, w – вес вектора, задаваемый
пользователем через params[AZ_weights], и
–
начальная невязка.
По умолчанию: AZ_r0.
options[AZ_output]
Специфицирует информацию, которая должна быть
выведена на печать в процессе решения (выражения
невязки см. options[AZ_conv]).
Возможные значения:
AZ_all
Выводит на печать матрицу и индексирующие
векторы для каждого процессора. Печатает все
промежуточные значения невязок.
AZ_none
Промежуточные результаты не печатаются.
AZ_warnings
Печатаются только предупреждения Aztec'а.
AZ_last
Печатается только окончательное значение
невязки.
n (n >0) Печатается значение невязки на каждой n-ой
итерации.
По умолчанию: 1.
options[AZ_pre_calc]
Показывает, использовать ли информацию о
факторизации из предыдущего вызова AZ_solve.
Возможные значения:
AZ_calc
Не использовать информацию из предыдущих
вызовов AZ_solve.
AZ_recalc
Использовать информацию предварительной
обработки из предыдущего вызова, но повторно
вычислять переобуславливающие множители.
AZ_reuse
Использовать переобуславливатель из
предыдущего вызова AZ_solve. Кроме того,
можно использовать масштабирующие
множители из предыдущего обращения для
масштабирования правой части, начальных
данных и окончательного решения.
По умолчанию: AZ_calc.
options[AZ_max_iter]
Максимальное число итераций.
По умолчанию: 500.
196
options[AZ_poly_ord]
Степень полинома при использовании
полиномиального переобуславливателя. А также
число шагов при переобуславливании Якоби или
симметричном переобуславливании Гаусса-Зейделя.
По умолчанию: 3.
options[AZ_overlap]
Определяет подматрицы, факторизуемые
алгоритмами декомпозиции области AZ_lu, AZ_ilu,
AZ_bilu.
Возможные значения:
AZ_none
Факторизовать определенную на этом процессоре
локальную подматрицу, отбрасывая столбцы,
которые соответствуют внешним элементам.
AZ_diag
Факторизовать локальную подматрицу на этом
процессоре, расширенную диагональной (блочно-
диагональной для VBR формата) матрицей. Эта
диагональная матрица состоит из диагональных
элементов строк матрицы, связанных с внешними
элементами.
AZ_full
Факторизовать определенную на этом процессоре
локальную подматрицу, расширенную строками,
связанными с внешними переменными.
Результирующая процедура – аддитивная
процедура Шварца с совмещением.
По умолчанию: AZ_none.
options[AZ_kspace]
Размер подпространства Крылова для GMRES.
По умолчанию: 30.
options[AZ_orthog]
Схема ортогонализации GMRES.
Возможные значения:
AZ_classic
Классическая ортогонализация Грамм-Шмидта.
AZ_modified
Модифицированная ортогонализация Грамм-
Шмидта.
По умолчанию: AZ_classic.
Массив params двойной точности служит для передачи в процедуры
значений параметров вещественного типа. Элементы этого массива имеют
следующие значения:
params[AZ_tol]
Определяет критерий сходимости.
По умолчанию: 10
—6
197
params[AZ_drop]
Определяет величину допустимого отклонения
для LU переобуславливателей. По умолчанию: 0.0.
params[AZ_weights]
Когда options[AZ_conv] = AZ_weighted,
i-ая локальная компонента вектора веса хранится в
элементе params[AZ_weights+i].
Вся целочисленная информация, возвращаемая из AZ_solve,
переводится в вещественные значения двойной точности и помещается в
массив status. Содержание элементов status описано ниже.
status[AZ_its]
Число итераций, выполненных итерационным
методом.
status[AZ_why]
Причина завершения программы AZ_solve.
Возможные значения
AZ_normal
Критерий сходимости, который запросил
пользователь, удовлетворен.
AZ_param
Некорректно заданная опция.
AZ_breakdown Произошло численное прерывание.
AZ_loss
Произошла потеря точности.
AZ_ill_cond
Метод Хейссенберга в GMRES некорректен. Это
может быть вызвано сингулярностью матрицы. В
этом случае GMRES пробует найти решение
наименьшими квадратами.
AZ_maxits
Сходимость не достигнута после выполнения
максимального число итераций, заданного
соответствующим параметром
status[AZ_r]
Истинная норма невязки, соответствующая выбору
options[AZ_conv] (для вычисления нормы
используется полученное решение).
status[AZ_scaled_r]
Истинное выражение отношения невязки как
определено в options[AZ_conv].
status[AZ_rec_r]
Норма соответствующая options[AZ_conv] конечной
невязки или оценочной конечной невязки
(рекурсивно вычисленной итерационным методом).
15.3. Основные подпрограммы библиотеки Aztec
В состав библиотеки Aztec входит около 50 подпрограмм (функций
в языке С), однако большая их часть имеет вспомогательный характер и не
требуется прямое обращение к ним. Стандартное использование
198
библиотеки требует обращения к 5-6 подпрограммам. Рассмотрим их в
соответствии с очередностью вызовов этих подпрограмм в программах,
основанных на библиотеке Aztec.
Функция идентификации процессоров AZ_processor_info
Эта функция является аналогом функции whoami в PSE и функций
MPI_Comm_rank, MPI_Comm_size в MPI.
call AZ_processor_info(proc_config)
Информация возвращается в массив
integer proc_config(0:AZ_PROC_SIZE)
При этом номер текущего процессора IAM и количество процессоров
NPROCS заносятся в соответствующие элементы этого массива:
IAM = proc_config(AZ_node)
– номер вызывающего
процессора;
NPROCS = proc_config (AZ_N_procs)
– общее число процессоров,
доступных программе.
Функция рассылки информации по процессорам AZ_broadcast
Это аналог функции MPI_Bcast, ее реализация выполнена в стиле
PVM: рассылаемая информация сначала упаковывается в системный
буфер, а затем посылается одной командой. Рассылать может только 0-й
процессор. Вызов функции имеет следующий вид:
call AZ_broadcast(n, 4, proc_config, AZ_PACK) –
упаковываем в
буфер целую
переменную n
call AZ_broadcast(d, 8, proc_config, AZ_PACK) –
упаковываем в
буфер
переменную d
типа real*8
call AZ_broadcast(NULL, 0, proc_config, AZ_SEND) –
посылаем буфер
Функция определения параметров декомпозиции матрицы
AZ_read_update
Эта функция определяет, сколько строк глобальной матрицы должно
находиться в данном процессоре и номера этих строк. Вызов функции
имеет следующий вид:
199
call AZ_read_update(N_update, update, proc_config, nz, 1, 0)
N_update
– целая переменная, возвращает количество строк на
процессоре;
update
– массив целого типа размерности не меньше, чем
N_update+1, после вызова содержит номера строк в
глобальной нумерации;
nz
– размерность глобальной матрицы (входной параметр).
Два последних параметра вызова процедуры – константы.
После вызова всех рассмотренных выше функций в каждом
процессоре должна быть сформирована размещенная в нем часть
разреженной матрицы, представленная в виде двух массивов:
•
•
массива двойной точности val, в котором хранятся ненулевые
матричные элементы,
целого массива bindx, в котором хранятся номера столбцов
ненулевых матричных элементов (в случае хранения в формате
MSR).
Этот этап целиком и полностью возлагается на программиста и
требует от него некоторой изобретательности. Для VBR формата требуется
сохранять больше информации (в данном пособии мы его рассматривать
не будем). Кроме того, должны быть сформированы векторы правых
частей b и начальное приближение решения x (только расположенные в
данном процессоре части).
Функция преобразования глобальной индексации в локальную
AZ_transform
call AZ_transform(proc_config, external, bindx, val, update,
$ update_index, extern_index, data_org, N_update,
$ NULL, NULL, NULL, NULL, AZ_MSR_MATRIX)
Входные параметры этой процедуры proc_config, bindx, val,
update, N_update рассмотрены выше. Выходные параметры – целые
массивы external, update_index, extern_index, data_org размерности
не меньше, чем N_update + 1 –будут передаваться процедуре решения
200
системы уравнений AZ_solve. Параметры, имеющие значения NULL, в
случае MSR формата не используются.
Перед обращением к процедуре решения системы вектор правых
частей и начальное приближение должны быть переопределены в
соответствии с новой индексацией.
do i = 0, N_update-1
xn(update_index(i)) = x(i)
bn(update_index(i)) = b(i)
end do
Функция инициализации предопределенных параметров решателя
AZ_defaults
call AZ_defaults(options, params)
В данной процедуре оба параметра выходные и были подробно
рассмотрены выше. Установки по умолчанию могут быть переопределены:
options(AZ_solver) = AZ_cgs –
выбор метода решения CGS
options(AZ_precond) =
AZ_dom_decomp
–
выбор переобуславливателя
options(AZ_subdomain_solve) = AZ_ilu –
неполное LU разложение
options(AZ_output) = AZ_none –
диагностику не выдавать
options(AZ_max_iter) = 1000 –
максимальное число
итераций 1000
params(AZ_tol) = 1.d-8 –
критерий сходимости 10
-8
Функция решения системы линейных алгебраических уравнений
AZ_solve
Эта функция является основной "рабочей лошадкой" пакета. Ее
вызов имеет следующий вид:
call AZ_solve(xn, bn, options, params, NULL, bindx, NULL,
$ NULL, NULL, val, data_org, status, proc_config)
Параметры NULL не используются в случае MSR формата хранения
матрицы. Выходными параметрами являются xn – распределенное по
процессорам решение системы, и рассмотренный выше массив status.