Выпуск №10 (Июль)
XLIІI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.07.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLII Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.06.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.05.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XL Международная научно-практическая конференция «Актуальные проблемы современной науки», 28.03.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

МНПК "Цифровая трансформация и инновации в экономике, праве, государственном управлении, науке и образовательных процессах", 18-21.03.2019

XXXIX Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.02.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XIII Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 31.01.2019 (Совместная конференция с Финансово-экономическим научным советом)

XXXVIII Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.01.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XXXVІI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2018 (Совместная конференция с Международным научным центром)

XXXVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2018 (Совместная конференция с Международным научным центром)

XIII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXXV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.10.2018 (Совместная конференция с Международным научным центром)

XXXIV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2018 (Совместная конференция с Международным научным центром)

ХXXIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.08.2018 (Совместная конференция с Международным научным центром)

ХXXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 31.07.2018 (Совместная конференция с Международным научным центром)

XII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХXXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2018 (Совместная конференция с Международным научным центром)

ХІ Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2018 (Совместная конференция с Международным научным центром)

XXIХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.04.2018 (Совместная конференция с Международным научным центром)

ХХVIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.03.2018 (Совместная конференция с Международным научным центром)

ІІІ МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 19-22.03.2018 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 28.02.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХХVІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2018 (Совместная конференция с Международным научным центром)

ХХVІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2018 (Совместная конференция с Международным научным центром)

XІІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.12.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2017 (Совместная конференция с Международным научным центром)

ХХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2017 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2017 (Совместная конференция с Финансово-экономическим научным советом)

XІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.09.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2017 (Совместная конференция с Международным научным центром)

X Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.07.2017 (Совместная конференция с Международным научным центром)

ХXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2017 (Совместная конференция с Международным научным центром)

"Тенденции развития национальных экономик: экономическое и правовое измерение" 18-19.05.2017 (Совместная конференция с Финансово-экономическим научным советом и ККИБиП)

ХIX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.04.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.03.2017 (Совместная конференция с Международным научным центром)

МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 20–23.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

VIII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.02.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2017 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.01.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2017 (Совместная конференция с Международным научным центром)

ХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2016 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 28.12.2016 (Совместная конференция с Финансово-экономическим научным советом)

VII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.11.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.10.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.10.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конф. «Научный диспут: вопросы экономики и финансов», 30.09.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.09.2016 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.08.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 29.07.2016 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.07.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.06.2016 (Совместная конференция с Финансово-экономическим научным советом)

ІX Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2016 (Совместная конференция с Международным научным центром)

VI Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.05.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 30.05.2016 (Совместная конференция с Международным научным центром)

V Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 29.04.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.04.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 31.03.2016 (Совместная конференция с Международным научным центром)

ІI Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 30.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 21-24.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 26.02.2016 (Совместная конференция с Финансово-экономическим научным советом)

II Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 20.02.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.12.2015 (Совместная конференция с Международным научным центром)

IV Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.12.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.11.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 29.10.2015 (Совместная конференция с Финансово-экономическим научным советом)

Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 28.10.2015 (Совместная конференция с Международным научным центром)

III Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.09.2015 (Совместная конференция с Финансово-экономическим научным советом)

III Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.08.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІІ Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 30.06.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2015 (Совместная конференция с Международным научным центром)

II Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.05.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы экономики и финансов, 29.04.2015 (Совместная конференция с Финансово-экономическим научным советом)

Научный диспут: вопросы экономики и финансов, 31.03.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы современной науки, 27.03.2015 (Совместная конференция с Международным научным центром)

Глобальные проблемы экономики и финансов, 27.02.2015 (Совместная конференция с финансово-экономическим научным советом)



Романенко Л. А. Експериментальне порівняння роботи засобів паралельного програмування на різних суперкомп’ютерах для алгоритму Флойда-Уоршала // Міжнародний науковий журнал "Інтернаука". — 2017. — №10.


Отрасль науки: Технические науки
Скачать статью (pdf)

Технічні науки

УДК 004.4

Романенко Лев Анатолійович

бакалавр програмної інженерії

Національного технічного університету України

