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

Pairwise summation of numbers, locality

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


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

1 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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