Iphone
shpora.me - незаменимый помощник для студентов и школьников, который позволяет быстро создавать и получать доступ к шпаргалкам или другим заметкам с любых устройств. В любое время. Абсолютно бесплатно. Зарегистрироватся | Войти

* данный блок не отображается зарегистрированым пользователям и на мобильных устройствах

MPI -mike

Тема: Комутація і синхронізація в розподілених системах

Вступ

Реальні розподілені системи будуються зазвичай на основі якоїсь парадигми,  наприклад, «все кругом - це файли ». В якості парадигм обрані системи об'єктів, розподілені файлові системи, системи документів і системи узгодження.

До питань зв'язку процесів, реалізованої через передачу повідомлень чи викликів RPC, тісно прилягають і питання синхронізації процесів. Синхронізація необхідна процесам для організації спільного використання ресурсів, як от файли чи пристрої, а також для обміну даними.

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

Системи, в яких комп'ютери використовують пам'ять спільно, зазвичай називаються мультипроцесорі, а працюючі кожен зі своєю пам'яттю - мультиком - Пьютера. Основна різниця між ними полягає в тому, що мультипроцесори мають єдиний адресний простір , спільно використовуване усіма процесорами. Якщо один з процесорів записує, наприклад, значення 44 за адресою 1000, будь-який інший процесор , який після цього прочитає значення, що лежить за адресою 1000, отримає 44 . Всі машини задіють одну і ту ж пам'ять.

На відміну від таких машин в мультикомпьютерах кожна машина використовує свою власну пам'ять. Після того як один процесор запише значення 44 за адресою 1000, другий процесор, прочитавши значення, лежаче за адресою 1000, отримає те значення, яке зберігалося там раніше. Запис за цією адресою значення 44 іншим процесором ніяк не позначиться на вмісті його пам'яті.

  1. 1.     Синхронизация в розподілених системах

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

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

1.1.Алгоритм синхронізації логічного годинника

У централізованій однопроцесорній системі, як правило, важливо тільки відносний час і не важлива точність годинника. У розподіленій системі, де кожен процесор має власний годинник зі своєю точністю ходу, ситуація різко міняється: програми, що використовують час (наприклад, програми, подібні до команди make в UNIX, які використовують час створення файлів, чи програми, для яких важливо час прибуття повідомлень і тому подібне) стають залежними від того, годинником якого комп'ютера вони користуються. У розподілених системах синхронізація фізичних годинника (що показують реальний час) є складною проблемою, але з іншої сторони дуже часто в цьому немає ніякої необхідності: тобто процесам не треба, щоб в усіх машинах був правильний час, для них важливо, щоб воно було скрізь однакове, більше того, для деяких процесів важливий тільки правильний порядок подій. У цьому випадку ми маємо справу з логічними годинами.

Введемо для двох довільних подій відношення "сталося до". Вираження a ® b читається "a сталося до b" і означає, що усі процеси в системі вважають, що спочатку сталася подія a, а потім - подія b. Відношення "сталося до" має властивість транзитивності: якщо вирази a ® b і b ® c істинні, то справедливо і вираження a ® c. Для двох подій одного і того ж процесу завжди можна встановити відношення "сталося до", аналогічно може бути встановлено це відношення і для подій передачі повідомлення одним процесом і прийомом його іншим, оскільки прийом не може статися раніше відправки. Проте, якщо дві довільних події сталися в різних процесах на різних машинах, і ці процесів не мають між собою ніякому зв'язку (навіть непрямою через треті процеси), то не можна сказати з повною визначеністю, яке з подій сталося раніше, а яке пізніше.

Ставиться завдання створення такого механізму ведення часу, який би для кожної події а міг вказати значення часу Т(а), з яким би були згідні усі процеси в системі. При цьому повинно виконуватися умова: якщо а ® b, то Т(а)<Т(b). Крім того, час може тільки збільшуватися і, отже, будь-які коригування часу можуть виконуватися тільки шляхом додавання позитивних значень, і ніколи - шляхом віднімання.

Розглянемо алгоритм рішення цього завдання, який запропонував Lamport. Для відміток часу в нім використовуються події. На рисунку 1 показані три процеси, що виконуються на різних машинах, кожна з яких має свій годинник, що йде зі своєю швидкістю. Як видно з рисунка 1, коли годинник процесу 0 показали час 6, в процесі 1 годинник показував 8, а в процесі 2 - 10. Передбачається, що усі ці годинники йдуть з постійною для себе швидкістю.

У момент часу 6 процес 0 посилає повідомлення А процесу 1. Це повідомлення приходить до процесу 1 в момент часу 16 по його годиннику. У логічному сенсі це цілком можливо, оскільки 6<16. Аналогічно, повідомлення. В, послане процесом 1 процесу 2 прийшло до останнього в момент часу 40, тобто його передача зайняла 16 одиниць часу, що також є правдоподібним.

 

Рис. 1. Синхронізація логічного годинника 

а - три процеси, кожен зі своїми власними годинами; 
би - алгоритм синхронізації логічного годинника

Ну а далі починаються дуже дивні речі. Сполучення З від процесу 2 до процесу 1 було відправлено у момент часу 64, а поступило в місце призначення в момент часу 54. Очевидно, що це неможливо. Таким ситуаціям необхідно запобігати. Рішення Lamport 'а витікає безпосередньо із стосунків "сталося до". Так як З було відправлено у момент 60, то воно повинне дійти у момент 61 або пізніше. Отже, кожне повідомлення повинне нести з собою час свого відправлення по годиннику машини-відправника. Якщо в машині, що отримала повідомлення, годинник показують час, який менше часу відправлення, то цей годинник переводяться вперед, так, щоб вони показали час, більший часу відправлення повідомлення. На рисунку 1 , би видно, що З поступило в момент 61, а повідомлення D - в 70.

Цей алгоритм задовольняє сформульованим вище вимогам.

1.2. Алгоритми взаємного виключення

Системи, що складаються з декількох процесів, часто легше програмувати, використовуючи так звані критичні секції. Коли процесу треба читати або модифікувати деякі структури даних, що розділяються, він передусім входить в критичну секцію для того, щоб забезпечити собі виняткове право використання цих даних, при цьому він упевнений, що ніякий процес не матиме доступу до цього ресурсу одночасно з ним. Це називається взаємним виключенням. У однопроцесорних системах критичні секції захищаються семафорами, моніторами і іншими аналогічними конструкціями. Розглянемо, які алгоритми можуть бути використані в розподілених системах.

1.2.1 Централізований алгоритм

Найбільш очевидний і простий шлях реалізації взаємного виключення в розподілених системах - це застосування тих же методів, які використовуються в однопроцесорних системах. Один з процесів вибирається в якості координатора (наприклад, процес, що виконується на машині, що має найбільше значення мережевої адреси). Коли який-небудь процес хоче увійти в критичну секцію, він посилає сполучення із запитом до координаторові, оповіщаючи його про те, в яку критичну секцію він хоче увійти, і чекає від координатора дозвіл. Якщо у цей момент ні один з процесів не знаходиться в критичній секції, то координатор посилає відповідь з дозволом. Якщо ж деякий процес вже виконує критичну секцію, пов'язану з цим ресурсом, то ніяка відповідь не посилається; що просив процес ставиться в чергу, і потім звільнення критичної секції йому вирушає відповідь-дозвіл. Цей алгоритм гарантує взаємне виключення, але внаслідок своєї централізованої природи володіє низькою відмовостійкістю.

1.2.2. Розподілений алгоритм

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

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

Процес може увійти до критичної секцію тільки у тому випадку, якщо він отримав відповіді повідомлення-дозволи від усіх інших процесів. Коли процес покидає критичну секцію, він посилає дозвіл усім процесам зі своєї черги і виключає їх з черги.

1.2.3. Алгоритм Token Ring

Абсолютно інший підхід по досягненню взаємного виключення в розподілених системах ілюструється рисунок 2. Усі процеси системи утворюють логічне кільце, тобто кожен процес знає номер своєї позиції в кільці, а також номер найближчого до йому наступного процесу. Коли кільце ініціалізувалося, процесу 0 передається так званий токен. Токен циркулює по кільцю. Він переходить від процесу n до процесу n+1 шляхом передачі повідомлення за типом "точка-точка". Коли процес отримує токен від свого сусіда, він аналізує, чи не вимагається йому самому увійти до критичної секції. Якщо так, то процес входить в критичну секцію. Після того, як процес вийде з критичної секції, він передає токен далі по кільцю. Якщо ж процес, що прийняв токен від свого сусіда, не зацікавлений у входженні в критичну секцію, то він відразу відправляє токен в кільце. Отже, якщо жоден з процесів не бажає входити в критичну секцію, то в цьому випадку токен просто циркулює по кільцю з високою швидкістю.

Порівняємо ці три алгоритми взаємного виключення. Централізований алгоритм є найбільш простим і найбільш ефективним. При його використанні вимагається тільки три повідомлення для того, щоб процес увійшов і покинув критичну секцію: запит і повідомлення-дозвіл для входу і повідомлення про звільнення ресурсу при виході. При використанні розподіленого алгоритму для одного використання критичній секції потрібно послати (n - 1) повідомлень-запитів (де n - число процесів) - по одному на кожен процес і отримати (n - 1) повідомлень-дозволів, тобто усього необхідно 2(n - 1) повідомлень. У алгоритмі Token Ring число повідомлень змінно: від 1 у разі, якщо кожен процес входив в критичну секцію, до нескінченно великого числа, при циркуляції токена по кільцю, в якому жоден процес не входив в критичну секцію.

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

 

Рис2. Засоби взаємного виключення в розподілених системах 
а - неврегульована група процесів в мережі; 
би - логічне кільце, утворене програмним забезпеченням

1.3. Неділимі транзакції

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

Модель неділимої транзакції прийшла з бізнесу. Уявіть собі переговорний процес двох фірм про продажу-купівлі деякого товару. В процесі переговорів умови договори можуть багаторазово мінятися, уточнюватися. Поки договір ще не підписаний обома сторонами, кожна з них може від нього відмовитися. Але після підписання контракту угода (transaction) повинна бути виконана.

Комп'ютерна транзакція повністю аналогічна. Один процес оголошує, що він хоче почати транзакцію з одним або більше процесами. Вони можуть деякий час створювати і знищувати різні об'єкти, виконувати які-небудь операції. Потім ініціатор оголошує, що він хоче завершити транзакцію. Якщо усі з ним погоджуються, то результат фіксується. Якщо один або більше процесів відмовляються (чи вони потерпіли крах ще до вироблення згоди), тоді змінені об'єкти повертаються точно до того стану, в якому вони знаходилися до початку виконання транзакції. Така властивість "все-или-ничего" полегшує роботу програміста.

Для програмування з використанням транзакцій потрібно деякий набір примітивів, які мають бути надані програмістові або операційною системою, або мовою програмування. Приклади примітивів такого роду:

BEGIN_TRANSACTION

 

команди, які йдуть за цим примітивом, формують транзакцію.

END_TRANSACTION

 

завершує транзакцію і намагається зафіксувати її.

ABORT_TRANSACTION

 

перериває транзакцію, відновлює попередні значення.

READ

 

читає дані з файлу (чи іншого об'єкту)

WRITE

 

пише дані у файл (чи інший об'єкт).

Перші два примітиви використовуються для визначення меж транзакції. Операції між ними є тілом транзакції. Або усі вони повинні бути виконані, або жодна з них. Це може бути системний виклик, бібліотечна процедура або група операторів мови програмування, ув'язнений в дужки.

Транзакції мають наступні властивості: впорядкування, неподільність, постійність.

Впорядкованість гарантує, що якщо дві або більше транзакції виконуються в один і те й же час, то кінцевий результат виглядає так, як якби усі транзакції виконувалися послідовно в деякому (у залежності від системи) порядку.

Неподільність означає, що коли транзакція знаходиться в процесі виконання, то ніякий інший процес не бачить її проміжні результати.

Постійність означає, що після фіксації транзакції ніякий збій не може відмінити результатів її виконання.

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

Розглянемо деякі підходи до реалізації механізму транзакцій.

Відповідно до першого підходу, коли процес починає транзакцію, те він працює в індивідуальному робочому просторі, що містить усі файли і інші об'єкти, до яким він має доступ. Поки транзакція не зафіксується або не урветься, усі зміни даних відбуваються в цьому робочому просторі, а не в "реальному", під яким ми розуміємо звичайну файлову систему. Головна проблема цього підходу полягає у великих накладних витратах по копіюванню великого об'єму даних в індивідуальний робочий простір, хоча і є декілька прийомів зменшення цих витрат.

Другий загальний підхід до реалізації механізму транзакцій називається списком намірів. Цей метод полягає в тому, що модифікуються самі файли, а не їх копії, але перед зміною будь-кого блоку робиться запис в спеціальний файл - журнал реєстрації, де відзначається, яка транзакція робить зміни, який файл і блок змінюється і які старі і нові значення змінюваного блоку. Тільки потім успішному запису в журнал реєстрації робляться зміни в початковому файлі. Якщо транзакція фіксується, то і про це робиться запис в журнал реєстрації, але старі значення змінених даних зберігаються. Якщо транзакція уривається, то інформація журналу реєстрації використовується для приведення файлу в початкове стан, і ця дія називається відкатом.

У розподілених системах фіксація транзакцій може зажадати взаємодії декількох процесів на різних машинах, кожна з яких зберігає деякі змінні, файли, бази даних. Для досягнення властивості неподільності транзакцій в розподілених системах використовується спеціальний протокол, званий протоколом двофазної фіксації транзакцій. Хоча він і не є єдиним протоколом такого роду, але він найширше використовується.

Суть цього протоколу полягає в наступному. Один з процесів виконує функції координатора (рисунок 3.). Координатор починає транзакцію, роблячи запис про це у своєму журналі реєстрації, потім він посилає усім підлеглим процесам, що також виконують цю транзакцію, повідомлення "підготуватися до фіксації". Коли підпорядковані процеси отримують це повідомлення, то вони перевіряють, чи готові вони до фіксації, роблять запис у своєму журналі і посилають координаторові повідомлення-відповідь "готова до фіксації". Після цього підпорядковані процеси залишаються в стані готовності і чекають від координатора команду фіксації. Якщо хоч би один з підлеглих процесів не відгукнувся, то координатор відкочує підпорядковані транзакції, включаючи і ті, які підготувалися до фіксації.

Виконання другої фази полягає в тому, що координатор посилає команду "фіксувати" (commit) усім підпорядкованим процесам. Виконуючи цю команду, останні фіксують зміни і завершують підлеглі транзакції. В результаті гарантується одночасне синхронне завершення (вдале або невдале) розподіленої транзакції.

 

Рис. 3Двофазний протокол фіксації транзакції

 

1.4. Синхронізація годин

В централізованих системах час визначається однозначно. Якщо процесу необхідно час , він організовує системний виклик, і ядро видає йому відповідь. Якщопроцес Л запрошувати час , а трохи пізніше те ж саме робить процес J3, значення, яке отримає 5, буде більше (або, можливо, так само) значенню, отриманому. А воно не може бути менше.

У розподілених системах досягнення домовленості про час не настільки тривіально. Для того щоб зрозуміти, до чого можуть призвести проблеми визначення глобального часу, достатньо одного прикладу з програмою зробити операційної системи UNIX. Зазвичай в UNIX великі програми розбиваються на кілька файлів вихідного тексту, і внесення змін в один з цих файлів вимагає повторної компіляції не всіх, а тільки одного з цих файлів такий підхід значно підвищує продуктивність роботи програмістів. Наприклад, якщо програма містить 100 файлів, а виправлений був тільки один, досить перекомпілювати тільки цей файл.

Звичайна методика застосування програми роблять просто, коли програміст закінчує свою роботу, змінивши всі файли з текстом програми, він запускає програму, яка перевіряє час останньої модифікації всіх файлів

з вихідним текстом і всіх об'єктних файлів програми. Якщо файл з вихідним

текстом input.c має час останньої модифікації 2151, а відповідний йому об'єктний файл input.o - 2150, вважає, що input.c з часу створення input.o був змінений, і перекомпілюються його. З іншого боку, якщо output.c має час останньої модифікації 2144, а output.o - 2145, компіляція не потрібно. Таким чином, програма перевіряє всі файли з вихідним текстом у пошуках тих з них, які потребують повторної компіляції, викликаючи при необхідності компілятор.

Уявімо тепер, що станеться, якщо в розподіленої системи відсутня глобальна угода про час. Припустимо, що output.o, як і раніше.має відмітку часу зміни 2144, а output.c після створення був модифікований, але отримав відмітку часу 2143, тому що годинник на машині, де він знаходиться, трохи запізнюються, як це показано на рис. 4. тоді програма не стане викликати компілятор. В результаті виконуваний файл програми міститиме суміш об'єктних файлів зі старих і нових вихідних файлів. При виконанні це легко може привести до помилок, і програміст зійде з розуму, намагаючись зрозуміти, що в його коді не так.

 

Рис.4. Коли кожна з машин має власні годинник, подія, що відбулася пізніше

1.5. Логічний годинник

У багатьох випадках необхідно, щоб всі машини домовилися про використання одного і того ж часу. Не настільки вже й важливо, щоб цей час збігався з істинним часом, який кожну годину оголошують по радіо. Для роботи програми, достатньо, щоб всі машини вважали, що зараз 10:00, навіть якщо насправді зараз 10:02. Так, для деякого класу алгоритмів подібна внутрішня несуперечливість має набагато більше значення, ніж те, наскільки їх час близько до реального. Для таких алгоритмів прийнято говорити про логічний годиник.

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

і не створить проблем. Крім того, він вказав, що зазвичай має значення не точний час виконання процесів, а його порядок. У прикладі з програмою, нас цікавило, щоб файл input.c був більш старим або більш новим , ніж input.o, а не абсолютний час їх створення.

1.6. Розподілені транзакції

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

2.     Коммунікація в розподілених системах

Всі комп'ютери в розподіленій системі пов'язані між собою комунікаційною мережею. Комунікаційні мережі поділяються на широкомасштабні (Wide Area Networks, WANs) і локальні (Local Area Networks, LANs).

А) Широкомасштабні мережі

WAN складається з комунікаційних ЕОМ, пов'язаних між лініями, собою комунікаційними лініями (телефонні радіолінії, супутникові канали, оптоволокно) і забезпечують транспортування повідомлень. Зазвичай використовується техніка store-and-forward.

Б) Локальні мережі.

Особливості LAN:

• географічна область охоплення невелика (будівлю або декілька будівель);

• висока швидкість передачі (10-100 Mbps);

• мала ймовірність помилок передачі.

2.1.         Комутація пакетів чи комутація ліній.

Комутація ліній (телефонні розмови) вимагає резервування ліній на час всього сеансу спілкування двох пристроїв.

Пакетна комутація заснована на розбитті повідомлень в пункті відправлення на порції (пакети), посилці пакетів за адресою призначення, і збірці повідомлення з пакетів в пункті призначення. При цьому лінії використовуються ефективніше, повідомлення можуть передаватися швидше, але потрібна робота по розподіленню і збірці повідомлень, а також можливі затримки (для передачі мови або музики такий метод не годиться).

2.2.         Віддалений виклик процедури

           Send, receive - підхід введення/виведення Більш природний підхід, який застосовується в централізованих ЕОМ - виклик процедур.

Birrell and Nelson ( 1984 ) ( незалежно і раніше - Ілюшин А.І. , 1978 ) запропонували дозволити викликає програмі перебувати на інший ЕОМ .

MPP з розподіленою пам'яттю може розглядатися як окремий випадок локальної мережі. Решітка транспьютерів, в якій кожен транспьютер паралельно з обчисленнями може обмінюватися одночасно по 8 каналах з 4 сусідами, є гарним прикладом, для якого будуть зформулюватися різні екзаменаційні завдання. Час передачі повідомлення між двома вузлами транспьютерном матриці ( характеристики апаратури - час старту передачі Ts, час передачі одного байта інформації сусіднього вузла Tb, процесорні операції, включаючи читання з пам'яті і запис в пам'ять вважаються нескінченно швидкими ). За час Ts + Tb транспьютер може передати 1 байт інформації своїм чотирьом сусідам і прийняти від них 4 байта інформації ( по одному байту від кожного). Конвеєризация і паралельне використання декількох маршрутів.

2.2.1. Обмін повідомленнями між прикладними процесами
SEND, RECEIVE (адресат/відправникь, [тег], адрес памяті, довжина)

Адресація - фізичний/логічний номер процесора, унікальний ідентифікатор динамічно створюваного процесу, служба імен (сервер імен або широкомовлення - broadcasting). Зазвичай пересилання в сусідній комп'ютер вимагає три копіювання - з пам'яті процесу - відправника в буфер ОС на своєму комп'ютері, пересилання між буферами ОС, копіювання в пам'ять процесу - одержувача .

Блокуючі операції send - до звільнення пам'яті з даними або до завершення фактичної передачі.

Буферизованих і небуферізуемие  rendezvous або з втратою інформації при відсутності receive.

Надійні і ненадійні

2.3. MPI - Message-Passing Interface

(1) Цілі:

• Створити інтерфейс прикладного програмування (не тільки для компіляторів або бібліотек реалізації систем);

• Забезпечити можливість ефективних комунікацій (уникнути копіювання з пам'яті в пам'ять, дозволити суміщення обчислень і комунікацій або розвантаження на комунікаційний процесор там, де він є);

• Дозволити розширення для використання в гетерогенному середовищі;

• Виходити з надійності комунікацій (користувач не повинен боротися з комунікаційними збоями - це справа комунікаційних підсистем нижнього рівня);

• Визначити інтерфейс, який би не надто відрізнявся від використовуваних в даний час, таких як PVM , Express, P4;

• Визначити інтерфейс, який міг би швидко бути реалізований на багатьох продаваних платформах без серйозної переробки небажаного комунікаційного та системного ПЗ.

(2) Що включено в MPI?

• Комунікації точка-точка;

• Колективні операції;

• Групи процесів;

• Комунікаційні контексти;

• Простий спосіб створення процесів для моделі SPMD (одна програма використовується для обробки різних даних на різних процесорах);

• Топологія процесів.

(3) Що не включено в MPI?

• Явні операції з пам'яттю;

• Операції, які вимагають більше підтримки від операційних систем, ніж діючі в даний час стандарти на ОС (наприклад, отримання повідомлень через механізм переривань, активні повідомлення);

• Допоміжні функції, такі як таймери.

 (4) Деякі поняття 
Комунікаційні операції можуть бути:

• неблокующі - якщо повернення здійснюється до завершення операції;

• блокующі - якщо повернення означає, що користувач може використовувати ресурси (наприклад, буфера), зазначені у виклику.

(5) Групи, контексти, комунікатори.

Група - впорядкована (від 0 до рангу групи) велика кількість ідентифікаторів процесів (тобто процесів). Групи служать для вказівки адресата при посилці повідомлень (процес - адресат представляє свій номер у групі), визначають виконавців колективних операцій. Є потужним засобом функціонального розпаралелювання - дозволяють розділити групу процесів на кілька підгруп, кожна з яких повинна виконувати свою паралельну процедуру. При цьому істотно спрощується проблема адресації при використанні паралельних процедур.

Контекст - область видимості для повідомлень, аналогічне області видимості змінних в разі вкладених викликів процедур. Повідомлення, послані в деякому контексті, можуть бути прийняті тільки в цьому ж контексті. Контексти - також важливі засоби підтримки паралельних процедур.

