|
|
| Строка 10: |
Строка 10: |
| | === Описание входных и выходных данных === | | === Описание входных и выходных данных === |
| | === Свойства алгоритма === | | === Свойства алгоритма === |
| − | == Программная реализация ==
| + | #перенаправление [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)]] |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − | === Описание локальности данных и вычислений ===
| |
| − | ==== Описание локальности алгоритма ====
| |
| − | ==== Описание локальности реализации алгоритма ====
| |
| − | ===== Описание структуры обращений в память и качественная оценка локальности =====
| |
| − | | |
| − | [[file:matrmult 1.PNG|thumb|center|700px|Рисунок 12.1. Профили обращений для 6 вариантов перемножения матриц]] | |
| − | | |
| − | На рисунке 12.1 представлены 6 профилей обращений для различных вариантов классического перемножения матриц (в зависимости от выбранного порядка циклов). На каждом профиле хорошо выделяются фрагменты профилей для 3-х массивов, используемых в программе. При этом порядок обращений к разным массивам во всех 6 вариантах один и тот же; т.е. взаимодействие между массивами везде устроен одинаково. В этом случае отличия в локальности задаются внутренним строением фрагментов профиля для каждого массива в отдельности.
| |
| − | | |
| − | Исходя из исходного кода, можно увидеть, что всего встречается 6 разных видов фрагментов для отдельных массивов (эти виды выделены на рис. 12.1 зеленым). Стоит сделать два уточнения: 1) профиль для результирующего массива С всегда в 2 раза больше, поскольку к элементам этого массива всегда происходят по два обращения подряд; 2) если во внутреннем цикле используется элементы массива, то обращение к этому элементу выносится за пределы внутреннего цикла (в цикле используется скалярная переменная вместо него).
| |
| − | | |
| − | Также заранее отметим, что рисунки по профилям получаются следующим образом: строится рисунок по общему профилю, после чего из него оставляется только часть для рассматриваемого массива. Доля обращений к одному массиву может меняться, поэтому и частота обращений на каждом рисунке может в значительной степени отличаться.
| |
| − | | |
| − | Рассмотрим подробнее каждый из данных 6 фрагментов на примере массива С.
| |
| − | | |
| − | '''Фрагмент 1.''' На рисунке 12.2 показано начало фрагмента 1 (здесь и далее начало фрагмента соответствует выделенной оранжевой области на рис. 12.1). Можно увидеть, что данный фрагмент устроен достаточно просто: выполняется перебор некоторого блока элементов массива, затем данный перебор циклически повторяется. После этого происходит переход к следующему блоку элементов массива, и выполняется тот же перебор в цикле.
| |
| − | | |
| − | Если рассмотреть фрагмент более подробно (рисунок 12.3), можно увидеть, что каждый перебор является на самом деле последовательным перебором, при этом к каждому элементу происходит обращение дважды.
| |
| − | | |
| − | В результате можно сделать вывод, что фрагмент 1 обладает высокой пространственной локальностью (из-за последовательного перебора и последовательной смены блоков перебора), а также высокой временно́й локальностью (из-за двойного обращения к элементам, а также сгруппированности всех обращений к одному элементу в рамках одного блока перебора).
| |
| − | | |
| − | [[file:matrmult 2.PNG|thumb|center|700px|Рисунок 12.2. Начало фрагмента 1]]
| |
| − | [[file:matrmult 3.PNG|thumb|center|700px|Рисунок 12.3. Начало фрагмента 1, первые 3 итерации]]
| |
| − | | |
| − | '''Фрагмент 2.''' На рисунке 12.4 представлено начало фрагмента 2. Видно, что данный фрагмент также представляет собой перебор элементов массива в цикле, однако в данном случае на каждой итерации цикла перебираются сразу все элементы массива, а не только элементы одного блока. При более подробном рассмотрении итерации (рис. 12.5) видно, что здесь также происходит именно последовательный перебор, и также к каждому элементу обращение происходит дважды (поскольку это массив С).
| |
| − | | |
| − | [[file:matrmult 4.PNG|thumb|center|700px|Рисунок 12.4. Начало фрагмента 2]]
| |
| − | [[file:matrmult 5.PNG|thumb|center|700px|Рисунок 12.5. Начало фрагмента 2, часть первой итерации]]
| |
| − | | |
| − | Такой фрагмент также обладает высокой пространственной локальностью, однако временна́я локальность несколько ниже, чем во фрагменте 1. Это связано с тем, что на каждой итерации цикла перебираются все элементы массива, а не только отдельный блок, т.е. повторные обращения происходят реже.
| |
| − | | |
| − | '''Фрагмент 3.''' Начало данного фрагмента представлено на рисунке 12.6. Данный профиль является последовательным перебором всех элементов массива, однако более подробное рассмотрение показывает, что к каждому элементу происходит обращение дважды, при этом между обращениями происходит достаточно много других обращений. Это связано с указанным ранее замечанием касательно вынесения повторяющегося обращения за предел внутреннего цикла.
| |
| − | | |
| − | [[file:matrmult 6.PNG|thumb|center|700px|Рисунок 12.6. Начало фрагмента 3]]
| |
| − | [[file:matrmult 7.PNG|thumb|center|700px|Рисунок 12.7. Начало фрагмента 3, первые несколько обращений]]
| |
| − | | |
| − | Такой фрагмент также обладает высокой пространственной локальностью, однако очень низкой временно́й, поскольку к каждому элементу обращение происходит только два раза.
| |
| − | | |
| − | '''Фрагмент 4.''' По началу фрагмента 4 видно, что профиль снова состоит из перебора всех элементов массива, однако на этот раз перебор не последовательный, а с некоторым шагом. Также можно заметить, что на каждой новой итерации перебор с шагом начинается с элемента, индекс которого немного больше, чем на предыдущей итерации. В данном случае нет нужды рассматривать профиль более подробно, поскольку из данного рисунка можно получить всю необходимую информацию.
| |
| − | | |
| − | По сравнению с предыдущим фрагментом, данный профиль обладает более низкой пространственной локальностью, поскольку перебор элементов идет с шагом, и также очень низкой временно́й локальностью, поскольку на каждой итерации происходят обращения к новым элементам.
| |
| − | | |
| − | [[file:matrmult 8.PNG|thumb|center|700px|Рисунок 12.8. Начало фрагмента 4]]
| |
| − | | |
| − | '''Фрагмент 5.''' В отличие от предыдущих фрагментов, исходя из визуализации начала данного фрагмента (рис. 12.8), сложно сделать выводы относительно структуры обращения в память. Однако более подробное рассмотрение (рис. 12.9) показывает, что данный профиль практически идентичен профилю предыдущего фрагмента. Более того, фрагмент 5 на самом деле состоит из итерационно повторяющихся фрагментов 4.
| |
| − | | |
| − | [[file:matrmult 9.PNG|thumb|center|700px|Рисунок 12.9. Начало фрагмента 5]]
| |
| − | [[file:matrmult 10.PNG|thumb|center|700px|Рисунок 12.10. Начало фрагмента 5, первые несколько итераций]]
| |
| − | | |
| − | Данный фрагмент обладает по сравнению с фрагментом 4 практически такой же пространственной локальностью, однако более высокой временной локальностью. Причина в обоих случаях одна – в данном случае тот же набор обращений повторяется несколько раз.
| |
| − | | |
| − | '''Фрагмент 6.''' Данный фрагмент, представленный на рис. 12.11 и 12.12, так же сильно напоминает фрагмент 5, но с одним отличием. Во фрагменте 5 несколько раз повторяется фрагмент 4, в рамках которого выполняется несколько итераций, и на каждой итерации внутри фрагмента 4 используются разные элементы (поскольку первый элемент сдвигается на 1). В случае данного фрагмента выполняются все те же итерации, но в перемешанном виде. Сначала выполняются все итерации, начинающиеся с одного и того же элемента; затем все итерации, который начинаются с элемента, чей индекс идет следующим; и т.д.
| |
| − | | |
| − | Такой фрагмент обладает более высокой и пространственной, и временно́й локальностью по сравнению с фрагментом 5, поскольку обращения в одним и тем же элементам расположены ближе друг к другу в профиле.
| |
| − | | |
| − | [[file:matrmult 11.PNG|thumb|center|700px|Рисунок 12.11. Начало фрагмента 6]]
| |
| − | [[file:matrmult 12.PNG|thumb|center|700px|Рисунок 12.12. Начало фрагмента 6, первые несколько итераций]]
| |
| − | | |
| − | В итоге можно сказать, что наиболее низкой локальностью в целом обладают фрагменты 5 и 6. Фрагмент 4 также обладает низкой локальностью, однако содержит значительно меньшее число обращений, а значит, привносит меньший вклад в общий профиль обращений. Это позволяет определить, что наименее эффективными с точки зрения работы с памятью являются варианты kji и jki, поскольку каждый из них содержит фрагменты 5 и 6. Далее идут варианты ijk и jik – в них по одному такому фрагменту. Самые лучшие варианты – ikj и kij.
| |
| − | | |
| − | ===== Количественная оценка локальности =====
| |
| − | | |
| − | Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
| |
| − | | |
| − | На рисунке 12.13 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, как и предполагалось наиболее эффективными являются варианты kij,ikj. Заметно хуже результат у вариантов jik,ijk, при этом эти варианты практически равны между собой. Самый плохой результат ожидаемо у вариантов jki,kji.
| |
| − | | |
| − | [[file:matrmult daps ru.PNG|thumb|center|700px|Рисунок 12.13. Сравнение значений оценки daps]]
| |
| − | | |
| − | Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
| |
| − | | |
| − | На рисунке 12.14 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Относительное сравнение результатов по cvg в целом повторяет результаты daps.
| |
| − | | |
| − | [[file:matrmult cvg.PNG|thumb|center|700px|Рисунок 12.14. Сравнение значений оценки cvg]]
| |
| − | | |
| − | === Возможные способы и особенности реализации параллельного алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | ==== Описание масштабируемости алгоритма ====
| |
| − | ==== Описание масштабируемости реализации алгоритма ====
| |
| − | | |
| − | [[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рисунок 1. Параллельная реализация Скалярного произведения векторов Максимальная производительность. ]]
| |
| − | [[file:Масштабируемость параллельной реализации перемножения матриц Эффективность.png|thumb|center|700px|Рисунок 2. Параллельная реализация Скалярного произведения векторов Максимальная эффективность. ]]
| |
| − | Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
| |
| − | * число процессоров [4 : 1024]
| |
| − | * размерность матрицы [1024 : 20480]
| |
| − | Эффективность выполнения реализации алгоритма
| |
| − | * Минимальная эффективность 4,71%
| |
| − | * Максимальная эффективность 31,72%
| |
| − | Оценка масштабируемости
| |
| − | * По числу процессов: -0.0436 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
| |
| − | * По размеру задачи: -0.0255 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
| |
| − | * По двум направлениям: -0.000968 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 25% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.
| |
| − | | |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
