Уровень реализации

Dot product, locality

Материал из Алговики
Версия от 14:35, 8 июля 2022; ASA (обсуждение | вклад) (Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску


Основные авторы описания: Вад.В.Воеводин (раздел 2)

1 Ссылки

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция KernelScalarSeqpar).

2 Локальность данных и вычислений

2.1 Локальность реализации алгоритма

2.1.1 Структура обращений в память и качественная оценка локальности

Рисунок 1. Скалярное произведение векторов. Общий профиль обращений в память

На рис.1 представлен профиль обращений в память для вычисления скалярного произведения векторов, вещественная версия. Данный профиль состоит из обращений к трем массивам, фрагменты для отдельных массивов выделены на рис.1 зеленым цветом. Поскольку мы рассматриваем последовательную реализацию последовательно-параллельного метода суммирования, строение профиля практически никак не зависит от выбранного количества ветвей – будет меняться только число задействованных элементов во фрагменте 1.

Можно увидеть, что фрагменты 2 и 3 идентичны и являются просто последовательным перебором всех элементов массивов. Такой профиль характеризуется высокой пространственной локальностью и очень низкой временной локальностью, поскольку отсутствуют повторные обращения к элементам.

Рассмотрим подробнее фрагмент 1, показанный на рис.2. Из общего профиля на рис.1 это заметить сложно, однако при подобном приближении сразу становится понятно, что данный фрагмент состоит из двух одинаковых последовательных переборов всех элементов массива. В данном случае временная локальность становится немного лучше, поскольку появляется повторное обращение к каждому элементу.

Рисунок 2. Фрагмент 1 (профиль обращений к первому массиву)

2.1.2 Количественная оценка локальности

Условия запуска описаны здесь.

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, благодаря высокой пространственной локальности, производительность данной программы достаточно высока и находится на уровне теста CG из набора тестов NPB.

Рисунок 3. Сравнение значений оценки daps

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, профиль по уровню локальности подобен, например, тесту Triad или Sum из набора тестов STREAM. Это выглядит закономерным, поскольку в данных тестах также происходит перебор элементов массивов.

Рисунок 4. Сравнение значений оценки cvg

3 Масштабируемость алгоритма и его реализации

3.1 Масштабируемость алгоритма

3.2 Масштабируемость реализации алгоритма

4 Динамические характеристики и эффективность реализации алгоритма

5 Результаты прогонов