«Київський політехнічний інститут імені Ігоря Сікорського»

Романенко Лев Анатольевич

бакалавр программной инженерии

Национального технического университета Украины

«Киевский политехнический институт имени Игоря Сикорского»

Lev Romanenko

Bachelor of software engineering

The National Technical University of Ukraine

«Igor Sikorsky Kyiv Polytechnic Institute»

ЕКСПЕРИМЕНТАЛЬНЕ ПОРІВНЯННЯ РОБОТИ ЗАСОБІВ ПАРАЛЕЛЬНОГО ПРОГРАМУВАННЯ НА РІЗНИХ СУПЕРКОМП’ЮТЕРАХ ДЛЯ АЛГОРИТМУ ФЛОЙДА-УОРШАЛА

ЭКСПЕРИМЕНТАЛЬНОЕ СРАВНЕНИЕ РАБОТЫ СРЕДСТВ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ НА РАЗЛИЧНЫХ СУПЕРКОМПЬЮТЕРАХ ДЛЯ АЛГОРИТМА ФЛОЙДА-УОРШАЛА

EXPERIMENTAL COMPARISON OF THE WORK OF PARALLEL PROGRAMMING TOOLS ON VARIOUS SUPERCOMPUTERS FOR THE FLOYD-WARSHAL ALGORITHM

Анотація: Проведено експериментальне порівняння роботи бібліотек паралельного програмування MPI та openMP на суперкомп’ютері Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського» та кластері Colfax International для динамічного алгоритму Флойда-Уоршала.

Ключові слова: MPI, openMP, алгоритм Флойда-Уоршала, суперкомп’ютер.

Аннотация: Проведено экспериментальное сравнение работы библиотек параллельного программирования MPI и openMP на суперкомпьютере Национального технического университета Украины «Киевский политехнический институт имени Игоря Сикорского» и кластере Colfax International для динамического алгоритма Флойда-Уоршала.

Ключевые слова: MPI, openMP, алгоритм Флойда-Уоршала, суперкомпьютер.

Summary: The experimental comparison of the parallel programming libraries MPI and openMP on the supercomputer of the National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" and the cluster Colfax International for the dynamic Floyd-Worshall algorithm is carried out.

Key words: MPI, openMP, Floyd-Worshall algorithm, supercomputers.

Під-час написання програм для кластерних систем, доводиться звертати увагу на особливості тієї машини, де дане програмне забезпечення буде виконуватися. Метою дослідження було дізнатися як впливає апаратне устаткування на характеристики обчислень і визначити яка комбінація фізично-логічних засобів буде найкращою. До уваги бралися дві бібліотеки для паралельного програмування – MPI та openMP і два еквівалентних за потужністю суперкомп’ютери – Colfax International та кластер КПІ ім. Ігоря Сікорського. Об’єктом програмування обраний алгоритм Флойда-Уоршала.

Алгоритм Флойда-Уоршала

Алгоритм Флойда-Воршелла – це динамічний алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Його було розроблено в 1962 році Робертом Флойдом і Стівеном Уоршеллом.

Більш точне формулювання цього завдання: є орієнтований граф G = (V, Е) кожній дузі v → w цього графа співставлена ​​позитивна вартість C [v, w]. Загальне завдання знаходження найкоротших шляхів полягає в знаходженні для кожної впорядкованої пари вершин (v, w) будь-якого шляху від вершини v в вершини w, довжина якого мінімальна серед усіх можливих шляхів від v до w.

Апаратне забезпечення кластерів

Для виконання обчислень було обрано два суперкомп’ютери: Colfax International та кластер Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського».

Характеристики  КПІ ім. Ігоря Сікорського [2]:

  1. Вузли:
    • 44 з двома 4-ядерними процесорами Intel Xeon E5440 @ 2.83ГГц та 8 Гб оперативної пам’яті у кожному;
    • 68 з двома 2-ядерними процесорами Intel Xeon 5160 @ 3.00ГГц та 4 Гб оперативної пам’яті у кожному;
  2. ОС –  CentOS release 6.4;
  3. Локальний менеджер ресурсів – Slurm.

