RB
Size: a a a
2021 February 27
2021 February 28
IJ
Коллеги, а у кого есть примеры работающих в популярных компиляторах оптимизаций таких, которые понижают класс сложности программы?
IJ
скажем. понижающую O(n) до O(log(n)) когда мы в цикле умножаем вектор на матрицу
H
скажем. понижающую O(n) до O(log(n)) когда мы в цикле умножаем вектор на матрицу
M
скажем. понижающую O(n) до O(log(n)) когда мы в цикле умножаем вектор на матрицу
Начнем с того, что умножение вектора на матрицу - это O(m * n) или O(n^2) если ранг матрицы равен длине вектора. Произведение двух квадратных матриц это соответственно O(n^3) или O(m*n*p) если колличества столбцов / строк разняться.
Можно ли это ускорить в общем случае? Можно сделать некоторые оптимизации в полигедральной модели. Ну например сделать loop tiling что улучшить когеренность кеша, векторизировать все это. Ну и пожалй все.
Можно ли это ассимптотически улучшить? В теории можно, если матрица сильно разраженная, но компилятор об этом не догадается.
Можно разбить на блоки и перемножать по-блочно (не путать с тайлизацией)
Можно пойти еще дальше. На сколько мне известно наиболее быстрый вот этот модифицированный алгоритм Копперсмита-Винограда сводящий перемножение матриц из O(n^3) к субкубическому O(n^2.373)
https://people.csail.mit.edu/virgi/matrixmult-f.pdf
Можно ли это ускорить в общем случае? Можно сделать некоторые оптимизации в полигедральной модели. Ну например сделать loop tiling что улучшить когеренность кеша, векторизировать все это. Ну и пожалй все.
Можно ли это ассимптотически улучшить? В теории можно, если матрица сильно разраженная, но компилятор об этом не догадается.
Можно разбить на блоки и перемножать по-блочно (не путать с тайлизацией)
Можно пойти еще дальше. На сколько мне известно наиболее быстрый вот этот модифицированный алгоритм Копперсмита-Винограда сводящий перемножение матриц из O(n^3) к субкубическому O(n^2.373)
https://people.csail.mit.edu/virgi/matrixmult-f.pdf
M
Насчет оптимизаций компилятора. Я знаю только что LLVM умеет сворачивать некоторые циклы в которых находит арифметическую сумму до собственно аналитической формылы подсчета для такой суммы или произведения
IJ
Начнем с того, что умножение вектора на матрицу - это O(m * n) или O(n^2) если ранг матрицы равен длине вектора. Произведение двух квадратных матриц это соответственно O(n^3) или O(m*n*p) если колличества столбцов / строк разняться.
Можно ли это ускорить в общем случае? Можно сделать некоторые оптимизации в полигедральной модели. Ну например сделать loop tiling что улучшить когеренность кеша, векторизировать все это. Ну и пожалй все.
Можно ли это ассимптотически улучшить? В теории можно, если матрица сильно разраженная, но компилятор об этом не догадается.
Можно разбить на блоки и перемножать по-блочно (не путать с тайлизацией)
Можно пойти еще дальше. На сколько мне известно наиболее быстрый вот этот модифицированный алгоритм Копперсмита-Винограда сводящий перемножение матриц из O(n^3) к субкубическому O(n^2.373)
https://people.csail.mit.edu/virgi/matrixmult-f.pdf
Можно ли это ускорить в общем случае? Можно сделать некоторые оптимизации в полигедральной модели. Ну например сделать loop tiling что улучшить когеренность кеша, векторизировать все это. Ну и пожалй все.
Можно ли это ассимптотически улучшить? В теории можно, если матрица сильно разраженная, но компилятор об этом не догадается.
Можно разбить на блоки и перемножать по-блочно (не путать с тайлизацией)
Можно пойти еще дальше. На сколько мне известно наиболее быстрый вот этот модифицированный алгоритм Копперсмита-Винограда сводящий перемножение матриц из O(n^3) к субкубическому O(n^2.373)
https://people.csail.mit.edu/virgi/matrixmult-f.pdf
речь не совсем об этом, а о том, что вместо умножения на матрицу 1000 раз можно возвести матрицу в 1000 степень быстрее, чем за 1000 умножений
IJ
это классический трюк с помощью которого можно считать фибоначчи быстрее. чем за линию
RP
Коллеги, а у кого есть примеры работающих в популярных компиляторах оптимизаций таких, которые понижают класс сложности программы?
РЕФАЛ
DF
Насчет оптимизаций компилятора. Я знаю только что LLVM умеет сворачивать некоторые циклы в которых находит арифметическую сумму до собственно аналитической формылы подсчета для такой суммы или произведения
+++
DF
Всегда угорал с этой фичи
DF
Интересно кто додумался ее впилить
AZ
Dollar Føølish
Интересно кто додумался ее впилить
ну а почему бы и нет - времени компилятора не жалко :)
DF
Ну потому что это как ускорение от лто , работать всегда будет только на хелловолдах
DF
Нужен более системный подход
DF
В случае со сворачиванием прогрессий не знаю , но в случае с лто - полнопрограммная оптимизация
AZ
Dollar Føølish
Ну потому что это как ускорение от лто , работать всегда будет только на хелловолдах
вот про LTO уже интереснее
DF
Whole program optimization / дефункционализация и иже с ними
LA
Dollar Føølish
В случае со сворачиванием прогрессий не знаю , но в случае с лто - полнопрограммная оптимизация
У LLVM есть ведь ещё полиэдральные оптимизации циклов, не знаю, насколько живые. Как раз об этом
M
речь не совсем об этом, а о том, что вместо умножения на матрицу 1000 раз можно возвести матрицу в 1000 степень быстрее, чем за 1000 умножений
А можно по-подробнее, потому что
A * B = exp(log(A) + log(B)) возможно только для квадратных матрицах это раз и удовлетворяет условию X*Y = Y*X это два