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

2022-07-14T09:09:53Z

Литература =

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

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

	<references />		<references />

ASA: Новая страница: «{{level-i}} Основные авторы описания: А.Н.Дарьин. = Ссылки = [https://code.google.com/p/prir-di...»

2022-07-04T08:05:57Z

Новая страница: «{{level-i}} Основные авторы описания: А.Н.Дарьин. = Ссылки = [https://code.google.com/p/prir-di...»

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

{{level-i}}

Основные авторы описания: [[Участник:Daryin|А.Н.Дарьин]].

= Ссылки =

[https://code.google.com/p/prir-dijkstra-mpi/source/browse/trunk/project/dijkstra_mpi.c Исследованная параллельная реализация на языке C].
Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

= Локальность данных и вычислений =
== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===
=== Количественная оценка локальности ===
= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==
Проведём исследование масштабируемости параллельной реализации алгоритма согласно [[Scalability methodology|методике]].

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

* число процессоров [4, 8 : 128] со значениями квадрата целого числа;
* размер графа [16000:64000] с шагом 16000.

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

[[file:Dijkstra perf.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера области.]]

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

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

Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0.
На рисунках показана эффективность реализации алгоритма Дейкстры на 32 процессах.

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

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

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

На Рисунке 3 показан график количества операций с плавающей точкой в секунду. На графике видна общая очень низкая производительность вычислений около 250 Kфлопс в пике и около 150 Кфлопс в среднем по всем узлам. Это указывает то, что в программе почти все вычисления производятся с целыми числами.
[[file:Dijkstra L1.png|thumb|center|700px|Рисунок 4. График кэш-промахов L1 в секунду при работе алгоритма Дейкстры]]

На графике кэш-промахов первого уровня видно, что число промахов очень большое для нескольких ядер и находится на уровне 15 млн/сек (в пике до 60 млн/сек), что указывает на интенсивные вычисления в части процессов. В среднем по всем узлам значения значительно ниже (около 9 млн/сек). Это указывает на неравномерное распределение вычислений.
[[file:Dijkstra L3.png|thumb|center|700px|Рисунок 5. График кэш-промахов L3 в секунду при работе алгоритма Дейкстры]]

На графике кэш-промахов третьего уровня видно, что число промахов очень невелико и находится на уровне 1,2 млн/сек, однако в среднем по всем узлам значения около 0,5 млн/сек. Соотношение кэш промахов L1|L3 для процессов с высокой производительностью доходит до 60, однако в среднем около 30. Это указывает на очень хорошую локальность вычислений как у части процессов, так и для всех в среднем, и это является признаком высокой производительности.

[[file:Dijkstra Mem Load.png|thumb|center|700px|Рисунок 6. График количества чтений из оперативной памяти при работе алгоритма Дейкстры]]

На графике обращений в память видна достаточно типичная картина для таких приложений. Активность чтения достаточно низкая, что в совокупности с низкими значениями кэш-промахов L3 указывает на хорошую локальность. Хорошая локальность приложения также указывает на то, что значение около 1 млн/сек для задачи является результатом высокой производительности вычислений, хотя и присутствует неравномерность между процессами.
[[file:Dijkstra Mem Store.png|thumb|center|700px|Рисунок 7. График количества записей в оперативную память при работе алгоритма Дейкстры]]

На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения. Стоит отметить достаточно низкое число обращений на запись в память. Это указывает на хорошую организацию вычислений и достаточно эффективную работу с памятью.
[[file:Dijkstra Inf DATA.png|thumb|center|700px|Рисунок 8. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Дейкстры]]

На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются интенсивно и вероятно достаточно малыми порциями данных, потому как производительность вычислений высока. Стоит отметить, что скорость передачи отличается между процессами, что указывает на дисбаланс вычислений.
[[file:Dijkstra Inf PCKTS.png|thumb|center|700px|Рисунок 9. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Дейкстры]]

На графике скорости передачи данных в пакетах в секунду наблюдается крайне высокая интенсивность передачи данных. Это говорит о том, что, вероятно, процессы обмениваются не очень существенными объемами данных, но очень интенсивно. Используются коллективные операции на каждом шаге с небольшими порциями данных, что объясняет такую картину. Также наблюдается меньший дизбаланс между процессами, чем наблюдаемый в графиках использования памяти, вычислений и передачи данных в байтах/сек. Это указывает на то, что процессы обмениваются по алгоритму одинаковым числом пакетов, однако получают разные объемы данных и ведут неравномерные вычисления.
[[file:Dijkstra Load ABG.png|thumb|center|700px|Рисунок 10. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Дейкстры]]
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 8. Это свидетельствует о стабильной работе программы с загруженными вычислениями всеми узлами. Это указывает на очень рациональную и статичную загрузку аппаратных ресурсов процессами. И показывает достаточно хорошую эффективность выполняемой реализации.
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала достаточно эффективно, и стабильно. Использование памяти очень интенсивное, а использование коммуникационной среды крайне интенсивное, при этом объемы передаваемых данных не являются высокими. Это указывает на требовательность к латентности коммуникационной среды алгоритмической части программы.
Низкая эффективность связана, судя по всему, с достаточно высоким объемом пересылок на каждом процессе и с интенсивными обменами сообщениями.

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

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

<references />

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

[[En:Dijkstra, Google]]

Dijkstra, Google - История изменений

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

ASA: Новая страница: «{{level-i}} Основные авторы описания: А.Н.Дарьин. = Ссылки = [https://code.google.com/p/prir-di...»