Комунікатори - дозволяють обмежити область видимості (життя, визначення) повідомлень рамками певної групи процесів, тобто можуть розглядатися як пара - група і контекст. Крім того, вони служать і для цілей оптимізації, зберігаючи необхідні для цього додаткові об'єкти. Є зумовлені комунікатори (точніше, створювані при ініціалізації MPI -системи):

• MPI_COMM_ALL - всі процеси

• MPI_COMM_PEER - все, крім головного процесу

(6) Операції над групами (локальні, без обміну повідомленями).

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

(7) Точні коммунікації.

Основні операції send, receive. Операцію можуть бути блокуючі і не блокуючі. В операції send задається:

• адреса буфера в пам'яті;

• кількість посилаються елементів;

• тип даних кожного елемента;

• номер процесу - адресата в його групі ;

• тег повідомлення;

• комунікатор.

В операції receive задається :

• адреса буфера в пам'яті;

• кількість посилаються елементів;

• тип даних кожного елемента;

• номер процесу - адресата в його групі ( або будь-який) ;

• тег повідомлення ( або будь-який) ;

• комунікатор ;

• статус ( джерело і тег , необхідні в тому випадку, коли вони невідомі - при їх завданні за допомогою шаблону будь-який) .

Передбачена конвертація даних при роботі в гетерогенному середовищі. Є чотири режими комунікацій - стандартний, буферизованих , синхронний і режим готовності.

У стандартному режимі послідовність видачі операцій send і receive довільна, операція send завершується тоді, коли повідомлення вилучено з пам'яті і вона вже може використовуватися процесом. При цьому виконання операції може здійснюватися незалежно від наявності receive, або вимагати наявність ( питання реалізації MPI). Тому операція вважається нелокальною.

У буферизованому режимі послідовність видачі операцій send і receive довільна, операція send завершується тоді, коли повідомлення вилучено з пам'яті і поміщено в буфер. Якщо місця в буфері немає - помилка програми (але є можливість визначити свій буфер). Операція локальна.

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

У всіх чотирьох режимах операція receive завершується після отримання повідомлення в заданий користувачем буфер прийому.

Неблокуючі операції не зупиняють процес до свого завершення, а повертають посилання на комунікаційний об'єкт, що дозволяє опитувати стан операції або чекати її закінчення. Є операції перевірки вступників процесу повідомлень, без читання їх в буфер (наприклад, для визначення довжини повідомлення та запиту потім пам'яті під нього ). Є можливість аварійно завершувати видані неблокуючий операції, і тому надані можливості перевірки, чи добре завершилися операції. Мається складова операція send - receive, що дозволяє уникнути труднощів з порядком видачі окремих операцій в обмінювальних між собою процесах. Для окремого випадку обміну даними одного типу і довжини пропонується спеціальна операція повідомлення (send - receive - replace), в якій для посилки і прийому використовується один буфер.

(8) Колективні комунікації.
Для забезпечення колективних комунікацій введені наступні функції:

• бар'єр для всіх членів групи (BARRIER) ;

• передача повідомлення всім членам групи від одного (BROADCAST);

• збір даних від усіх членів групи для одного (GATHER) ;

• розсилка даних всім членам групи від одного (SCATTER) ;

• збір даних від усіх членів групи для всіх (ALLGATHER) ;

• розсилка даних всім членам групи від всіх (ALLTOALL) ;

• глобальні операції, коли результат передається всім членам групи або тільки одному. При цьому користувач може сам визначити глобальну операцію – функцію.

Схема переміщення даних між 4 процесами

 

Назви функцій та параметри:
MPI_BARRIER(IN comm)
MPI_BCAST(IN/OUT buffer, IN cnt, IN type, IN root, IN comm)
MPI_GATHER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf, IN recvcnt, IN recvtype, IN root, IN comm)
MPI_SCATTER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf, IN recvcnt, IN recvtype, IN root, IN comm)
MPI_ALLGATHER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf, IN recvcnt, IN recvtype, IN comm)
MPI_ALLTOALL(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf, IN recvcnt, IN recvtype, IN comm)

2.4. PVM (Parallel Virtual Machine)

Широко відома система PVM [5] була створена для об'єднання декількох пов'язаних мережею робочих станцій у єдину віртуальну паралельну ЕОМ. Система являє собою надбудову над операційною системою UNIX і використовується в даний час на різних апаратних платформах, включаючи і ЕОМ з масовим паралелізмом.

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

Переваги - простота, наявність наследованного від OS UNIX апарату процесів і сигналів, а також можливість динамічного додавання до групи новостворених процесів .

Недоліки - низька продуктивність і функціональна обмеженість (наприклад, є тільки один режим передачі повідомлень - з буферизацією ).

2.5. MPI - 2 (1997 р.)

Розвиває MPI в наступних напрямках:

• Динамічне створення і знищення процесів (важливо для роботи в мережах ЕОМ).

• Односторонні комунікації та засоби синхронізації для організації взаємодії процесів через загальну пам'ять (для ефективної роботи на системах з безпосереднім доступом процесорів до пам'яті інших процесорів).

• Паралельні операції вводу-виводу (для ефективного використання існуючих можливостей паралельного доступу багатьох процесорів до різних дисковим пристроїв ).

2.6. Беступікова комутація пакетів

ПОВІДОМЛЕННЯ (пакети), які подорожують через мережу з комутацією пакетів посані зберігатися в шкірному вузлі перед тим, відправленням до настуного Вузла на шляху до адресата. Кожен вузол мережі для цієї мети резервує певний буфер. Оскількі кількість буферного місця звичайній в шкірному вузлі , можуть виникнуть ситуації, коли ніякого пакета не може бути послано того, що всі буфери в наступному вузлі зайняті.

КОЖЕН з чотирьох вузлів має буфера. Bкожен з яких може містити точно один пакет. Вузол s пославши t пакетів з адресатом v, і вузол v пославши u пакетів з адресатом s. Всі буфера в u и v тепер зайняті, І, отже, жоден з пакетів, збереження в t и u НЕ може бути послань до адресата. Ситуації, коли група пакетів ніколи не може досягти їх адресата, тому що всі чекають буфера.

ВАЖЛИВА проблема в проектуванні мереж з пакетною комутацією - що робити з тупиками. Два види методів, базуються на структурованій і неструктурованій буферних накопичувачів.

Троллер як алгоритм, дозволяє або забороняє різні рухи в мережі у відповідності з наступний вимогами:

( 1 ) Виведення пакета ( в місці его призначення ) зажди дозволяється.

( 2 ) Генерація пакета в вершині, в якій всі буфери порожні, завжди дозволяються.

( 3 ) Контролер використовую тільки локальну інформацію, тобто, рішення, може чи пакет бути чинний у вершині u, залежить тільки від інформації, містіться в пакеті .

Контролер con дозволяє генерацію пакета p в вершині u , де стан u - cu, тоді і тільки тоді, коли (cu, p) ∈ Genu, и дозволяє Просування пакету p зu в w тоді і тільки тоді, коли (cw , p) ∈ Forw.

Висновки

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

До питань зв'язку процесів, реалізованої через передачу повідомлень чи викликів RPC, тісно прилягають і питання синхронізації процесів. Синхронізація необхідна процесам для організації спільного використання ресурсів, як от файли чи пристрої, а також для обміну даними.

Системи, в яких комп'ютери використовують пам'ять спільно, зазвичай називаються мультипроцесорі, а працюючі кожен зі своєю пам'яттю - мультиком - Пьютера. Основна різниця між ними полягає в тому, що мультипроцесори мають єдиний адресний простір , спільно використовуване усіма процесорами. Якщо один з процесорів записує, наприклад, значення

44 за адресою 1000, будь-який інший процесор , який після цього прочитає

значення, що лежить за адресою 1000, отримає 44 . Всі машини задіють одну і ту ж пам'ять.

На відміну від таких машин в мультикомпьютерах кожна машина використовує свою власну пам'ять. Після того як один процесор запише значення 44 за адресою 1000, другий процесор, прочитавши значення, лежаче за адресою 1000, отримає те значення, яке зберігалося там раніше. Запис за цією адресою значення 44 іншим процесором ніяк не позначиться на вмісті його пам'яті.

Отже комутація і синхронізація в розподілених системах тісно між собою пов’язані. Тобто між цими двома процесами є багато спільного але також між ними є розбіжності. Якщо можна так сказати то один без одного не може існувати.

6.2 Комунікаційні, колективні, глобальні обчислювальні операції над розподіленими даними.

Глобальні обчислювальні операції над розподіленими даними

У рівнобіжному програмуванні математичні операції над блоками даних, розподілених по процесорах, називають глобальними операціями редукції. У загальному випадку операцією редукції називається операція, аргументом якої є вектор, а результатом – скалярна величина, отримана застосуванням деякої математичної операції до всіх компонентів вектора. Зокрема, якщо компоненти вектора розташовані в адресних просторах процесів, що виконуються на різних процесорах, то в цьому випадку говорять про глобальну (рівнобіжної) редукції. Наприклад, нехай в адресному просторі всіх процесів деякої групи процесів маються копії перемінної var (необов'язково мають те саме значення), тоді застосування до неї операції обчислення глобальної чи суми, іншими словами, операції редукції SUM поверне одне значення, що буде містити суму всіх локальних значень цієї перемінної. Використання цих операцій є одним з основних засобів організації розподілених обчислень.

У MPI глобальні операції редукції представлені в декількох варіантах:

  • Зі збереженням результату в адресному просторі одного процесу      (MPI_Reduce). 
  •  Зі збереженням результату в адресному просторі всіх процесів (MPI_Allreduce). 
  • Префіксна операція редукції, що як результат операції повертає вектор. i-я компонента цього вектора є результатом редукції перших i компонент розподіленого вектора (MPI_Scan). 
  • Сполучена операція Reduce/Scatter (MPI_Reduce_scatter). 

Функція MPI_Reduce об’єднує  елементи вхідного буфера кожного процесу в групі, використовується операцію op , і повертає об’єднені  значення  вихідного буфера процесу з номером root. Операція глобальної редукції, зазначена параметром op, виконується над першими елементами вхідного буфера, і результат посилається в перший елемент буфера прийому процесу root. Потім тих же саме робиться для других елементів буфера і т.д.

int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, 

MPI_Op op, int root, MPI_Comm comm)


Малюнок

 Графічна інтерпретація операції Reduce.

Функція MPI_Allreduce зберігає результат редукції в адресному просторі всіх процесів, тому в списку параметрів функції відсутній ідентифікатор кореневого процесу root. В іншому, набір параметрів такий же, як і в попередній функції.

INT  MPI_Allreduce ( void *  sendbuf ,  void *  recvbuf ,  INT  Count ,  MPI_Datatype  datatype ,  MPI_Op  OP ,  MPI_Comm  COMM )

де sendbuf - адреса початку вхідного буфера, recvbuf - адреса початку буфера прийому, count - число елементів у вхідному буфері, datatype - тип елементів у вхідному буфері, op - операція, за якою виконується редукція, comm - комунікатор.

 Малюнок

Графічна інтерпретація операції Allreduce.

Функція MPI_Reduce_scatter поєднує в собі операції редукції і розподілу результату по процесах.

MPI_Reduce_scatter ( void *  sendbuf ,  void *  recvbuf ,  int  * recvcounts ,  MPI_Datatype  datatype ,  MPI_Op  op ,  MPI_Comm  comm )

де sendbuf - адреса початку вхідного буфера, recvbuf - адреса початку буфера прийому, revcount - масив, в якому задаються розміри блоків, що посилаються процесам, datatype - тип елементів у вхідному буфері, op - операція, за якою виконується редукція, comm - комунікатор.

 Малюнок

Графічна інтерпретація операції Reduce_scatter.

Функція MPI_Reduce_scatter  відрізняється від  MPI_Allreduce тим, що результат операції розрізається на непересічні частини по числу процесів у групі, i-а частина надсилається i-ому процесу в його буфер прийому. Довжини цих частин задає третій параметр, що є масивом.

 

Синхронізація

 Види синхронізації:

 

  • Бар'єр

 

  • Зазвичай означає, що беруть участь всі завдання
  • Кожне завдання виконує свою роботу, поки не досягне бар'єру. Потім воно зупиняється або "блокується".
  • Коли останнє завдання досягає бар'єру, всі завдання є синхронізованими.
  • Часто повинна бути виконана послідовна частина роботи. В інших випадках завдання автоматично продовжують свою роботу

 

  • Блокування / семафор

 

  • Може включати будь-яку кількість завдань
  • Як правило, використовується для серіалізації (захисту) доступу до глобальних даних або частини коду. Тільки одне завдання за раз може використовувати (володіти) блокування / семафор / прапорець.
  • Перше завдання, яке досягає блокування, «налаштовує» його. Тоді це завдання може безпечно (серійно) отримати доступ до захищених даних або коду.
  • Інші завдання можуть спробувати досягнути блокування, але повинні зачекати, поки завдання, яке володіє блокуванням, звільнить його.
  • Може бути блокуючим або не блокуючим.

 

  • Синхронні операції комунікації

 

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

 

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

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

Функція синхронізації процесів MPI_Barrier блокує роботу викликав її процесу до тих пір, поки всі інші процеси групи також не викличуть цю функцію. Завершення роботи цієї функції можливе тільки всіма процесами одночасно (всі процеси "долають бар'єр" одночасно).

INT  MPI_Barrier ( MPI_Comm  COMM )

де comm - комунікатор.

Синхронізація за допомогою бар'єрів використовується, наприклад, для завершення всіма процесами деякого етапу рішення задачі, результати якого використовуватимуться на наступному етапі. Використання бар'єру гарантує, що жоден з процесів не приступить завчасно до виконання наступного етапу, поки результат роботи попереднього не буде остаточно сформований. Неявну синхронізацію процесів виконує будь-яка колективна функція.

Комунікатор в MPI — це спеціально створюваний службовий об’єкт, що об’єднує в своєму складі групу процесів та ряд додаткових параметрів (контекст): парні операції передачі даних виконуються для процесів, що належать одному і тому ж комунікатору; колективні операції застосовуються одночасно для всіх процесів комунікатору.

Скористатися результатом не блокуючий комунікаційної операції або повторно використовувати її параметри можна тільки після її повного завершення. Є два типи функцій завершення неблокирующих операцій:

  1. Операції очікування завершення сімейства WAIT блокують роботу процесу до повного завершення операції.
  2. Операції перевірки завершення сімейства TEST повертають значення TRUE або FALSE залежно від того, завершилася операція чи ні. Вони не блокують роботу процесу і корисні для попереднього визначення факту завершення операції.

Функція очікування завершення не блокуючий операції MPI_Wait

int MPI_Wait (MPI_Request * request, MPI_Status * status)

 

request – запит обміну.

status – атрибути повідомлення.

Це нелокальна блокуюча операція. Повернення відбувається після завершення операції, пов'язаної із запитом request. У параметрі status повертається інформація про закінченою операції.

Функція перевірки завершення не блокуючий операції MPI_Test

int MPI_Test (MPI_Request * request, int * flag, MPI_Status * status)

 

request– запит обміну;

flag– ознака завершеності перевіреній операції;

status– атрибути повідомлення, якщо операція завершилася.

Це локальна не блокуючий операція. Якщо зв'язана із запитом request операція завершена, повертається flag = true, а status містить інформацію про завершеною операції. Якщо проверяемая операція не завершена, повертається flag = false, а значення status в цьому випадку не визначено.

Комутація

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

Способи комутації мереж, називаються мережі, в яких зв'язок між вузлами встановлюється тільки за запитом. Абоненти з'єднуються з комутаторами виділеними (індивідуальних) лініями зв'язку. Лінії зв'язку, які з'єднують комутатори, використовуються абонентами спільно.

Комутація може здійснюватися в двох режимах: динамічно і статично. У першому випадку комутація виконується на час сеансу зв'язку (зазвичай від секунд до годин) за ініціативою одного з вузлів, а по закінченні сеансу зв'язок розривається. У другому випадку комутація виконується обслуговуючим персоналом мережі на значно більше тривалий період часу (кілька місяців або років) і не може бути змінена за ініціативою користувачів.

Дві групи способів комутації: комутація каналів  (circuitswitchingі) комутація з проміжним зберіганням (store-and-forward). Друга група складається з двох способів: комутації повідомлень (messageswitchingі комутації пакетів(packetswitching).

комутації каналів між вузлами, яким необхідно встановити зв'язок один з одним, забезпечується організація безперервного складеного каналу, який складається з послідовно сполучених окремих каналів між вузлами. Окремі канали з'єднуються між собою коммутирующим обладнанням (комутаторами). Перед передачею даних необхідно виконати процедуру встановлення з'єднання, в процесі якої створюється складений канал.

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

комутації пакетів всі передані користувачем дані розбиваються передавальним вузлом на невеликі (до декількох кілобайт) частини - пакети (packet). Кожен пакет оснащується заголовком, в якому вказується, як мінімум, адреса вузла-одержувача та номер пакету. Передача пакетів по мережі відбувається незалежно один від одного. Комутатори такої мережі мають внутрішню буферну пам'ять для тимчасового зберігання пакетів, що дозволяє згладжувати пульсації трафіка на лініях зв'язку між комутаторами.

Обобщенная передача данных от всех процессов одному процессу

Операция обобщенной передачи данных от всех процессов одному процессу

(сбор данных) является двойственной к процедуре распределения данных.

 

Функція MPI_Gather виробляє складання блоків даних, що посилаються всіма процесами групи, в один масив процесу з номером root. Довжина блоків передбачається однаковою. Об'єднання відбувається в порядку збільшення номерів процесів-відправників. Тобто дані, послані процесом i з свого буфера sendbuf, поміщаються в i-ю порцію буфера recvbuf процесу root. Довжина масиву, в який збираються дані, повинна бути достатньою для їх розміщення.

Виробляє складання блоків даних, що посилаються всіма процесами групи, в один масив процесу з номером root.  Для выполнения этой операции в MPI предназначена функция:

 

int MPI_Gather(void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int root, MPI_Comm comm),

где

• sbuf, scount, stype —параметри відправлення повідомлення;

• rbufrcountrtype — параметри приймального повідомлення;

• root — ранг процеса, виконуваного збору данних;

• comm — комунікатор, в рамках якого виконується передача

данних.

 

 Малюнок

Графічна інтерпретація операції Gather.

 

Функція MPI_Allgather аналогічна функції MPI_Gather, але прийом здійснюється не в одному процесі з ідентифікатором root, а у всіх. При цьому кожен процес має специфічне вміст в передавальному буфері, але всі отримують однаковий вміст в буфері приймальному. Як і в MPI_Gather, приймальний буфер послідовно заповнюється елементами даних з усіх передавальних буферів.

 

 Малюнок

Графічна інтерпретація операції Allgather.

Функція MPI_Scatter розбиває повідомлення з буфера посилки процесу root на рівні частини розміром sendcount і посилає i-ю частину в буфер прийому процесу з номером

int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype,int root, MPI_Comm comm)

sendbuf – адреса початку розміщення блоків розподіляються даних (використовується тільки в процесі-відправника root)

sendcount – число елементів, що посилаються кожному процесу;

sendtype – тип посилаються елементів;

recvbuf – адреса початку буфера прийому;

recvcount – число одержуваних елементів;

recvtype – тип одержуваних елементів;

root – номер процесу-відправника;

comm – комунікатор.

 Малюнок

Графічна інтерпретація операції Scatter.

6.3 Комутація і синхронізація в розподілених системах

Розпаралелювання можна розділити на ручне та автоматичне.

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

Автоматичний параллелізатор зазвичай фокусується на таких керуючих конструкціях, як цикли, оскільки, в загальному випадку, більша частина виконання програми проходить всередині певних циклів. Компілятор намагається розділити цикл на частини так, щоб його окремі ітерації могли виконуватися на різних процесорах одночасно.

Компілятори проводять аналіз перед проведенням розпаралелювання, щоб відповісти на наступні питання:

  • Чи безпечно розпаралелювати даний цикл? Потрібен акуратний аналіз залежностей і аналіз незалежності покажчиків або аласів.
  • Чи варто розпаралелювати цикл? Відповідь на це питання вимагає надійної оцінки (моделювання) роботи програми та врахування властивостей паралельної системи.

Автоматичне розпаралелювання складно для компіляторів з причин:

  • Аналіз залежностей складний для коду, що використовує вказівники, рекурсію, віртуальні функції (заздалегідь невідомого класу).
  • Цикли можуть мати заздалегідь невідому кількість ітерацій, тому ускладнюється вибір циклів, що вимагають розпаралелювання.
  • Доступ до глобальних ресурсів важко координувати в термінах виділення пам'яті, вводу-виводу, поділюваних змінних.

Через складність повного автоматичного розпаралелювання існує кілька підходів для його спрощення:

  • Дати програмістам можливість додавати до програми підказки компілятору, щоб впливати на процес розпаралелювання (або щоб спростити аналізи, помітивши покажчики як непересічні або вказавши "гарячі" цикли).
  • Створити інтерактивну систему компіляції, в роботі якої брала б участь людина.
  • Додати в апаратуру спекулятивну багатопоточність.

 

Сучасні компілятори з підтримкою розпаралелювання:

  • Sun studio
  • Intel C + + Compiler
  • gcc
  • GHC

 

Важливо згадати, що для суперкомп’ютерів з розподільною пам’яттю використовуються або методи ручного або ж частково автоматичного розпаралелювання. Немає методів автоматичного розпаралелювання на суперкомп’ютераї з паралельною, а не розподіленою, пам’яттю, такої, як у суперкомп’ютера RP-3 чи суперкомп’ютера зі структурно-процедурною організацією обчислень.

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

  • можуть бути отримані неправильні результати;
  • продуктивність може реально знизитися;
  • набагато менша гнучкість, ніж при ручному розпаралелюванні;
  • обмежується підмножиною (в основному циклами) коду;
  • фактично може не розпаралелити код, якщо компіляторний аналіз покаже, що є уповільнювачі або код заскладний.

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

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

Приклад проблеми, що піддається розпаралелюванню:

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

Ця проблема може бути вирішена з використанням паралелізму. Кожна молекулярна структура є незалежно визначеною. Розрахунок структури з мінімальною енергією є також розпаралелюваною проблемою.

Приклад нерозпаралелюваної проблеми:

Обчислення послідовності Фібоначчі (0,1,1,2,3,5,8,13,21,...) шляхом використання формули:

F(n) = F(n-1) + F(n-2)

Це є нерозпаралелюваною проблемою, тому що розрахунок послідовності Фібоначчі, як видно, потребує залежних розрахунків, а не незалежних.

Розрахунок значення F(n) використовує значення і F(n-1), і F(n-2). Ці три вирази не можна обчислити самостійно, а, отже, і паралельно.

Ідентифікувати у програмі "гарячі точки":

  • Дізнатися, де буде виконана більша частина реальної роботи. Більшість наукових і технічних програм зазвичай виконують більшу частину роботи в декількох місцях. Тут можуть допомогти профайлери та інструменти аналізу продуктивності.
  • Зосередитися на розпаралелюванні "гарячих точок" і ігнорувати ті частини програми, на які припадає невелике використання ЦП.

