Моделі паралельних обчислень у паралельному програмуванні

Размещено на http://www.allbest.ru/

Луганський національний університет ім. Тараса Шевченко

МОДЕЛІ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ У ПАРАЛЕЛЬНОМУ ПРОГРАМУВАННІ

Козуб Галина Олександрівна канд. техн. наук, доцент,

доцент кафедри інформаційних технологій та систем

Козуб Владислав Юрійович PhD, асистент

кафедри математики та інформатики

м. Полтава

Анотація

У статті розглянуто моделі паралельних обчислень, описано загальновизнані структури паралельного програмування: OpenMP, MPI. OpenMP є стандартом для паралельного програмування в системах зі спільною пам'яттю. MPI є промисловим стандартом для систем розподіленої пам'яті. Розглянуто та наведено аналіз характеристики та продуктивність парадигм при правильному виборі інструменту Ключові слова: MPI, OpenMP, UMA, SMP, SPMD, MPMD

Виклад основного матеріалу

При розв'язанні завдань, що вимагають інтенсивної обробки даних або значних обчислень, розроблено ефективні алгоритми для їх вирішення. Для обробки даних використовують високопродуктивні обчислювальні ресурси з паралельними та розподіленими обчислювальниими технологіями.

Технологія паралельних та розподілених обчислень зосереджується на максимізації внутрішнього паралелізму за допомогою багатоядерних/багатопроцесорних систем та мережевих обчислювальних ресурсів [1]. Було розроблено різні архітектури обчислювальних систем та методи апаратного забезпечення, такі як архітектура симетричного мультипроцесора (SMP), архітектура нерівномірного доступу до пам'яті (NUMA), архітектура одночасної багатопотокової обробки (SMT), архітектура однієї інструкції з кількома даними (SIMD), графічний процесор (GPU), загальнопризначений графічний процесор (GPGPU) та суперскалярний процесор [2].

Для ефективного використання можливостями апаратного забезпечення розроблено паралельні та розподілені програми [3] з різноманітними технологіями програмного забезпечення. Проведемо аналіз дослідження продуктивності фреймворків паралельного програмування: OpenMP, MPI та MapReduce. Порівняльні дослідження проведені для двох наборів задач: проблема всіх пар найкоротшого шляху та проблема об'єднання для великих наборів даних. OpenMP [4] -- це фактично стандартна модель із систем спільної пам'яті, MPI [5] -- фактично стандарт для систем розподіленої пам'яті, а MapReduce визнано фактично стандартною структурою, призначеною для обробки великих даних. Для кожної задачі представлено паралельні програми за моделями та проведено спостереження за їх продуктивністю. паралельний програма пам'ять багатопроцесорний

В архітектурах пам'яті з паралельними обчисленнями існує спільна пам'ять, розподілена пам'ять і гібридна спільно розподілена пам'ять. Архітектури спільної пам'яті дозволяють усім процесорам отримувати доступ до всіх пам'ятів як глобального простору пам'яті. Зазвичай їх класифікують як універсальний доступ до пам'яті (UMA) і NUMA. Машини UMA зазвичай називають SMP і передбачають, що всі процесори ідентичні. Машини NUMA часто організовуються шляхом фізичного з'єднання двох або більше SMP, у яких не всі процесори мають однаковий час доступу до всіх пам'яті.

У архітектурі розподіленої пам'яті процесори мають власну пам'ять, але немає глобального адресного простору для всіх процесорів. Вони мають комунікаційну мережу для з'єднання пам'яті процесорів.

Гібридна спільно розподілена пам'ять використовує як спільну, так і розподілену архітектуру пам'яті. У кластерах багатоядерних або багатоядерних процесорів ядра процесора спільно використовують свою пам'ять, а кілька машин зі спільною пам'яттю об'єднані в мережу для переміщення даних з однієї машини на іншу.

Існує кілька моделей паралельного програмування, які дозволяють користувачам вказувати паралелізм і локальність на високому рівні: потоки, передача повідомлень, паралельні дані та моделі кількох даних однієї програми (SPMD) і моделі кількох даних кількох програм (MPMD).

Модель потоків організовує важкий процес із кількома легкими потоками, які виконуються одночасно. Бібліотека потоків POSIX (така ж pthreads) [6] і OpenMP [4] є типовою реалізацією цієї моделі.

У моделі передачі повідомлень програма складається з набору завдань, які використовують власну локальну пам'ять, яка може бути розташована на одній машині або на певній кількості машин. Завдання обмінюються даними, надсилаючи та отримуючи повідомлення для виконання місії. MPI [5] є промисловим стандартом для передачі повідомлень.

Паралельна модель даних, яка також називається моделлю розділеного глобального адресного простору (PGAS), забезпечує кожному процесу перегляд глобальної пам'яті, навіть якщо пам'ять розподілена між машинами. Він розрізняє локальне та глобальне посилання на пам'ять під керуванням програміста. Компілятор і середовище виконання піклуються про перетворення віддаленого доступу до пам'яті в операції передачі повідомлень між процесами [1]. Існує кілька реалізацій паралельної моделі даних: Coarray Fortran, Unified Parallel C, X10 і Chapel.

Модель SPMD -- це парадигма програмування високого рівня, яка виконує ту саму програму з різними даними кілька разів. Ймовірно, це найбільш часто використовувана модель паралельного програмування для кластерів вузлів. Модель MPMD -- це парадигма програмування високого рівня, яка дозволяє виконувати декілька програм з різними даними. З появою графічного процесора загального призначення (GPGPU) були розроблені моделі гібридних паралельних обчислень для використання багатоядерного графічного процесора для виконання важких обчислень під керуванням головного потоку, що виконується на головному центральному процесорі.

