ASA: /* Локальность реализации алгоритма */

2022-07-14T06:12:53Z

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

← Предыдущая версия		Версия от 06:12, 14 июля 2022
Строка 19:		Строка 19:
	На рис. 1 представлен профиль обращений в память для реализации точечного варианта прогонки. Данный профиль состоит из обращений к 5 массивам – трем диагоналям матрицы, вектору правых частей и результирующему вектору. Исходя из общего профиля, можно увидеть, что программа состоит из двух этапов – на первом выполняется последовательный перебор элементов 4-х массивов, на втором – также последовательный перебор, только в обратном порядке.		На рис. 1 представлен профиль обращений в память для реализации точечного варианта прогонки. Данный профиль состоит из обращений к 5 массивам – трем диагоналям матрицы, вектору правых частей и результирующему вектору. Исходя из общего профиля, можно увидеть, что программа состоит из двух этапов – на первом выполняется последовательный перебор элементов 4-х массивов, на втором – также последовательный перебор, только в обратном порядке.

	[[file:tridiagonal_2.png\|thumb\|center\|500px\|Рисунок 2. Фрагмент общего профиля (выделенный зеленым цветом на рис. 3)]]		[[file:tridiagonal_2.png\|thumb\|center\|500px\|Рисунок 2. Фрагмент общего профиля (выделенный зеленым цветом на рис. 1)]]

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

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

2022-07-14T06:09:21Z

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

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

{{level-i}}

Основные авторы описания: [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|3]])
= Ссылки =

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

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

Как видно по графу алгоритма, локальность данных по пространству хорошая - все аргументы, которые необходимы для операций, вычисляются "рядом". Однако по времени локальность вычислений не столь хороша. Если данные задачи не помещаются в кэш, то вычисления в "верхнем левом углу" СЛАУ будут выполняться с постоянными промахами кэша. Отсюда может следовать одна из рекомендаций прикладникам, использующим прогонку, - нужно организовать все вычисления так, чтобы прогонки были "достаточно коротки" для помещения данных в кэш.

При этом, однако, прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней<ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Подана на конференцию "Параллельные вычислительные технологии (ПаВТ'2016)".</ref>. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что резко ухудшает эффективность выполнения прогонки даже на современных однопроцессорных и одноядерных системах.

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

[[file:tridiagonal_1.png|thumb|center|700px|Рисунок 1. Прогонка, точечный вариант. Общий профиль обращений в память]]

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

[[file:tridiagonal_2.png|thumb|center|500px|Рисунок 2. Фрагмент общего профиля (выделенный зеленым цветом на рис. 3)]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведём исследование масштабируемости реализации алгоритма согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:

* число процессоров 1;
* размер области [10240 : 1024000] с шагом 10240.

В результате проведенных экспериментов был получен следующий диапазон [[Глоссарий#Эффективность реализации|эффективности реализации]] алгоритма:

* минимальная эффективность реализации 0.019%;
* максимальная эффективность реализации 0.0255%.

На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

[[file:Tridiag Perf.png|thumb|center|700px|Рисунок 5. Реализация алгоритма. Изменение производительности в зависимости от размера вектора.]]
[[file:Tridiag eff.png|thumb|center|700px|Рисунок 6. Реализация алгоритма. Изменение эффективности в зависимости от размера вектора.]]

Малая эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о [[#Локальность данных и вычислений|локальности данных и вычислений]].

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

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

Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7.
На рисунках показана эффективность реализации алгоритма прогонки.

[[file:Tridiag1 CPU user.png|thumb|center|700px|Рисунок 7. График загрузки CPU при выполнении алгоритма погонки]]

На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 4% в среднем. Это указывает на достаточно низкую нагрузку выполнения последовательного алгоритма на 8-ми ядерном процессоре.

[[file:Tridiag1 FLops.png|thumb|center|700px|Рисунок 8. График операций с плавающей точкой в секунду при выполнении алгоритма прогонки]]

На Рисунке 9 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений, достигающая в пике 2,2 млн операций в секунду.
[[file:Tridiag1 L1.png|thumb|center|700px|Рисунок 9. График кэш-промахов L1 в секунду при работе алгоритма прогонки]]

На графике кэш-промахов первого уровня видно, что число промахов достаточно низкое даже для одного ядра и находится на уровне 500 тыс/сек. Это указывает на достаточно хорошую локальность данных.
[[file:Tridiag1 L3.png|thumb|center|700px|Рисунок 10. График кэш-промахов L3 в секунду при работе алгоритма прогонки]]

На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно низкое для небольшого числа процессов и находится на уровне 80 тыс/сек. Отношение промахов L1/L3 около 6, что выше средних показателей по типичным задачам. Это также указывает на хорошую локальность вычислений.
[[file:Tridiag1 Mem Load.png|thumb|center|700px|Рисунок 11. График количества чтений из оперативной памяти при работе алгоритма прогонки]]

На графике чтений из памяти на наблюдается достаточно высокая активность чтения из памяти процессами. Так как активно работает только один процесс, то и активность чтения соответствует максимальным значениям. Активность достаточно типична для приложений такого класса.
[[file:Tridiag1 Mem Store.png|thumb|center|700px|Рисунок 12. График количества записей в оперативную память при работе алгоритма прогонки]]

Активность записи в память достаточно низкая, это вполне ожидаемо для такого алгоритма, и так же указывает на достаточно высокую локальность вычислений.
[[file:Tridiag1 Load Avg.png|thumb|center|700px|Рисунок 13. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма прогонки]]
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 1. Это свидетельствует о стабильной работе программы с работающим только одним процессом.
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала не очень эффективно, но с высокой локальностью вычислений. Интенсивность использования памяти низкая, при этом локальность вычислений обеспечивает достаточно эффективное использование кэш-памяти.

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

= Литература ==

<references />

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

[[En:Thomas algorithm, locality]]

Thomas algorithm, locality - История изменений

ASA: /* Локальность реализации алгоритма */

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