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

Содержание

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

Слайд 1Спецкурс кафедры «Вычислительной математки» Параллельные алгоритмы вычислительной алгебры
Александр Калинкин
Сергей Гололобов

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

Слайд 3Blas
Basic Linear Algebra Subprograms
- BLAS Level 1 – операции с векторами

(скалярное произведение вектор, умножение вектор на скалярную величину, нормы вектора и т.д.)
- BLAS Level 2 – матрично-векторные операции (умножение матрицы разных типов на вектор)
- BLAS Level 3 – операции с матрицами (перемножение прямоугольных матриц различных типов)

Опубликован в 1979 году
В свободном доступе на netlib.org
Содержится в оптимизированном виде в огромном количестве математических библиотек (Intel MKL, ACML, ATLAS, и тд)

Слайд 4Linpack
Linear Algebra Package
Пакет для решения систем линейных уравнений и задачи

о наименьших квадратах

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

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

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

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

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

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

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

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

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

Слайд 13







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

















Может быть выполнено с помощью BLAS level1

Слайд 14Linpack

Плюсы:
Достаточно оптимизировать BLAS level 1 для процессора, чтоб получить оптимизированный

Linpack

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

Слайд 15LAPACK
Linear Algebra Package
Пакет для решения систем линейных уравнений, поиска сингулярных

значений матриц, задач о наименьших квадратах и многое другое...

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

Слайд 16







LAPACK

















Пусть каждый блок не один столбец, а группа. Тогда BLAS level

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

Слайд 17LAPACK

Плюсы:
Достаточно оптимизировать BLAS level 3 для процессора, чтоб получить оптимизированное

разложение Холесского

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

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

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

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

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

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

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

Слайд 24Dag подход (Directed acyclic graph)
L11

Слайд 25Dag подход (Directed acyclic graph)
L11
L12
L13
L14

Слайд 26Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22

Слайд 27Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24

Слайд 28Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24
L33

Слайд 29Dag подход (Directed acyclic graph)
L11
L12
L13
L14
L22
L23
L24
L33
L34

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

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

3 задачи одновременно

Слайд 32Dag подход (Directed acyclic graph)
Более того, мы можем постепенно модифицировать
Lij, а

не только перед самим вычислением Lij, т.е. добавляется дополнительная возможность разбить работу

Слайд 33Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

Слайд 34Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

Слайд 35Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

L22

L23

L33

L24

L34

L44

Слайд 36Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

L22

L23

L33

L24

L34

L44

L22

Слайд 37Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

L22

L23

L33

L24

L34

L44

L22

L23

L24

Слайд 38Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

L22

L23

L33

L24

L34

L44

L22

L23

L24

L33

L34

L44

Слайд 39Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

L22

L23

L33

L24

L34

L44

L22

L23

L24

L33

L33

L34

L44

Слайд 40Dag подход (Directed acyclic graph)



Перемножение прямоугольных матриц *GEMM
Обращение треугольной матрицы на

прямоугольной *TRSM
Разложение квадратной матрицы на произведение треугольных *GETF2

L11

L12

L13

L14

L22

L23

L33

L24

L34

L44

L22

L23

L24

L33

L33

L34

L44

L34

Слайд 41Dag подход (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

Слайд 42Dag подход (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

Слайд 43Dag подход (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 задач одновременно

Слайд 44Dag подход (Directed acyclic graph)
Плюсы:
Очень хорошая шкалируемость на старте алгоритма
Динамическое

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

Минусы:
Слабая шкалируемость на окончании алгоритма
Динамическое распределение задач

Слайд 45Далее...

Как реализовать алгорититм для очень большого числа ядер (> 100)?

Как модифицировать алгоритм в случае большого количества кэшей разного уровня?

Как выбирать размер блоков в зависимости от процессора/платформы?

Вопросы открыты.....

Слайд 46Вопросы и Ответы

Похожие презентации

Теорема Байеса 577
Урок з математики у 2 класі 371
Решение логических задач 300
Решение задач на нахождение дроби от числа и числа по его дроби 455
Извлечение корня из числа 240
Понятие булева вектора (двоичного вектора) 237

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика