Участник:DenisAnuprienko/Метод Штрассена
Основные авторы описания: Д.В.Ануприенко.
Общая схема описания алгоритмов имеет следующий вид:
Свойства и структура алгоритмов
Общее описание алгоритма
Метод Штрассена предназначен для умножения матриц. Здесь будет рассмотрен вариант метода, который можно применять к квадратным матрицам размера [math]\displaystyle{ N = 2^n }[/math]. В таком случае две матрицы можно умножить быстрее, чем за [math]\displaystyle{ O(N^3) }[/math].
Математическое описание алгоритма
Пусть имеются две матрицы [math]\displaystyle{ A, B \in \mathbb{R}^{N\times N} }[/math]. Представим их в блочном виде:
[math]\displaystyle{
A =
\begin{bmatrix}
A_{11} & A_{12}\\
A_{21} & A_{22}\\
\end{bmatrix},
B =
\begin{bmatrix}
B_{11} & B_{12}\\
B_{21} & B_{22}\\
\end{bmatrix}.
}[/math]
При обычном умножении матриц пришлось бы совершить 8 умножений подматриц порядка [math]\displaystyle{ N/2 }[/math]. В методе Штрассена предлагается обойтись всего 7 умножениями. Находятся 7 вспомогательных подматриц [math]\displaystyle{ M_1, ..., M_7 }[/math] по следующим формулам:
[math]\displaystyle{
M_1 = (A_{11} + A_{22})(B_{11} + B_{22})
}[/math]
[math]\displaystyle{
M_2 = (A_{21} + A_{22})B_{11}
}[/math]
[math]\displaystyle{
M_3 = A_{11}(B_{12} - B_{22})
}[/math]
[math]\displaystyle{
M_4 = A_{22}(B_{21} - B_{11})
}[/math]
[math]\displaystyle{
M_5 = (A_{11} + A_{12})B_{22}
}[/math]
[math]\displaystyle{
M_6 = (A_{21} - A_{22})(B_{11} + B_{12})
}[/math]
[math]\displaystyle{
M_7 = (A_{12} - A_{22})(B_{21} + B_{22})
}[/math]
После этого матрица [math]\displaystyle{ C }[/math], являющаяся произведением [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], находится по формулам
[math]\displaystyle{
C_{11} = M_1 + M_4 - M_5 + M_7
}[/math]
[math]\displaystyle{
C_{12} = M_3 + M_5
}[/math]
[math]\displaystyle{
C_{21} = M_2 + M_4
}[/math]
[math]\displaystyle{
C_{22} = M_1 - M_2 + M_3 + M_6
}[/math]
Если и умножения подматриц, необходимые для нахождения [math]\displaystyle{ M_i }[/math], проводить по такой же схеме, получается рекурсивный алгоритм. Всего в нем понадобится выполнить [math]\displaystyle{ O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81}) }[/math] умножений. На практике рекурсию можно не разворачивать до конца, а использовать обычное умножение уже на матрицах размера 512.
[math]\displaystyle{ }[/math]
Вычислительное ядро алгоритма
Основное время работы алгоритма приходится на формирование множителей для умножения подматриц, рекурсивные вызовы и умножение матриц обычным методом в конце рекурсии.
Макроструктура алгоритма
Схема реализации последовательного алгоритма
- Если размер матриц меньше или равен некоторого числа [math]\displaystyle{ N_{min} }[/math], умножить их обычным способом.
- Иначе
- Сформировать множители для матрицы [math]\displaystyle{ M_1 }[/math]
- Применить метод Штрассена для этих множителей
- Сформировать множители для матрицы [math]\displaystyle{ M_2 }[/math]
- Применить метод Штрассена для этих множителей
- ...
- Сформировать множители для матрицы [math]\displaystyle{ M_7 }[/math]
- Применить метод Штрассена для этих множителей
- Сформировать результат из матриц [math]\displaystyle{ M_1, ..., M_7 }[/math].
Последовательная сложность алгоритма
Метод Штрассен позволяет сократить число умножений, поэтому оценивается именно оно. В методе Штрассена число умножений составляет [math]\displaystyle{ O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81}) }[/math].
Информационный граф
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа (графа алгоритма [1]). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций [1].
Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.
В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.
Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.
В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение ярусно-параллельной формы графа и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.
На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.
Ресурс параллелизма алгоритма
Умножения, которые необходимы для нахождения матриц [math]\displaystyle{ M_1, ..., M_7 }[/math], можно провести параллельно. Их можно предоставить 7 узлам (1 хозяин, который раздает задания 6 рабочим и получает результаты, а также работает вместе с ними) или 8 узлам (1 хозяин, который раздает задания 7 рабочим и получает результаты).
Входные и выходные данные алгоритма
Нет никаких предположений насчет структуры матриц. Предполагается, что это обычные плотные матрицы. Они хранятся в виде одномерного массива, что позволяет легко выделять из них подматрицы.
Свойства алгоритма
- Алгоритм устойчив
- Алгоритм детерминирован
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Все действия с двумя главными матрицами проводит только процесс-хозяин. Каждый процесс также создает и освобождает для себя вспомогательные матрицы [math]\displaystyle{ M_i }[/math], а также две матрицы для записи множителей для нахождения [math]\displaystyle{ M_i }[/math].
Возможные способы и особенности параллельной реализации алгоритма
Устройство метода Штрассена накладывает ограничения на количество узлов для распараллеливания.
- Как уже было отмечено, распараллеливать можно 7 умножений, из которых получаются матрицы [math]\displaystyle{ M_1, ..., M_7 }[/math], с помощью 7 или 8 процессов.
- Распараллеливание этих 7 умножений с помощью меньшего, чем 7, или большего, чем 8, числа процессов не рассматривается, так как в первом случае количество пересылок будет тем же, а время работы - большим, а во втором случае получается более 1 процесса на 1 умножение, что является дополнительным усложнением с негарантированной пользой.
- В таком случае, распараллеливание [math]\displaystyle{ n }[/math] уровней рекурсии требует как минимум [math]\displaystyle{ 7^n }[/math] узлов. Количество узлов меняется тогда и только тогда, когда меняется число распараллеливаемых уровней рекурсии.
- Здесь будет рассмотрен вариант метода Штрассена, где распараллеливается 1 уровень рекурсии с помощью 8 процессов: 1 хозяина и 7 рабочих. Эта версия работает несколько быстрее, чем версия с 7 процессами.
Масштабируемость алгоритма и его реализации
По описанным в предыдущем пункте причинам предлагаемая реализация с распараллеливанием 1 уровня рекурсии может быть запущена только на определенном количестве узлов. Запуск на другом количестве узлов означает использование уже другой программы, поэтому оценить масшатбируемость в текущей реализации не представляется возможным.
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.