Характеристики Colfax Internatioanl [1]:

  1. Вузли – 79 з восьми одноядерними  процесорами Intel Xeon Phi 2.1 ГГц та 4 Гб оперативної пам’яті у кожному;
  2. ОС – CentOS, Fedora, Scientific Linux;
  3. Локальний менеджер ресурсів – Brigth Cluster Manager.

Обидва кластера, і КПІ ім. Ігоря Сікорського і Сolfax, дотримуються політики обмеження ресурсів для користувача.

Colfax використовує віртуальне середовище, яке обмежує кількість ресурсів для кожного користувача.

Кластер КПІ ім. Ігоря Сікорського обмежує ресурси загально, не з допомогою віртуального середовища. Система обмежує кількість потоків та кількість вузлів для користувача. Програма може бути виконана на одному вузлі, але на декількох потоках, або на декількох вузлах, але з одним потоком. 

Collfax використовує специфічний Intel C Compiler [3, c. 41], який розрахований під конкретне апаратне устаткування.

Основні можливості:

  • міжпроцедурна оптимізація;
  • автоматичне розпаралелювання коду;
  • векторизація для SSE, SSE3, SSE4;
  • оптимізація з урахуванням профільної інформації.

Intel C++ compiler підтримує стандарт OpenMP 3.0 для написання паралельних програм. Також містить модифікацію OpenMP під назвою Cluster OpenMP, за допомогою якої можна запускати додатки написані відповідно до OpenMP на кластерах, що використовують MPI.

Кластер КПІ ім. Ігоря Сікорського має базовий GNU C Compiler. Він використовується як стандартний компілятор для вільних UNIX-подібних операційних систем.

Результати обчислень

Для порівняння засобів паралельного програмування було обрано такі характеристики як час обчислення, коефіцієнт прискорення та коефіцієнт ефективності. Обчислення здійснювалися на наборі векторів розміром 2700 елементів для 8 потоків виконання.

Результати випробувань для кластера КПІ ім. Ігоря Сікорського наведені в таблиці нижче (табл.1)

Таблиця 1

Результати вимірювань для КПІ ім. Ігоря Сікорського

К-ть потоків

Час

Прискорення

Ефективність

 

MPI

openMP

MPI

openMP

MPI

openMP

1

41,308186

41,308186

1

1

1

1

2

22,956614

22,731996

1,799402

1,817183

0,899701

0,908591

3

22,587734

22,739856

1,828788

1,816554

0,609596

0,605518

4

16,121003

16,181408

2,562383

2,552818

0,640596

0,638204

5

19,122467

19,319592

2,160191

2,13815

0,432038

0,42763

6

15,877504

21,076918

2,60168

1,959878

0,433613

0,326646

7

18,669774

18,802218

2,21257

2,196985

0,316081

0,313855

8

16,261717

16,25834

2,540211

2,540738

0,317526

0,317592

На таблиці з  даними можна спостерігати скорочення часу, це природньо адже збільшується кількість ядр при одному і тому ж  об’ємі даних – графік наглядно це показує (рисунок 1). Різниця в часі для обраних бібліотек майже відсутня, а це говорить про  рівнозначну швидкість обчислень.

Рисунок 1 – Графік залежності часу від кількості потоків обчислення

На таблиці з  даними про прискорення (табл.1), можна бачити що прискорення обчислень збільшується на ядрах 2, 3, 4, а потім коливається в сталому діапазоні. Можливо така поведінка обчислень на кількості ядр 5, 6, 7, 8 пов’язана з накладними затратами на комунікацію між ними. Виходячи  з результатів, такий об’єм  даних оптимальніше обчислювати на кількості ядр від 1 до 4, а якщо об’єм  даних пропорційно більший, то на кількості ядр від 5 до 8. Знову ж таки обидві бібліотеки показують ідентичні результати для прискорення (рисунок 2).

Рисунок 2 – Графік залежності коефіцієнта прискорення від кількості потоків обчислення

