Уровень реализации

Cooley-Tukey, scalability: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|1.2]])
+
{{level-i}}
  
= Программная реализация алгоритма: Cooley-Tukey, scalability =
+
Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|3]], [[#Динамические характеристики и эффективность реализации алгоритма|4]])
 +
 
 +
= Ссылки =
  
 
Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].
 
Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].
  
== Локальность данных и вычислений ==
+
= Локальность данных и вычислений =
=== Локальность реализации алгоритма ===
+
== Локальность реализации алгоритма ==
==== Структура обращений в память и качественная оценка локальности ====
+
=== Структура обращений в память и качественная оценка локальности ===
==== Количественная оценка локальности ====
+
=== Количественная оценка локальности ===
  
== Масштабируемость алгоритма и его реализации ==
+
= Масштабируемость алгоритма и его реализации =
=== Масштабируемость алгоритма ===
+
== Масштабируемость алгоритма ==
=== Масштабируемость реализации алгоритма ===
+
== Масштабируемость реализации алгоритма ==
 
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:  
 
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:  
  
Строка 30: Строка 32:
 
Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.
 
Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.
  
== Динамические характеристики и эффективность реализации алгоритма ==
+
= Динамические характеристики и эффективность реализации алгоритма =
== Результаты прогонов ==
+
 
 +
Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7.
 +
На рисунках показана эффективность реализации алгоритма Кули-Тьюки на 64 процессах.
 +
 
 +
[[file:Cooley-Tukey CPU USER.png|thumb|center|700px|Рисунок 3. График загрузки CPU при выполнении алгоритма Кули-Тьюки]]
 +
 
 +
На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 20%. Это указывает на существенную недозагруженность вычислениями процессора.
 +
 
 +
[[file:Cooley-Tukey CPU FLOPS.png|thumb|center|700px|Рисунок 4. График операций с плавающей точкой в секунду при выполнении алгоритма Кули-Тьюки]]
 +
 
 +
На Рисунке 11 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений.
 +
[[file:Cooley-Tukey L1.png|thumb|center|700px|Рисунок 5. График кэш-промахов L1 в секунду при работе алгоритма Кули-Тьюки]]
 +
 +
На графике кэш-промахов первого уровня видно, что число промахов достаточно большое для нескольких ядер и находится на уровне 25 млн/сек. В среднем по всем узлам значения значительно ниже. Это указывает на неравномерное распределение вычислений.
 +
[[file:Cooley-Tukey L3.png|thumb|center|700px|Рисунок 6. График кэш-промахов L3 в секунду при работе алгоритма Кули-Тьюки]]
 +
 
 +
На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно большое для небольшого числа процессов и находится на уровне 1,5 млн/сек, однако в среднем по всем узлам значения низкие.
 +
[[file:Cooley-Tukey MEM LOAD.png|thumb|center|700px|Рисунок 7. График количества чтений из оперативной памяти при работе алгоритма Кули-Тьюки]]
 +
 
 +
На графике чтений из памяти на наблюдается неравномерная активность чтения из памяти процессами: несколько читают очень активно, остальные используют значительно менее эффективно. Однако активность тех нескольких процессов чтения из памяти достаточно высока, что в сочетании с показаниями достаточно высокого уровня кэш-промахов указывает на достаточно большой процент промахов из кэш в оперативную память.
 +
[[file:Cooley-Tukey MEM STORE.png|thumb|center|700px|Рисунок 8. График количества записей в оперативную память при работе алгоритма Кули-Тьюки]]
 +
 
 +
На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения и указывает на низкую эффективность данной реализации.
 +
[[file:Cooley-Tukey INF DATA.png|thumb|center|700px|Рисунок 9. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Кули-Тьюки]]
 +
 
 +
На графике скорости передачи данных по сети Infiniband наблюдается достаточно низкая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются небольшими порциями данных.
 +
[[file:Cooley-Tukey INF PCKTS.png|thumb|center|700px|Рисунок 10. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Кули-Тьюки]]
 +
 
 +
На графике скорости передачи данных в пакетах в секунду наблюдается очень высокая интенсивность передачи данных выраженная в пакетах в секунду. Это говорит о том, что, вероятно, процессы обмениваются сообщениями очень низкой длины, но очень интенсивно.  Так же наблюдается меньший дизбаланс между процессами чем наблюдаемый в графиках использования памяти и вычислений. Это указывает на то, что при поступлении необходимых данных часть процессов начинает интенсивные вычисления, хотя другие продолжают простаивать.
 +
[[file:Cooley-Tukey LOADAVG.png|thumb|center|700px|Рисунок 17. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Кули-Тьюки]]
 +
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 3. Это свидетельствует о стабильной работе программы с загруженной только частью вычислительных узлов. Это указывает на очень нерациональную и статичную загрузку аппаратных ресурсов процессами. И показывает низкую эффективность выполняемой реализации.
 +
В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала неэффективно, но стабильно. Использование памяти и коммуникационной среды достаточно интенсивное, при этом объемы передаваемых данных являются крайне малыми. Это указывает на необходимость использования оптимизаций алгоритмической части программы.
 +
Низкая эффективность связана судя по всему с недостаточным объемом вычислений на каждом процессе, интенсивными обменами малой длины сообщений. Это приводит к постоянному ожиданию процессами данных для вычислений и простою даже в рамках одного вычислительного узла.
 +
 
 +
= Результаты прогонов =
  
 
[[Категория:Статьи в работе]]
 
[[Категория:Статьи в работе]]
  
 
[[En:Cooley-Tukey, scalability]]
 
[[En:Cooley-Tukey, scalability]]

Текущая версия на 15:09, 1 июля 2022


Основные авторы описания: А.М.Теплов (разделы 3, 4)

1 Ссылки

Исследованная параллельная реализация алгоритма.

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

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

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

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

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

3.1 Масштабируемость алгоритма

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

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

  • число процессоров [4, 8 : 64] с шагом 8;
  • размер вектора [128 : 32768] с шагом равным степени двойки.

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

  • минимальная эффективность реализации 0.000000002% (1.85994069951e-09%);
  • максимальная эффективность реализации 0.00002% (2.07351573426e-05%).

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

Рисунок 1. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера области.
Рисунок 2. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.

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

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

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

На рисунках показана эффективность реализации алгоритма Кули-Тьюки на 64 процессах.

Рисунок 3. График загрузки CPU при выполнении алгоритма Кули-Тьюки

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

Рисунок 4. График операций с плавающей точкой в секунду при выполнении алгоритма Кули-Тьюки

На Рисунке 11 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений.

Рисунок 5. График кэш-промахов L1 в секунду при работе алгоритма Кули-Тьюки

На графике кэш-промахов первого уровня видно, что число промахов достаточно большое для нескольких ядер и находится на уровне 25 млн/сек. В среднем по всем узлам значения значительно ниже. Это указывает на неравномерное распределение вычислений.

Рисунок 6. График кэш-промахов L3 в секунду при работе алгоритма Кули-Тьюки

На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно большое для небольшого числа процессов и находится на уровне 1,5 млн/сек, однако в среднем по всем узлам значения низкие.

Рисунок 7. График количества чтений из оперативной памяти при работе алгоритма Кули-Тьюки

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

Рисунок 8. График количества записей в оперативную память при работе алгоритма Кули-Тьюки

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

Рисунок 9. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Кули-Тьюки

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

Рисунок 10. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Кули-Тьюки

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

Рисунок 17. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Кули-Тьюки

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

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