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

The serial-parallel summation method, locality

Материал из Алговики
Перейти к навигации Перейти к поиску


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

1 Ссылки

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

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

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

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

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

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

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

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

Данные фрагмент характеризуются высокой пространственной локальностью и низкой временной, поскольку практически отсутствуют повторные обращения.

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

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

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

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

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

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

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

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

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

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

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

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

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