Параллельные алгоритмы вычислительной алгебры. Распараллеливание на компьютерах с распределенной памятью

Часть 5: Распараллеливание на компьютерах с распределенной памятью
Linpack
LAPACK
DAG алгоритм

Blas
Basic Linear Algebra Subprograms
- BLAS Level 1 – операции с векторами (скалярное произведение вектор, умножение вектор на скалярную величину, нормы вектора и т.д.)
- BLAS Level 2 – матрично-векторные операции (умножение матрицы разных типов на вектор)
- BLAS Level 3 – операции с матрицами (перемножение прямоугольных матриц различных типов)
Опубликован в 1979 году
В свободном доступе на netlib.org
Содержится в оптимизированном виде в огромном количестве математических библиотек (Intel MKL, ACML, ATLAS, и тд)

Linpack
Linear Algebra Package
Пакет для решения систем линейных уравнений и задачи о наименьших квадратах
Опубликован в конце 70-х годов Джеком Донгарра с коллективом
В свободном доступе на netlib.org
Впоследствии пакет стал основной замером производительности кластеров, в частности top500 определяются по модификации этого пакета.
Основная функциональность – разложение Холесского, в симметричном случае представление матрицы

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Может быть выполнено с помощью BLAS level1

Linpack
Плюсы:
Достаточно оптимизировать BLAS level 1 для процессора, чтоб получить оптимизированный Linpack
Минусы:
При увеличении кэша становится неэффективно умножать только строку на число – кэш значительно больше, есть возможность использовать его более разумно
После каждого использования BLAS level 1 приходится вычислять корень из 1 вещественного числа – неэффективно для современныю процессоров
Blas level 1 не очень хорошо параллелизуется, появление многоядерных процессоров накладывает свои требования

LAPACK
Linear Algebra Package
Пакет для решения систем линейных уравнений, поиска сингулярных значений матриц, задач о наименьших квадратах и многое другое...
Опубликован в конце 1992 году Джеком Донгарра с коллективом
В свободном доступе на netlib.org
Содержится в оптимизированном виде в огромном количестве математических библиотек (Intel MKL, ACML, ATLAS, и тд)
Содержит параллельную версию разложения Холесского

LAPACK
Пусть каждый блок не один столбец, а группа. Тогда BLAS level 1 заменяется на BLAS level 3– за счет большего объема данных параллелизуется более эффективно чем level 1.

LAPACK
Плюсы:
Достаточно оптимизировать BLAS level 3 для процессора, чтоб получить оптимизированное разложение Холесского
Минусы:
Не такая эффективная работа на процессорах с разным уровнем кэша – постоянно приходится перекачивать данные с уровня на уровень.
Каждый эффективный вызов BLAS level 3 чередуется с неэффективным вызовом LLT разложения для диагонального блока.
При большом числе процессоров возникает ограничение на “шкалирование” вычисления группы столбов – если группа большая, то время на вычисление диагонального блока станосится существенным.

Решение проблемы с диагональным блоком
Красным обозначены известные значения
Синим неизвестные

Решение проблемы с диагональным блоком
Красным обозначены известные значения
Синим неизвестные

Решение проблемы с диагональным блоком
Красным обозначены известные значения
Синим неизвестные

Решение проблемы с диагональным блоком
Красным обозначены известные значения
Синим неизвестные

Разложение Холесского для симметричных матриц
Красным обозначены известные значения
Синим неизвестные

Решение проблемы с диагональным блоком
Красным обозначены известные значения
Синим неизвестные

Dag подход (Directed acyclic graph)
L11

Dag подход (Directed acyclic graph)
L11
L12
L13
L14

Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22

Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24

Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24
L33

Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24
L33
L34

Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24
L33
L34
L44

Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24
L33
L34
L44
3 задачи одновременно

Dag подход (Directed acyclic graph)
Более того, мы можем постепенно модифицировать
Lij, а не только перед самим вычислением Lij, т.е. добавляется дополнительная возможность разбить работу

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24
L33
L34
L44

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24
L33
L33
L34
L44

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24
L33
L33
L34
L44
L34

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24
L33
L33
L34
L44
L34
L44

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24
L33
L33
L34
L44
L44
L34
L44

Dag подход (Directed acyclic graph)
Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2
L11
L12
L13
L14
L22
L23
L33
L24
L34
L44
L22
L23
L24
L33
L33
L34
L44
L44
L34
L44
6 задач одновременно

Dag подход (Directed acyclic graph)
Плюсы:
Очень хорошая шкалируемость на старте алгоритма
Динамическое распределение задач
Возможность изменения размеров блоков в зависимости от положения в графе
Минусы:
Слабая шкалируемость на окончании алгоритма
Динамическое распределение задач

Далее...
Как реализовать алгорититм для очень большого числа ядер (> 100)?
Как модифицировать алгоритм в случае большого количества кэшей разного уровня?
Как выбирать размер блоков в зависимости от процессора/платформы?
Вопросы открыты.....