Dot product, locality
Основные авторы описания: Вад.В.Воеводин (раздел 2)
Содержание
1 Ссылки
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция KernelScalarSeqpar).
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис.1 представлен профиль обращений в память для вычисления скалярного произведения векторов, вещественная версия. Данный профиль состоит из обращений к трем массивам, фрагменты для отдельных массивов выделены на рис.1 зеленым цветом. Поскольку мы рассматриваем последовательную реализацию последовательно-параллельного метода суммирования, строение профиля практически никак не зависит от выбранного количества ветвей – будет меняться только число задействованных элементов во фрагменте 1.
Можно увидеть, что фрагменты 2 и 3 идентичны и являются просто последовательным перебором всех элементов массивов. Такой профиль характеризуется высокой пространственной локальностью и очень низкой временной локальностью, поскольку отсутствуют повторные обращения к элементам.
Рассмотрим подробнее фрагмент 1, показанный на рис.2. Из общего профиля на рис.1 это заметить сложно, однако при подобном приближении сразу становится понятно, что данный фрагмент состоит из двух одинаковых последовательных переборов всех элементов массива. В данном случае временная локальность становится немного лучше, поскольку появляется повторное обращение к каждому элементу.
2.1.2 Количественная оценка локальности
Условия запуска описаны здесь.
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, благодаря высокой пространственной локальности, производительность данной программы достаточно высока и находится на уровне теста CG из набора тестов NPB.
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, профиль по уровню локальности подобен, например, тесту Triad или Sum из набора тестов STREAM. Это выглядит закономерным, поскольку в данных тестах также происходит перебор элементов массивов.
