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

Givens method, locality

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


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

1 Ссылки

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

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

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

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

Рисунок 1. Метод Гивенса (вращений) QR-разложения квадратной матрицы (вещественный вариант). Общий профиль обращений в память

На рис. 1 представлен профиль обращений в память для реализации вещественного варианта метода Гивенса (вращений) QR-разложения квадратной матрицы. Данный профиль состоит из обращений к одному двумерному массиву, в котором хранится матрица значений. Из данного графика можно увидеть наличие однотипных итераций, из которых профиль и состоит. [math]i[/math]-я итерация затрагивает элементы массива, начиная с [math](i-1)*k[/math], то есть после каждой итерации первые [math]k[/math] элементов (значение [math]k[/math] нам пока неизвестно) больше не рассматриваются. Каждая итерация состоит из двух параллельно выполняемых частей – последовательного перебора всех элементов, начиная с [math](i-1)*k[/math], и активного использования первых [math]i*k[/math] элементов.

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

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

Рисунок 2. Выделенный фрагмент общего профиля

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

Рисунок 3. Фрагмент общего профиля, дальнейшее приближение

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

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

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

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

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

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

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

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

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

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

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

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

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

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