Dense matrix multiplication, locality
Основные авторы описания: Вад.В.Воеводин (раздел 2).
Содержание
1 Ссылки
Основные фрагменты реализации, на основе которых были получены количественные оценки, приведены здесь (функция Kernel***, где *** - порядок циклов (напр., KernelIJK)).
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис.1 представлены 6 профилей обращений для различных вариантов классического перемножения матриц (в зависимости от выбранного порядка циклов). На каждом профиле хорошо выделяются фрагменты профилей для 3-х массивов, используемых в программе. При этом порядок обращений к разным массивам во всех 6 вариантах один и тот же; т.е. взаимодействие между массивами везде устроен одинаково. В этом случае отличия в локальности задаются внутренним строением фрагментов профиля для каждого массива в отдельности.
Исходя из исходного кода, можно увидеть, что всего встречается 6 разных видов фрагментов для отдельных массивов (эти виды выделены на рис.2 зеленым). Стоит сделать два уточнения: 1) профиль для результирующего массива С всегда в 2 раза больше, поскольку к элементам этого массива всегда происходят по два обращения подряд; 2) если во внутреннем цикле используется элементы массива, то обращение к этому элементу выносится за пределы внутреннего цикла (в цикле используется скалярная переменная вместо него).
Также заранее отметим, что рисунки по профилям получаются следующим образом: строится рисунок по общему профилю, после чего из него оставляется только часть для рассматриваемого массива. Доля обращений к одному массиву может меняться, поэтому и частота обращений на каждом рисунке может в значительной степени отличаться.
Рассмотрим подробнее каждый из данных 6 фрагментов на примере массива С.
Фрагмент 1. На рис.2 показано начало фрагмента 1 (здесь и далее начало фрагмента соответствует выделенной оранжевой области на рис.1). Можно увидеть, что данный фрагмент устроен достаточно просто: выполняется перебор некоторого блока элементов массива, затем данный перебор циклически повторяется. После этого происходит переход к следующему блоку элементов массива, и выполняется тот же перебор в цикле.
Если рассмотреть фрагмент более подробно (рис.3), можно увидеть, что каждый перебор является на самом деле последовательным перебором, при этом к каждому элементу происходит обращение дважды.
В результате можно сделать вывод, что фрагмент 1 обладает высокой пространственной локальностью (из-за последовательного перебора и последовательной смены блоков перебора), а также высокой временно́й локальностью (из-за двойного обращения к элементам, а также сгруппированности всех обращений к одному элементу в рамках одного блока перебора).
Фрагмент 2. На рис.4 представлено начало фрагмента 2. Видно, что данный фрагмент также представляет собой перебор элементов массива в цикле, однако в данном случае на каждой итерации цикла перебираются сразу все элементы массива, а не только элементы одного блока. При более подробном рассмотрении итерации (рис.5) видно, что здесь также происходит именно последовательный перебор, и также к каждому элементу обращение происходит дважды (поскольку это массив С).
Такой фрагмент также обладает высокой пространственной локальностью, однако временна́я локальность несколько ниже, чем во фрагменте 1. Это связано с тем, что на каждой итерации цикла перебираются все элементы массива, а не только отдельный блок, т.е. повторные обращения происходят реже.
Фрагмент 3. Начало данного фрагмента представлено на рисунке 6. Данный профиль является последовательным перебором всех элементов массива, однако более подробное рассмотрение показывает, что к каждому элементу происходит обращение дважды, при этом между обращениями происходит достаточно много других обращений. Это связано с указанным ранее замечанием касательно вынесения повторяющегося обращения за предел внутреннего цикла.
Такой фрагмент также обладает высокой пространственной локальностью, однако очень низкой временно́й, поскольку к каждому элементу обращение происходит только два раза.
Фрагмент 4. По началу фрагмента 4 видно, что профиль снова состоит из перебора всех элементов массива, однако на этот раз перебор не последовательный, а с некоторым шагом. Также можно заметить, что на каждой новой итерации перебор с шагом начинается с элемента, индекс которого немного больше, чем на предыдущей итерации. В данном случае нет нужды рассматривать профиль более подробно, поскольку из данного рисунка можно получить всю необходимую информацию.
По сравнению с предыдущим фрагментом, данный профиль обладает более низкой пространственной локальностью, поскольку перебор элементов идет с шагом, и также очень низкой временно́й локальностью, поскольку на каждой итерации происходят обращения к новым элементам.
Фрагмент 5. В отличие от предыдущих фрагментов, исходя из визуализации начала данного фрагмента (рис.8), сложно сделать выводы относительно структуры обращения в память. Однако более подробное рассмотрение (рис.9) показывает, что данный профиль практически идентичен профилю предыдущего фрагмента. Более того, фрагмент 5 на самом деле состоит из итерационно повторяющихся фрагментов 4.
Данный фрагмент обладает по сравнению с фрагментом 4 практически такой же пространственной локальностью, однако более высокой временной локальностью. Причина в обоих случаях одна – в данном случае тот же набор обращений повторяется несколько раз.
Фрагмент 6. Данный фрагмент, представленный на рис.11 и рис.12, так же сильно напоминает фрагмент 5, но с одним отличием. Во фрагменте 5 несколько раз повторяется фрагмент 4, в рамках которого выполняется несколько итераций, и на каждой итерации внутри фрагмента 4 используются разные элементы (поскольку первый элемент сдвигается на 1). В случае данного фрагмента выполняются все те же итерации, но в перемешанном виде. Сначала выполняются все итерации, начинающиеся с одного и того же элемента; затем все итерации, который начинаются с элемента, чей индекс идет следующим; и т.д.
Такой фрагмент обладает более высокой и пространственной, и временно́й локальностью по сравнению с фрагментом 5, поскольку обращения в одним и тем же элементам расположены ближе друг к другу в профиле.
В итоге можно сказать, что наиболее низкой локальностью в целом обладают фрагменты 5 и 6. Фрагмент 4 также обладает низкой локальностью, однако содержит значительно меньшее число обращений, а значит, привносит меньший вклад в общий профиль обращений. Это позволяет определить, что наименее эффективными с точки зрения работы с памятью являются варианты kji и jki, поскольку каждый из них содержит фрагменты 5 и 6. Далее идут варианты ijk и jik – в них по одному такому фрагменту. Самые лучшие варианты – ikj и kij.
2.1.2 Количественная оценка локальности
Условия запуска описаны здесь.
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рис.13 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, как и предполагалось наиболее эффективными являются варианты kij,ikj. Заметно хуже результат у вариантов jik,ijk, при этом эти варианты практически равны между собой. Самый плохой результат ожидаемо у вариантов jki,kji.
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
На рис.14 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Относительное сравнение результатов по cvg в целом повторяет результаты daps.