Визначити вузькі місця у програмі:

  • Чи є області, які непропорційно повільні, або спричиняють зупинку чи затримку паралельної роботи? Наприклад, ввід/вивід, як правило, є чинником, що уповільнює програму.
  • Може бути можливість перебудувати програму або використовувати інший алгоритм, щоб зменшити або усунути непотрібні повільні ділянки.
  • Визначити уповільнювачів паралелізму. Одним загальним класом уповільнювачів є залежність даних, як показано вище послідовністю Фібоначчі.
  • Досліджувати інші алгоритми, якщо це можливо. Це може бути одним найбільш важливим фактором при проектуванні паралельних застосунків.
  • Скористатися стороннім оптимізованим паралельним програмним забезпеченням і високо оптимізованими математичними бібліотеками, доступними у провідних виробників.

Виділяють наступні етапи розробки паралельного алгоритму:

  • Декомпозиція.
  • Проектування комунікацій.
  • Нагромадження
  • Планування обчислень

 

 Одним з перших кроків в проектуванні паралельної програми є розбиття проблеми на дискретні "шматки" роботи, які можуть бути розподілені між кількома завданнями. Це називається декомпозицією або розділенням. На цьому етапі виконується аналіз задачі і оцінка можливостей розпаралелювання. Задачі і пов’язані з нею дані розподіляються на менші частини – під задачі і фрагменти структур даних. Особливості конкретної архітектури на даному етапі можна не враховувати.

Існують два основні способи розділити обчислювальну роботу між паралельними завданнями: доменна декомпозиція і функціональна декомпозиція.

Доменна декомпозиція:

Спершу фрагментуються дані, а потім алгоритм їх обробки. Дані розбиваються на фрагменти приблизно однакового розміру. З фрагментами даних зв’язуються операції їх обробки, з яких вже формуються підзадачі, а потім визначаються необхідні пересилки даних. Пересікання частин повинно бути зведене до мінімуму, щоб зменшити кількість дублювання даних. Спершу аналізуються структури даних найбільшого розміру чи ті, до яких найчастіше виконується звернення. Можливе використання як статичних так і динамічних схем декомпозиції структур.

Функціональна декомпозиція:

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

Ефективність декомпозиції забезпечується виконанням наступних рекомендацій:

  • Кількість задач після декомпозиції повинно бути значно більшим ніж кількість процесорів.
  • Слід уникати зайвих обчислень і пересилок даних.
  • Підзадачі повинні бути приблизно однакового розміру.
  • Сегментація повинна бути такою, щоб зі збільшенням об’єму задачі, кількість підзадач також зростало (при збереженні статичного розміру підзадачі).

Головною умовою декомпозиції є незалежність задачі. Існують такі види незалежності:

  • По даних – дані, що обробляються однією частиною програми, не модифікуються іншою.
  • По керуванню – порядок виконання частин програми може бути визначений тільки під час виконання програми         .
  • По ресурсах – виникає, якщо дві під задачі не виконуються запис в одну і ту ж змінну, а незалежність по вводу-виводу, якщо оператори вводу/виводу двох або більше під задач не звертаються до одного файлу (чи змінної).

Приклади функціональної декомпозиції:

  • Моделювання екосистеми 
    Кожна програма обчислює населення заданої групи, де приріст в кожній групі залежить від її сусідів. З проходженням часу кожен процес обчислює її поточний стан, а тоді обмінюється інформацією з сусідньою популяцією. Тоді на наступному часовому кроці всі завдання далі розвиваються у розрахунках стану.
  • Обробка сигналів 
    Набір даних звукового сигналу передається через чотири різних обчислювальних фільтри. Кожен фільтр є окремим процесом. Перший сегмент даних повинен пройти через перший фільтр перед просуванням до другого. Коли це станеться, другий сегмент даних проходить через перший фільтр. На той час, коли четвертий сегмент даних буде знаходитися в першому фільтрі, всі чотири завдання будуть зайняті.
  • Моделювання клімату 
    Кожен компонент моделі може розглядатися як окреме завдання. Стрілки показують обмін даними між компонентами під час обчислення: модель атмосфери генерує дані про швидкість вітру, які використовує модель океану, модель океану генерує дані про температуру поверхні води, які використовуються в моделі атмосфери і так далі.

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

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

 

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

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

Комунікація – з’єднання, передача, повідомлення.

Можна виділити наступні основні типи комунікацій:

  • Локальні – кожна задача з’єднана з невеликим набором інших підзадач.
  • Глобальні – кожна підзадача зв’язана з великою кількість інших під задач.
  • Структуровані – кожна під задача, і під задачі які з нею пов’язані, утворюють регулярну структуру.
  • Статичні – схема комунікацій не змінюється з плином часу.
  • Динамічні – відправник і отримувач даних координують обмін.
  • Асинхронні – обмін даними не координується.

Потреба у зв'язках між завданнями залежить від вашої проблеми.

Вам не потрібні комунікації, якщо деякі види проблем можна розділити і виконати з застосуванням паралелізму практично без необхідності спільного використання даних завданнями. Наприклад, операцію обробки зображення, де кожен піксель на чорно-білому зображенні повинен змінити колір на протилежний. Дані зображення можна легко розподілити між кількома завданнями, які потім незалежно один від одного виконають свою частину роботи.

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

Є ряд важливих факторів для розгляду при проектуванні зв'язків між завданнями у програмі:

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

Латентність проти пропускної здатності:

  • латентність – це час, необхідний для відправлення мінімального (0 байт) повідомлення з точки А в точку Б. Зазвичай виражається в мікросекундах.
  • пропускна здатність – це обсяг даних, які можуть бути передані за одиницю часу. Зазвичай виражається в мегабайтах за секунду або гігабайтах за секунду.

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

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

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

В свою чергу, асинхронні зв'язки дозволяють завданням передавати дані незалежно один від одного. Наприклад, завдання 1 може підготувати і відправити повідомлення завданню 2, а потім негайно почати виконувати іншу роботу. Немає значення, коли завдання 2 фактично отримає дані.

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

Чергування обчислень з комунікаціями є однією найбільшою вигодою з використання асинхронних зв'язків.

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

 – включає в себе два завдання, одне з яких діє як відправник/виробник даних, а інше діє як приймач/споживач.

Колективні – передбачає обмін даними між двома і більше завданнями, які часто вказані як члени єдиної групи або колективні завдання.

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

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

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

Вимоги:

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

 

         На етапі планування визначають, на яких процесорах будуть виконуватися підзадачі. Головний критерій ефективності – мінімізація часу виконання програми.

Стратегія розміщення задач на процесорах будується на основі компромісу між вимогами максимальної незалежності виконуваних задач (мінімізація комунікацій) та глобальним врахуванням станів обчислень. Найчастіше застосовується стратегія господар/працівник, ієрархічні та децентралізовані стратегії.

Господар/робітник:

Головна задача відповідає за розміщення підопічних задач. Підопічна задача отримує вихідні дані для обробки від задачі і повертає їй результат роботи.

Ієрархічна схема господар/робітник:

         Підопічні множини розділені на неперетинні множини і в кожного з них є своя головна задача. Головні задачі підмножини керуються однією найголовнішою задачею.

Децентралізовані схеми:

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

         Динамічно збалансоване навантаження може бути ефективно реалізоване, якщо враховано:

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

 

 

 

 

 

MPI

         Розглянемо просту програму:

 

#include <stdio.h>

 #include "mpi.h"

 int main(int argc, char* argv[]){

         int ProcNum, ProcRank, RecvRank;

         MPI_Status Status;

         MPI_Init(&argc, &argv);

         MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);

         MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);

         if ( ProcRank == 0 ){

         printf("\n Hello from process %3d", ProcRank);

 for (int i = 1; i < ProcNum; i++ ) {

                   MPI_Recv(&RecvRank, 1, MPI_INT, MPI_ANY_SOURCE,

 MPI_ANY_TAG, MPI_COMM_WORLD, &Status);

 printf("\n Hello from process %3d", RecvRank);

                   }

         }

 else

         MPI_Send(&ProcRank,1,MPI_INT,0,0,MPI_COMM_WORLD);

 MPI_Finalize();

         return 0;

 }

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

Приклад виконання:

Hello from process 0

Hello from process 2

Hello from process 1

Hello from process 3

 

В даному випадку присутня непостійність. Це погіршує тестування та відладку програми, тому такого намагаються уникати. Рішенням проблеми може бути зміна MPI_ANY_SOURCE на і (ітератор циклу), що призведе до виведення у строго зростаючому порядку. Але, часто, це приводить до уповільнення паралельних обчислень.

Варто ще зазначити, що функція MPI_Recv є блокуючою для процеса отримувача. Це означає, що його процес буде заблокований до завершення прийому повідомлення. Тому, якщо не має відправленого повідомлення, то функція заблокує виконання паралельної програми.

Можна сказати, що MPI програма – «макропрограма», адже вона використовується для породження всіх процесів паралельної програми, отже повинна визначати обчислення, які виконуються всіма цими процесами. Тому, як рекомендація, рекомендується виносити роботу процесів в окремі блоки програми – функції.

Якщо попереднє правило застосувати до приведеної програми, то вона може набути вигляду:

MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);

if ( ProcRank == 0 ){

 ManageProcess();

}

else {

SendData();

}

Потрібно зауважити, що майже всіі функції MPI (крім MPI_Wtime і MPI_Wtick) повертають код виконання, який дорівнює MPI_SUCCESS у разі успіху. У MPI визначені константи, які відповідають за різні коди помилок.

Вище згадано 2 функції: MPI_Wtime та MPI_Wtick. Перша використовується для визначення часу роботи фрагмента коду(відлік секунд які пройшли з певного часу в минулому, а точність може залежати від середовища реалізації MPI). Рекомендується використовувати для визначення часу виконання певних фрагментів коду. Для визначення поточного значення точності можна викликати функцію MPI_Wtick, яка визначає час в секундах між двома послідовними показниками часу апаратного таймера системи.

Як згадувалося, функції MPI_Recv та MPI_Send використовуються для парних операцій передачі та прийому даних. Для виконання комунікаційних колективних операцій, в яких приймає участь всі процеси комунікатора, в MPI передбачено спеціальний набір функцій.

Розглянемо задачу, де нам потрібно просумувати елементи вектора. Для цього розділимо дані на рівні блоки, передамо ці блоки процесам, в цих процесах виконаємо частини сумування отриманих даних, зберемо ці значення в одному місці і додамо їх для отримання загальної суми. Для вирішення цієї задачі можна використати функцію передачі MPI_Send та функцію прийому MPI_Recv. Але це не ефективно, бо підготовка до виклику функції передачі буде сумувати затрати на підготовку передачі(латентність).

Для ефективного виконання операції передачі даних від одного процесу всім іншим може бути виконано за допомогою функції MPI_Bcast.

int MPI_Bcast(void *buf, int count, MPI_Datatype type, int root, MPI_Comm comm),

де buf – буфер пам’яті, де знаходиться повідомлення, count – розмір буфера, root – ранг процесу, який виконує розсилання даних, comm – комунікатор, в рамках якого виконується передача.

         Функція Bcast виконує розсилку даних з буфера buf , який містить count елементів типу type, з процесу під номером root всім процесам, які входять в комунікатор comm.

Bcast є колективною операцією, тому використовувати Recv неможна.

 

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include "mpi.h"int main(int argc, char* argv[]){

 double x[100], TotalSum, ProcSum = 0.0;

 int ProcRank, ProcNum, N=100, k, i1, i2;

 MPI_Status Status;

 MPI_Init(&argc,&argv);

 MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);

 MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);

 // підготовка даних

 if ( ProcRank == 0 ) DataInitialization(x,N);

 // розсилаємо дані на всі процеси

 MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

 // Обчислення часткової суми на кожному з процесів. На кожному процесі муються елементи вектора х від i1 до i2

 k = N / ProcNum;

 i1 = k * ProcRank;

 i2 = k * ( ProcRank + 1 );

 if ( ProcRank == ProcNum-1 ) i2 = N;

 for ( int i = i1; i < i2; i++ )

 ProcSum = ProcSum + x;

 // збір часткових сум в нульовому процесі

 if ( ProcRank == 0 ) {

 TotalSum = ProcSum;

 for ( int i=1; i < ProcNum; i++ ) {

 MPI_Recv(&ProcSum,1,MPI_DOUBLE,MPI_ANY_SOURCE,0,

MPI_COMM_WORLD, &Status);

 TotalSum = TotalSum + ProcSum;

 }

 }

 else //всі процеси відправляють результат обчислення

 MPI_Send(&ProcSum, 1, MPI_DOUBLE, 0, 0,

MPI_COMM_WORLD);

 // вивід результату

 if ( ProcRank == 0 )

 printf("\nTotal Sum = %10.2f",TotalSum);

 MPI_Finalize();

return 0;

}

 

Функція DataInitialization підготовлює дані (введення з клавіатури чи читання з файлу або згенеровані випадково).

 

Операція редукції – передача даних від всіх процесів одному.

В цій задачі, над зібраними значеннями виконується та чи інша обробка даних. Реалізація редукції тими ж парними операціями є неефективною і досить трудомістка. Тому існує спеціальна функція – Reduce.

int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype type, MPI_Op op, int root, MPI_Comm comm), де

sendbuf – буфер пам’яті з відправленим повідомленням, recvbuf – буфер пам’яті для результуючого повідомлення (тільки для процесу з рангом root), count – кількість елементів в повідомленнях, type – тип елементів повідомлення, op – операція, яка повинна бути виконана над даними, root – ранг процесу, на якому повинен бути отриманий результат. Так, як Reduce – також колективна операція, то вона повинна бути застосована до всіх процесів вказаного комунікатора.

 

 

Тепер програма може бути переписана з використанням функції, яка приймає все в нульовому процесі. Виконується прийом часткових сум на процесі з рангом 0.

// збір часткових сум в нульовому процесі

