|
|
| (не показано 28 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| | Основные авторы описания: [[Участник:DenisAnuprienko|Д.В.Ануприенко]]. | | Основные авторы описания: [[Участник:DenisAnuprienko|Д.В.Ануприенко]]. |
| − |
| |
| − | Общая схема описания алгоритмов имеет следующий вид:
| |
| | | | |
| | = Свойства и структура алгоритмов = | | = Свойства и структура алгоритмов = |
| Строка 67: |
Строка 65: |
| | == Схема реализации последовательного алгоритма == | | == Схема реализации последовательного алгоритма == |
| | | | |
| − | # Если размер матриц меньше или равен некоторого числа <math>N_{min}</math>, умножить их обычным способом. | + | # Если размер матриц меньше некоторого числа <math>N_{min}</math>, умножить их обычным способом. |
| | # Иначе | | # Иначе |
| | ## Сформировать множители для матрицы <math>M_1</math> | | ## Сформировать множители для матрицы <math>M_1</math> |
| Строка 79: |
Строка 77: |
| | | | |
| | == Последовательная сложность алгоритма == | | == Последовательная сложность алгоритма == |
| − | Метод Штрассен позволяет сократить число умножений, поэтому оценивается именно оно. В методе Штрассена число умножений составляет <math>O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81})</math>. | + | Метод Штрассена позволяет сократить число умножений, поэтому оценивается именно оно. В методе Штрассена число умножений составляет <math>O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81})</math>. |
| | | | |
| | == Информационный граф == | | == Информационный граф == |
| − | Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.
| + | Рассмотрим блок-схему для последовательной реализации рекурсивной функции Strassen для числа <math>N_{min}</math>, равного 512. |
| | + | [[Файл:Serial.png|300px|center]] |
| | | | |
| − | Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.
| + | Здесь 7 рекурсивных вызовов функции Strassen можно выполнять параллельно: |
| | | | |
| − | В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.
| + | [[Файл:Parallel_1.png|600px|center]] |
| − | | |
| − | Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.
| |
| − | | |
| − | В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.
| |
| − | | |
| − | На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.
| |
| − | | |
| − | [[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
| |
| − | [[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]] | |
| | | | |
| | == Ресурс параллелизма алгоритма == | | == Ресурс параллелизма алгоритма == |
| − | Умножения, которые необходимы для нахождения матриц <math>M_1, ..., M_7</math>, можно провести параллельно. Их можно предоставить 7 узлам (1 хозяин, который раздает задания 6 рабочим и получает результаты, а также работает вместе с ними) или 8 узлам (1 хозяин, который раздает задания 7 рабочим и получает результаты). | + | Умножения, которые необходимы для нахождения матриц <math>M_1, ..., M_7</math>, можно провести параллельно. Их можно предоставить 7 процессам (1 хозяин, который раздает задания 6 рабочим и получает результаты, а также работает вместе с рабочими) или 8 процессам (1 хозяин, который раздает задания 7 рабочим и получает результаты). |
| | | | |
| | == Входные и выходные данные алгоритма == | | == Входные и выходные данные алгоритма == |
| − | Нет никаких предположений насчет структуры матриц. Предполагается, что это обычные плотные матрицы. Они хранятся в виде одномерного массива, что позволяет легко выделять из них подматрицы. | + | Нет никаких предположений насчет структуры матриц. Считается, что это обычные плотные матрицы. Они хранятся в виде одномерного массива, что позволяет легко выделять из них подматрицы. |
| | | | |
| | == Свойства алгоритма == | | == Свойства алгоритма == |
| Строка 109: |
Строка 99: |
| | | | |
| | = Программная реализация алгоритма = | | = Программная реализация алгоритма = |
| − | Вторая часть описания алгоритмов в рамках AlgoWiki рассматривает все составные части процесса их реализации. Рассматривается как последовательная реализация алгоритма, так и параллельная. Описывается взаимосвязь свойств программ, реализующих алгоритм, и особенностей архитектуры компьютера, на которой они выполняются. Исследуется работа с памятью, локальность данных и вычислений, описывается масштабируемость и эффективность параллельных программ, производительность компьютеров, достигаемая на данной программе. Обсуждаются особенности реализации для разных классов архитектур компьютеров, приводятся ссылки на реализации в существующих библиотеках.
| + | |
| | + | === Исходный код === |
| | + | [https://bitbucket.org/DenisAnuprienko/strassen/src Исходный код] |
| | | | |
| | == Особенности реализации последовательного алгоритма == | | == Особенности реализации последовательного алгоритма == |
| − | Здесь описываются особенности и варианты реализации алгоритма в виде последовательной программы, которые влияют на [[глоссарий#Эффективность реализации|''эффективность ее выполнения'']]. В частности, в данном разделе имеет смысл ''сказать о существовании блочных вариантов реализации алгоритма'', дополнительно описав потенциальные преимущества или недостатки, сопровождающие такую реализацию. Важный вопрос - это ''возможные варианты организации работы с данными'', варианты структур данных, наборов временных массивов и другие подобные вопросы. Для различных вариантов реализации следует оценить доступный ресурс параллелизма и объем требуемой памяти.
| + | Матрицы хранятся как одномерные массивы. Благодаря этому в составе матрицы легко выделить подматрицу, зная размеры подматрицы и родительской матрицы, а также указатель на начало подматрицы.<br> |
| − | | + | В этом состоит выгодное отличие от некоторых существующих реализаций, где при использовании подматриц выделяется отдельная память. |
| − | Важным нюансом является ''описание необходимой разрядности выполнения операций алгоритма'' (точности). На практике часто нет никакой необходимости выполнять все арифметические операции над вещественными числами с двойной точностью, т.к. это не влияет ни на устойчивость алгоритма, ни на точность получаемого результата. В таком случае, если значительную часть операций можно выполнять над типом float, и лишь в некоторых фрагментах необходим переход к типу double, это обязательно нужно отметить. Это прямое указание не только на правильную реализацию с точки зрения устойчивости по отношению к ошибкам округления, но и на более эффективную.
| |
| − | | |
| − | Опираясь на информацию из [[#Описание ресурса параллелизма алгоритма|п.1.8]] (описание ресурса параллелизма алгоритма), при описании последовательной версии стоит сказать про возможности [[глоссарий#Эквивалентное преобразование|''эквивалентного преобразования программ'']], реализующих данных алгоритм. В дальнейшем, это даст возможность простого использования доступного параллелизма или же просто покажет, как использовать присущий алгоритму параллелизм на практике. Например, параллелизм на уровне итераций самого внутреннего цикла обычно используется для векторизации. Однако, в некоторых случаях этот параллелизм можно поднять "вверх" по структуре вложенности объемлющих циклов, что делает возможной и эффективную реализацию данного алгоритма на многоядерных SMP-компьютерах.
| |
| − | | |
| − | С этой же точки зрения, в данном разделе весьма полезны соображения по реализации алгоритма на различных параллельных вычислительных платформах. Высокопроизводительные кластеры, многоядерные узлы, возможности для векторизации или использования ускорителей - особенности этих архитектур не только опираются на разные свойства алгоритмов, но и по-разному должны быть выражены в программах, что также желательно описать в данном разделе.
| |
| | | | |
| | == Локальность данных и вычислений == | | == Локальность данных и вычислений == |
| − | Вопросы локальности данных и вычислений не часто изучаются на практике, но именно локальность определяет эффективность выполнения программ на современных вычислительных платформах <ref>Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.</ref><ref>Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.</ref>. В данном разделе приводятся оценки степени [[глоссарий#Локальность использования данных|''локальности данных'']] и [[глоссарий#Локальность вычислений|вычислений]] в программе, причем рассматривается как [[глоссарий#Временная локальность|''временна́я'']], так и [[глоссарий#Пространственная локальность|''пространственная'']] локальность. Отмечаются позитивные и негативные факты, связанные с локальностью, какие ситуации и при каких условиях могут возникать. Исследуется, как меняется локальность при переходе от последовательной реализации к параллельной. Выделяются ключевые шаблоны взаимодействия программы, реализующей описываемый алгоритм, с памятью. Отмечается возможная взаимосвязь между используемыми конструкциями языков программирования и степенью локальности, которыми обладают результирующие программы.
| + | Все действия с двумя главными матрицами проводит только процесс-хозяин. Каждый процесс также создает и освобождает для себя вспомогательные матрицы <math>M_i</math>, а также две матрицы для записи множителей для нахождения <math>M_i</math>. |
| − | | |
| − | Отдельно приводятся профили взаимодействия с памятью для вычислительных ядер и ключевых фрагментов. Если из-за большого числа обращений по общему профилю сложно понять реальную специфику взаимодействия программ с памятью, то проводится последовательная детализация и приводится серия профилей более мелкого масштаба.
| |
| − | | |
| − | На рис.3 и рис.4 показаны профили обращения в память для программ, реализующих разложение Холецкого и быстрое преобразование Фурье, по которым хорошо видна разница свойств локальности у данных алгоритмов.
| |
| − | | |
| − | [[file:Cholesky_locality1.jpg|thumb|center|700px|Рис.3 Реализация метода Холецкого. Общий профиль обращений в память]]
| |
| − | [[file:fft 1.PNG|thumb|center|700px|Рис.4 Нерекурсивная реализация БПФ для степеней двойки. Общий профиль обращений в память]]
| |
| | | | |
| | == Возможные способы и особенности параллельной реализации алгоритма == | | == Возможные способы и особенности параллельной реализации алгоритма == |
| − | Раздел довольно обширный, в котором должны быть описаны основные факты и положения, формирующие параллельную программу. К их числу можно отнести:
| |
| − | * представленный иерархически ресурс параллелизма, опирающийся на структуру циклических конструкций и на граф вызовов программы;
| |
| − | * комбинацию (иерархию) массового параллелизма и параллелизма конечного;
| |
| − | * возможные способы распределения операций между процессами/нитями;
| |
| − | * возможные способы распределения данных;
| |
| − | * оценку количества операций, объёма и числа пересылок данных (как общего числа, так и в пересчёте на каждый параллельный процесс);
| |
| | | | |
| − | и другие.
| + | Устройство метода Штрассена накладывает ограничения на количество процессов для распараллеливания. |
| − | | + | * Как уже было отмечено, распараллеливать можно 7 умножений, из которых получаются матрицы <math>M_1, ..., M_7</math>, с помощью 7 или 8 процессов. |
| − | В этом же разделе должны быть даны рекомендации или сделаны комментарии относительно реализации алгоритма с помощью различных технологий параллельного программирования: MPI, OpenMP, CUDA или использования директив векторизации. | + | * Распараллеливание этих 7 умножений с помощью меньшего, чем 7, или большего, чем 8, числа процессов не рассматривается, так как в первом случае количество пересылок будет тем же, а время работы - большим, а во втором случае получается более 1 процесса на 1 умножение, что является дополнительным усложнением с негарантированной пользой. |
| | + | * В таком случае, распараллеливание <math>n</math> уровней рекурсии требует как минимум <math>7^n</math> процессов. Количество процессов меняется тогда и только тогда, когда меняется число распараллеливаемых уровней рекурсии. |
| | + | * Здесь будет рассмотрен вариант метода Штрассена, где распараллеливается '''1''' уровень рекурсии с помощью 8 процессов: 1 хозяина и 7 рабочих. Эта версия работает несколько быстрее, чем версия с 7 процессами. |
| | | | |
| | == Масштабируемость алгоритма и его реализации == | | == Масштабируемость алгоритма и его реализации == |
| − | Задача данного раздела - показать пределы [[глоссарий#Масштабируемость|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость|''сильной'']] и [[глоссарий#Слабая масштабируемость|''слабой'']] масштабируемости алгоритма и его реализаций.
| + | По описанным в предыдущем пункте причинам предлагаемая реализация с распараллеливанием 1 уровня рекурсии может быть запущена только на определенном количестве процессов. Запуск на другом количестве процессов означает использование уже другой программы, поэтому оценить масшатбируемость в текущей реализации не представляется возможным. |
| | | | |
| − | Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).
| + | === Сравнение работы последовательной и параллельной реализаций === |
| − | | + | Эксперименты проводились на суперкомпьютере [http://users.parallel.ru/wiki/pages/22-config "Ломоносов"]. Использовались gcc и mpicc 4.4.7 с флагом компиляции -O3, а также OpenMPI 1.8.4. Параллельная версия задействовала 8 процессов. |
| − | Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи <ref>Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.</ref>. При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.
| + | {| class="wikitable" |
| − | | + | |+Результаты запусков на "Ломоносове" |
| − | На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.
| + | |- |
| − | [[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рис.5 Масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи]]
| + | |Размер матрицы |
| | + | |Последовательная реализация |
| | + | |Параллельная реализация с использованием MPI |
| | + | |Ускорение |
| | + | |- |
| | + | |512 |
| | + | |0.18 c |
| | + | |0.035 c |
| | + | |5.14 |
| | + | |- |
| | + | |1024 |
| | + | |1.99 c |
| | + | |0.40 c |
| | + | |4.98 |
| | + | |- |
| | + | |2048 |
| | + | |16.1 c |
| | + | |3.45 c |
| | + | |4.67 |
| | + | |- |
| | + | |4096 |
| | + | |230.1 c |
| | + | |71.0 c |
| | + | |3.23 |
| | + | |- |
| | + | |} |
| | | | |
| | == Динамические характеристики и эффективность реализации алгоритма == | | == Динамические характеристики и эффективность реализации алгоритма == |
| − | Это объемный раздел AlgoWiki, поскольку оценка эффективности реализации алгоритма требует комплексного подхода <ref>Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.</ref>, предполагающего аккуратный анализ всех этапов от архитектуры компьютера до самого алгоритма. Основная задача данного раздела заключается в том, чтобы оценить степень эффективности параллельных программ, реализующих данный алгоритм на различных платформах, в зависимости от числа процессоров и размера задачи. Эффективность в данном разделе понимается широко: это и [[глоссарий#Эффективность распараллеливания|''эффективность распараллеливания'']] программы, это и [[глоссарий#Эффективность реализации|''эффективность реализации'']] программ по отношению к пиковым показателям работы вычислительных систем.
| |
| − |
| |
| − | Помимо собственно показателей эффективности, нужно описать и все основные причины, из-за которых эффективность работы параллельной программы на конкретной вычислительной платформе не удается сделать выше. Это не самая простая задача, поскольку на данный момент нет общепринятой методики и соответствующего инструментария, с помощью которых подобный анализ можно было бы провести. Требуется оценить и описать эффективность работы с памятью (особенности профиля взаимодействия программы с памятью), эффективность использования заложенного в алгоритм ресурса параллелизма, эффективность использования коммуникационной сети (особенности коммуникационного профиля), эффективность операций ввода/вывода и т.п. Иногда достаточно интегральных характеристик по работе программы, в некоторых случаях полезно показать данные мониторинга нижнего уровня, например, по загрузке процессора, кэш-промахам, интенсивности использования сети Infiniband и т.п. Хорошее представление о работе параллельной MPI-программы дают данные трассировки, полученные, например, с помощью системы Scalasca.
| |
| | | | |
| | == Выводы для классов архитектур == | | == Выводы для классов архитектур == |
| − | В данный раздел должны быть включены рекомендации по реализации алгоритма для разных классов архитектур. Если архитектура какого-либо компьютера или платформы обладает специфическими особенностями, влияющими на эффективность реализации, то это здесь нужно отметить.
| |
| − |
| |
| − | На практике это сделать можно по-разному: либо все свести в один текущий раздел, либо же соответствующие факты сразу включать в предшествующие разделы, где они обсуждаются и необходимы по смыслу. В некоторых случаях, имеет смысл делать отдельные варианты всей [[#ЧАСТЬ. Программная реализация алгоритмов|части II]] AlgoWiki применительно к отдельным классам архитектур, оставляя общей машинно-независимую [[#ЧАСТЬ. Свойства и структура алгоритмов|часть I]]. В любом случае, важно указать и позитивные, и негативные факты по отношению к конкретным классам. Можно говорить о возможных вариантах оптимизации или даже о "трюках" в написании программ, ориентированных на целевые классы архитектур.
| |
| | | | |
| | == Существующие реализации алгоритма == | | == Существующие реализации алгоритма == |
| − | Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.
| |
| | | | |
| | = Литература = | | = Литература = |
| − | <references />
| + | # [http://www.inm.ras.ru/vtm/lection/all.pdf Тыртышников Е.Е. "Матричный анализ и линейная алгебра", М.:2004-2005] |
| − | | |
| − | [[en:Description of algorithm properties and structure]]
| |
Основные авторы описания: Д.В.Ануприенко.
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Метод Штрассена предназначен для умножения матриц. Здесь будет рассмотрен вариант метода, который можно применять к квадратным матрицам размера [math]N = 2^n[/math]. В таком случае две матрицы можно умножить быстрее, чем за [math]O(N^3)[/math].
1.2 Математическое описание алгоритма
Пусть имеются две матрицы [math]A, B \in \mathbb{R}^{N\times N}[/math]. Представим их в блочном виде:
[math]
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]N/2[/math]. В методе Штрассена предлагается обойтись всего 7 умножениями. Находятся 7 вспомогательных подматриц [math]M_1, ..., M_7[/math] по следующим формулам:
[math]
M_1 = (A_{11} + A_{22})(B_{11} + B_{22})
[/math]
[math]
M_2 = (A_{21} + A_{22})B_{11}
[/math]
[math]
M_3 = A_{11}(B_{12} - B_{22})
[/math]
[math]
M_4 = A_{22}(B_{21} - B_{11})
[/math]
[math]
M_5 = (A_{11} + A_{12})B_{22}
[/math]
[math]
M_6 = (A_{21} - A_{22})(B_{11} + B_{12})
[/math]
[math]
M_7 = (A_{12} - A_{22})(B_{21} + B_{22})
[/math]
После этого матрица [math]C[/math], являющаяся произведением [math]A[/math] и [math]B[/math], находится по формулам
[math]
C_{11} = M_1 + M_4 - M_5 + M_7
[/math]
[math]
C_{12} = M_3 + M_5
[/math]
[math]
C_{21} = M_2 + M_4
[/math]
[math]
C_{22} = M_1 - M_2 + M_3 + M_6
[/math]
Если и умножения подматриц, необходимые для нахождения [math]M_i[/math], проводить по такой же схеме, получается рекурсивный алгоритм. Всего в нем понадобится выполнить [math]O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81})[/math] умножений. На практике рекурсию можно не разворачивать до конца, а использовать обычное умножение уже на матрицах размера 512.
[math][/math]
1.3 Вычислительное ядро алгоритма
Основное время работы алгоритма приходится на формирование множителей для умножения подматриц, рекурсивные вызовы и умножение матриц обычным методом в конце рекурсии.
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
- Если размер матриц меньше некоторого числа [math]N_{min}[/math], умножить их обычным способом.
- Иначе
- Сформировать множители для матрицы [math]M_1[/math]
- Применить метод Штрассена для этих множителей
- Сформировать множители для матрицы [math]M_2[/math]
- Применить метод Штрассена для этих множителей
- ...
- Сформировать множители для матрицы [math]M_7[/math]
- Применить метод Штрассена для этих множителей
- Сформировать результат из матриц [math]M_1, ..., M_7[/math].
1.6 Последовательная сложность алгоритма
Метод Штрассена позволяет сократить число умножений, поэтому оценивается именно оно. В методе Штрассена число умножений составляет [math]O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81})[/math].
1.7 Информационный граф
Рассмотрим блок-схему для последовательной реализации рекурсивной функции Strassen для числа [math]N_{min}[/math], равного 512.
Здесь 7 рекурсивных вызовов функции Strassen можно выполнять параллельно:
1.8 Ресурс параллелизма алгоритма
Умножения, которые необходимы для нахождения матриц [math]M_1, ..., M_7[/math], можно провести параллельно. Их можно предоставить 7 процессам (1 хозяин, который раздает задания 6 рабочим и получает результаты, а также работает вместе с рабочими) или 8 процессам (1 хозяин, который раздает задания 7 рабочим и получает результаты).
1.9 Входные и выходные данные алгоритма
Нет никаких предположений насчет структуры матриц. Считается, что это обычные плотные матрицы. Они хранятся в виде одномерного массива, что позволяет легко выделять из них подматрицы.
1.10 Свойства алгоритма
- Алгоритм устойчив
- Алгоритм детерминирован
2 Программная реализация алгоритма
2.1 Исходный код
Исходный код
2.2 Особенности реализации последовательного алгоритма
Матрицы хранятся как одномерные массивы. Благодаря этому в составе матрицы легко выделить подматрицу, зная размеры подматрицы и родительской матрицы, а также указатель на начало подматрицы.
В этом состоит выгодное отличие от некоторых существующих реализаций, где при использовании подматриц выделяется отдельная память.
2.3 Локальность данных и вычислений
Все действия с двумя главными матрицами проводит только процесс-хозяин. Каждый процесс также создает и освобождает для себя вспомогательные матрицы [math]M_i[/math], а также две матрицы для записи множителей для нахождения [math]M_i[/math].
2.4 Возможные способы и особенности параллельной реализации алгоритма
Устройство метода Штрассена накладывает ограничения на количество процессов для распараллеливания.
- Как уже было отмечено, распараллеливать можно 7 умножений, из которых получаются матрицы [math]M_1, ..., M_7[/math], с помощью 7 или 8 процессов.
- Распараллеливание этих 7 умножений с помощью меньшего, чем 7, или большего, чем 8, числа процессов не рассматривается, так как в первом случае количество пересылок будет тем же, а время работы - большим, а во втором случае получается более 1 процесса на 1 умножение, что является дополнительным усложнением с негарантированной пользой.
- В таком случае, распараллеливание [math]n[/math] уровней рекурсии требует как минимум [math]7^n[/math] процессов. Количество процессов меняется тогда и только тогда, когда меняется число распараллеливаемых уровней рекурсии.
- Здесь будет рассмотрен вариант метода Штрассена, где распараллеливается 1 уровень рекурсии с помощью 8 процессов: 1 хозяина и 7 рабочих. Эта версия работает несколько быстрее, чем версия с 7 процессами.
2.5 Масштабируемость алгоритма и его реализации
По описанным в предыдущем пункте причинам предлагаемая реализация с распараллеливанием 1 уровня рекурсии может быть запущена только на определенном количестве процессов. Запуск на другом количестве процессов означает использование уже другой программы, поэтому оценить масшатбируемость в текущей реализации не представляется возможным.
2.5.1 Сравнение работы последовательной и параллельной реализаций
Эксперименты проводились на суперкомпьютере "Ломоносов". Использовались gcc и mpicc 4.4.7 с флагом компиляции -O3, а также OpenMPI 1.8.4. Параллельная версия задействовала 8 процессов.
Результаты запусков на "Ломоносове"
| Размер матрицы
|
Последовательная реализация
|
Параллельная реализация с использованием MPI
|
Ускорение
|
| 512
|
0.18 c
|
0.035 c
|
5.14
|
| 1024
|
1.99 c
|
0.40 c
|
4.98
|
| 2048
|
16.1 c
|
3.45 c
|
4.67
|
| 4096
|
230.1 c
|
71.0 c
|
3.23
|
2.6 Динамические характеристики и эффективность реализации алгоритма
2.7 Выводы для классов архитектур
2.8 Существующие реализации алгоритма
3 Литература
- Тыртышников Е.Е. "Матричный анализ и линейная алгебра", М.:2004-2005
