|
|
| (не показано 14 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| == Описание свойств и структуры алгоритма ==
| | {{level-p}} |
| === Общее описание алгоритма ===
| |
| === Математическое описание ===
| |
| === Вычислительное ядро алгоритма ===
| |
| === Макроструктура алгоритма ===
| |
| === Описание схемы реализации последовательного алгоритма ===
| |
| === Последовательная сложность алгоритма ===
| |
| === Информационный граф ===
| |
| === Описание ресурса параллелизма алгоритма ===
| |
| === Описание входных и выходных данных ===
| |
| === Свойства алгоритма ===
| |
| == Программная реализация ==
| |
| === Особенности реализации последовательного алгоритма ===
| |
| === Описание локальности данных и вычислений ===
| |
| ==== Описание локальности алгоритма ====
| |
| ==== Описание локальности реализации алгоритма ====
| |
| ===== Описание структуры обращений в память и качественная оценка локальности =====
| |
|
| |
|
| [[file:matrmult 1.PNG|thumb|center|700px|Рисунок 12.1. Профили обращений для 6 вариантов перемножения матриц]]
| | '''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. |
| | Здесь мы рассмотрим умножение <math>C = AB</math> плотных неособенных матриц, то есть тот вариант, где никак не может использоваться специальный вид матрицы<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. |
|
| |
|
| На рисунке 12.1 представлены 6 профилей обращений для различных вариантов классического перемножения матриц (в зависимости от выбранного порядка циклов). На каждом профиле хорошо выделяются фрагменты профилей для 3-х массивов, используемых в программе. При этом порядок обращений к разным массивам во всех 6 вариантах один и тот же; т.е. взаимодействие между массивами везде устроен одинаково. В этом случае отличия в локальности задаются внутренним строением фрагментов профиля для каждого массива в отдельности.
| | :<math> |
| | \begin{align} |
| | c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l]. |
| | \end{align} |
| | </math> |
|
| |
|
| Исходя из исходного кода, можно увидеть, что всего встречается 6 разных видов фрагментов для отдельных массивов (эти виды выделены на рис. 12.1 зеленым). Стоит сделать два уточнения: 1) профиль для результирующего массива С всегда в 2 раза больше, поскольку к элементам этого массива всегда происходят по два обращения подряд; 2) если во внутреннем цикле используется элементы массива, то обращение к этому элементу выносится за пределы внутреннего цикла (в цикле используется скалярная переменная вместо него).
| | Классический алгоритм - [[Перемножение_плотных_неособенных_матриц_(последовательный_вещественный_вариант)]]. Для больших размеров существуют и более быстрые алгоритмы (метод Штрассена и т.д.). |
|
| |
|
| Также заранее отметим, что рисунки по профилям получаются следующим образом: строится рисунок по общему профилю, после чего из него оставляется только часть для рассматриваемого массива. Доля обращений к одному массиву может меняться, поэтому и частота обращений на каждом рисунке может в значительной степени отличаться.
| | = Литература = |
|
| |
|
| Рассмотрим подробнее каждый из данных 6 фрагментов на примере массива С.
| | [[Категория:Статьи в работе]] |
|
| |
|
| '''Фрагмент 1.''' На рисунке 12.2 показано начало фрагмента 1 (здесь и далее начало фрагмента соответствует выделенной оранжевой области на рис. 12.1). Можно увидеть, что данный фрагмент устроен достаточно просто: выполняется перебор некоторого блока элементов массива, затем данный перебор циклически повторяется. После этого происходит переход к следующему блоку элементов массива, и выполняется тот же перебор в цикле.
| | [[en:Dense matrix multiplication]] |
| | |
| Если рассмотреть фрагмент более подробно (рисунок 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]] | |
| | |
| === Возможные способы и особенности реализации параллельного алгоритма ===
| |
| === Масштабируемость алгоритма и его реализации ===
| |
| ==== Описание масштабируемости алгоритма ====
| |
| ==== Описание масштабируемости реализации алгоритма ====
| |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
| === Выводы для классов архитектур ===
| |
| === Существующие реализации алгоритма ===
| |