MPI_Reduce(&ProcSum, &TotalSum, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

 

6.4 Організація паралельних обчислень з використанням наявних технологій (PVM, MPI).

Паралельні обчислення - це форма обчислень, в яких кілька дій проводяться одночасно. Грунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.

Є кілька різних рівнів паралельних обчислень: бітовийінструкційданих та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях, але зацікавлення ним зросло тільки недавно, через фізичні обмеження зростання частоти. Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки,  паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів.

Паралельні комп'ютери можуть бути грубо класифіковані згідно з рівнем, на якому апаратне забезпечення підтримує паралелізм:багатоядерністьбагатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а такожкластериMPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач.

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

Поняття паралельної програми

Під паралельної програмою в рамках MPI розуміється безліч одночасно виконуваних процесів :

–  Процеси можуть виконуватися на різних процесорах; разом з цим, на одному процесорі можуть розташовуватися кілька процесів,

–  Кожен процес паралельної програми породжується на основі копії одного і того ж програмного коду (модель SPMP). Вихідний програмний код розробляється на алгоритмічних мовах C або Fortran з використанням бібліотеки MPI.

Кількість процесів і число використовуваних процесорів визначається в момент запуску паралельної програми засобами середовища виконання MPI програм. Всі процеси програми послідовно пронумеровані. Номер процесу іменується рангом процесу.

 

В обчислювальних системах з розподіленою пам'яттю процесори працюють незалежно один від одного.

Для організації паралельних обчислень необхідно вміти:

–  розподіляти обчислювальне навантаження,

–  організувати інформаційну взаємодію (передачу даних) між процесорами.

–  вирішення всіх перерахованих питань забезпечує MPI-інтерфейс передачі даних

У рамках MPI для вирішення завдання розробляється одна програма, вона запускається на виконання одночасно на всіх наявних процесорах. Для організації різних обчислень на різних процесорах:

–  є можливість підставляти різні дані для програми на різних процесорах, 

–  є засоби для ідентифікації процесора, на якому виконується програма

Такий спосіб організації паралельних обчислень зазвичай називається модель "одна програма безліч процесів" (одна програма кілька процесів або SPMP)

У MPI існує безліч операцій передачі даних:

–  забезпечуються різні способи пересилки даних,

–  реалізовані практично всі основні комунікаційні операції.

Ці можливості є найбільш сильною стороною MPI (про це, зокрема, свідчить і сама назва MPI)

 

 Що таке MPI?

MPI - це стандарт, якому повинні задовольняти засоби організації передачі повідомлень.

MPI - це програмні засоби, які забезпечують можливість передачі повідомлень і при цьому відповідають всім вимогам стандарту MPI:

    - програмні засоби повинні бути організовані у вигляді бібліотек програмних модулів (бібліотеки MPI),

    - повинні бути доступні для найбільш широко використовуваних алгоритмічних мов C і Fortran.

 

Переваги MPI

MPI дозволяє істотно знизити гостроту проблеми переносимості паралельних програм між різними комп'ютерними системами.

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

Зменшує складність розробки паралельних програм:

–  більша частина основних операцій передачі даних передбачається стандартом MPI,

–  є велика кількість бібліотек паралельних методів, створених з використанням MPI.

Message Passing Interface (MPI, інтерфейс передачі повідомлень) - програмний інтерфейс ( API) для передачі інформації, який дозволяє обмінюватися повідомленнями між процесами, що виконують одну задачу.

MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для великого числа комп'ютерних платформ. Використовується при розробці програм для кластерів і суперкомп'ютерів. Основним засобом комунікації між процесами в MPI є передача повідомлень один одному. Стандартизацією MPI займається MPI Forum. У стандарті MPI описаний інтерфейс передачі повідомлень, який повинен підтримуватися як на платформі, так і в додатках користувача. В даний час існує велика кількість безкоштовних і комерційних реалізацій MPI. Існують реалізації для мов Фортран 77/90, JavaСі і Сі + +.

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

Стандарти MPI

Перша версія MPI розроблялася в 1993-1994 році, і MPI 1 вийшла в 1994.

Більшість сучасних реалізацій MPI підтримують версію 1.1. Стандарт MPI версії 2.0 підтримується більшістю сучасних реалізацій, але деякі функції можуть бути реалізовані не до кінця.

У MPI 1.1 (опублікований 12 червня 1995, перша реалізація з'явилася в 2002 році) підтримуються наступні функції:

  • передача та отримання повідомлень між окремими процесами;
  • колективні взаємодії процесів;
  • взаємодії в групах процесів;
  • реалізація топологій процесів;

У MPI 2.0 (опублікований 18 липня 1997) додатково підтримуються наступні функції:

  • динамічне породження процесів і керування процесами;
  • односторонні комунікації (Get / Put);
  • паралельний введення і виведення;
  • розширені колективні операції (процеси можуть виконувати колективні операції не тільки всередині одного комунікатора, але й в рамках декількох комунікаторів).

Версія MPI 2.1 вийшла на початку вересня 2008 року.

Версія MPI 2.2 вийшли 4 вересня 2009 року.

Версія MPI 3.0 вийшла 21 вересня 2012 року.

 

Функціонування інтерфейсу

Базовим механізмом зв'язку між MPI процесами є передача і прийом повідомлень. Повідомлення несе в собі передані дані і інформацію, що дозволяє приймаючій стороні здійснювати їх вибірковий прийом:

  • відправник - ранг (номер в групі) відправника повідомлення;
  • одержувач - ранг одержувача;
  • ознака - може використовуватися для поділу різних видів повідомлень;
  • комунікатор - код групи процесів.

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

Іншим способом зв'язку є віддалений доступ до пам'яті (RMA), що дозволяє читати і змінювати область пам'яті віддаленого процесу. Локальний процес може переносити область пам'яті віддаленого процесу (всередині зазначеного процесами вікна) в свою пам'ять і назад, а також комбінувати дані, передані в віддалений процес з наявними в його пам'яті даними (наприклад, шляхом підсумовування). Всі операції віддаленого доступу до пам'яті не блокуються, однак, до і після їх виконання необхідно викликати блокуючі функції синхронізації.

Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів рангом поменше, обєднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер.

Паралельна модель програмування сильно відрізняється від звичайної – послідовної. Існують дві моделі паралельного програмування: модель паралелізм даних і модель паралелізму задач. Модель паралелізми даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізами задач передбачає розбивка основної задачі на підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: MPI (Message Passing Interface) і PVM (Parallel Virtual Machine).

 

Що таке MPI/MPICH?

При розробці паралельних програм виникають специфічні для даної моделі обчислень проблеми сугубо технічного характеру: забезпечення комунікацій між підзадачами, забезпечення надійності й ефективності цих комунікацій, дозвіл проблем зв'язаних із загальним доступом до поділюваних ресурсів та інше. Для рішення цих проблем можна реалізувати власні методи, а можна використовувати вже готові стандарти/специфікації/бібліотеки. MPI – «Інтерфейс передачі повідомлень» - це специфікація, що була розроблена в 1993-1994 роках групою MPI Forum (http://www.mpi-forum.org),і забезпечує реалізацію моделі обміну повідомленнями між процесами. Остання версія даної специфікації MPI-2. У моделі програмування MPI програма породжує кілька процесів, взаємодіючих між собою за допомогою звертання до підпрограм прийому і передачі повідомлень.

Звичайно, при ініціалізації MPI-програми створюється фіксований набір процесів, причому (що, утім, необов'язково) кожний з них виконується на своєму процесорі. У цих процесах можуть виконуватися різні програми, тому MPI-модель іноді називають MPMD-моделлю (Multiple Program, Multiple Data), на відміну від SPMD (Single Program…)моделі, де на кожному процесорі виконуються тільки однакові задачі. MPI підтримує двохточкові і глобальні, синхронні й асинхронні, блокуючі і типи комунікацій, що неблокуються. Спеціальний механізм – комунікатор – ховає від програміста внутрішні комунікаційні структури. Структура комунікацій може змінюватися протягом часу життя процесу, але кількість задач повинна залишатися постійним (MPI-2 уже підтримує динамічна зміна числа задач).

Специфікація MPI забезпечує переносимість програм на рівні вихідних кодів і велику функціональність. Підтримується робота на гетерогенних кластерах і симетричних мультипроцесорних системах. Не підтримується, як уже відзначалося, запуск процесів під час виконання MPI-програми. У специфікації відсутні опису паралельного введення-висновку і налагодження програм – ці можливості можуть бути включені до складу конкретної реалізації MPI у виді додаткових пакетів і утиліт. Сумісність різних реалізацій не гарантується.

Важливою властивістю паралельної програми є детермінізм – програма повинна завжди давати той самий результат для того самого набору вхідних даних. Модель передачі повідомлень, загалом даною властивістю не володіє, оскільки не визначений порядок одержання повідомлень від двох процесів третім. Якщо ж один процес послідовно посилає кілька повідомлень іншому процесу, MPI гарантує, що одержувач одержить їхній саме в тім порядку, у якому вони були відправлені. Відповідальність за забезпечення детермінованого виконання програми лягає на програміста (з цього приводу див. приклад 3).

MPICH – MPI Chameleon – одна з реалізацій MPICH яка підтримує роботу на великому числі платформ із різними комунікаційними інтерфейсами, у т.ч. і TCP/IP.

Основні особливості MPICH v 1.2.2:

-         повна сумісність зі специфікацією MPI-1;

-         наявність інтерфейсу в стилі MPI-2 з функціями для мови C++ зі специфікації MPI-1;

-         наявність інтерфейсу з процедурами мови FORTRAN-77/90;

-         є реалізація для Windows NT (несумісна з UNIX-реалізацією);

-         підтримка великого числа архітектур, у т.ч. кластерів, SMP і т.д.;

-         часткова підтримка MPI-2;

-         часткова підтримка паралельного введення-висновку – ROMIO;

-         наявність засобів трасування і протоколювання (SLOG-based);

-         наявність засобів візуалізації продуктивності паралельних програм (upshot і jumpshot);

-         наявність у складі MPICH тестів продуктивності і перевірки функціонування системи.

Недоліки MPICH – неможливість запуску процесів під час роботи програми і відсутність засобів моніторингу за поточним станом системи.

До складу MPICH входять бібліотечні і заголовні файли, що реалізують біля сотні підпрограм. Ми будемо розглядати реалізацію MPICH.NT 1.2.4 для Windows NT.

Реалізації MPI

  • MPICH - найпоширеніша безкоштовна реалізація, працює на UNIX -системах і Windows NT
  • LAM / MPI - ще одна безкоштовна реалізація MPI. Підтримує гетерогенні конфігурації, LAM (http://www.lam-mpi.org) підтримує гетерогенні конфігурації, пакет Globus і задовольняє IMPI (Interoperable MPI).

Підтримуються різні комунікаційні системи (у тому числі Myrinet).

МРІ не містить механізмів динамічного створення і знищення процесів під час виконання програми.

Для ідентифікації наборів процесів вводиться поняття групи і комунікатора. 

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

Процедури МРІ:
- ініціалізації та закриття МРІ –процесів;
- реалізації комутаційних операцій типу “точка-точка”;
- реалізації колективних операцій;
- для роботи з групами процесів і комунікаторами;
- для роботи з структурами даних;
- формування топології процесів.

 

До базових функцій МРІ відносяться:

  • ініціалізація МРІ;
  • завершення МРІ;
  • визначення кількості процесів в області зв’язку;
  • визначення номеру процесу, який виконується;
  • передача повідомлень;
  • приймання повідомлень;
  • функції відліку часу.

Кожна МРІ – функція характеризується способом виконання.

  1. Локальна функція – виконується всередині процесу, що її викликав. Її завершення не вимагає комунікацій.
  2. Нелокальна функція – для її завершення необхідно виконати МРІ – процедуру іншим процесом.
  3. Глобальна функція – процедуру повинні виконати всі процеси групи. Невиконання цієї умови може привести до “зависання” задачі.
  4. Блокуюча функція – повернення керування з процедури гарантує можливість повторного використання параметрів, які приймали участь у виклику. Ніякої змін в стан процесу, що викликав блокуючий запит до виходу з процедури не може відбуватися.
  5. Неблокуюча функція – повернення з процедури відбувається негайно, без очікування завершення операції. Завершення неблокуючих операцій здійснюється спеціальними функціями.

Операції обміну повідомленнями

Розглянемо: режими обміну, обмін типу “точка-точка”, колективний обмін, способи реалізації моделі передачі повідомлень

Режими обміну:

В загальному випадку є чотири режими обміну: асинхронний (стандартний), синхронний, з буферизацією, по “готовності”.

Обмін типу “точка-точка” – найпростіша форма обміну повідомленнями, в якій приймають участь тільки два процеси: джерело і адресат. Є кілька різновидностей двохточкового обміну:

  • синхронний обмін – супроводжується повідомленням про завершення прийому повідомлення;
  • асинхронний обмін – таким повідомленням не супроводжується;
  • блокуючі прийом/передача – призупиняють виконання процесу на час приймання повідомлення. Організація блокуючого обміну повідомленнями наведена на рис.8.3;
  • неблокуючі прийом/передача  - виконання процесу продовжується в фоновому режимі, а програма в потрібний момент може запитати підтвердження завершення приймання повідомлення.


Неблокуючий обмін вимагає акуратності при виконанні функцій прийому. Оскільки неблокуючий прийом завершується негайно, для системи неважливо, чи прибуло повідомлення до місця призначення чи ні. Переконатися про це можна за допомогою функції перевірки отримання повідомлення. Звичайно виклик таких функцій розміщується в циклі, який повторюється до тих пір, доки функція перевірки не поверне значення “істина” (перевірка отримання пройшла успішно). Після цього можна викликати функцію прийому повідомлення з буферу повідомлень. 


Колективний обмін . В операціях використовуються не два а більше процесів. Різновидностями обміну є:

  • широкосмугова передача – передача виконується від одного процесу до всіх;
  • обмін з бар’єром – форма синхронізації роботи процесів, коли обмін повідомленнями проходить тільки після того, як до певної процедури звернулась певна кількість процесів;
  • операції приведення – вхідними є дані кількох процесів, а результат – одне значення, яке стає доступним всі процесам, які приймали участь в обміні.


Важливою властивістю системи передачі повідомлень є гарантія збереження порядку прийому повідомлень (при відправленні одним процесом іншому кількох повідомлень вони повинні бути прийняті в тій самій послідовності в якій були відправлені). Більшість реалізацій моделі передачі повідомлень забезпечують цю властивість, але не у всіх режимах обміну. 

Способи реалізації моделі передачі повідомлень:

  • створення спеціалізованої мови паралельного програмування.  Приклад – мова Occam;
  • розширення звичайної послідовної мови шляхом включення в неї засобів обміну повідомленнями. Приклад – мова CC++, FORTRAN M;
  • використання спеціалізованих бібліотек в програмах, що написані на звичайних мовах послідовного програмування. Приклад – PVM, MPI

 

Поняття комунікаторів

Комунікатор в MPI - спеціально створюваний службовий об'єкт, який об'єднує в своєму складі групу процесів і ряд додаткових параметрів:

– парні операції передачі даних виконуються для процесів, належать одному і тому ж коммуникатору,

– колективні операції застосовуються одночасно для всіх процесів комунікатора.

Вказівка ​​використовуваного комунікатора є обов'язковою для операцій передачі даних в MPI.

У ході обчислень можуть створюватися нові і видалятися існуючі комунікатори.

Один і той же процес може належати різним комунікаторам.

Усі наявні в паралельній програмі процеси входять до складу створюваного за замовчуванням комунікатора з ідентифікатором MPI_COMM_WORLD.

При необхідності передачі даних між процесами з різних груп необхідно створювати глобальний комунікатор (intercommunicator).

 

Типи даних

    При виконанні операцій передачі повідомлень для вказівки передаваючих або одержуваних даних у функціях MPI необхідно вказувати тип даних, що пересилаються.

    MPI містить великий набір базових типів даних, багато в чому збігаються з типами даних в алгоритмічних мовах C і Fortran.

    У MPI є можливості для створення нових похідних типів даних для більш точного і короткого опису вмісту пересилаються.

 

Віртуальні топології

    Логічна топологія ліній зв'язку між процесами має структуру повного графа (незалежно від наявності реальних фізичних каналів зв'язку між процесорами).

    У MPI є можливість подання безлічі процесів у вигляді решітки довільної розмірності. При цьому, граничні процеси решіток можуть бути оголошені сусідніми і, тим самим, на основі решіток можуть бути визначені структури типу тор.

    У MPI є засоби і для формування логічних (віртуальних) топологій будь-якого необхідного типу.

Основи MPI

q    Ініціалізація і завершення MPI програм

    Першою функцією MPI повинна бути функція:

         int MPI_Init ( int *agrc, char ***argv )

 

    (служить для ініціалізації середовища виконання MPI програми; параметрами функції є кількість аргументів у командному рядку і текст самого командного рядка.)

–                    Останньою функцією MPI обов'язково повинна бути функція:

–                   int MPI_Finalize (void)

–                     

–                    структура паралельної програми, розроблена з використанням MPI, повинна мати наступний вигляд :

–                   #include "mpi.h"

–                   int main ( int argc, char *argv[] ) {

–                     < програмний код без використання MPI функцій >

–                     MPI_Init ( &agrc, &argv );

–                       < програмний код з використанням MPI функцій >

–                     MPI_Finalize();

–                     < програмний код без використання MPI функцій >

–                     return 0;

–                   }

Передача повідомлень

    Надсилаюче повідомлення визначається через вказівку блоку пам'яті ( буфера) , в якому це повідомлення розташовується . Використовувані для вказівки буфера buf, count, type входять до складу параметрів практично всіх функцій передачі даних ,

    Процеси , між якими виконується передача даних , обов'язково повинні належати коммуникатору , що вказується у функції MPI_Send ,

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

 

 

Прийом повідомлень…

    Буфер пам'яті повинен бути достатнім для прийому повідомлення, а тип елементів переданого і прийнятого повідомлення повинні збігатися; при нестачі пам'яті частина повідомлення буде втрачена і в коді завершення функції буде зафіксована помилка переповнення,

    При необхідності прийому повідомлення від будь-якого процесу-відправника для параметра Джерело може бути зазначено значення MPI_ANY_SOURCE,

При необхідності прийому повідомлення з будь-яким тегом для параметра тега може бути зазначено значення MPI_ANY_TAG

         Функція MPI_Recv є блокуючої для процесу-одержувача, тобто його виконання призупиняється до завершення роботи функції. Таким чином, якщо з якихось причин очікуване для прийому повідомлення буде відсутнє, виконання паралельної програми буде блоковано.

 

 

 

    Передача даних від одного процесу всім процесам програми

–  Функція MPI_Bcast визначає колективну операцію, виклик функції MPI_Bcast повинен бути здійснений всіма процесами що вказується комунікатором,

–  Вказаний в функції MPI_Bcast буфер пам'яті має різне призначення в різних процесах:

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

–  Для всіх інших процесів що вказуються буфер призначений для прийому переданих даних.        

 

  Передача даних від всіх процесів одному…

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

 

  

Додаток(основні функції)

MPI_Initialized

Вказує, чи була викликана MPI_Init - повертає прапор як логічне true (1) або false (0). MPI вимагає, щоб MPI_Init викликалася один раз і тільки один кожним процесом. Це може створити проблеми для модулів, які потребують використання MPI і готові викликати MPI_Init, якщо це необхідно. MPI_Initialized вирішує цю проблему.

MPI_Initialized(&flag) 
MPI_INITIALIZED (flag,ierr)

MPI_Wtime

Повертає час виклику процесора в секундах (подвійної точності).

MPI_Wtime()
MPI_WTIME ()

MPI_Wtick

Повертає роздільну здатність MPI_Wtime у секундах (подвійної точності).

MPI_Wtick()
MPI_WTICK ()

MPI_Finalize

Припиняє роботу середовища виконання MPI. Ця функція повинна бути останньою підпрограмою MPI, викликаною в кожній програмі MPI - жодна інша підпрограма MPI не може бути викликана після цього.

MPI_Finalize()
MPI_FINALIZE (ierr)

MPI_Abort

Зупиняє всі процеси MPI, пов'язані з комунікатором. У більшості реалізацій MPI зупиняє ВСІ процеси незалежно від вказаного комунікатора.

MPI_Abort(comm,errorcode)
MPI_ABORT (comm,errorcode,ierr)

  MPI_Send

Основна блокуюча операція надсилання. Підпрограма виконує "return" лише після того, як буфер застосунку у надсилаючому завданні є вільним для повторного використання. Зверніть увагу, що ця процедура може бути реалізована по-різному в різних системах. Стандарт MPI дозволяє використовувати системний буфер, але не вимагає цього. Деякі реалізації можуть фактично використовувати синхронне надсилання (описане нижче) для реалізації базового блокуючого надсилання.

MPI_Send(&buf,count,datatype,dest,tag,comm) 
MPI_SEND (buf,count,datatype,dest,tag,comm,ierr)

MPI_Recv

Приймає повідомлення і заблоковується доти, поки запитувані дані стануть доступними у буфері застосунку в завданні приймання.

MPI_Recv(&buf,count,datatype,source,tag,comm,&status) 
MPI_RECV (buf,count,datatype,source,tag,comm,status,ierr)

MPI_Barrier

Операція синхронізації. Створює бар'єр синхронізації в групі. Кожне завдання, яке досягає виклику MPI_Barrier, блокується, поки всі завдання у групі не досягнуть того самого виклику MPI_Barrier. Тоді всі завдання можуть продовжуватись.

MPI_Barrier(comm)
MPI_BARRIER (comm,ierr)

MPI_Bcast

Операція переміщення даних. Транслює (надсилає) повідомлення з процесу з рангом "root" до всіх інших процесів у групі. 

MPI_Bcast(&buffer,count,datatype,root,comm) 
MPI_BCAST (buffer,count,datatype,root,comm,ierr)

MPI_Scatter

Операція переміщення даних. Розподіляє окремі повідомлення від одного джерела завдання до кожного завдання у групі. 

MPI_Scatter(&sendbuf,sendcnt,sendtype,&recvbuf, 
  ...... recvcnt,recvtype,root,comm) 
MPI_SCATTER(sendbuf,sendcnt,sendtype,recvbuf, 
  ......  recvcnt,recvtype,root,comm,ierr)

MPI_Gather

Операція переміщення даних. Збирає окремі повідомлення від кожного завдання у групі до одного завдання призначення. Ця підпрограма є зворотною до операції MPI_Scatter. 

MPI_Gather(&sendbuf,sendcnt,sendtype,&recvbuf, 
  ......  recvcount,recvtype,root,comm) 
MPI_GATHER(sendbuf,sendcnt,sendtype,recvbuf, 
  ......  recvcount,recvtype,root,comm,ierr)

MPI_Allgather

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

MPI_Allgather(&sendbuf,sendcount,sendtype,&recvbuf, 
  ......  recvcount,recvtype,comm) 
MPI_ALLGATHER(sendbuf,sendcount,sendtype,recvbuf, 
  ......  recvcount,recvtype,comm,info)

MPI_Reduce

Операція колективних обчислень. Виконує операцію агрегації зі всіх завдань у групі і поміщає результат в одне завдання. 
MPI_Reduce(&sendbuf,&recvbuf,count,datatype,op,root,comm) 
MPI_REDUCE (sendbuf,recvbuf,count,datatype,op,root,comm,ierr)

Попередньо визначені MPI-операції агрегації описані нижче. Користувачі також можуть визначати свої власні функції агрегації за допомогою звичайної підпрограми

6.5 Паралельні архітектури комп'ютерної пам'яті. Моделі паралельного програмування.


Спільна пам'ять Огляд/Рівномірний доступ до пам’яті

Cпільна пам’ять
Спільна пам'ять паралельних комп'ютерів широко варіюється, але зазвичай всі процесори мають можливість доступу до всієї пам'яті як до глобального адресного простору. Кілька процесорів можуть працювати самостійно, але поділяють ті самі ресурси пам'яті. Зміни в пам'яті, виконані одним процесором, є видимими для всіх інших процесорів.  Історично, машини з спільною пам'яттю класифікувались як UMA і NUMA, що базувалося на часі доступу до пам'яті. 
Рівномірний доступ до пам'яті (Uniform Memory Access, UMA): 
• Найбільш широко представлені сьогодні симетричними багатопроцесорними (SMP) машинами 
• Ідентичні процесори 
• Рівний доступ і час доступу до пам'яті

Спільна пам'ять нерівномірний доступ до пам’яті
Нерівномірний доступ до пам'яті (Non-Uniform Memory Access, NUMA): 
• Не всі процесори мають однаковий доступ до всієї пам'яті 
• Часто робиться фізичним зв'язуванням двох або більше SMP 
• Один SMP може отримати доступ безпосередньо до пам'яті іншого SMP 
• Доступ до пам'яті через посилання є повільнішим 
• Якщо підтримується зв'язок з кешем, то також називають CC-NUMA, Cache Coherent NUMA - кеш-когерентний нерівномірний доступ до пам'яті 

Спільна пам'ять переваги та недоліки
Переваги: 
• Глобальний адресний простір забезпечує зручну програмну перспективу пам'яті 
• Обмін даними між завданнями є швидким і рівномірним завдяки близькому розташуванню пам'яті і процесора 
Недоліки: 
• Відсутність масштабованості між пам'яттю і ЦП. Приєднання додаткових процесорів може геометрично збільшити трафік на шляху спільна пам'ять-процесор, і для кеш-когерентних систем геометрично збільшити трафік, пов'язаний з управлінням кешем/пам'яттю. 
• Відповідальність програміста за конструкції синхронізації, які забезпечують "правильний" доступ до глобальної пам'яті. 
• Витрати: стає все більш складно і дорого проектувати і виробляти машини зі спільною пам'яттю з постійним збільшенням кількості процесорів. 

Розподілена пам'ять загальні особливості

Подібно до систем зі спільною пам'яттю, системи з розподіленою пам'яттю відрізняються одна від одної, але мають спільні характеристики. Системам з розподіленою пам'яттю необхідні комунікаційні мережі для зв'язку міжпроцесорної пам'яті.  Процесори мають свою власну локальну пам'ять. Адреси пам'яті в одному процесорі не зіставляються з іншим процесором, так що немає поняття глобального адресного простору всіх процесорів. Через те, що кожен процесор має власну локальну пам'ять, він працює самостійно. Зміни, які він робить в своїй локальній пам'яті, не впливають на пам'ять інших процесорів. Коли процесор потребує доступу до даних іншого процесора, як правило, завданням програміста є явно визначити, яким чином і коли дані передаються. Мережеві топології, які використовуються для передачі даних, широко відрізняються, хоч топологія може бути такою простою як Ethernet. 

 Розподілена пам'ять переваги та недоліки
Переваги:
• Пам'ять є масштабованою з кількістю процесорів. Число процесорів і розмір пам'яті збільшуються пропорційно. 
• Кожен процесор може швидко отримати доступ до власної пам'яті без перешкод і без накладних витрат, пов'язаних зі намаганням утримання зв'язку з глобальним кешем. 
• Економно: можна використовувати товарні, наявні у продажі процесори і мережі.

Недоліки: 
• Програміст несе відповідальність за багато деталей, пов'язаних з передачею даних між процесорами. 
• Може бути важко зіставляти існуючі структури даних на основі глобальної пам'яті з цією організацією пам'яті. 
• Нерівномірний час доступу до пам'яті - отримання доступу до даних, які знаходяться на віддаленому вузлі, займає більше часу, ніж до локальних даних у вузлі.


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

Гібридна розподілена і спільна пам'ять переваги та недоліки

• Все, що є звичайним для обох типів архітектури пам'яті. 
• Підвищена масштабованість є значною перевагою 
• Підвищення складності для програміста є важливим недоліком

Моделі паралельного програмування огляд
Є кілька моделей паралельного програмування загального користування: 
• Спільна пам'ять (без потоків) 
• Потоки 
• Розподілена пам'ять / передача повідомлень 
• Паралелізм даних 
• Гібридна модель 
• Єдина програма множинні дані (Single Program Multiple Data, SPMD) 
• Множинні програми множинні дані (Multiple Program Multiple Data, MPMD) 
 

Модель зі спільною пам'яттю (без потоків) Огляд та реалізація
У цій модель програмування завдання розділяють спільний адресний простір, в якому читання і запис вони здійснюють асинхронно.  Різні механізми, як блоки / семафори, можуть використовуватися для керування доступом до спільної пам'яті.  Перевагою цієї моделі з точки зору програміста є те, що поняття "власника" даних відсутнє, тому немає необхідності явно вказувати зв'язок даних між завданнями. Розробка програми часто може бути спрощена. Важливим недоліком з погляду продуктивності є те, що стає дедалі важче розуміти і керувати місцем знаходження даних. Збереження даних місцевих процесор, який працює на ньому зберігає доступу до пам'яті, оновлює кеш і рух автобусів, що відбувається, коли кілька процесорів використовувати однакові дані.  На жаль, контролювання місця знаходження даних важко зрозуміти і може бути поза контролем середнього користувача. 
Реалізації: 
• Рідні компілятори та/або апаратне забезпечення переводять користувацькі програмні змінні у фактичні адреси пам'яті, які є глобальними. На окремій машині зі спільною пам'яттю це просто.
• На машинах з розподіленою спільною пам'яттю пам'ять фізично розділена по всій мережі машин, але зроблена глобальною через спеціалізоване обладнання та програмне забезпечення.

Модель потоків Огляд та реалізація
Ця модель програмування — це тип програмування спільної пам'яті.  У моделі потоків паралельного програмування один "важкий" процес може мати кілька "легких" паралельних шляхів виконання.
Реалізації: 
o З погляду програмування реалізації потоків зазвичай включають: 
o Бібліотеку підпрограм, які викликаються зсередини паралельного вихідного коду 
o Набір директив компілятора, вбудованих в будь-який послідовний чи паралельний вихідний код 
o В обох випадках програміст несе відповідальність за визначення паралелізму (хоча іноді компілятори можуть допомагати). 
o Потокові реалізації не є новими в обчисленнях. Історично апаратне забезпечення реалізувало свої власні приватні версії потоків. Ці реалізації істотно відрізняються одна від одної і для програмістів це ускладнює розробку портативних багатопотокових застосунків.
o Непов'язані спроби стандартизації своїм результатом дали дві дуже різні реалізації потоків: POSIX Threads і OpenMP.

 

Розподілена пам'ять  передача повідомлень
Ця модель демонструє наступні характеристики: 
• Набір завдань, які використовують свою власну локальну пам'ять під час обчислень. Декілька завдань можуть виконуватись на тій самій фізичній машині і/або на довільному числі машин. 
• Завдання обмінюються даними через зв'язки шляхом надсилання й приймання повідомлень.
• Передавання даних зазвичай вимагає виконання спільних операцій кожним процесом. Наприклад, операція надсилання повинна мати відповідну операцію приймання.

Реалізації
MPI є "де-факто" галузевим стандартом для передачі повідомлень, він замінив практично всі інші реалізації передачі повідомлень, які використовуються у виробництві. MPI-реалізації існують для практично всіх популярних паралельних обчислювальних платформ.


Модель з паралелізмом даних
Модель з паралелізмом даних демонструє наступні характеристики: 
• Адресний простір розглядається глобально.
• Більшість паралельної роботи зосереджена на виконанні операцій над наборами даних. Набір даних зазвичай організований в загальну структуру, таку як масив або куб
• Набір завдань колективно працює з тією самою структурою даних, однак, кожне завдання працює з окремою частиною цієї структури даних. 
• Завдання виконують ту саму операцію над своєю частиною роботи, наприклад, "додати 4 до кожного елемента масиву".

Реалізації
o В даний час є кілька досить популярних, і іноді таких, що ще розробляються, реалізацій моделі паралельного програмування з паралелізмом даних
o Unified Parallel C (UPC): розширення до мови програмування C для паралельного програмування SPMD. Залежить від компілятора. 
o X10: паралельна мова програмування на основі PGAS, розроблена компанією IBM у Thomas J. Watson Research Center.

Гібридна модель

Гібридна модель поєднує в собі більше, ніж одну з попередньо описаних моделей програмування.

Реалізації
Поєднання моделі передачі повідомлень (MPI) з моделлю потоків (OpenMP). 
• Потоки становлять інтенсивні обчислювальні ядра, які використовують локальні дані на вузлі 
• Зв'язок між процесами на різних вузлах відбувається через мережу за допомогою MPI.
Використання MPI і програмуванням графічного процесора. 
• Графічні процесори становлять інтенсивні обчислювальні ядра, які використовують локальні дані на вузлі 
• Зв'язок між процесами на різних вузлах відбувається через мережу за допомогою MPI.

1.5 (ua) MPI

ЗмістMessage Passing InterfaceЗмістMVAPICHOpen MPIКластери IBM BlueGene:Приклади: підпрограми середовища управлінняПриступаючи до роботиЗагальні поняттяАргументи підпрограм передачі повідомлень MPIБлокуючі підпрограми передачі повідомленьПриклади: блокуючі підпрограми передачі повідомленьНеблокуючі підпрограми передачі повідомленьПриклади: неблокуючі підпрограми передачі повідомленьНадсилання повідомлення типу "точка-точка"Підпрограми колективної комунікаціїПриклади: колективна комунікаціяПідпрограми похідних типів данихПриклади: суміжний похідний тип данихПриклади: векторний похідний тип данихПриклади: індексований похідний тип данихПриклади: похідний тип даних structПідпрограми управління групами та комунікаторамиПідпрограми віртуальної топологіїВаш вибір

 
blaiseb@llnl.gov"> Tutorials | Exercises | Abstracts | LC Workshops | Comments | Search | Privacy & Legal Notice Tutorials | Exercises | Abstracts | LC Workshops | Comments | Search | Privacy & Legal Notice

 

Message Passing Interface

 

Автор: Blaise Barney, Lawrence Livermore National Laboratory UCRL-MI-133316

Зміст

  1. Анотація
  2. Що таке MPI?
  3. LLNL MPI реалізації та компілятори
  4. Приступаючи до роботи
  5. Підпрограми середовища управління
  6. Завдання 1
  7. Підпрограми зв'язку типу "точка-точка"
    1. Загальні поняття
    2. Аргументи підпрограм передачі повідомлень MPI
    3. Блокуючі підпрограми передачі повідомлень
    4. Неблокуючі підпрограми передачі повідомлень
  8. Завдання 2
  9. Підпрограми колективної комунікації
  10. Похідні типи даних
  11. Підпрограми управління групами та комунікаторами
  12. Віртуальні топології
  13. Коротко про MPI-2 і MPI-3
  14. Завдання 3
  15. Посилання і додаткова інформація
  16. Додаток А: перелік підпрограм MPI-1

  Анотація


Стандарт Message Passing Interface - це стандарт бібліотеки передачі повідомлень, погоджений групою MPI Forum, в якій беруть участь більше, ніж 40 організацій, включаючи постачальників, дослідників, розробників біблітек програмного забезпечення та користувачів. MPI покликаний затвердити портативний, ефективний і гнучкий стандарт для обміну повідомленнями, що буде широко використовуватися для написання програм передачі повідомлень. Таким чином, MPI є першою стандартизованою, незалежною від постачальника бібліотекою передачі повідомлень. Переваги розробки програмного забезпечення для передачі повідомлень з використанням MPI відповідають таким цілям проектування як портативність, ефективність і гнучкість. MPI не є стандартом IEEE або ISO, але по суті, є "галузевим стандартом" для написання програм передачі повідомлень на HPC платформах.

Цей підручник покликаний навчити тих, хто не знайомий з MPI, як розробляти і запускати розпаралелені програми відповідно до MPI стандарту. Основні представлені розділи зосереджуються на тому, що є найбільш корисним для нових MPI програмістів. Підручник починається з вступу, основ та базових відомостей про початок роботи з MPI. Це супроводжується детальним оглядом підпрограм MPI, які є найбільш корисними для нових MPI програмістів, включаючи підпрограми середовища управління MPI, зв'язків типу "точка-точка" та колективної комунікації. Надаються численні приклади на мовах C та Fortran, а також завдання для лабораторних.

Матеріали підручника також містять поглиблені теми, такі як похідні типи даних (Derived Data Types), управління групами і комунікаторами (Group and Communicator Management Routines) і віртуальні топології (Virtual Topologies). Тим не менш, вони фактично не представлені під час лекцій, але призначені в якості "подальшого читання" для тих, хто зацікавився.

Рівень/передумови: Цей підручник є одним з восьми підручників в ?(4+ day) майстер-класі "Використання суперкомп'ютерів LLNL". Ідеально підходить для тих, хто початківець в паралельному програмуванні з MPI. Необхідне базове розуміння паралельного програмування на мові C або Fortran. Для тих, хто не знайомі з паралельним програмуванням в загальному, матеріал, охоплений в EC3500: Вступ до паралельного комп'ютингу буде корисним. 


 

Що таке MPI?

 


 Специфікація інтерфейсу:Логотип MPI

 

  • M P I =  Message  Passing  Interface

     

  • MPI є специфікацією для розробників і користувачів бібліотек для обміну повідомленнями. Сам по собі він є не бібліотекою - а радше специфікацією того, якою повинна бути бібліотека.

     

  • MPI в першу чергу адресується моделі паралельного програмування передачі повідомлень: дані переміщуються з адресного простору одного процесу до адресного простору іншого процесу через спільні операції в кожному процесі.

     

  • Простіше кажучи, MPI забезпечує широко розповсюджений стандарт для написання програм передачі повідомлень. Інтерфейс намагається бути:
    • практичним
    • портативним
    • ефективним
    • гнучким

     

  • Стандарт MPI пережив декілька переробок, найновішою версією є MPI-3.

     

  • Специфікації інтерфейсу визначені з прив'язкою до мов C і Fortran90:
    • прив'язки до C++ з MPI-1 видалені в MPI-3
    • MPI-3 також забезпечує підтримку особливостям Fortran 2003 і 2008

     

  • Поточні реалізації бібліотек MPI відрізняються тим, які версії та особливості стандарту MPI вони підтримують. Розробники/користувачі повинні бути поінформовані про це.

 Модель програмування:

 

  • Спочатку MPI було розроблено для архітектур з розподіленою пам'яттю, які ставали все більш популярними в той час (1980-і - початок 1990-х років).

     

  • Оскільки архітектурні тенденції змінювалися, спільна пам'ять SMPs була об'єднана через мережі, створюючи гібридні системи з розподіленою/спільною пам'яттю.

     

  • Розробники MPI адаптували свої бібліотеки для того, щоб легко обробляти обидва типи архітектур основної пам'яті. Вони також пристосували/розробили способи обробки різних з'єднань і протоколів.

     

     

  • Сьогодні MPI працює на практично будь-якій апаратній платформі:
    • Розподілена пам'ять
    • Спільна пам'ять
    • Гібридні

     

  • Тим не менш модель програмування залишається повністю моделлю з розподіленою пам'яттю, незалежно від основної фізичної архітектури машини.

     

  • Весь паралелізм є явним: програміст несе відповідальність за правильно виявлений паралелізм та реалізацію паралельних алгоритмів, що використовують конструкції MPI.

 Причини використання MPI:

 

  • Стандартизація - MPI є єдиною бібліотекою передачі повідомлень, яку можна вважати стандартом. Вона підтримує практично всі HPC платформи. Вона практично замінила всі попередні бібліотеки передачі повідомлень.

     

  • Портативність - необхідності змінювати вихідний код, коли переносиш застосунок на іншу платформу, що підтримує (і сумісна з) стандартом MPI, немає або вона невелика.

     

  • Можливості продуктивності - реалізації постачальника повинні мати можливість використовувати рідні апаратні особливості для оптимізації продуктивності.

     

  • Функціональність – є понад 440 ?(процедур), визначених у MPI-3, які включають в себе більшість тих, що були в MPI-2 і MPI-1.

     

  • Доступність — доступне різноманіття реалізацій, як від постачальників, так і загальних надбань.

 

 Історія та еволюція: (для тих, кому цікаво)

 

  • MPI є результатом зусиль численних окремих осіб і груп з 1992 року. Трохи історії:

     

  • 1980-і - початок 1990-х: Розподілена пам'ять, розвиваються паралельні обчислення, ряд несумісних програмних засобів для написання таких програм - як правило, з компромісами між портативністю, продуктивністю, функціональністю і вартістю. Виникло усвідомлення потреби у стандарті.

    Еволюція MPI

     

  • Квітень 1992: Семінар з питань стандартів передачі повідомлень в середовищі розподіленої пам'яті, організований Центром досліджень паралельних обчислень (Center for Research on Parallel Computing), Вільямсбург, Вірджинія. Обговорювалися основні особливості стандарту інтерфейсу передачі повідомлень і створена робоча група для продовження процесу стандартизації. Попередній план проекту розроблений згодом.

     

  • Листопад 1992: Робоча група зустрілася в Міннеаполісі. Представлено план проекту MPI (MPI1) від ORNL. Група приймає процедури і організацію у формі MPI Forum. Зрештою він складається з приблизно 175 осіб з 40 організації, включаючи постачальників паралельних комп'ютерів, розробників програмного забезпечення, академічних кіл та вчених.

     

  • Листопад 1993: Конференція суперкомп'ютингу 93 - представлено проект стандарту MPI.

     

  • Травень 1994: Випущена остаточна версія MPI-1.0

     

  • За MPI-1.0 послідували версії MPI-1.1 (червень 1995), MPI-1.2 (липень 1997) і MPI-1.3 (травень 2008).

     

  • MPI-2 забрав те, осторонь чого залишився перший MPI і був адресований темам, які виходять далеко за межі специфікації MPI-1. Був завершений в 1996 році.

     

  • Далі йшли слідом MPI-2.1 (вересень 2008) і MPI-2.2 (вересень 2009)

     

  • Вересень 2012: Було затверджено стандарт MPI-3.0.

 Документація:

 


  LLNL реалізації та компілятори MPI


Хоча програмний інтерфейс MPI був стандартизований, актуальні реалізації бібліотек будуть відрізнятися в тому, які версії та особливості стандарту вони підтримують. Способи компіляції і запуску програм MPI на різних платформах також можуть відрізнятися.

Основні відомості про MPI-середовище LC надані тут разом з посиланнями на додаткову детальну інформацію.

 

MVAPICH

 Загальна інформація:
  • MVAPICH MPI Державного університету Огайо (Ohio State University) є MPI-бібліотекою за замовчуванням на всіх Linux кластерах LC.

     

  • Станом на червень 2013 року стандартною версією для LC є MVAPICH 1.2
    • Реалізація MPI-1, що включає підтримку для MPI/O, але не для односторонньої комунікації MPI.
    • Базується на бібліотеці MPI MPICH 1.2.7 від Аргоннської національної лабораторії (Argonne National Laboratory)
    • Не є потоко-безпечним. Усі виклики MPI у мультипоточній MPI-програмі повинні проводитися майстром потоків.
    • Дивись /usr/local/docs/mpi.mvapich.basics для деталей використання LC.

     

  • MVAPICH2 також доступна на Linux кластерах LC
    • Реалізація MPI-2 базується на MPI-бібліотеці MPICH2 з Аргоннської національної лабораторії (Argonne National Laboratory)
    • В даний час не за замовчуванням – вимагає команду "use", щоб завантажити вибрані ?(dotkit) - дивисьhttps://computing.llnl.gov/?set=jobs&page=dotkit для деталей.
    • Потоко-безпечна
    • Дивись /usr/local/docs/mpi.mvapich.basics для деталей використання LC.

     

  • Код, скомпільований з MVAPICH на одному Linux кластері LC, має запускатися на будь-якому Linux кластері LC.
    • Clusters with an interconnect - message passing is done in shared memory on-node and over the switch inter-node
    • Clusters without an interconnect - message passing is done in shared memory

     

  • Більше інформації:

 MPI-сценарії для побудови:

  • Обгортки сценаріїв компілятора MPI використовуються для компіляції програм MPI - всі вони повинні бути у $PATH за замовчуванням, якщо їх не було змінено. Ці скрипти імітують знайомі MPICH-скрипти у своїй функціональності, це означає, вони автоматично включають відповідні MPI, включно з файлами та посиланнями на необхідні бібліотеки MPI, і передають перемикачі основному компілятору.

     

  • Доступні скрипти наведені нижче:

     

    Мова Ім'я сценарію Основний компілятор C mpicc gcc mpigcc gcc mpiicc icc mpipgcc pgcc C++ mpiCC g++ mpig++ g++ mpiicpc icpc mpipgCC pgCC Fortran mpif77 g77 mpigfortran gfortran mpiifort ifort mpipgf77 pgf77 mpipgf90 pgf90

     

     

  • За додатковою інформацією:
    • Переглянути довідкові сторінки (якщо існують)
    • Запустити ім'я сценарію з опцією -help (майже марно)
    • Безпосередньо переглянути сценарій самому

     

  • За замовчуванням скрипти націлені на типову версію свого основного компілятора та бібліотеку MPI за замовчуванням.
    • If you need to build with a different compiler version, you can use use LC's dotkit tool to query what's available and then load it. The MPI build script will then point to that. Наприклад:
      use -l           (to list available compilers)
      use ic-13.1.163  (use the package of interest)

       

    • If you need to build with a different version of the MPI library, see /usr/local/docs/linux.basics for advice.

 Running MVAPICH MPI Jobs:

  • MPI executables are launched using the SLURM srun command with the appropriate options. For example, to launch an 8-process MPI job split across two different nodes in the pdebug pool:
    srun -N2 -n8 -ppdebug a.out

     

  • The srun command is discussed in detail in the Running Jobs section of the Linux Clusters Overview tutorial.

 


 

Open MPI

 Загальна інформація:
  • Open MPI - це потоко-безпечна реалізація MPI-2 з відкритим вихідним кодом, яка розроблена і обслуговується консорціумом академічних, дослідницьких та індустріальних партнерів.

     

  • Open MPI доступний на більшості Linux кластерів LC. Необхідно завантажити потрібний ?(доткіт) пакунок, використовуючи"use" команду. Наприклад:
    use -l                 (список доступних пакунків)  use openmpi-gnu-1.4.3  (використати потрібний пакунок)

     

  • Це гарантує, що обгортка MPI-скрипта LC буде націлена на потрібну версію Open MPI.

     

  • Команди компілятора такі ж, як показано вище для MVAPICH.

     

  • Запуск Open MPI виконується по-іншому, ніж запуск MVAPICH MPI - необхідна команда mpiexec.

     

  • Детальну інформацію щодо використання для кластерів LC можна знайти у файлі /usr/local/docs/mpi.openmpi.basics.

     

  • Детальніше про Open MPI в цілому: www.open-mpi.org

 


 

Кластери IBM BlueGene:

 

  • На цих платформах підтримується лише бібліотека IBM MPI.

     

  • Ця реалізація IBM базується на MPICH2. Включає в себе функціональність MPI-2 крім динамічних процесів (Dynamic Processes).

     

  • Потоко-безпечність

     

  • Підтримуються C, C++, Fortran77/90/95

     

  • Для компіляції та виконання MPI програм дивись:

  Приступаючи до роботи


 Загальна структура програми MPI:

 

Загальна структура програми MPI

 

 Заголовний файл:

 

  • Необхідний для всіх програм, які роблять виклики бібліотеки MPI.

     

         Заголовний файл C      Заголовний файл Fortran #include "mpi.h" include 'mpif.h'

     

     

  • З MPI-3 Fortran переважно використовують модуль USE mpi_f08 замість include-файлу, показаного вище.

 Формат викликів MPI:

 

  • У C імена чутливі до регістру; у Fortran - не чутливі.

     

  • Програми не повинні оголошувати змінні або функції з іменами, що починаються префіксом MPI_ або PMPI_ (інтерфейс профілювання).

     

    Зв'язування з C Формат:   rc = MPI_Xxxxx(parameter, ... )   Приклад:   rc = MPI_Bsend(&buf,count,type,dest,tag,comm)   Код помилки: Повертається як "rc". MPI_SUCCESS у разі успіху Зв'язування в Fortran Формат:   CALL MPI_XXXXX(parameter,..., ierr)
      call mpi_xxxxx(parameter,..., ierr)  
    Приклад:   CALL MPI_BSEND(buf,count,type,dest,tag,comm,ierr)   Код помилки: Повертається як параметр "ierr". MPI_SUCCESS у разі успіху

     

 Комунікатори (Communicators) і групи (Groups):

 

  • MPI використовує об'єкти, які називаються комунікаторами (Communicators) і групами (Groups), щоб визначити набір процесів, які можуть спілкуватися один з одним.

     

  • Більшість процедур MPI потребує зазначення комунікатора в якості аргументу.

     

  • Комунікатори та групи будуть описані більш докладно пізніше. До того просто використовуйте MPI_COMM_WORLD кожного разу, коли потрібен комунікатор - це попередньо визначений комунікатор, що містить усі процеси MPI.

     

     

 Ранг:

 

  • Всередині комунікатора кожен процес має свій власний унікальний цілочисельний ідентифікатор, що призначається системою, коли процес ініціалізується. Ранг іноді називається "ідентифікатором завдання". Послідовність рангів є неперервною і починається від нуля.

     

  • Використовується програмістом, щоб вказати вихідне та кінцеве розташування повідомлення. Часто використовується додатком в умові для контролю виконання програми (якщо ранг = 0 виконати це / якщо ранг = 1 виконати інше).

 Обробка помилок:

 

  • Більшість підпрограм MPI включають параметр код повернення/помилки, як описано в попередньому розділі "Формат викликів MPI".

     

  • Однак відповідно до стандарту MPI, поведінка за замовчуванням виклику MPI така, що операція переривається, якщо відбувається помилка. Це означає, що ви ймовірно не зможете отримати код повернення/помилки, відмінний від MPI_SUCCESS (нуль).

     

  • Стандарт забезпечує спосіб перевизначення такої обробки помилок за замовчуванням. Обговорення того, як це зробити, доступне тут. Також можна ознайомитися з розділом стандарту MPI про обробку помилок, що доступний за посиланнямhttp://www.mpi-forum.org/docs/mpi-11-html/node148.html.

     

  • Види помилок, що відображаються користувачу, залежать від реалізації.

  Підпрограми середовища управління


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

 

MPI_Init

 

Ініціалізує середовище виконання MPI. Ця функція повинна бути викликана в кожній програмі MPI, повинна бути викликана перед будь-якими іншими функціями MPI і має викликатися тільки один раз у програмі MPI. Для програм на C MPI_Init може використовуватися для передачі аргументів командного рядка всім процесам, хоча це не вимагається стандартом і залежить від реалізації.

MPI_Init (&argc,&argv) 
MPI_INIT (ierr)

 

MPI_Comm_size

 

Повертає загальну кількість процесів MPI у вказаний комунікатор, такий як MPI_COMM_WORLD. Якщо комунікатором є MPI_COMM_WORLD, тоді це відображатиме кількість завдань MPI, доступних для застосунку.

MPI_Comm_size (comm,&size) 
MPI_COMM_SIZE (comm,size,ierr)

 

MPI_Comm_rank

 

Повертає ранг процесу MPI, що викликається, в межах вказаного комунікатора. Спочатку кожному процесу буде присвоєно унікальний цілочисельний ранг в межах від 0 до кількість завдань - 1 в рамках комунікатора MPI_COMM_WORLD. Цей ранг часто називають ідентифікатором завдання. Якщо процес стає пов'язаним з іншими комунікаторами, він також буде мати унікальний ранг в межах кожного з них.

MPI_Comm_rank (comm,&rank) 
MPI_COMM_RANK (comm,rank,ierr)

 

MPI_Abort

 

Зупиняє всі процеси MPI, пов'язані з комунікатором. У більшості реалізацій MPI зупиняє ВСІ процеси незалежно від вказаного комунікатора.

MPI_Abort (comm,errorcode)
MPI_ABORT (comm,errorcode,ierr)

 

MPI_Get_processor_name

 

Повертає ім'я процесора. Також повертає довжину імені. Буфер для "імені" має бути розміром щонайбільше MPI_MAX_PROCESSOR_NAME символів. Що саме повертається в "ім'я" залежить від реалізації - може бути не таким самим, як вивід команд оболонки "hostname" або "host".

MPI_Get_processor_name (&name,&resultlength)
MPI_GET_PROCESSOR_NAME (name,resultlength,ierr)

 

MPI_Get_version

 

Повертає версію (1 або 2) і підверсію MPI.

MPI_Get_version (&version,&subversion)
MPI_GET_VERSION (version,subversion,ierr)

 

MPI_Initialized

 

Вказує, чи була викликана MPI_Init - повертає прапор як логічне true (1) або false (0). MPI вимагає, щоб MPI_Init викликалася один раз і тільки один кожним процесом. Це може створити проблеми для модулів, які потребують використання MPI і готові викликати MPI_Init, якщо це необхідно. MPI_Initialized вирішує цю проблему.

MPI_Initialized (&flag) 
MPI_INITIALIZED (flag,ierr)

 

MPI_Wtime

 

Повертає час виклику процесора в секундах (подвійної точності).

MPI_Wtime ()
MPI_WTIME ()

 

MPI_Wtick

 

Повертає роздільну здатність MPI_Wtime у секундах (подвійної точності).

MPI_Wtick ()
MPI_WTICK ()

 

 

MPI_Finalize

 

Припиняє роботу середовища виконання MPI. Ця функція повинна бути останньою підпрограмою MPI, викликаною в кожній програмі MPI - жодна інша підпрограма MPI не може бути викликана після цього.

MPI_Finalize ()
MPI_FINALIZE (ierr)

 

 


 

Приклади: підпрограми середовища управління

 

 Мова С - приклад підпрограми середовища управління
   #include "mpi.h"
   #include <stdio.h>

   int main(argc,argv)
   int argc;
   char *argv[]; {
   int  numtasks, rank, len, rc; 
   char hostname[MPI_MAX_PROCESSOR_NAME];

   rc = MPI_Init(&argc,&argv);
   if (rc != MPI_SUCCESS) {
     printf ("Error starting MPI program. Terminating.\n");  
MPI_Abort(MPI_COMM_WORLD, rc);  }    
MPI_Comm_size(MPI_COMM_WORLD,&numtasks);  
MPI_Comm_rank(MPI_COMM_WORLD,&rank);  
MPI_Get_processor_name(hostname, &len);  
printf ("Number of tasks= %d My rank= %d Running on %s\n", numtasks,rank,hostname);
    /*******  щось виконується *******/    
MPI_Finalize();  }

 

 

 Fortran - приклад підпрограми середовища управління
   program simple
   include 'mpif.h'

   integer numtasks, rank, len, ierr  
   character(MPI_MAX_PROCESSOR_NAME) hostname

   call MPI_INIT(ierr)
   if (ierr .ne. MPI_SUCCESS) then
      print *,'Error starting MPI program. Terminating.'
      call MPI_ABORT(MPI_COMM_WORLD, rc, ierr)
   end if

   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)
   call MPI_GET_PROCESSOR_NAME(hostname, len, ierr)
   print *, 'Number of tasks=',numtasks,' My rank=',rank,
  &         ' Running on=',hostname

C ****** do some work ******

   call MPI_FINALIZE(ierr)

   end

 


  MPI Завдання 1

Приступаючи до роботи

Огляд:
  • Увійти в кластер LC, використовуючи свій логін і одноразовий пароль токена
  • Ознайомитися з MPI-середовищем LC
  • Написати просту MPI-програму «Hello World», використовуючи декілька підпрограм середовища управління MPI
  • Успішно скомпілювати програму
  • Успішно запустити програму - кількома різними способами
  • Ознайомитися з MPI-документацією LC

Перейти до виконання зараз


  Підпрограми зв'язку типу "точка-точка"

Загальні поняття

 Для початку простий приклад:

 

 

  • Значення числа Пі можна обчислити рядом способів. Розглянемо такий метод наближення Пі
    1. Впишемо коло в квадрат
    2. Згенеруємо випадковим чином точку в квадраті
    3. Визначимо кількість точок в квадраті, які лежать також у колі
    4. Нехай r - кількість точок у колі, поділена на кількість точок в квадраті
    5. Пі ~ 4 r
    6. Зверніть увагу, що чим більше точок згенеровано, тим краще наближення

     

  • Послідовний псевдо-код для цієї процедури:

     

    npoints = 10000
    circle_count = 0
    
    do j = 1,npoints
      generate 2 random numbers between 0 and 1
      xcoordinate = random1
      ycoordinate = random2
      if (xcoordinate, ycoordinate) inside circle
      then circle_count = circle_count + 1
    end do
    
    PI = 4.0*circle_count/npoints
    

     

     

  • Привести до "приголомшливо паралельного" рішення:
    • Розірвати цикл ітерацій на шматки, які можуть бути виконані різними завданнями одночасно.
    • Кожне завдання виконує свою частину циклу кілька разів.
    • Кожне завдання може робити свою роботу, не вимагаючи жодної інформації від інших завдань (немає залежності від даних).
    • Головне завдання отримує результати від інших завдань за допомогою операцій надсилання/отримання типу "точка-точка".

     

  • Псевдо-код рішення: червоним підкреслено зміни для розпаралелювання.

     

    npoints = 10000
    circle_count = 0
    
    p = number of tasks
    num = npoints/p
    
    find out if I am MASTER or WORKER 
    
    do j = 1,num 
      generate 2 random numbers between 0 and 1
      xcoordinate = random1
      ycoordinate = random2
      if (xcoordinate, ycoordinate) inside circle
      then circle_count = circle_count + 1
    end do
    
    if I am MASTER
      receive from WORKERS their circle_counts
      compute PI (use MASTER and WORKER calculations)
    else if I am WORKER
      send to MASTER circle_count
    endif

     

    Приклад MPI-програм на C:    mpi_pi_reduce.c       dboard.c   
      Приклад MPI-програм на мові Fortran:    mpi_pi_reduce.f       dboard.f

     

Один метод визначення Пі

Один метод визначення Пі

 Типи операцій "точка-точка":

 

  • MPI-операції типу "точка-точка" зазвичай залучають передачу повідомлень між двома і тільки двома різними завданнями MPI. Одне завдання виконує операцію надсилання, а друге завдання виконує добір операції приймання.

     

  • Існують різні види підпрограм надсилання й приймання для різних цілей. Наприклад:
    • Синхронне надсилання
    • Блокуюче надсилання / блокуюче приймання
    • Неблокуюче надсилання / неблокуюче приймання
    • Буферизоване надсилання
    • Комбіноване надсилання/приймання
    • Надсилання "за готовністю"

     

  • Будь-який тип підпрограми надсилання може працювати в парі з будь-яким типом підпрограми приймання.

     

  • MPI також надає кілька підпрограм, пов'язаних з операціями надсилання - приймання, таких, що використовуються для очікування прибуття повідомлення або спроби дізнатися, чи повідомлення прибуло.
 Буферизація:
  • В ідеальному світі кожна операція надсилання була б ідеально синхронізована з відповідною операцією отримання. Це трапляється досить рідко. Так чи інакше, MPI-реалізації повинні бути здатні зберігати дані, коли два завдання не синхронізовано.

     

  • Розглянемо наступні два випадки:
    • Операція надсилання відбувається 5 секунд до того, поки операція приймання буде готова - де повідомлення тоді, коли приймання очікує?
    • Кілька надсилань прибуває до того самого завдання приймання, яке може прийняти тільки одне надсилання за один раз - що відбувається з повідомленнями, які "повертаються назад"?

     

  • Реалізація MPI (не стандарт MPI) вирішує, що відбувається з даними у подібних випадках. Як правило, зона системного буферу зарезервована для зберігання даних, які перебувають в дорозі. Наприклад:

    Приклад системної буферизації

     

  • Простір системного буфера є:
    • Непрозорим програмісту і повністю керованим бібліотекою MPI
    • Скінченним ресурсом, який може бути легко вичерпаним
    • Часто таємничим і не дуже добре документованим
    • Здатним існувати на стороні надсилання, стороні приймання або обох
    • Тим, що може підвищити продуктивність програми, тому що дозволяє операціям надсилання - приймання бути асинхронними.

     

  • Адресний простір, яким керує користувач (тобто змінні програми), називається буфером застосунку. MPI також надає керований користувачем буфер надсилання.
 Блокування проти неблокування:
  • Більшість MPI-процедур "точка-точка" можуть бути використані в режимі блокування або неблокування.

     

  • Блокування:
    • Блокуюча підпрограма надсилання виконає "return" лише тоді, коли буде безпечно змінити буфер застосунку (надісланими даними) для повторного використання. Безпечно означає, що зміни не вплинуть на дані, призначені для завдання приймання. Безпечно не означає, що дані фактично отримані - вони можуть знаходитися у системному буфері.
    • Блокуюче надсилання може бути синхронним, що означає, що завданню приймання повинно надаватися підтвердження про безпечне надсилання.
    • Блокуюче надсилання може бути асинхронним, якщо системний буфер використовується для зберігання даних поки вони врешті-реш не будуть доставлені до завдання приймання.
    • Блокуюче приймання виконає "return" після того, як дані прибудуть і будуть готовими до використання програмою.

     

  • Неблокування:
    • Підпрограми неблокуючого надсилання й приймання працюють подібно - вони будуть виконувати "return" майже негайно. Вони не очікують будь-якої події зв'язку для завершення, такої як копіювання повідомлення з пам'яті користувача до простору системного буферу або фактичного прибуття повідомлення.
    • Неблокуючі операції просто виконують запит бібліотеки MPI для виконання операції, коли це можливо. Користувач не може передбачити, коли це станеться.
    • Не є безпечно змінювати буфер застосунку (простір змінних), поки ви точно не дізнаєтесь, що запитувана неблокуюча операція була справді виконана бібліотекою. Для цього використовуються підпрограми, що «чекають».
    • Неблокуючі зв'язки використовуються в першу чергу для того, щоб перекрити зв'язки обчисленнями та використати можливий приріст продуктивності.

 Порядок й ?(справедливість):

  • Порядок:
    • MPI гарантує, що повідомлення не наздоганяють один одного.
    • Якщо відправник надсилає два повідомлення підряд (Повідомлення 1 та Повідомлення 2) в те саме місця призначення і в обидвох співпадають отримувачі, операція приймання прийме Повідомлення 1 перед Повідомленням 2.
    • If a receiver posts two receives (Receive 1 and Receive 2), in succession, and both are looking for the same message, Receive 1 will receive the message before Receive 2.
    • Правила слідування не застосовуються, якщо у операціях комунікації бере участь декілька потоків.

     

  • Fairness:
    • MPI не гарантує справедливість - програмісту належить запобігти "операційному голодуванню".
    • Приклад: завдання 0 надсилає повідомлення завданню 2. Проте завдання 1 посилає конкуруюче повідомлення, яке потребує прийняття завданням 2. Лише одне з відправлень буде завершено.

      MPI не гарантує чесність


  Підпрограми зв'язку типу "точка-точка"

Аргументи підпрограм передачі повідомлень MPI

MPI-програми зв'язку типу "точка-точка", як правило, мають список аргументів, що приймає один із таких форматів:

 

Блокуюче надсилання MPI_Send(buffer,count,type,dest,tag,comm)   Неблокуюче надсилання MPI_Isend(buffer,count,type,dest,tag,comm,request)   Блокуюче приймання MPI_Recv(buffer,count,type,source,tag,comm,status)   Неблокуюче приймання MPI_Irecv(buffer,count,type,source,tag,comm,request)
Буфер (buffer)

 

Адресний простір програми (застосунку), що посилається на дані, які можуть бути відправлені або отримані. У більшості випадків це просто ім'я змінної, яке буде надіслане/прийняте. Для програм на мові C цей аргумент передається за посиланням й зазвичай має починатися амперсантом: &var1

 

Кількість даних (count)

 

Вказує кількість елементів даних певного типу, які буде надіслано.

 

Тип даних (type)

 

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

 

Типи даних C Типи даних Fortran MPI_CHAR signed char MPI_CHARACTER character(1) MPI_WCHAR wchar_t - wide character     MPI_SHORT signed short int     MPI_INT signed int MPI_INTEGER
MPI_INTEGER1  
MPI_INTEGER2
MPI_INTEGER4
integer
integer*1
integer*2
integer*4 MPI_LONG signed long int     MPI_LONG_LONG_INT  
MPI_LONG_LONG
signed long long int     MPI_SIGNED_CHAR signed char     MPI_UNSIGNED_CHAR unsigned char     MPI_UNSIGNED_SHORT unsigned short int     MPI_UNSIGNED unsigned int     MPI_UNSIGNED_LONG unsigned long int     MPI_UNSIGNED_LONG_LONG unsigned long long int     MPI_FLOAT float MPI_REAL
MPI_REAL2  
MPI_REAL4
MPI_REAL8
real
real*2
real*4
real*8 MPI_DOUBLE double MPI_DOUBLE_PRECISION double precision MPI_LONG_DOUBLE long double     MPI_C_COMPLEX
MPI_C_FLOAT_COMPLEX
float _Complex MPI_COMPLEX complex MPI_C_DOUBLE_COMPLEX double _Complex MPI_DOUBLE_COMPLEX double complex MPI_C_LONG_DOUBLE_COMPLEX long double _Complex     MPI_C_BOOL _Bool MPI_LOGICAL logical MPI_C_LONG_DOUBLE_COMPLEX long double _Complex     MPI_INT8_T  
MPI_INT16_T
MPI_INT32_T 
MPI_INT64_T
int8_t
int16_t
int32_t 
int64_t     MPI_UINT8_T  
MPI_UINT16_T 
MPI_UINT32_T 
MPI_UINT64_T
uint8_t
uint16_t
uint32_t
uint64_t     MPI_BYTE 8 binary digits MPI_BYTE 8 binary digits MPI_PACKED data packed or unpacked with MPI_Pack()/ MPI_Unpack MPI_PACKED data packed or unpacked with MPI_Pack()/ MPI_Unpack

 

Примітки:

  • Програмісти також можуть створювати свої власні типи даних (див. Похідні типи даних).
  • MPI_BYTE і MPI_PACKED не належать до стандартних типів C або Fortran.
  • Типи, підсвічені СІРИМ ШРИФТОМ, рекомендується використовувати, якщо це можливо.
  • Деякі реалізації можуть включати додаткові елементарні типи даних (MPI_LOGICAL2, MPI_COMPLEX32, і т. д.). Перевірте заголовний файл MPI.

 

Призначення (dest)

 

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

 

Джерело (source)

 

Аргумент підпрограм приймання, який вказує на процес, де було створено повідомлення. Вказується як ранг процесу надсилання. Може бути встановлено як MPI_ANY_SOURCE для того, щоб отримувати повідомлення від будь-якого завдання.

 

Тег (tag)

 

Довільне невід'ємне ціле число, призначене програмісту для однозначної ідентифікації повідомлення. В операціях надсилання й приймання має співпадати тег повідомлення. В операціях приймання може використовуватися MPI_ANY_TAG для прийому будь-якого повідомлення, незалежно від його тега. Стандарт MPI гарантує, що цілі числа 0-32767 може бути використані як теги, але більшість реалізацій надають більш широкий діапазон, ніж цей.

 

Комунікатор (comm)

 

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

 

Статус (status)

 

Для операції приймання визначає джерело і тег повідомлення. В C цей аргумент є вказівником на попередньо визначені структури MPI_Status (ex. stat.MPI_SOURCE stat.MPI_TAG). У Fortran - це цілочисельний масив розміром MPI_STATUS_SIZE (ex. stat(MPI_SOURCE) stat(MPI_TAG)). Крім того, фактична кількість отриманих байтів доступна зі Статусу за допомогою підпрограми MPI_Get_count.

 

Запит (request)

 

Використовується неблокуючими операціями надсилання та приймання. Оскільки неблокуючі операції можуть виконати "return" до того, як необхідний простір системного буферу стане доступним, система видає унікальний "номер запиту". Програміст використовує це призначене системою "керування" пізніше (у процедурі типу WAIT), щоб визначити завершення неблокуючої операції. В C цей аргумент є вказівником на попередньо визначену структуру MPI_Request. У Fortran він є цілим числом.


  Підпрограми зв'язку типу "точка-точка"

Блокуючі підпрограми передачі повідомлень

Блокуючі MPI-підпрограми передачі повідомлень, що найчастіше використовуються, описані нижче.

 

  MPI_Send

 

Основна блокуюча операція надсилання. Підпрограма виконує "return" лише після того, як буфер застосунку у надсилаючому завданні є вільним для повторного використання. Зверніть увагу, що ця процедура може бути реалізована по-різному в різних системах. Стандарт MPI дозволяє використовувати системний буфер, але не вимагає цього. Деякі реалізації можуть фактично використовувати синхронне надсилання (описане нижче) для реалізації базового блокуючого надсилання.

MPI_Send (&buf,count,datatype,dest,tag,comm) 
MPI_SEND (buf,count,datatype,dest,tag,comm,ierr)

 

MPI_Recv

 

Приймає повідомлення і заблоковується доти, поки запитувані дані стануть доступними у буфері застосунку в завданні приймання.

MPI_Recv (&buf,count,datatype,source,tag,comm,&status) 
MPI_RECV (buf,count,datatype,source,tag,comm,status,ierr)

 

MPI_Ssend

 

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

MPI_Ssend (&buf,count,datatype,dest,tag,comm) 
MPI_SSEND (buf,count,datatype,dest,tag,comm,ierr)

 

MPI_Bsend

 

Буферизоване блокуюче надсилання: дозволяє програмісту виділити необхідний обсяг простору буфера, в якому дані можуть бути скопійовані, поки виконується надсилання. Ізолює проблеми, пов'язані з недостатнім обсягом системного буфера. Підпрограма виконує "return" після того, як дані були скопійовані з простору буферу застосунку у виділений буфер надсилання. Повинна використовуватись з підпрограмою MPI_Buffer_attach.

MPI_Bsend (&buf,count,datatype,dest,tag,comm) 
MPI_BSEND (buf,count,datatype,dest,tag,comm,ierr)

 

MPI_Buffer_attach 
MPI_Buffer_detach

 

Використовуються програмістом, щоб виділити/звільнити простір буферу повідомлення, що використовується підпрограмою MPI_Bsend. Розмір аргументу задається фактичним обсягом байтів даних, а не кількістю елементів даних. Тільки один буфер може бути прикріплений до процесу за один раз. Note that the IBM implementation uses MPI_BSEND_OVERHEAD bytes of the allocated buffer for overhead.

MPI_Buffer_attach (&buffer,size) 
MPI_Buffer_detach (&buffer,size) 
MPI_BUFFER_ATTACH (buffer,size,ierr) 
MPI_BUFFER_DETACH (buffer,size,ierr)

 

MPI_Rsend

 

Блокуюче надсилання "за готовністю". Слід використовувати лише якщо програміст впевнений, що відповідне приймання вже було розміщене.

MPI_Rsend (&buf,count,datatype,dest,tag,comm) 
MPI_RSEND (buf,count,datatype,dest,tag,comm,ierr)

 

MPI_Sendrecv

 

Send a message and post a receive before blocking. Will block until the sending application buffer is free for reuse and until the receiving application buffer contains the received message.

MPI_Sendrecv (&sendbuf,sendcount,sendtype,dest,sendtag, 
...... &recvbuf,recvcount,recvtype,source,recvtag, 
...... comm,&status) 
MPI_SENDRECV (sendbuf,sendcount,sendtype,dest,sendtag, 
...... recvbuf,recvcount,recvtype,source,recvtag, 
...... comm,status,ierr)

 

MPI_Wait
MPI_Waitany
MPI_Waitall
MPI_Waitsome

 

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

MPI_Wait (&request,&status) 
MPI_Waitany (count,&array_of_requests,&index,&status) 
MPI_Waitall (count,&array_of_requests,&array_of_statuses) 
MPI_Waitsome (incount,&array_of_requests,&outcount, 
...... &array_of_offsets, &array_of_statuses) 
MPI_WAIT (request,status,ierr) 
MPI_WAITANY (count,array_of_requests,index,status,ierr) 
MPI_WAITALL (count,array_of_requests,array_of_statuses, 
...... ierr) 
MPI_WAITSOME (incount,array_of_requests,outcount, 
...... array_of_offsets, array_of_statuses,ierr)

 

MPI_Probe

 

Виконує тест на блокування для повідомлення. Аргументи MPI_ANY_SOURCE і MPI_ANY_TAG можуть використовуватись для тестування повідомлення від будь-якого джерела або з будь-яким тегом. Для підпрограм C фактичне джерело і тег повертаються у структурі статусу як status.MPI_SOURCE і status.MPI_TAG. Для підпрограм Fortran вони повертаються в цілочисельний масив status(MPI_SOURCE) і status(MPI_TAG).

MPI_Probe (source,tag,comm,&status) 
MPI_PROBE (source,tag,comm,status,ierr)

 

 


 

Приклади: блокуючі підпрограми передачі повідомлень

Завдання 0 відправляє запит завданню 1 і чекає повернення

 

 Мова С - приклад блокуючої підпрограми передачі повідомлень
#include "mpi.h"
#include <stdio.h>

int main(argc,argv) 
int argc;
char *argv[];  {
int numtasks, rank, dest, source, rc, count, tag=1;  
char inmsg, outmsg='x';
MPI_Status Stat;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (rank == 0) {
  dest = 1;
  source = 1;
  rc = MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
  rc = MPI_Recv(&inmsg, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
  } 

else if (rank == 1) {
  dest = 0;
  source = 0;
  rc = MPI_Recv(&inmsg, 1, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
  rc = MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD);
  }

rc = MPI_Get_count(&Stat, MPI_CHAR, &count);
printf("Task %d: Received %d char(s) from task %d with tag %d \n",
       rank, count, Stat.MPI_SOURCE, Stat.MPI_TAG);


MPI_Finalize();
}

 

 

 Fortran - приклад блокуючої підпрограми передачі повідомлень
   program ping
   include 'mpif.h'

   integer numtasks, rank, dest, source, count, tag, ierr
   integer stat(MPI_STATUS_SIZE)
   character inmsg, outmsg
   outmsg = 'x'
   tag = 1

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   if (rank .eq. 0) then
      dest = 1
      source = 1
      call MPI_SEND(outmsg, 1, MPI_CHARACTER, dest, tag, 
 &            MPI_COMM_WORLD, ierr)
      call MPI_RECV(inmsg, 1, MPI_CHARACTER, source, tag, 
 &            MPI_COMM_WORLD, stat, ierr)

   else if (rank .eq. 1) then
      dest = 0
      source = 0
      call MPI_RECV(inmsg, 1, MPI_CHARACTER, source, tag, 
 &       MPI_COMM_WORLD, stat, err)
      call MPI_SEND(outmsg, 1, MPI_CHARACTER, dest, tag, 
 &       MPI_COMM_WORLD, err)
   endif

   call MPI_GET_COUNT(stat, MPI_CHARACTER, count, ierr)
   print *, 'Task ',rank,': Received', count, 'char(s) from task',
  &         stat(MPI_SOURCE), 'with tag',stat(MPI_TAG)

   call MPI_FINALIZE(ierr)

   end

 


  Підпрограми зв'язку типу "точка-точка"

Неблокуючі підпрограми передачі повідомлень

Неблокуючі MPI-підпрограми передачі повідомлень, що найчастіше використовуються, описані нижче.

 

MPI_Isend

 

Визначає місце в пам'яті, що служитиме як буфер надсилання. Обробка продовжується відразу, не чекаючи, щоб повідомлення було скопійовано з буфера застосунку. A communication request handle is returned for handling the pending message status. Програма не може змінити буфер застосунку, поки наступні виклики MPI_Wait або MPI_Test не вкажуть, що неблокуюче надсилання завершено.

MPI_Isend (&buf,count,datatype,dest,tag,comm,&request) 
MPI_ISEND (buf,count,datatype,dest,tag,comm,request,ierr)

 

MPI_Irecv

 

Визначає місце в пам'яті, що служитиме як буфер приймання. Обробка продовжується відразу, фактично не чекаючи, щоб повідомлення було прийнято і скопійовано в буфер застосунку. A communication request handle is returned for handling the pending message status. Програма повинна виконувати виклики MPI_Wait або MPI_Test, щоб визначити, коли неблокуюча операція приймання завершилась і запитуване повідомлення знаходиться в буфері застосунку.

MPI_Irecv (&buf,count,datatype,source,tag,comm,&request) 
MPI_IRECV (buf,count,datatype,source,tag,comm,request,ierr)

 

MPI_Issend

 

Неблокуюче синхронне надсилання. Схожа на MPI_Isend(), за винятком того, що MPI_Wait() або MPI_Test() вказує, коли процес призначення отримав повідомлення.

MPI_Issend (&buf,count,datatype,dest,tag,comm,&request) 
MPI_ISSEND (buf,count,datatype,dest,tag,comm,request,ierr)

 

MPI_Ibsend

 

Неблокуюче буферизоване надсилання. Схожа на MPI_Bsend(), за винятком того, що MPI_Wait() або MPI_Test() вказує, коли процес призначення отримав повідомлення. Повинна використовуватись з підпрограмою MPI_Buffer_attach.

MPI_Ibsend (&buf,count,datatype,dest,tag,comm,&request) 
MPI_IBSEND (buf,count,datatype,dest,tag,comm,request,ierr)

 

MPI_Irsend

 

Неблокуюче надсилання "за готовністю". Схожа на MPI_Bsend(), за винятком того, що MPI_Wait() або MPI_Test() вказує, коли процес призначення отримав повідомлення. Слід використовувати лише тоді, коли програміст впевнений, що відповідне приймання вже було розміщене.

MPI_Irsend (&buf,count,datatype,dest,tag,comm,&request) 
MPI_IRSEND (buf,count,datatype,dest,tag,comm,request,ierr)

 

MPI_Test
MPI_Testany
MPI_Testall
MPI_Testsome

 

MPI_Test перевіряє стан вказаної неблокуючої операції надсилання або приймання. Параметр "flag" повертається як логічне true (1), якщо операція була завершена, та логічне false (0), якщо не була. Для кількох неблокучих операцій програміст може вказати завершення жодної, всіх або деякої операції.

MPI_Test (&request,&flag,&status) 
MPI_Testany (count,&array_of_requests,&index,&flag,&status)
MPI_Testall (count,&array_of_requests,&flag,&array_of_statuses)
MPI_Testsome (incount,&array_of_requests,&outcount,
...... &array_of_offsets, &array_of_statuses)
MPI_TEST (request,flag,status,ierr)
MPI_TESTANY (count,array_of_requests,index,flag,status,ierr)
MPI_TESTALL (count,array_of_requests,flag,array_of_statuses,ierr)
MPI_TESTSOME (incount,array_of_requests,outcount,
...... array_of_offsets, array_of_statuses,ierr)

 

MPI_Iprobe

 

Виконує тест на неблокування для повідомлення. Аргументи MPI_ANY_SOURCE і MPI_ANY_TAG можуть бути використані для тестування повідомлення від будь-якого джерела або з будь-яким тегом. Цілочисельний параметр "flag" повертається як логічне true (1), якщо повідомлення прибуло, і логічне false (0), якщо не прибуло. Для підпрограм C фактичне джерело і тег повертаються у структурі статусу як status.MPI_SOURCE і status.MPI_TAG. Для підпрограм Fortran вони повертаються в цілочисельний масив status(MPI_SOURCE) і status(MPI_TAG).

MPI_Iprobe (source,tag,comm,&flag,&status)
MPI_IPROBE (source,tag,comm,flag,status,ierr)

 

 


 

Приклади: неблокуючі підпрограми передачі повідомлень

Nearest neighbor exchange in a ring topology

 

 Мова С - приклад неблокуючої програми передачі повідомлення
#include "mpi.h"
#include <stdio.h>

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, next, prev, buf[2], tag1=1, tag2=2;
MPI_Request reqs[4];
MPI_Status stats[2];

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

prev = rank-1;
next = rank+1;
if (rank == 0)  prev = numtasks - 1;
if (rank == (numtasks - 1))  next = 0;

MPI_Irecv(&buf[0], 1, MPI_INT, prev, tag1, MPI_COMM_WORLD, &reqs[0]);
MPI_Irecv(&buf[1], 1, MPI_INT, next, tag2, MPI_COMM_WORLD, &reqs[1]);

MPI_Isend(&rank, 1, MPI_INT, prev, tag2, MPI_COMM_WORLD, &reqs[2]);
MPI_Isend(&rank, 1, MPI_INT, next, tag1, MPI_COMM_WORLD, &reqs[3]);
  
      {  do some work  }

MPI_Waitall(4, reqs, stats);

MPI_Finalize();
}

 

 

 Fortran - приклад неблокуючої програми передачі повідомлення
   program ringtopo
   include 'mpif.h'

   integer numtasks, rank, next, prev, buf(2), tag1, tag2, ierr
   integer stats(MPI_STATUS_SIZE,2), reqs(4)
   tag1 = 1
   tag2 = 2

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   prev = rank - 1
   next = rank + 1
   if (rank .eq. 0) then
      prev = numtasks - 1
   endif
   if (rank .eq. numtasks - 1) then
      next = 0
   endif

   call MPI_IRECV(buf(1), 1, MPI_INTEGER, prev, tag1, 
 &     MPI_COMM_WORLD, reqs(1), ierr)
   call MPI_IRECV(buf(2), 1, MPI_INTEGER, next, tag2, 
 &     MPI_COMM_WORLD, reqs(2), ierr)

   call MPI_ISEND(rank, 1, MPI_INTEGER, prev, tag2,
 &     MPI_COMM_WORLD, reqs(3), ierr)
   call MPI_ISEND(rank, 1, MPI_INTEGER, next, tag1,
 &     MPI_COMM_WORLD, reqs(4), ierr)

C        do some work

   call MPI_WAITALL(4, reqs, stats, ierr);

   call MPI_FINALIZE(ierr)

   end

 


  MPI Завдання 2

Надсилання повідомлення типу "точка-точка"

Огляд:
  • Увійти в кластер LC, якщо ви ще не ввійшли до системи
  • Використати MPI-програму "Hello World" з Завдання 1, додати блокуючу MPI-підпрограму типу "точка-точка" для надсилання та отримання повідомлень
  • Успішної скомпілювати програму
  • Успішно запустити програму - кількома різними способами
  • Спробувати те ж саме з неблокуючими підпрограмами надсилання й приймання

Перейти до виконання зараз


  Підпрограми колективної комунікації


 Область:

 

  • Підпрограми колективної комунікації повинні включати всі процеси у межах комунікатора.

     

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

     

  • Програміст відповідальний за те, щоб всі процеси в межах комунікатора брали участь у будь-якій колективній операції.

 Види колективних операцій:Колективні комунікації

 

  • Синхронізація - процеси очікують, поки всі члени групи досягнуть точки синхронізації.

     

  • Data Movement - broadcast, scatter/gather, all to all.

     

  • Колективні обчислення (агрегація) - один з членів групи збирає дані від інших членів і виконує операції (мінімум, максимум, додавання, множення тощо) з цими даними.
 Programming Considerations and Restrictions:

 

  • З MPI-3 колективні операції можуть бути блокуючими або неблокуючими. У цьому підручнику розглядаються тільки блокуючі операції.

     

  • Підпрограми колективної комунікації не приймають такий аргумент як тег повідомлення.

     

  • Колективні операції всередині підмножини процесів здійснюють спочатку виділення підмножин у нову групу і тоді прикріплення нової групи до нового комунікатора (обговорюється в розділі Підпрограми управління групами та комунікаторами).

     

  • Можна використовувати лише з стандартними типами даних MPI - не з Похідними типами даних.

     

  • MPI-2 extended most collective operations to allow data movement between intercommunicators (not covered here).

 


 

Підпрограми колективної комунікації

 

MPI_Bcast

 

Операція переміщення даних. Транслює (надсилає) повідомлення з процесу з рангом "root" до всіх інших процесів у групі. 

MPI_Bcast (&buffer,count,datatype,root,comm) 
MPI_BCAST (buffer,count,datatype,root,comm,ierr)

 

MPI_Scatter

 

Операція переміщення даних. Розподіляє окремі повідомлення від одного джерела завдання до кожного завдання у групі. 

MPI_Scatter (&sendbuf,sendcnt,sendtype,&recvbuf, 
  ......  recvcnt,recvtype,root,comm) 
MPI_SCATTER (sendbuf,sendcnt,sendtype,recvbuf, 
  ......  recvcnt,recvtype,root,comm,ierr)

 

MPI_Gather

 

Операція переміщення даних. Збирає окремі повідомлення від кожного завдання у групі до одного завдання призначення. Ця підпрограма є зворотною до операції MPI_Scatter. 

MPI_Gather (&sendbuf,sendcnt,sendtype,&recvbuf, 
  ......  recvcount,recvtype,root,comm) 
MPI_GATHER (sendbuf,sendcnt,sendtype,recvbuf, 
  ......  recvcount,recvtype,root,comm,ierr)

 

MPI_Allgather

 

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

MPI_Allgather (&sendbuf,sendcount,sendtype,&recvbuf, 
  ......  recvcount,recvtype,comm) 
MPI_ALLGATHER (sendbuf,sendcount,sendtype,recvbuf, 
  ......  recvcount,recvtype,comm,info)

 

MPI_Reduce

 

Операція колективних обчислень. Виконує операцію агрегації зі всіх завдань у групі і поміщає результат в одне завдання. 

MPI_Reduce (&sendbuf,&recvbuf,count,datatype,op,root,comm) 
MPI_REDUCE (sendbuf,recvbuf,count,datatype,op,root,comm,ierr)

Попередньо визначені MPI-операції агрегації описані нижче. Користувачі також можуть визначати свої власні функції агрегації за допомогою звичайної підпрограми MPI_Op_create.

 

MPI-операція агрегації Типи даних C Типи даних Fortran MPI_MAX максимум integer, float integer, real, complex MPI_MIN мінімум integer, float integer, real, complex MPI_SUM сума integer, float integer, real, complex MPI_PROD добуток integer, float integer, real, complex MPI_LAND логічне І integer logical MPI_BAND побітове І integer, MPI_BYTE integer, MPI_BYTE MPI_LOR логічне АБО integer logical MPI_BOR побітове АБО integer, MPI_BYTE integer, MPI_BYTE MPI_LXOR логічне ВИКЛЮЧНЕ АБО integer logical MPI_BXOR побітове ВИКЛЮЧНЕ АБО integer, MPI_BYTE integer, MPI_BYTE MPI_MAXLOC максимальне значення і розташування float, double and long double real, complex,double precision MPI_MINLOC мінімальне значення і розташування float, double and long double real, complex, double precision

 

 

MPI_Allreduce

 

Операція колективних обчислень + переміщення даних. Виконує операцію агрегації і поміщає результат в усі завдання у групі. Це еквівалентно виконанню MPI_Reduce і потім MPI_Bcast. 

MPI_Allreduce (&sendbuf,&recvbuf,count,datatype,op,comm) 
MPI_ALLREDUCE (sendbuf,recvbuf,count,datatype,op,comm,ierr)

 

MPI_Reduce_scatter

 

Операція колективних обчислень + переміщення даних. Спочатку виконує поелементну агрегацію на векторі через всі завдання у групі. Далі результат вектора ділиться на окремі сегменти та розподіляється між завданнями. Це еквівалентно виконанню операції MPI_Reduce і тоді MPI_Scatter. 

MPI_Reduce_scatter (&sendbuf,&recvbuf,recvcount,datatype, 
  ......  op,comm) 
MPI_REDUCE_SCATTER (sendbuf,recvbuf,recvcount,datatype, 
  ......  op,comm,ierr)

 

MPI_Alltoall

 

Операція переміщення даних. Кожне завдання у групі виконує операцію розподілення, відправивши окреме повідомлення до всіх завдань у групі попорядку за індексом. 

MPI_Alltoall (&sendbuf,sendcount,sendtype,&recvbuf, 
  ......  recvcnt,recvtype,comm) 
MPI_ALLTOALL (sendbuf,sendcount,sendtype,recvbuf, 
  ......  recvcnt,recvtype,comm,ierr)

 

MPI_Scan

 

Виконує операцію сканування по відношенню до операції агрегації через групу завдань. 

MPI_Scan (&sendbuf,&recvbuf,count,datatype,op,comm) 
MPI_SCAN (sendbuf,recvbuf,count,datatype,op,comm,ierr)

 

MPI_Barrier

 

Операція синхронізації. Створює бар'єр синхронізації в групі. Кожне завдання, яке досягає виклику MPI_Barrier, блокується, поки всі завдання у групі не досягнуть того самого виклику MPI_Barrier. Тоді всі завдання можуть продовжуватись.

MPI_Barrier (comm)
MPI_BARRIER (comm,ierr)

 

 


 

Приклади: колективна комунікація

Виконання операції розподілення по рядках масиву

 

 

 Мова С - приклад колективної комунікації
#include "mpi.h"
#include <stdio.h>
#define SIZE 4

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, sendcount, recvcount, source;
float sendbuf[SIZE][SIZE] = {
  {1.0, 2.0, 3.0, 4.0},
  {5.0, 6.0, 7.0, 8.0},
  {9.0, 10.0, 11.0, 12.0},
  {13.0, 14.0, 15.0, 16.0}  };
float recvbuf[SIZE];

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

if (numtasks == SIZE) {
  source = 1;
  sendcount = SIZE;
  recvcount = SIZE;
  MPI_Scatter(sendbuf,sendcount,MPI_FLOAT,recvbuf,recvcount,
             MPI_FLOAT,source,MPI_COMM_WORLD);

  printf("rank= %d  Results: %f %f %f %f\n",rank,recvbuf[0],
         recvbuf[1],recvbuf[2],recvbuf[3]);
  }
else
  printf("Must specify %d processors. Terminating.\n",SIZE);

MPI_Finalize();
}

 

 

 Fortran - приклад колективної комунікації
   program scatter
   include 'mpif.h'

   integer SIZE
   parameter(SIZE=4)
   integer numtasks, rank, sendcount, recvcount, source, ierr
   real*4 sendbuf(SIZE,SIZE), recvbuf(SIZE)

C  Fortran stores this array in column major order, so the 
C  scatter will actually scatter columns, not rows.
   data sendbuf /1.0, 2.0, 3.0, 4.0, 
 &         5.0, 6.0, 7.0, 8.0,
 &         9.0, 10.0, 11.0, 12.0, 
 &         13.0, 14.0, 15.0, 16.0 /

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   if (numtasks .eq. SIZE) then
      source = 1
      sendcount = SIZE
      recvcount = SIZE
      call MPI_SCATTER(sendbuf, sendcount, MPI_REAL, recvbuf, 
 &   recvcount, MPI_REAL, source, MPI_COMM_WORLD, ierr)
      print *, 'rank= ',rank,' Results: ',recvbuf 
   else
      print *, 'Must specify',SIZE,' processors.  Terminating.' 
   endif

   call MPI_FINALIZE(ierr)

   end



     
  • Зразок програмного виводу:

     

    rank= 0  Results: 1.000000 2.000000 3.000000 4.000000
    rank= 1  Results: 5.000000 6.000000 7.000000 8.000000
    rank= 2  Results: 9.000000 10.000000 11.000000 12.000000
    rank= 3  Results: 13.000000 14.000000 15.000000 16.000000
    

  Похідні типи даних  

 

  • Як згадувалося раніше, MPI попередньо визначає власні примітивні типи даних:

     

    Типи даних C Типи даних Fortran
    MPI_CHAR
    MPI_WCHAR
    MPI_SHORT
    MPI_INT
    MPI_LONG
    MPI_LONG_LONG_INT 
    MPI_LONG_LONG	 	 
    MPI_SIGNED_CHAR
    MPI_UNSIGNED_CHAR
    MPI_UNSIGNED_SHORT
    MPI_UNSIGNED_LONG
    MPI_UNSIGNED
    MPI_FLOAT
    MPI_DOUBLE
    MPI_LONG_DOUBLE
    
    MPI_C_COMPLEX
    MPI_C_FLOAT_COMPLEX
    MPI_C_DOUBLE_COMPLEX
    MPI_C_LONG_DOUBLE_COMPLEX	 	 
    MPI_C_BOOL
    MPI_LOGICAL
    MPI_C_LONG_DOUBLE_COMPLEX 	 
    MPI_INT8_T 
    MPI_INT16_T
    MPI_INT32_T 
    MPI_INT64_T	 	 
    MPI_UINT8_T 
    MPI_UINT16_T 
    MPI_UINT32_T 
    MPI_UINT64_T
    MPI_BYTE
    MPI_PACKED
    
    MPI_CHARACTER
    MPI_INTEGER
    MPI_INTEGER1 
    MPI_INTEGER2
    MPI_INTEGER4
    MPI_REAL
    MPI_REAL2 
    MPI_REAL4
    MPI_REAL8
    MPI_DOUBLE_PRECISION
    MPI_COMPLEX
    MPI_DOUBLE_COMPLEX
    MPI_LOGICAL
    MPI_BYTE
    MPI_PACKED
    

     

     

  • MPI також надає можливості для визначення власних структур даних, що базуються на послідовності примітивних типів даних MPI. Такі визначені користувачем структури називаються похідними типами даних.

     

  • Примітивні типи даних є близькими. Похідні типи даних дозволяють визначати несуміжні дані у зручний спосіб і розглядати їх як суміжні.

     

  • MPI надає кілька способів для побудови похідних типів даних:
    • Суміжні дані
    • Векторні дані
    • Індексовані дані
    • Дані типу struct

 


 

Підпрограми похідних типів даних

 

MPI_Type_contiguous

 

Найпростіший конструктор. Утворює новий тип даних, роблячи число копій існуючого типу даних.

MPI_Type_contiguous (count,oldtype,&newtype) 
MPI_TYPE_CONTIGUOUS (count,oldtype,newtype,ierr)

 

MPI_Type_vector
MPI_Type_hvector

 

Similar to contiguous, but allows for regular gaps (stride) in the displacements. MPI_Type_hvector is identical to MPI_Type_vector except that stride is specified in bytes.

MPI_Type_vector (count,blocklength,stride,oldtype,&newtype)
MPI_TYPE_VECTOR (count,blocklength,stride,oldtype,newtype,ierr)

 

MPI_Type_indexed
MPI_Type_hindexed

 

Масив зміщень вхідного типу даних надається як карта для нового типу даних. MPI_Type_hindexed є ідентичним до MPI_Type_indexed за винятком того, що зміщення вказуються в байтах.

MPI_Type_indexed (count,blocklens[],offsets[],old_type,&newtype)
MPI_TYPE_INDEXED (count,blocklens(),offsets(),old_type,newtype,ierr)

 

MPI_Type_struct

 

Новий тип даних формується за повністю визначеною мапою компонентних типів даних.

MPI_Type_struct (count,blocklens[],offsets[],old_types,&newtype)
MPI_TYPE_STRUCT (count,blocklens(),offsets(),old_types,newtype,ierr)

 

MPI_Type_extent

 

Повертає розмір у байтах указаного типу даних. Корисно для підпрограм MPI, які вимагають специфікації зсувів в байтах.

MPI_Type_extent (datatype,&extent)
MPI_TYPE_EXTENT (datatype,extent,ierr)

 

MPI_Type_commit

 

Віддає новий тип даних системі. Потрібно для всіх побудованих користувачем (похідних) типів даних.

MPI_Type_commit (&datatype)
MPI_TYPE_COMMIT (datatype,ierr)

 

MPI_Type_free

 

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

MPI_Type_free (&datatype)
MPI_TYPE_FREE (datatype,ierr)

 

 


 

Приклади: суміжний похідний тип даних

Створити тип даних, який відповідає рядку масиву, і роздати різні рядки усім процесам. 

 

 Мова С - приклад суміжного похідного типу даних
#include "mpi.h"
#include <stdio.h>
#define SIZE 4

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, source=0, dest, tag=1, i;
float a[SIZE][SIZE] =
  {1.0, 2.0, 3.0, 4.0,
   5.0, 6.0, 7.0, 8.0,
   9.0, 10.0, 11.0, 12.0,
   13.0, 14.0, 15.0, 16.0};
float b[SIZE];

MPI_Status stat;
MPI_Datatype rowtype;

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

MPI_Type_contiguous(SIZE, MPI_FLOAT, &rowtype);
MPI_Type_commit(&rowtype);

if (numtasks == SIZE) {
  if (rank == 0) {
     for (i=0; i<numtasks; i++)
       MPI_Send(&a[0], 1, rowtype, i, tag, MPI_COMM_WORLD);
     }

  MPI_Recv(b, SIZE, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &stat);
  printf("rank= %d  b= %3.1f %3.1f %3.1f %3.1f\n",
         rank,b[0],b[1],b[2],b[3]);
  }
else
  printf("Must specify %d processors. Terminating.\n",SIZE);

MPI_Type_free(&rowtype);
MPI_Finalize();
}

 

 

 Fortran - приклад суміжного похідного типу даних
   program contiguous
   include 'mpif.h'

   integer SIZE
   parameter(SIZE=4)
   integer numtasks, rank, source, dest, tag, i,  ierr
   real*4 a(0:SIZE-1,0:SIZE-1), b(0:SIZE-1)
   integer stat(MPI_STATUS_SIZE), columntype

