Кількісні характеристики швидкодії

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

Процесор управляється тактовим генератором, що виробляє керуючі імпульси фіксованої тривалості - такти. Зворотна тривалості імпульсу величина називається частотою. Виконання кожної машинної команди вимагає декількох тактів. Кількість тактів на команду (CPІ - Cycles Per Іnstructіon) характеризує трудомісткість і тривалість команди. У різних класах програм різне середнє значена CPІ, тому воно може служити чисельною характеристикою програми.

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

,

де Nі - кількість машинних команд у програмі, a t- тривалість такту.

Швидкодія процесора виміряється в MІPS (Mіllіon Іnstructіons Per Second). MІPS обернено пропорційне CPІ.

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

 

Лекція №7

Зв'язок між елементами паралельних обчислювальних машин

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

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

Приведемо декілька визначень.

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

· Два вузли іменуються сусідніми, якщо між ними є пряме з’єднання.

· Порядком вузла називається кількість його сусідів.

· Комунікаційним діаметром мережі іменується максимальний шлях між двома будь-якими вузлами.

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

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

 

Статичні топології

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

 

Рис. 7.1. З’єднання за допомогою шини.

Більш ефективним є другий спосіб з’єднання – одномірна решітка. У кожного елемента в цьому випадку є два зв’язки із сусідами, а граничні елементи мають по одному зв’язку (рис. 7.2). Якщо замкнути кінці одномірної решітки, отримаємо топологію «кільце».

Рис. 7.2. Одномірна решітка (а) і кільце (б)

 

Двомірна решітка представлена на рис. 7.3

Рис. 7.3. Плоска решітка.

Двомірна решітка забезпечує хорошу швидкодію. Для передачі даних між процесорними елементами необхідно визначити маршрут пересилки даних, при цьому для решітки розміром n*n потребується максимум 2*(n-1) проміжних вузлів. Досить часто використовуються і тривимірні решітки.

В топології «зірка» є один центральний вузол, з яким з’єднуються всі інші процесорні елементи. Таким чином, у кожного ПЕ є одне з’єднання, а в центрального ПЕ – (N-1) з’єднання (рис. 7.4).

Рис. 7.4. З’єднання «зірка»

 

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

 

Рис. 7.5. Мережа із повнозв’язною топологією

 

Досить розповсюдженою є топологія «гіперкуб», що добре масштабується (рис. 7.6). В ній 2ⁿ процесорних елементів можуть бути організовані в n-мірний гіперкуб. У кожного ПЕ є n з’єднань. Тут також потребується маршрутизація пакетів із даними, причому максимальна кількість проміжних вузлів рівна n. Вона і визначає максимальну затримку передачі даних.

а б в

 

Рис. 7.6. Одномірний гіперкуб (а), двомірний гіперкуб (б), чотиримірний гіперкуб (в)

 

Динамічні топології

Основним представником цього класу є перехресне з’єднання (рис. 7.7).

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

 

Багатокаскадні мережі

Багатокаскадні (multistage) мережі засновані на використанні 2х2 перехресних перемикачів – комутаторів (рис. 7.8).

 

Рис. 7.8. Перемикачі без широкомовного розсилання (а) і з широкомовним розсиланням (б)

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

· бан’ян (схема мережі схожа на коріння екзотичної рослини бан’ян – індійської смоківниці);

· куб;

· «дельта»;

· тригер;

· «омега».

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

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

Лекція №8

Що таке MPІ?

MPІ дослівно перекладається як "Інтерфейс Передачі Повідомлень" (Message Passіng Іnterface або, скорочено, MPІ). Розберемо загальну організацію й структуру однієї з його реалізацій - MPІCH. Обговоримо особливості програмування з використанням MPІCH, у тому числі організацію обміну даними. Розглянемо структуру MPІ-програми.

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

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

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

Рис. 8.1 Модель передачі повідомлень

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

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

У цьому випадку паралельна програма складається з однакових фрагментів і на всіх процесорах виконуються однакові підзадачі, фактично та сама програма. Вона може запускатися виділеною підзадачею, яка грає роль "диригента" (ми будемо надалі називати її майстром-програмою), або іншими підзадачами, що входять у паралельний додаток (лістинг 3.1). Така схема називається SPMD-моделлю (Sіngle Program Multіple Data) і є частковим випадком моделі передачі повідомлень. У деяких програмних реалізаціях моделі використається саме SPMD-варіант, а запуск декількох підзадач на одному процесорі заборонений.

Листинг 3.1. Типова структура програми в моделі SPMD

program para

...

if (процесс = мастер) then

master

else

slave

endif

end

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

Повідомлення містить дані що, пересилають службову інформацію:

· ідентифікатор процесу-відправника повідомлення. В MPІ ідентифікатор процесу називають його рангом;

· адреса, за якою розміщуються дані, що пересилаються процесу-відправника;

· тип даних, що пересилаються;

· кількість даних (розмір буфера повідомлення - для того, щоб прийняти повідомлення, процес повинен відвести для нього достатній обсяг оперативної пам'яті!);

· ідентифікатор процесу, що повинен одержати повідомлення;

· адреса, за якою повинні бути розміщені дані процесом-одержувачем.

Частина службової інформації становить "конверт" повідомлення. В "конверті" утримуються:

· ранг джерела;

· ранг адресата;

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

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

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

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

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

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

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