Givens method, locality
Основные авторы описания: Вад.В.Воеводин (раздел 2).
Содержание
1 Ссылки
Основной фрагмент реализации, с помощью которого были получены количественные оценки, приведен здесь (функция Kernel).
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис. 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 более подробно (рис. 3). Здесь уже видны отдельные обращения, и теперь можно с уверенностью сказать, что каждый участок представляет собой последовательный перебор небольшого числа элементов. При этом в верхней части на каждом новом участке перебираются новые элементы, а в нижней – одни и те же данные. Поэтому в целом подобный фрагмент обладает высокой пространственной локальностью (обе части состоят из последовательных переборов), но средней временной локальностью (верхняя часть – очень низкой, нижняя – очень высокой локальностью).
Общий профиль состоит из набора таких фрагментов. При этом данные в этих фрагментах используются повторно на разных итерациях, поэтому общий профиль, скорее всего, обладает более высокой временной локальностью. Поэтому в целом можно сказать, что обращения в память в данной программе обладают высокой пространственной локальностью и достаточно неплохой временной локальностью.
2.1.2 Количественная оценка локальности
Условия запуска описаны здесь.
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 4 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью достаточно высока для этой программы, что соответствует нашим представлениям согласно изученной локальности.
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать и тем лучше локальность.
На рисунке 5 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, как и daps, cvg показывает достаточно хороший результат, тем самым подтверждая качественную оценку, описанную выше.