C  Fortran stores this array in column major order
   data a  /1.0, 2.0, 3.0, 4.0, 
  &         5.0, 6.0, 7.0, 8.0,
  &         9.0, 10.0, 11.0, 12.0, 
  &         13.0, 14.0, 15.0, 16.0 /

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   call MPI_TYPE_CONTIGUOUS(SIZE, MPI_REAL, columntype, ierr)
   call MPI_TYPE_COMMIT(columntype, ierr)
  
   tag = 1
   if (numtasks .eq. SIZE) then
      if (rank .eq. 0) then
         do 10 i=0, numtasks-1
         call MPI_SEND(a(0,i), 1, columntype, i, tag,
  &                    MPI_COMM_WORLD,ierr)
 10      continue
      endif

      source = 0
      call MPI_RECV(b, SIZE, MPI_REAL, source, tag, 
  &                MPI_COMM_WORLD, stat, ierr)
         print *, 'rank= ',rank,' b= ',b

   else
      print *, 'Must specify',SIZE,' processors.  Terminating.' 
   endif

   call MPI_TYPE_FREE(columntype, ierr)
   call MPI_FINALIZE(ierr)

   end



     
  • Зразок програмного виводу:

     

    rank= 0  b= 1.0 2.0 3.0 4.0
    rank= 1  b= 5.0 6.0 7.0 8.0
    rank= 2  b= 9.0 10.0 11.0 12.0
    rank= 3  b= 13.0 14.0 15.0 16.0
    

 


 

