Участник:Илья Карандеев(ВТМ, 403)/QR-Факторизация методом Хаусхолдера: различия между версиями
(не показано 7 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
+ | |||
+ | |||
+ | |||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
Строка 4: | Строка 7: | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
+ | |||
+ | ==== Реализация без распараллеливания ==== | ||
+ | Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Она написана с помощью библиотеки cblas - | ||
+ | оболочки замечательной фортрановской библиотеки BLAS для си. Это для одного процесса, | ||
+ | нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции | ||
+ | из cblas на 52-58 строке. После факторизации производится проверка ||Q * R - A|| / ||A||. Q - ортогональная матрица, R - | ||
+ | верхняя треугольная. Их вычисление цель реализации алгоритма. Ну и Q * R должно примерно равняться A, это следует из теории. | ||
+ | Вернее, без погрешности вычисления, в точности Q * R = A. Вычисленный порядок погрешности на персональном компьютере | ||
+ | примерно 10^(-14), что есть довольно хорошо. | ||
+ | |||
+ | |||
+ | [[Файл:Code1.png|слева]] | ||
+ | [[Файл:Code2.png|слева]] | ||
+ | |||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | |||
+ | ==== Распараллеленная реализация ==== | ||
+ | А это распараллеленная реализация. Распараллеливание осуществляется при помощи библиотекки open MPI. Данные у каждого процесса | ||
+ | свои. Они пересылаются друг другу, что и следует из названия библиотеки: "Message passing interface". В этой реализации проверка | ||
+ | ||Q*R - A|| / ||A|| выполняется только при условии, что размер матрицы кратен числу процессов. Написать проверку в этом случае | ||
+ | сложнее из-за того, что нужно пересылать размер отдела матрицы, которую обрабатывает процесс (а он, вообще говоря, может отличаться | ||
+ | у разных процессво, пусть и не более чем на единицу). | ||
+ | <br><br> | ||
+ | В изначальной версии программы ядром (тем, что занимает бОльшую часть времени при исполнении) являлась, как ни странно, | ||
+ | пересылка между процессами. Это узкое место было исправлено: рассылка одного процесса всем остальным стала исполняться | ||
+ | не при помощи функции MPI_Isend, а при помощи специальной функции - MPI_Bcast. Начальная версия программы, хоть и работала, | ||
+ | но не только не приносила выигрыша в скорости, но даже замедляла распараллеленную версию относительно исходной, однопроцессной. | ||
+ | |||
+ | [[Файл:Code3.png|Слева]] | ||
+ | [[Файл:Code4.png|Слева]] | ||
+ | [[Файл:Code5.png|Слева]] | ||
+ | [[Файл:Code6.png|Слева]] | ||
+ | |||
+ | |||
+ | |||
=== Локальность данных и вычислений === | === Локальность данных и вычислений === | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
Строка 26: | Строка 75: | ||
Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц | Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц | ||
− | от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам | + | от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментальных |
+ | запусков программы на суперкомпьютере "Ломоносов-2". | ||
[[Файл:My.3.png|слева]] | [[Файл:My.3.png|слева]] | ||
Строка 32: | Строка 82: | ||
[[Файл:Figure_3.png|слева]] | [[Файл:Figure_3.png|слева]] | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
+ | <br><br><br><br><br><br><br><br><br> | ||
В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. | В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. | ||
Строка 46: | Строка 112: | ||
На языке Python: | На языке Python: | ||
https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/ | https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/ | ||
+ | <br> | ||
https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e | https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e | ||
Строка 55: | Строка 122: | ||
== Литература == | == Литература == | ||
+ | В. Б. Андреев: "Численные методы" |
Текущая версия на 01:42, 17 ноября 2021
Содержание
- 1 Свойства и структура алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.1.1 Реализация без распараллеливания
Ниже приведена моя реализация QR-факторизации методом Хаусхолдера. Она написана с помощью библиотеки cblas - оболочки замечательной фортрановской библиотеки BLAS для си. Это для одного процесса, нераспараллеленная программа. Ее ядро (то что отнимает больше всего времени при счете) - функции из cblas на 52-58 строке. После факторизации производится проверка ||Q * R - A|| / ||A||. Q - ортогональная матрица, R - верхняя треугольная. Их вычисление цель реализации алгоритма. Ну и Q * R должно примерно равняться A, это следует из теории. Вернее, без погрешности вычисления, в точности Q * R = A. Вычисленный порядок погрешности на персональном компьютере примерно 10^(-14), что есть довольно хорошо.
2.1.2 Распараллеленная реализация
А это распараллеленная реализация. Распараллеливание осуществляется при помощи библиотекки open MPI. Данные у каждого процесса
свои. Они пересылаются друг другу, что и следует из названия библиотеки: "Message passing interface". В этой реализации проверка
||Q*R - A|| / ||A|| выполняется только при условии, что размер матрицы кратен числу процессов. Написать проверку в этом случае
сложнее из-за того, что нужно пересылать размер отдела матрицы, которую обрабатывает процесс (а он, вообще говоря, может отличаться
у разных процессво, пусть и не более чем на единицу).
В изначальной версии программы ядром (тем, что занимает бОльшую часть времени при исполнении) являлась, как ни странно,
пересылка между процессами. Это узкое место было исправлено: рассылка одного процесса всем остальным стала исполняться
не при помощи функции MPI_Isend, а при помощи специальной функции - MPI_Bcast. Начальная версия программы, хоть и работала,
но не только не приносила выигрыша в скорости, но даже замедляла распараллеленную версию относительно исходной, однопроцессной.
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Вот исследование масштабируемости параллельной реализации QR-факторизации квадртной матрицы методом Хаусхолдера. Оно проводилось на суперкомпьютере "Ломоносов-2" суперкомпьютерного комплекса МГУ. В первом эксперименте, эксперименте на сильную масштабируемость, бралась матрица размером 14000 на 14000. Количество процессов в эксперименте рассматривалось таким: 1, 2, 4, 8. 14, 28, 56, 112, 224, 448, 700. Этот выбор обусловлен тем, что в одном узле на суперкомпьютере "Ломоносов-2" 14 ядер, а доступное количество узлов автору было равным 50. То есть максимум можно было задействовать 700 ядер.
Следующая серия экспериментов на масштабируемость была проведена на 1, 2, 4, 14, 28 и 42 ядрах. Для матриц
от 200 до 8500, выбранных более-менее произвольно. Вот график в разных проекциях, полученный по результатам экспериментальных
запусков программы на суперкомпьютере "Ломоносов-2".
В целом, все работает объяснимо: больше размерность матрицы → больше время счета. Больше процессов → меньше время счета. Можно заметить, что на малых размерах матрицы при большом количестве процессов начинает падать эффективность. Возможно, это из-за накладных расходов из-за обмена сообщениями между процессами.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Большинство пакетов: LINPACK, LAPACK, SCALAPACK и прочие - используют для QR-разложения матриц именно метод Хаусхолдера, правда, в различных модификациях (обычно с использованием BLAS). Существует большая подборка исследовательских работ по блочным версиям.
Можно найти и много пользовательских реализаций:
На языке Python:
https://www.quantstart.com/articles/QR-Decomposition-with-Python-and-NumPy/
https://gist.github.com/Hsankesara/cd35edb30825df19f182a6ecf96e126e
На языке R: https://rpubs.com/aaronsc32/qr-decomposition-householder - R
Для MatLab: https://www.mathworks.com/matlabcentral/answers/169648-qr-factorization-using-householder-transformations
3 Литература
В. Б. Андреев: "Численные методы"