ASA: /* Литература = */

2022-07-14T08:44:00Z

Литература =

← Предыдущая версия		Версия от 08:44, 14 июля 2022
Строка 107:		Строка 107:
	= Результаты прогонов =		= Результаты прогонов =

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

	<references />		<references />

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

2022-07-14T08:43:01Z

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

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

{{level-i}}

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

= Ссылки =

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

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

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

При этом, однако, прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней, если две основные ветви реализуются по отдельности на разных ядрах или же последовательно друг за другом <ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref>. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что резко ухудшает эффективность исполнения прогонки даже на современных однопроцессорных и одноядерных системах. Именно поэтому в примере п.2.1 обе ветви (как прямого, так и обратного хода) сведены в общий цикл. Это, однако, даёт выигрыш только по сравнению с чересчур локальной монотонной прогонкой, ибо эффективность остаётся малой.

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

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

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

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

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

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

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

[[file:tridiagonal2_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, тем в общем случае выше производительность). В целом значение daps для данной программы показывает достаточно высокую производительность работы с памятью, что соответствует нашим ожиданиям согласно приведенному выше описанию локальности.

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

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

На рисунке 5 значения приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Для этой программы оценка cvg очень высока, даже лучше, чем в случае теста Linpack. Здесь можно отметить довольно заметную разницу между двумя оценками, daps и cvg. Возможные причины такой разницы здесь могут быть те же, что и в случае обычной прогонки, которые описаны [http://algowiki-project.org/ru/%D0%9F%D1%80%D0%BE%D0%B3%D0%BE%D0%BD%D0%BA%D0%B0,_%D1%82%D0%BE%D1%87%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D0%BD%D1%82#.D0.9B.D0.BE.D0.BA.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D0.B4.D0.B0.D0.BD.D0.BD.D1.8B.D1.85_.D0.B8_.D0.B2.D1.8B.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D0.B9 здесь].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для проведения экспериментов использовалась реализация алгоритма прогонки, в реализации, доступной [http://git.algowiki-project.org/Teplov/Scalability/blob/master/tridiagonal_other/tridiagonal_other.h здесь]. Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7.
На рисунках показана эффективность реализации алгоритма встречной прогонки.

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

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

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

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

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

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

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

Активность записи в память достаточно низкая, это вполне ожидаемо для такого алгоритма, и так же указывает на достаточно высокую локальность вычислений.
[[file:Tridiag LOAD AVG.png|thumb|center|700px|Рисунок 14. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма встречной прогонки]]

На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 1. Это свидетельствует о стабильной работе программы с работающим только одним процессом.
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала не очень эффективно, но с высокой локальностью вычислений. Интенсивность использования памяти низкая, при этом локальность вычислений обеспечивает достаточно эффективное использование кэш-памяти.

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

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

<references />

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

[[En:Two-sided Thomas, locality]]

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

ASA: /* Литература = */

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