Приклади: векторний похідний тип даних

Створити тип даних, який відповідає стовпцю масиву, і роздати різні стовпці усім процесам. 

 

 Мова С - приклад векторного похідного типу даних
#include "mpi.h"
#include <stdio.h>
#define SIZE 4

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, source=0, dest, tag=1, i;
float a[SIZE][SIZE] = 
  {1.0, 2.0, 3.0, 4.0,  
   5.0, 6.0, 7.0, 8.0, 
   9.0, 10.0, 11.0, 12.0,
  13.0, 14.0, 15.0, 16.0};
float b[SIZE]; 

MPI_Status stat;
MPI_Datatype columntype;

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
   
MPI_Type_vector(SIZE, 1, SIZE, MPI_FLOAT, &columntype);
MPI_Type_commit(&columntype);

if (numtasks == SIZE) {
  if (rank == 0) {
     for (i=0; i<numtasks; i++) 
       MPI_Send(&a[0], 1, columntype, i, tag, MPI_COMM_WORLD);
        }
 
  MPI_Recv(b, SIZE, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &stat);
  printf("rank= %d  b= %3.1f %3.1f %3.1f %3.1f\n",
        rank,b[0],b[1],b[2],b[3]);
  }
else
  printf("Must specify %d processors. Terminating.\n",SIZE);
   