На графіку можна чітко спостерігати пропорційне зменшення ефективності до кількості ядр. Особливі піки спаду ефективності можна спостерігати на непарній кількості ядр. Можливо що  така закономірність зумовлена апаратними особливостями. Загалом спад ефективності можна пов’язати з тими ж таки затратами на комунікацію та синхронізацію між ядрами. Аналізуючи дані коефіцієнта ефективності, можна сказати що на 6 ядрах, бібліотека openMP втрачає показники в порівнянні з MPI (рисунок 3).

Рисунок 3 – Графік залежності коефіцієнта ефективності від кількості потоків обчислення

Результати випробувань для кластера Colfax International наведені в таблиці нижче (табл.2)

Таблиця 2

Результати вимірювань для Colfax International

К-ть потоків

Час

Прискорення

Ефективність

 

MPI

openMP

MPI

openMP

MPI

openMP

1

20,390237

20,390237

1

1

1

1

2

11,336521

10,747534

1,798633

1,897201

0,899316

0,948601

3

7,706041

7,563788

2,646007

2,695771

0,882002

0,89859

4

6,22211

5,778772

3,277061

3,528472

0,819265

0,882118

5

4,87605

4,81701

4,181712

4,232965

0,836342

0,846593

6

4,603811

4,403029

4,428991

4,630957

0,738165

0,771826

7

3,781575

3,728906

5,391996

5,468155

0,770285

0,781165

8

3,297379

3,429241

6,183771

5,945991

0,772971

0,743249

Аналізуючи дані для Colfax, можна спостерігати ті ж тенденції що і для кластера КПІ ім. Ігоря Сікорського (рис.4, рис.5, рис.6). Відмінність полягає лиш в швидкості – Colfax cluster обчислює той же об’єм даних, але на порядок швидше. Також можна відзначити те що коефіцієнт ефективності openMP на даному кластері більший за MPI.

Рисунок 4 – Графік залежності часу від кількості потоків обчислення

Рисунок 5 – Графік залежності коефіцієнта прискорення від кількості потоків обчислення

Рисунок 6 – Графік залежності коефіцієнта ефективності від кількості потоків обчислення

Висновки

Як показали дослідження, коефіцієнт ефективності бібліотек openMP та MPI варіюється в залежності від обладнання на якому вони застосовуються. Загалом різниця в показниках не суттєва, але на великих наборах даних буде відчутна. 

Компілятор відіграє важливу роль в швидкості обчислень. Апаратно орієнтовні компілятори э більше оптимізовані. Таку тенденцію можна побачити спостерігаючи час за який було оброблено один і той же об’єм даних на кластерах КПІ ім. Ігоря Сікорського та Colfax International. Апаратно орієнтовані компілятори є ефективніші, в порівнянні з базовими-універсальними, тому що мають змогу виконувати високо рівневі, а також цільові оптимізації під процесори на які вони розраховані. Як результат,  такі компілятори в парі з їх процесорами працюють швидше. Це можна побачити на прикладі Colfax International.

Технологія MPI менш вимоглива до засобів зв'язку між процесорами на якій вона може бути ефективно реалізована, але більш вимоглива до програміста, важче в застосуванні ніж технологія OpenMP.

Апаратне устаткування, на базі якої можлива ефективна реалізація OpenMP (SMP-сервери), коштує дорого і погано масштабується. Обладнання, придатне для реалізації MPI (спеціалізовані мережі обчислювальних кластерів), набагато дешевше, і масштабується практично необмежено, але має набагато більш низькою ефективністю.

Отже вибір засобу паралельного програмування повинен залежати від наявного обладнання та апаратного програмного забезпечення.

Література:

  1. Colfax International [Електронний ресурс] – Режим доступу: http://www.colfax-intl.com/nd/index.aspx
  2. Центр суперкомпютерних обчислень НТУУ «КПІ ім. І.Сікорського» [Електронний ресурс] – Режим доступу: http://grid.kpi.ua/index.php/ru/national-resource-centre/10-centr-superkompyuternih-obchislen.html
  3. Parallel programming and optimization with intel xeon PHI coprocessors / A. Vladimirov, R. Asai, V. Karpusenko, 2013 – 2015.