1631124674-6a00ac47f208bd132d328527d69fe75d (848586), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Будем рассматривать уравнение типа Au=f

Хотим решать систему с помощью распараллеливания, поэтому матрицу А разбиваем на блоки {A_k_l} - блочные строки и блочные столбцы (например, квадратные блоки будут). Выбираем предобуславливающую матрицу B_AS (as = аддитивный метод шварца) = блочно-диагональная матрица (каждый блок A_kk соответствует задаче в k подобласти). Рассмотрим итерационный процесс:

Где u^n – заданное приближение на n итерации, надо вычислить n+1 итерацию, записали процесс в обеих канонических формах, где T – матрица перехода, g – вектор свободных членов

В итоге записали блочный метод Якоби (если подобласти очень измельчить, чтобы блоки в матрице были размерности 1, то получим поточечный метод Якоби (вроде был рассмотрен ранее). С другой стороны, записанный процесс - аддитивный метод декомпозиции областей: преобразуем уравнение и получим , где В - блочно-диагональная матрица = аддитивный метод декомпозиции. Матрица В - блочно-диагональная, поэтому чтобы её обратить, надо одновременно и синхронно обратить каждый диагональный блок, то есть решить вспомогательные задачи в подобластях.

Предположим, что итерационный процесс сходится, тогда с помощью предельного перехода уберём номера итераций и перепишем систему в обычном виде

Теперь можем перейти от решения задачи без черточек к задаче с чёрточками, эта система уже предобусловлена (при этом В входит неявно). Можно применить итерационный метод крыловского типа (снова ссылка на 33-34 вопрос скорее всего). Для начала надо найти невязку, u^0 – произвольный начальный вектор

Теперь можно применить, например, методы сопряжённых невязок или градиентов. Все формулы стандартные как в методе Якоби. При этом чтобы посчитать умножение на Т, надо обратить В, а для этого решить подсистемы в подобластях

Как реализовать задачи в подобластях: запишем метод якоби для одной блочной строки. U с крышкой – промежуточный итерационный процесс.

Обобщим уравнение с помощью добавления блочной матрицы С:

Так как u^n сходятся, то при предельном переходе слагаемые с матрицей С уйдут, решение не изменится. A_qq+C_qq – объявим предобуславливающей. Матрицу С можно подобрать таким образом, чтобы ускорить итерационный процесс. Это вроде называется методом возмущения диагональных матриц.

39.Грубосеточная коррекция в МДО (Меркулов)

http://www.mathnet.ru/links/6972608a2547e7e3cf56ee76b65d9034/vyurv116.pdf

(сама идея метода)

Решив систему (не большого размера ) получаем вектор затем -- решение на исходной (частой сетке).

40.Взвешенные МДО (не будет)

41.Классификация уровней параллелизма и примеры к ним (Меркулов)

В 47 вопросе написаны другие уровни параллелизма, но в лекциях у него такие:

1. Физический уровень – ядра процессора.

2. Виртуальный физический уровень – технология, позволяющая операционной системе воспринимать одно физическое ядро как два логических.

3. Системный уровень – операционная система автоматически распределяет задачи по доступным ядрам, заставляя их обрабатывать информацию параллельно.

4. Программный – программы, исполняемые в рамках системы, используют ее механизм распределения задач.

Первые два уровня определяются производителями вычислительной машины, 3ий авторами операционной системы, 4ый непосредственно программистом, пишущим программы для системы.

42.DAG Технология построения параллельных алгоритмов (Семибратов)

Дед скипнул слайд, так как его должен был рассказывать Гололобов на семинарах.

DAG (Directed Acyclic Graph) - направленный граф без циклов.

Каждый поток (набор команд) - узел, а ребра представляют зависимости между потоками. Необходимо строить граф в зависимости от решаемой задачи. Хорошо подходит для описания асинхронных задач.

Плюсы:

• Хорошая скалируемость на старте алгоритма

• Динамическое распределение задач

• Возможность изменения размеров блоков в зависимости от положения в графе

Минусы:

• Слабая скалируемость на окончании алгоритма

43.Пакет BLAS базовых операций линейной алгебры

BLAS (Basic Linear Algebra Subprograms — базовые подпрограммы линейной алгебры) — стандарт интерфейса программирования приложений для создания библиотек, выполняющих основные операции линейной алгебры, такие как умножение векторов и матриц.

Впервые опубликован в 1979 году, и использован для создания больших пакетов, например LAPACK. Интенсивно используемые в высокопроизводительных вычислениях, высоко оптимизированные реализации интерфейса BLAS были разработаны производителями аппаратного обеспечения, такими как Intel, а также другими авторами.

Тест LINPACK Benchmark в своей работе основывается в большой степени на DGEMM, подпрограмме BLAS.

Функциональность BLAS делится на три уровня:

Уровень 1

Этот уровень содержит векторные операции вида:

операции скалярного произведения, взятия нормы вектора и другие операции.

Уровень 2

Этот уровень содержит операции матрица-вектор вида:

Решение для x с треугольной матрицей T и другие операции.

Уровень 3

Содержит операции матрица-матрица вида:

Решение для треугольной матрицы T и другие операции. Этот уровень содержит широко используемую операцию GEMM (англ. General Matrix Multiply).

44.Пакет LINPACK и его применение для ранжирования суперкомпьютеров.

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

На основе LINPACK формируется список TOP500 суперкомпьютеров мира.

45.Lapack для решения задач линейной алгебры (Воропаева)

http://distolymp2.spbu.ru/www/comlan/LAPACK_info.html

Пакет для решения плотных систем уравнений и задачи о наименьших квадратах

Библиотека на фортране (+ использовать на си)

Использует BLAS и Linpack

Подпрограммы LAPACK написаны так, чтобы наибольшее число вычислительных операций выполнялось пакетом BLAS (Basic Linear Algebra Set). Этот пакет предназначен для выполнения элементарных операций, таких как сложение и умножение векторов и матриц, вычисление скалярного произведения и т.п. Он имеет большое количество реализаций, предназначенных для различных платформ. Использование его в LAPACK положительно сказывается на переносимости последнего, без потери производительности, также это позволяет учитывать архитектурные особенности платформ. С пакетом LAPACK поставляется стандартная версия пакета BLAS. В BARSIC используются пакет LAPACK версии 3.0.

Подпрограммы пакета LAPACK разделены на три группы:

• Готовые решения (driver routines). Каждая из таких подпрограмм позволяет решать цельную задачу. Например решение системы линейных уравнений, или вычисление собственных значений матрицы. Разработчики пакета рекомендуют в первую очередь использовать эти подпрограммы.

• Вычислительные (computational) – подпрограммы, выполняющие отдельную численную операцию. Например, LU разложение или приведение симметричной матрицы к диагональному виду. Каждая подпрограмма относящаяся к driver routines как правило состоит из набора вычислительных подпрограмм.

• Вспомогательные – подпрограммы предназначенные для внутренних задач LAPACK. Например, выполнение операций над блоками для блочных алгоритмов, низкоуровневые вычисления, такие как умножения матрица на число, расчет нормы матрицы. Также сюда относятся дополнения к BLAS. Эти подпрограммы редко используются при написании программ с применением LAPACK.

LAPACK содержит подпрограммы одинакового назначения как для вещественных, так и для комплексных данных. Но есть некоторые исключения. Например, аналогом решения симметричных систем линейных уравнений для комплексных данных являются подпрограммы предназначенные как для симметричных матриц, так и для эрмитовских. В то же время не существует комплексного аналога подпрограммы для нахождения собственных значений вещественной симметричной трехдиагональной матрицы, так как комплексная эрмитовская матрица всегда может быть приведена к симметричной трехдиагональной.

Все подпрограммы LAPACK имеют версии единичной и двойной точности. Их названия выглядят так: XYYZZZ. Последняя буква может быть опущена для некоторых подпрограмм уровня driver. Первая буква (“X”) определяет тип данных, с которыми оперирует подпрограмма:

• S – REAL (Float32)

• D – DOUBLE PRECISION (Float64)

• C – COMPLEX (2*Float32)

• Z – DOUBLE COMPLEX (2*Float64)

Буквы YY обозначают тип матрицы с которой работает подпрограмма:

• BD – двухдиагональная

• DI – диагональная

• GE – произвольная матрица

• GT – трехдиагональная

• PO – симметричная, положительно определенная

• SY – симметричная

• TG – треугольная

Буквы ZZZ обозначают тип проводимых вычислений, например TRF обозначает LU разложение, EV – поиск собственных значений. Более подробный перечень обозначений можно найти в справке LAPACK users guide[http://www.netlib.org/lapack/].

Характеристики

Список файлов ответов (шпаргалок)