MPI_Type_free(&columntype);
MPI_Finalize();
}

 

 

 Fortran - приклад векторного похідного типу даних
   program vector
   include 'mpif.h'

   integer SIZE
   parameter(SIZE=4)
   integer numtasks, rank, source, dest, tag, i,  ierr
   real*4 a(0:SIZE-1,0:SIZE-1), b(0:SIZE-1)
   integer stat(MPI_STATUS_SIZE), rowtype

C  Fortran stores this array in column major order
   data a  /1.0, 2.0, 3.0, 4.0, 
  &         5.0, 6.0, 7.0, 8.0,
  &         9.0, 10.0, 11.0, 12.0, 
  &         13.0, 14.0, 15.0, 16.0 /

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   call MPI_TYPE_VECTOR(SIZE, 1, SIZE, MPI_REAL, rowtype, ierr)
   call MPI_TYPE_COMMIT(rowtype, ierr)
  
   tag = 1
   if (numtasks .eq. SIZE) then
      if (rank .eq. 0) then
         do 10 i=0, numtasks-1
         call MPI_SEND(a(i,0), 1, rowtype, i, tag,
  &                    MPI_COMM_WORLD, ierr)
 10      continue
      endif

      source = 0
      call MPI_RECV(b, SIZE, MPI_REAL, source, tag, 
  &                MPI_COMM_WORLD, stat, ierr)
      print *, 'rank= ',rank,' b= ',b

   else
      print *, 'Must specify',SIZE,' processors.  Terminating.' 
   endif

   call MPI_TYPE_FREE(rowtype, ierr)
   call MPI_FINALIZE(ierr)

   end



     
  • Зразок програмного виводу:

     

    rank= 0  b= 1.0 5.0 9.0 13.0
    rank= 1  b= 2.0 6.0 10.0 14.0
    rank= 2  b= 3.0 7.0 11.0 15.0
    rank= 3  b= 4.0 8.0 12.0 16.0
    

 


 

Приклади: індексований похідний тип даних

Створити тип даних, вибравши частину змінних масиву, і поширити в усі завдання. 

 

 Мова С - приклад індексованого похідного типу даних
#include "mpi.h"
#include <stdio.h>
#define NELEMENTS 6

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, source=0, dest, tag=1, i;
int blocklengths[2], displacements[2];
float a[16] = 
  {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 
   9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0};
float b[NELEMENTS]; 

MPI_Status stat;
MPI_Datatype indextype;

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

blocklengths[0] = 4;
blocklengths[1] = 2;
displacements[0] = 5;
displacements[1] = 12;
   
MPI_Type_indexed(2, blocklengths, displacements, MPI_FLOAT, &indextype);
MPI_Type_commit(&indextype);

if (rank == 0) {
  for (i=0; i<numtasks; i++) 
     MPI_Send(a, 1, indextype, i, tag, MPI_COMM_WORLD);
  }
 
