ASA: Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»

2022-07-08T13:23:45Z

Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»

Новая страница

{{level-i}}

Основные авторы описания: [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2]]).

= Ссылки =

Основной фрагмент реализации, с помощью которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/givens/givens.h здесь] (функция Kernel).

= Локальность данных и вычислений =
== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===

[[file:givens_1.png|thumb|center|700px|Рисунок 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 представлен фрагмент общего профиля, выделенный зеленым цветом. Можно увидеть, что обе параллельно выполняемые части на каждой итерации состоят из небольших участков, похожих на обычный последовательный перебор. Явно видна регулярная структура – все участки одинакового размера и расположены на одинаковом расстоянии.

[[file:givens_2.png|thumb|center|700px|Рисунок 2. Выделенный фрагмент общего профиля]]

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

[[file:givens_3.png|thumb|center|700px|Рисунок 3. Фрагмент общего профиля, дальнейшее приближение]]

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

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

Условия запуска описаны [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].

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

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

[[file:givens_daps.png|thumb|center|700px|Рисунок 4. Сравнение значений оценки daps]]

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

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

[[file:givens_cvg.png|thumb|center|700px|Рисунок 5. Сравнение значений оценки cvg]]

= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==
= Динамические характеристики и эффективность реализации алгоритма =
= Результаты прогонов =

[[Категория:Статьи в работе]]

[[En:Givens method, locality]]

Givens method, locality - История изменений

ASA: Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»