Коли обсяг даних великий, вимогливий обсяг пам'яті може перешкоджати маніпуляції з ними та обробці. Для вирішення таких ситуацій були розроблені інфраструктури обробки великих даних, такі як Hadoop і Dryad, які використовують кілька розподілених машин. Hadoop MapReduce -- це модель програмування, яка абстрагує програму на дві фази Map і Reduce. Структура обчислення представляє орієнтований граф, у якому вершини відповідають завданням, а ребра є каналами передачі даних.

Для легкої розробки паралельних програм зі спільною пам'яттю використовують багатопрцесорну прикладну програму (АРІ): OpenMP [4]. Вона надає набір директив компілятора для створення потоків, синхронізації операцій і керування спільною пам'яттю поверх pthreads. Програми, що використовують OpenMP, скомпільовані в багатопотокові програми, у яких потоки спільно використовують той самий адресний простір пам'яті, і, отже, зв'язок між потоками може бути дуже ефективним.

Порівняно з використанням pthreads і змінними умовами, OpenMP набагато легше використовувати, оскільки компілятор піклується про перетворення послідовного коду в паралельний відповідно до директив [4]. Отже, програмісти можуть писати багатопотокові програми без серйозного розуміння механізму багатопоточності. Його середовище виконання підтримує пул потоків і надає набір бібліотек [2].

OpenMP використовує блочно-структурований підхід для перемикання між послідовними та паралельними розділами, який відповідає моделі розгалуження/з'єднання. При вході в паралельний блок один потік керування розбивається на деяку кількість потоків, і новий послідовний потік запускається, коли всі розділені потоки завершуються. Його директиви дозволяють дрібно керувати потоками. Він підтримується на різних платформах, таких як UNIX, LINUX і Windows, а також на різних мовах, таких як C, C++ і Fortran [4].

MPI - це специфікація бібліотеки передачі повідомлень, яка визначає розширену модель передачі повідомлень для паралельного розподіленого програмування в розподіленому обчислювальному середовищі [5]. Насправді це не конкретна реалізація середовища паралельного програмування, і було створено декілька реалізацій, таких як OpenMPI, MPICH і GridMPI [2]. У моделі MPI кожен процес має власний адресний простір і спілкується з іншими процесами для доступу до адресного простору інших. Програмісти відповідають за розподіл робочого навантаження та відображення завдань щодо того, які завдання має обчислювати кожен процес.

MPI забезпечує моделі зв'язку «точка-точка», колективні, односторонні та паралельні моделі зв'язку введення/виведення [5]. Зв'язок «точка-точка» дозволяє обмінюватися даними між двома відповідними процесами. Колективне спілкування -- це трансляція повідомлення від процесу всім іншим. Односторонні комунікації полегшують віддалений доступ до пам'яті без відповідного процесу на віддаленому вузлі. Доступні три односторонні бібліотеки для віддаленого читання, віддаленого запису та віддаленого оновлення [4]. MPI надає різноманітні бібліотечні функції для координації передачі повідомлень у різних режимах, як-от заблокована та розблокована передача повідомлень. Він може надсилати повідомлення розміром у гігабайти між процесами.

MPI реалізовано на різних платформах, таких як Linux, OS X, Solaris і Windows. Більшість реалізацій MPI використовують якесь мережеве сховище файлів. Як мережеве сховище файлів можна використовувати мережеву файлову систему (NFS) і Hadoop HDFS. Оскільки MPI є абстракцією високого рівня для паралельного програмування, програмісти можуть легко створювати програми паралельної та розподіленої обробки без глибокого розуміння основного механізму створення та синхронізації процесу. Щоб використовувати багатоядерність процесорів, процеси MPI можуть бути організовані так, щоб вони мали кілька потоків. Програми на основі MPI можуть виконуватися на одному комп'ютері або кластері комп'ютерів.

Дослідження продуктивності OpenMP, MPI розглянуто при вирішенні проблеми винаходу найкоротшого шляху між усіма парами вузлів у графі. Проблема виникає в сферах комунікаційних мереж, планування логістики, дизайну компонування, навігації тощо. Алгоритм Флойда-Воршалла є одним із найвідоміших алгоритмів для цієї проблеми, який ітеративно шукає найкоротші шляхи, розглядаючи проміжні вузли один за одним [7].

Висновки

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

Список використаних джерел

1. K. M. Lee and K. M. Lee, "Similar pair identification using locality-sensitive hashing technique," (2012) in Proceedings of 6th International Conference on Soft Computing and Intelligent Systems, and 13th International Symposium on Advanced Intelligence Systems (SCIS/ISIS '12), pp. 2117-2119.

2. J. Diaz, C. Munoz-Caro, and A. Nino, "A survey of parallel programming models and tools in the multi and many-core era," (2012), IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 8, pp. 1369-1386.

3. S. C. Ravela, "Comparison of shared memory based parallel programming models," (2010). Tech. Rep. MSC-2010-01, Blekinge Institute of Technology.

4. OpenMP Architecture Review Board, "OpenMP Application Program Interface," (2024), http://www.openmp.org/mp-documents/spec30.pdf

5. W. Gropp, S. Huss-Lederman, A. Lumsdaine et al., (1998), MPI: The Complete Reference, the MPI-2 Extensions, vol. 2, The MIT Press.

6. POSIX-IEEE Standards Association, (2024), URL: http://standards.ieee.org/develop/wg/POSIX.html. (дата звернення: 3.05.2024).

7. TH Cormen, CE Leiserson, RL Rivest і C. Stein, Introduction to Algorithms, (2009), MIT Press, 1292рр.

Размещено на Allbest.ru