MPI_Recv(b, NELEMENTS, MPI_FLOAT, source, tag, MPI_COMM_WORLD, &stat);
printf("rank= %d  b= %3.1f %3.1f %3.1f %3.1f %3.1f %3.1f\n",
     rank,b[0],b[1],b[2],b[3],b[4],b[5]);
   
MPI_Type_free(&indextype);
MPI_Finalize();
}

 

 

 Fortran - приклад індексованого похідного типу даних
   program indexed
   include 'mpif.h'

   integer NELEMENTS
   parameter(NELEMENTS=6)
   integer numtasks, rank, source, dest, tag, i,  ierr
   integer blocklengths(0:1), displacements(0:1)
   real*4 a(0:15), b(0:NELEMENTS-1)
   integer stat(MPI_STATUS_SIZE), indextype

   data a  /1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0,
  &         9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0 /

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   blocklengths(0) = 4
   blocklengths(1) = 2
   displacements(0) = 5
   displacements(1) = 12

   call MPI_TYPE_INDEXED(2, blocklengths, displacements, MPI_REAL, 
  &                      indextype, ierr)
   call MPI_TYPE_COMMIT(indextype, ierr)
  
   tag = 1
   if (rank .eq. 0) then
      do 10 i=0, numtasks-1
      call MPI_SEND(a, 1, indextype, i, tag, MPI_COMM_WORLD, ierr)
 10   continue
   endif

   source = 0
   call MPI_RECV(b, NELEMENTS, MPI_REAL, source, tag, MPI_COMM_WORLD, 
  &              stat, ierr)
   print *, 'rank= ',rank,' b= ',b

   call MPI_TYPE_FREE(indextype, ierr)
   call MPI_FINALIZE(ierr)

   end



     
  • Зразок програмного виводу:

     

    rank= 0  b= 6.0 7.0 8.0 9.0 13.0 14.0
    rank= 1  b= 6.0 7.0 8.0 9.0 13.0 14.0
    rank= 2  b= 6.0 7.0 8.0 9.0 13.0 14.0
    rank= 3  b= 6.0 7.0 8.0 9.0 13.0 14.0
    

 


 

Приклади: похідний тип даних struct

Створити тип даних, який відображає частини, і поширити масив таких частини усім процесам. 

 

 Мова С - приклад похідного типу даних struct
#include "mpi.h"
#include <stdio.h>
#define NELEM 25

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, source=0, dest, tag=1, i;

typedef struct {
  float x, y, z;
  float velocity;
  int  n, type;
  }          Particle;
Particle     p[NELEM], particles[NELEM];
MPI_Datatype particletype, oldtypes[2]; 
int          blockcounts[2];

/* MPI_Aint type used to be consistent with syntax of */
/* MPI_Type_extent routine */
MPI_Aint    offsets[2], extent;

MPI_Status stat;

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
 
/* Setup description of the 4 MPI_FLOAT fields x, y, z, velocity */
offsets[0] = 0;
oldtypes[0] = MPI_FLOAT;
blockcounts[0] = 4;

/* Setup description of the 2 MPI_INT fields n, type */
/* Need to first figure offset by getting size of MPI_FLOAT */
MPI_Type_extent(MPI_FLOAT, &extent);
offsets[1] = 4 * extent;
oldtypes[1] = MPI_INT;
blockcounts[1] = 2;

/* Now define structured type and commit it */
MPI_Type_struct(2, blockcounts, offsets, oldtypes, &particletype);
MPI_Type_commit(&particletype);

/* Initialize the particle array and then send it to each task */
if (rank == 0) {
  for (i=0; i<NELEM; i++) {
     particles.x = i * 1.0;
     particles.y = i * -1.0;
     particles.z = i * 1.0; 
     particles.velocity = 0.25;
     particles.n = i;
     particles.type = i % 2; 
     }
  for (i=0; i<numtasks; i++) 
     MPI_Send(particles, NELEM, particletype, i, tag, MPI_COMM_WORLD);
  }
 
MPI_Recv(p, NELEM, particletype, source, tag, MPI_COMM_WORLD, &stat);

/* Print a sample of what was received */
printf("rank= %d   %3.2f %3.2f %3.2f %3.2f %d %d\n", rank,p[3].x,
     p[3].y,p[3].z,p[3].velocity,p[3].n,p[3].type);
   
MPI_Type_free(&particletype);
MPI_Finalize();
}

 

 

 Fortran - приклад похідного типу даних struct
   program struct
   include 'mpif.h'

   integer NELEM
   parameter(NELEM=25)
   integer numtasks, rank, source, dest, tag, i,  ierr
   integer stat(MPI_STATUS_SIZE)

   type Particle
   sequence
   real*4 x, y, z, velocity
   integer n, type
   end type Particle

   type (Particle) p(NELEM), particles(NELEM)
   integer particletype, oldtypes(0:1), blockcounts(0:1), 
  &        offsets(0:1), extent

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

C  Setup description of the 4 MPI_REAL fields x, y, z, velocity 
   offsets(0) = 0
   oldtypes(0) = MPI_REAL
   blockcounts(0) = 4

C  Setup description of the 2 MPI_INTEGER fields n, type 
C  Need to first figure offset by getting size of MPI_REAL
   call MPI_TYPE_EXTENT(MPI_REAL, extent, ierr)
   offsets(1) = 4 * extent
   oldtypes(1) = MPI_INTEGER
   blockcounts(1) = 2

C  Now define structured type and commit it 
   call MPI_TYPE_STRUCT(2, blockcounts, offsets, oldtypes, 
  &                     particletype, ierr)
   call MPI_TYPE_COMMIT(particletype, ierr)
  
C  Initialize the particle array and then send it to each task
   tag = 1
   if (rank .eq. 0) then
      do 10 i=0, NELEM-1
      particles(i) = Particle ( 1.0*i, -1.0*i, 1.0*i, 
  &                  0.25, i, mod(i,2) )
 10   continue

      do 20 i=0, numtasks-1
      call MPI_SEND(particles, NELEM, particletype, i, tag, 
  &                 MPI_COMM_WORLD, ierr)
 20   continue
   endif

   source = 0
   call MPI_RECV(p, NELEM, particletype, source, tag, 
  &              MPI_COMM_WORLD, stat, ierr)

   print *, 'rank= ',rank,' p(3)= ',p(3)
   call MPI_TYPE_FREE(particletype, ierr)
   call MPI_FINALIZE(ierr)
   end



     
  • Зразок програмного виводу:

     

    rank= 0   3.00 -3.00 3.00 0.25 3 1
    rank= 2   3.00 -3.00 3.00 0.25 3 1
    rank= 1   3.00 -3.00 3.00 0.25 3 1
    rank= 3   3.00 -3.00 3.00 0.25 3 1
    

  Підпрограми управління групами та комунікаторами


 Групи проти комунікаторів:

 

  • Група є впорядкованою множиною процесів. Кожен процес в групі пов'язаний з унікальним цілочисельним рангом. Значення рангів відраховуються від нуля і до N-1, де N — кількість процесів в групі. У MPI група представлена в межах системної пам'яті як об'єкт. Вона доступна програмісту тільки "вручну". Група є завжди пов'язаною з об'єктом комунікатора.

     

  • Комунікатор включає в себе групу процесів, які можуть спілкуватися один з одним. Усі повідомлення MPI повинні вказувати комунікатор. В найпростішому випадку, комунікатор є додатковим "тегом", який повинен бути включений у виклик MPI. Як і групи, комунікатори позначаються всередині системної пам'яті як об'єкти і є доступними програмісту тільки "вручну". Наприклад, "тегом" комунікатора, який включає в себе всі завдання, є MPI_COMM_WORLD.

     

  • З точки зору програміста, група і комунікатор є одним цілим. Підпрограми груп в першу чергу використовуються для визначення, які процеси слід використовувати для створення комунікатора.

 Основне призначення об'єктів груп та комунікаторів:

 

  1. Дозволяють організовувати завдання, які виконують одну функцію, в групи завдань.

     

  2. Увімкнути колективну комунікацію операцій між підмножиною пов'язаних завдань.

     

  3. Забезпечити основу для реалізації визначених користувачем віртуальних топологій

     

  4. Надання безпечного зв'язку

 Programming Considerations and Restrictions:

 

  • Групи/комунікатори є динамічними - вони можуть бути створені і знищені під час виконання програми.

     

  • Процеси можуть бути в більше, ніж одній групі/комунікаторі. Вони мають унікальний ранг в межах кожної групи/комунікатора.

     

  • MPI надає понад 40 процедур, пов'язаних з групами, комунікаторами та віртуальними топологіями.

     

  • Типове використання:
    1. Витягнути керування глобальною групою з MPI_COMM_WORLD за допомогою MPI_Comm_group
    2. Сформувати нову групу як підмножину глобальної групи за допомогою MPI_Group_incl
    3. Створити новий комунікатор для нової групи за допомогою MPI_Comm_create
    4. Визначити новий ранг в новому комунікаторі, використовуючи MPI_Comm_rank
    5. Провести комунікації за допомогою підпрограм передачі повідомлень MPI
    6. Коли все завершено, звільнити новий комунікатор і групу (за бажанням) за допомогою MPI_Comm_free і MPI_Group_free

 


 

Підпрограми управління групами та комунікаторами

Створити дві різні групи процесів для окремого колективного обміну повідомленнями. Також вимагає створення нових комунікаторів.

 

 Мова С - приклад підпрограм груп та комунікаторів
#include "mpi.h"
#include <stdio.h>
#define NPROCS 8

int main(argc,argv)
int argc;
char *argv[];  {
int        rank, new_rank, sendbuf, recvbuf, numtasks,
           ranks1[4]={0,1,2,3}, ranks2[4]={4,5,6,7};
MPI_Group  orig_group, new_group;
MPI_Comm   new_comm;

MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

if (numtasks != NPROCS) {
  printf("Must specify MP_PROCS= %d. Terminating.\n",NPROCS);
  MPI_Finalize();
  exit(0);
  }

sendbuf = rank;

/* Extract the original group handle */
MPI_Comm_group(MPI_COMM_WORLD, &orig_group);

/* Divide tasks into two distinct groups based upon rank */
if (rank < NPROCS/2) {
  MPI_Group_incl(orig_group, NPROCS/2, ranks1, &new_group);
  }
else {
  MPI_Group_incl(orig_group, NPROCS/2, ranks2, &new_group);
  }

/* Create new new communicator and then perform collective communications */
MPI_Comm_create(MPI_COMM_WORLD, new_group, &new_comm);
MPI_Allreduce(&sendbuf, &recvbuf, 1, MPI_INT, MPI_SUM, new_comm);

MPI_Group_rank (new_group, &new_rank);
printf("rank= %d newrank= %d recvbuf= %d\n",rank,new_rank,recvbuf);

MPI_Finalize();
}

 

 

 Fortran - приклад підпрограм груп та комунікаторів
   program group
   include 'mpif.h'

   integer NPROCS
   parameter(NPROCS=8)
   integer rank, new_rank, sendbuf, recvbuf, numtasks
   integer ranks1(4), ranks2(4), ierr
   integer orig_group, new_group, new_comm
   data ranks1 /0, 1, 2, 3/, ranks2 /4, 5, 6, 7/

   call MPI_INIT(ierr)
   call MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)

   if (numtasks .ne. NPROCS) then
     print *, 'Must specify MPROCS= ',NPROCS,' Terminating.'
     call MPI_FINALIZE(ierr)
     stop
   endif

   sendbuf = rank

C  Extract the original group handle
   call MPI_COMM_GROUP(MPI_COMM_WORLD, orig_group, ierr)

C  Divide tasks into two distinct groups based upon rank
   if (rank .lt. NPROCS/2) then
      call MPI_GROUP_INCL(orig_group, NPROCS/2, ranks1, 
 &                  new_group, ierr)
   else 
      call MPI_GROUP_INCL(orig_group, NPROCS/2, ranks2, 
 &                  new_group, ierr)
   endif

   call MPI_COMM_CREATE(MPI_COMM_WORLD, new_group, 
 &                  new_comm, ierr)
   call MPI_ALLREDUCE(sendbuf, recvbuf, 1, MPI_INTEGER,
 &                  MPI_SUM, new_comm, ierr)

   call MPI_GROUP_RANK(new_group, new_rank, ierr)
   print *, 'rank= ',rank,' newrank= ',new_rank,' recvbuf= ',
 &     recvbuf

   call MPI_FINALIZE(ierr)
   end



     
  • Зразок програмного виводу:

     

    rank= 7 newrank= 3 recvbuf= 22
    rank= 0 newrank= 0 recvbuf= 6
    rank= 1 newrank= 1 recvbuf= 6
    rank= 2 newrank= 2 recvbuf= 6
    rank= 6 newrank= 2 recvbuf= 22
    rank= 3 newrank= 3 recvbuf= 6
    rank= 4 newrank= 0 recvbuf= 22
    rank= 5 newrank= 1 recvbuf= 22
    

  Віртуальні топології


 Що це таке?

 

  • З точки зору MPI віртуальна топологія описує зіставлення/впорядкування MPI процесів в геометричну "форму".

     

  • Двома основними видами топологій, які підтримуються MPI, є декартова топологія (сітка) і топологія графа.

     

  • Топології MPI віртуальні - не може бути ніякого відношення між фізичною структурою паралельної машини і топологією процесів.

     

  • Віртуальні топології збудовані на комунікаторах і групах MPI.

     

  • Повинні бути "запрограмовані" розробником застосунку.

 Чому їх використовують?

 

  • Зручність
    • Віртуальні топології можуть бути корисними для застосунків з особливими шаблонами зв'язку - шаблони, які відповідають структурі топології MPI.
    • Наприклад, декартова топологія може виявитися зручною для застосунку, який потребує 4-стороннього зв'язку між найближчими сусідами для даних, що базуються на ?(сітці).

     

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

 Приклад:

Спрощене зіставлення процесів в декартовій віртуальній топології показано нижче:

 


 

Підпрограми віртуальної топології

Створити декартову топологію 4х4 з 16 процесорів і надати ранг кожного процесу чотирьом сусідам.

 

 Мова С - приклад декартової віртуальної топології
#include "mpi.h"
#include <stdio.h>
#define SIZE 16
#define UP    0
#define DOWN  1
#define LEFT  2
#define RIGHT 3

int main(argc,argv)
int argc;
char *argv[];  {
int numtasks, rank, source, dest, outbuf, i, tag=1, 
   inbuf[4]={MPI_PROC_NULL,MPI_PROC_NULL,MPI_PROC_NULL,MPI_PROC_NULL,}, 
   nbrs[4], dims[2]={4,4}, 
   periods[2]={0,0}, reorder=0, coords[2];

MPI_Request reqs[8];
MPI_Status stats[8];
MPI_Comm cartcomm;

MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

if (numtasks == SIZE) {
  MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &cartcomm);
  MPI_Comm_rank(cartcomm, &rank);
  MPI_Cart_coords(cartcomm, rank, 2, coords);
  MPI_Cart_shift(cartcomm, 0, 1, &nbrs[UP], &nbrs[DOWN]);
  MPI_Cart_shift(cartcomm, 1, 1, &nbrs[LEFT], &nbrs[RIGHT]);

  printf("rank= %d coords= %d %d  neighbors(u,d,l,r)= %d %d %d %d\n",
         rank,coords[0],coords[1],nbrs[UP],nbrs[DOWN],nbrs[LEFT],
         nbrs[RIGHT]);

  outbuf = rank;

  for (i=0; i<4; i++) {
     dest = nbrs;
     source = nbrs;
     MPI_Isend(&outbuf, 1, MPI_INT, dest, tag, 
               MPI_COMM_WORLD, &reqs);
     MPI_Irecv(&inbuf, 1, MPI_INT, source, tag, 
               MPI_COMM_WORLD, &reqs[i+4]);
     }

  MPI_Waitall(8, reqs, stats);
   
  printf("rank= %d                  inbuf(u,d,l,r)= %d %d %d %d\n",
         rank,inbuf[UP],inbuf[DOWN],inbuf[LEFT],inbuf[RIGHT]);  }
else
  printf("Must specify %d processors. Terminating.\n",SIZE);
   
MPI_Finalize();
}

 

 

 Fortran - приклад декартової віртуальної топології
   program cartesian
   include 'mpif.h'

   integer SIZE, UP, DOWN, LEFT, RIGHT
   parameter(SIZE=16)
   parameter(UP=1)
   parameter(DOWN=2)
   parameter(LEFT=3)
   parameter(RIGHT=4)
   integer numtasks, rank, source, dest, outbuf, i, tag, ierr,
  &        inbuf(4), nbrs(4), dims(2), coords(2),
  &        stats(MPI_STATUS_SIZE, 8), reqs(8), cartcomm,
  &        periods(2), reorder
   data inbuf /MPI_PROC_NULL,MPI_PROC_NULL,MPI_PROC_NULL,
  &     MPI_PROC_NULL/,  dims /4,4/, tag /1/, 
  &     periods /0,0/, reorder /0/ 

   call MPI_INIT(ierr)
   call MPI_COMM_SIZE(MPI_COMM_WORLD, numtasks, ierr)
  
   if (numtasks .eq. SIZE) then
      call MPI_CART_CREATE(MPI_COMM_WORLD, 2, dims, periods, reorder,
  &                        cartcomm, ierr)
      call MPI_COMM_RANK(cartcomm, rank, ierr)
      call MPI_CART_COORDS(cartcomm, rank, 2, coords, ierr)
      call MPI_CART_SHIFT(cartcomm, 0, 1, nbrs(UP), nbrs(DOWN), ierr)
      call MPI_CART_SHIFT(cartcomm, 1, 1, nbrs(LEFT), nbrs(RIGHT), 
  &                       ierr)

      write(*,20) rank,coords(1),coords(2),nbrs(UP),nbrs(DOWN),
  &               nbrs(LEFT),nbrs(RIGHT)

      outbuf = rank
      do i=1,4
         dest = nbrs(i)
         source = nbrs(i)
         call MPI_ISEND(outbuf, 1, MPI_INTEGER, dest, tag,
  &                    MPI_COMM_WORLD, reqs(i), ierr)
         call MPI_IRECV(inbuf(i), 1, MPI_INTEGER, source, tag,
  &                    MPI_COMM_WORLD, reqs(i+4), ierr)
      enddo

      call MPI_WAITALL(8, reqs, stats, ierr)

      write(*,30) rank,inbuf

   else
     print *, 'Must specify',SIZE,' processors.  Terminating.' 
   endif
   call MPI_FINALIZE(ierr)

20 format('rank= ',I3,' coords= ',I2,I2,
  &       ' neighbors(u,d,l,r)= ',I3,I3,I3,I3 )
30 format('rank= ',I3,'                 ',
  &       ' inbuf(u,d,l,r)= ',I3,I3,I3,I3 )

   end



     
  • Зразок програмного виводу: (частково)

     

    rank=   0 coords=  0 0 neighbors(u,d,l,r)=  -1  4 -1  1
    rank=   0                  inbuf(u,d,l,r)=  -1  4 -1  1
    rank=   8 coords=  2 0 neighbors(u,d,l,r)=   4 12 -1  9
    rank=   8                  inbuf(u,d,l,r)=   4 12 -1  9
    rank=   1 coords=  0 1 neighbors(u,d,l,r)=  -1  5  0  2
    rank=   1                  inbuf(u,d,l,r)=  -1  5  0  2
    rank=  13 coords=  3 1 neighbors(u,d,l,r)=   9 -1 12 14
    rank=  13                  inbuf(u,d,l,r)=   9 -1 12 14
    ...
    ...
    rank=   3 coords=  0 3 neighbors(u,d,l,r)=  -1  7  2 -1
    rank=   3                  inbuf(u,d,l,r)=  -1  7  2 -1
    rank=  11 coords=  2 3 neighbors(u,d,l,r)=   7 15 10 -1
    rank=  11                  inbuf(u,d,l,r)=   7 15 10 -1
    rank=  10 coords=  2 2 neighbors(u,d,l,r)=   6 14  9 11
    rank=  10                  inbuf(u,d,l,r)=   6 14  9 11
    rank=   9 coords=  2 1 neighbors(u,d,l,r)=   5 13  8 10
    rank=   9                  inbuf(u,d,l,r)=   5 13  8 10
    

  Коротко про MPI-2 і MPI-3


 MPI-2:

 

  • Специфікація MPI-1 навмисне не адресується кільком "важким" питанням. З міркувань доцільності ці питання були відкладені до другої специфікації, яка називається MPI-2 і вийшла в 1997 році.

     

  • MPI-2 була значною переробкою MPI-1 з додаванням нової функціональності та виправлень.

     

  • Основні сфери нової функціональності в MPI-2:

     

    • Динамічні процеси - розширення, що видаляє статичну модель процесів MPI. Забезпечує процедури для створення нових процесів після запуску завдання.

       

    • Односторонні комунікації - забезпечує процедури для односпрямованих комунікацій. Включає спільну пам'ять операцій (покласти/отримати) та дистанційне накопичення операцій.

       

    • Extended Collective Operations - allows for the application of collective operations to inter-communicators

       

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

       

    • Додаткові мовні прив'язки - описує прив'язки C++ і розповідає про Fortran 90.

       

    • Паралельний ввід/вивід - описує MPI-підтримку паралельного вводу-виводу.

 MPI-3:

 

  • Стандарт MPI-3 був прийнятий в 2012 році і містить значні розширення функціональності MPI-1 і MPI 2, включаючи:

     

    • Неблокуючі колективні операції - дозволяє завданням, що працюють колективно, виконувати операції без блокування, тим самим, можливо, поліпшуючи продуктивність.

       

    • Нові односторонні операції зв'язку - краще керування різними моделями пам'яті.

       

    • Neighborhood Collectives - Extends the distributed graph and Cartesian process topologies with additional communication power.

       

    • Зв'язування в Fortran 2008 - розширено зв'язування в Fortran90

       

    • MPIT інструмент інтерфейсу - цей новий інструмент інтерфейсу дозволяє реалізації MPI відкривати певні внутрішні змінні, лічильники та інше користувачу (найбільш ймовірно, інструмент продуктивності).

       

    • Matched Probe - Fixes an old bug in MPI-2 where one could not probe for messages in a multi-threaded environment.

 Більше інформації про MPI-2 і MPI-3:


Политология. Универсальная шпаргалка

перейти к оглавлению

1. Место политологии среди гуманитарных наук

Политология развивается в тесном взаимодействии с другими гуманитарными науками. Их всех объединяет общий объект исследования — жизнь общества во всем многообразии ее конкретных проявлений.

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

1) Политология тесно связана с экономикой. Экономика дает соответствующее обоснование реализации экономических...

законы диалектики

Основные законы диалектики.

1)Закон единства и борьбы противоположностей.

Этот закон является «ядром» диалектики, т.к. определяет источник развития, отвечает на вопрос, почему оно происходит.

Содержание закона: источник движения и развития мира находится в нем самом, в порождаемых им противоречиях.

Противоречие – это взаимодействие противоположных сторон, свойств и тенденций в составе той или иной системы или между системами. Диалектическое противоречие есть только там, где...

Русский язык и культура речи

перейти к оглавлению

1. ЭЛЕМЕНТЫ И УРОВНИ ЯЗЫКА

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

Самая простая единица языка – это фонема, неделимая и сама по себе...

Идеология

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