Відмінності між версіями «Паралельні обчислювальні системи»

Версія за 22:25, 11 січня 2013

1. Паралельні обчислювальні системи.

Визначень суперкомп’ютерам намагалися давати багато, іноді серйозних, іноді іронічних. Паралельний комп’ютер - це набір процесорів, здатних спільно працювати при вирішенні обчислювальних задач. Таке визначення достатньо широке, що включає як паралельні суперкомп’ютери, що мають сотні чи тисячі процесорів, так і мережі робочих станцій. Коли ця тема піднімалася в конференції comp.parallel, Кен Батчер (Ken Batcher) запропонував такий варіант: суперкомп’ютер – це пристрій, що зводить проблему обчислень до проблеми введення/виведення. Тобто те, що раніше довго обчислювалося, іноді скидаючи щось на диск, на суперкомп’ютері може виконатися миттєво, переводячи вказівники неефективності на відносно повільні пристрої введення/виведення. Ефективність найшвидших комп’ютерів зросла майже по експоненті. Перші комп’ютери виконували кілька десятків операцій з плаваючою комою за секунду, а продуктивність паралельних комп’ютерів середини дев’яностих досягає десятків і навіть сотень мільярдів операцій у секунду, і, швидше за все цей ріст буде продовжуватися. Однак архітектура обчислювальних систем, що визначають цей ріст, змінилася радикально - від послідовної до паралельної. Ера однопроцесорних комп’ютерів продовжувалася до появи сімейства CRAY X-MP / Y-MP - слабко паралельних векторних комп’ютерів з 4 - 16 процесорами, яких у свою чергу перемінили комп’ютери з масовим паралелізмом, тобто комп’ютери з чи сотнями тисячами процесорів. Ефективність комп’ютера залежить безпосередньо від часу, необхідного для виконання базової операції і кількості базових операцій, що можуть бути виконані одночасно. Час виконання базової операції обмежений часом виконання внутрішньої елементарної операції процесора (тактом процесора). Зменшення такту обмежене фізичними межами, такими як швидкість світла. Щоб обійти ці обмеження, виробники процесорів намагаються реалізувати паралельну роботу всередині чіпа - при виконанні елементарних і базових операцій. Однак теоретично було показано, що стратегія Надвисокого Рівня Інтеграції (Very Large Scale Integration - VLSI) є дорогою, що час виконання обчислень сильно залежить від розміру мікросхеми. Поряд з VLSI для підвищення продуктивності комп’ютера використовуються й інші способи: конвеєрна обробка (різні стадії окремих команд виконується одночасно), багатофункціональні модулі (окремі множники, суматори, і т.д., управляються одним потоком команд). Все більше і більше в ЕОМ включається більше “обчислювальних блоків” і відповідна логіка їхнього з’єднання. Кожен такий "обчислювальний блок" має свої власні процесор, пам’ять. Успіхи VLSI технології в зменшенні числа компонент комп’ютера, полегшують створення таких ЕОМ. Крім того, оскільки, хоча і дуже приблизно, вартість ЕОМ пропорційна числу наявних у ній компонент, то збільшення інтеграції компонент дозволяє збільшити число процесорів в ЕОМ при не дуже значному підвищенні вартості.

Інша важлива тенденція розвитку обчислень – це величезне збільшення продуктивності мереж ЕОМ. Ще недавно мережі мали швидкодію в 1.5 Mбіт/с, сьогодні вже існують мережі зі швидкодією в декілька гігабіт за секунду. Поряд із збільшенням швидкодії мереж збільшується надійність передачі даних. Це дозволяє розробляти додатки, що використовують фізично розподілені ресурси, начебто вони є частинами одного багатопроцесорного комп’ютера. Наприклад, колективне використання вилучених баз даних, обробка графічних даних на одному чи декількох графічних комп’ютерах, а вивід і управління в реальному масштабі часу на робочих станціях. Розглянуті тенденції розвитку архітектури і використання комп’ютерів, мереж дозволяють припустити, що у майбутньому паралельність не буде участю лише суперкомп’ютерів, вона проникне і на ринок робочих станцій, персональних комп’ютерів і мереж ЕОМ. Програми будуть використовувати не тільки безліч процесорів комп’ютера, але і процесори, доступні по мережі. Оскільки більшість існуючих алгоритмів припускають використання одного процесора, то будуть потрібні нові алгоритми і програми здатні виконувати багато операцій одночасно. Наявність і використання паралелізму буде ставати основною вимогою при розробці алгоритмів і програм. Число процесорів у комп’ютерах буде збільшуватися, отже, можна припустити, що протягом терміну служби програмного забезпечення воно буде експлуатуватися на кількості процесорів, яка постійно збільшується чи зменшується, залежно від потреб задачі. У цьому випадку можна припустити, що для захисту капіталовкладень у програмне забезпечення, маштабованість (scalability) програмного забезпечення (гнучкість стосовно зміни кількості використовуваних процесорів) буде настільки ж важлива як переносимість. Програма, здатна використовувати тільки фіксоване число процесорів, буде така ж недосконала, як і програма, здатна працювати тільки на одному типі комп’ютерів. Помітною ознакою багатьох паралельних архітектур є те, що доступ до локальної пам’яті процесора дешевший, ніж доступ до віддаленої пам’яті (пам’яті інших процесорів мережі). Отже, бажано, щоб доступ до локальних даних був більш частим, ніж доступ до віддалених даних. Така властивість програмного забезпечення називають локальністю (locality). Поряд з паралелізмом і маштабованістю, він є основною вимогою до паралельного програмного забезпечення. Важливість цієї властивості визначається відношенням вартості віддаленого і локального звертань до пам’яті. Це відношення може варіюватися від 10:1 до 1000:1 чи більше, що залежить від відносної ефективності процесора, пам’яті, мережі і механізмів, використовуваних для розміщення даних у мережі і їх добування.

2. Моделі паралельних комп’ютерів. Із самого початку комп’ютерної ери існувала необхідність у все більш і більш продуктивних системах. В основному це досягалося в результаті еволюції технологій виробництва комп’ютерів. Поряд з цим мали місце спроби використовувати кілька процесорів в одній обчислювальній системі з розрахунку на те, що буде досягнуте відповідне збільшення продуктивності. Першою такою спробою, здійсненою на початку 70-х років, є ILLIAC IV. Зараз є маса паралельних комп’ютерів і проектів їх реалізації. Архітектури паралельних комп’ютерів можуть значно відрізнятися один від одного. Розглянемо деякі істотні поняття і компоненти паралельних комп’ютерів.

Паралельні комп’ютери складаються з трьох основних компонентів: 1. процесори; 2. модулі пам’яті; 3. комутаційна мережа.

Можна розглядати і більш детальнішу розбиття паралельних комп’ютерів на компоненти, однак, дані три компоненти найкраще відрізняють один паралельний комп’ютер від іншого. Комутаційна мережа з’єднує процесори один з одним і іноді також з модулями пам’яті. Процесори, що використовуються в паралельних комп’ютерах, звичайно такі ж, як і процесори однопроцесорних систем, хоча сучасна технологія дозволяє розмістити на мікросхемі не тільки один процесор. На мікросхемі разом із процесором можуть бути розташовані ті їх складові, які дають найбільший ефект при паралельних обчисленнях. Наприклад, мікросхема трансп'ютера поряд з 32-розрядним мікропроцесором і 64-розрядним співпроцесором арифметики з плаваючою комою, містить всередині кристальний ОЗП ємністю 4 Кбайт, 32-розрядну шину пам’яті, що дозволяє адресувати до 4 Гбайт зовнішньої, стосовно кристала пам’яті, чотири послідовних двонаправлених ліній зв’язку, що забезпечують взаємодію трансп'ютера з зовнішнім світом і працюючих паралельно з ЦПП, інтерфейс зовнішніх подій. Однією із властивостей, що розрізняють паралельні комп’ютери, є кількість можливих потоків команд. Розрізняють наступні архітектури: 1. SIMD (Single Instruction Multiple); 2. MIMD (Multiple Instruction Multiple);

2.1. SIMD. SIMD (Single Instruction Multiple). SIMD комп’ютер має N ідентичних синхронно працюючих процесорів, N потоків даних і один потік команд. Кожен процесор володіє власною локальною пам’яттю. Мережа, що з’єднує процесори, звичайно має регулярну топологію.

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

2.2. MIMD. • MIMD (Multiple Instruction Multiple). MIMD комп'ютер має N процесорів, N потоків команд і N потоків даних. Кожен процесор функціонує під управлінням власного потоку команд, тобто MIMD комп'ютер може паралельно виконувати зовсім різні програми.

MIMD архітектури далі класифікуються в залежності від фізичної організації пам'яті, способу доступу до модулів пам’яті, тобто чи має процесор свою власну локальну пам'ять і звертається до інших блоків пам'яті, використовуючи комутаційну мережа, чи комутаційна мережа об’єднує всі процесори з загальнодоступною пам'яттю. Виходячи з доступу до пам’яті, її організації, розрізняють наступні типи паралельних (MIMD) архітектур: 1. Комп'ютери з розподіленою пам'яттю (distributed memory) – Кожен процесор має доступ лише до локальної, власної пам’яті. Процесори об’єднані в мережу. Доступ до віддаленої пам’яті можливий тільки за допомогою системи обміну повідомленнями. Процесор може звертатися до локальної пам'яті, може посилати й одержувати повідомлення, передані через мережу, що з'єднує процесори. Повідомлення використовуються для здійснення зв'язку між процесорами або, що є еквівалентним, для читання і запису віддалених блоків пам'яті. В ідеалізованій мережі вартість посилки повідомлення між двома вузлами мережі не залежить як від розташування обох вузлів, так і від трафіку мережі, але залежить від довжини повідомлення. Сюди належать так звані масово-паралельні обчислювальні (massively parallel processing – MPP) системи. Особливості даної архітектури наступні; Архітектура. Система складається з однорідних обчислювальних вузлів, що включають: • один чи декілька центральних процесорів (звичайно RISC); • локальну пам'ять (прямий доступ до пам'яті інших вузлів неможливий); • комунікаційний процесор чи мережевий адаптер; • іноді - жорсткі диски чи інші пристрої введення/виведення. До системи можуть бути додані спеціальні вузли введення/виведення і управляючі вузли. Вузли зв'язані через деяке комунікаційне середовище (високошвидкісна мережа, комутатор та інше). Приклади. • IBM RS/6000 SP2; • Intel PARAGON/ASCIRed; • SGI / CRAY T3E; • Hitachi SR8000; • системи Parsytec. Маштабованість. Загальне число процесорів у реальних системах досягає декількох тисяч (ASCI Red, Blue Mountain). Операційна система. Існують два основних варіанти: • повноцінна операційна система працює тільки на управляючій машині (front-end), на кожному вузлі працює скорочений варіант операційної системи, що лише забезпечує роботу розташованої в ньому гілки паралельного додатка. (Cray T3E); • на кожному вузлі працює повноцінна UNIX-подібна операційна система (варіант, близький до кластерного підходу). Прикладом є IBM RS/6000 SP з встановленою окремо на кожнім вузлі операційною системою AIX. Модель програмування. Програмування в рамках моделіпередачі повідомлень (MPI, PVM, BSPlib) 2. Комп'ютери з загальною пам'яттю (True shared memory). Всі процесори спільно звертаються до загальної пам'яті, як правило, через шину чи ієрархію шин. В ідеалізованої PRAM (Parallel Random Access Machine - паралельна машина з довільним доступом) моделі, яка часто використовується в теоретичних дослідженнях паралельних алгоритмів, будь-який процесор може звертатися до будь-якої комірки пам'яті за той самий час. У таких комп’ютерах не можна істотно збільшити число процесорів, оскільки при цьому відбувається різке збільшення числа конфліктів доступу до шини. На практиці маштабованість цієї архітектури звичайно приводить до деякої форми ієрархії пам’яті. Частота звертань до загальної пам’яті може бути зменшена за рахунок збереження копій часто використовуваних даних у кеш-пам'яті, зв'язаній з кожним процесором. Доступ до цієї кеш-пам'яті набагато швидший, ніж безпосередній доступ до загальної пам'яті. До цього класу відносяться так звані симетричні мультипроцесорні (symmetric multiprocessor SMP) системи. Особливості даної архітектури наступні; Архітектура. Система складається з декількох однорідних процесорів і масиву загальної пам'яті (звичайно з декількох незалежних блоків). Всі процесори мають доступ до будь-якої частини пам'яті з однаковою швидкістю. Процесори підключені до пам'яті або за допомогою загальної шини (базові 2-4 процесорні SMP-сервери), або за допомогою комутатора (HP 9000). Апаратно підтримується когерентність кешів. Приклади. • HP 9000 V-class, N-class; • SMP-cервери і робочі станції на базі процесорів Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu та інші). Маштабованість. Наявність загальної пам'яті значно спрощує взаємодію процесорів між собою, однак накладає сильні обмеження на їх число - не більше 32 у реальних системах. Для побудови маштабованих систем на базі SMP використовуються кластерні архітектури. Операційна система. Вся система працює під управлінням єдиної операційної системи (звичайно UNIX-подібна, але для Intel-платформ підтримується Windows NT). Операційна система автоматично (у процесі роботи) розподіляє процеси між процесорами (scheduling), але іноді можлива і явна прив'язка. Модель програмування. Програмування в моделі загальної пам'яті (POSIX threads, OpenMP). Для SMP-систем існують порівняно ефективні засоби автоматичного розпаралелювання. 3. Комп’ютери з віртуально спільною пам’яттю (Virtual shared memory). У таких системах загальна пам’ять, як така, відсутня. Кожен процесор має власну локальну пам’ять. Він може звертатися до локальної пам’яті інших процесорів, використовуючи “глобальну адресу”. Якщо “глобальна адреса” вказує не на локальну пам’ять, то доступ до пам’яті реалізується за допомогою повідомлень з малою затримкою, що пересилаються по мережі, яка з’єднує процесори. До цього класу належать так звані кластерні (claster) системи. Особливості даної архітектури наступні; Архітектура. Набір робочих станцій загального призначення, використовується як дешевий варіант масово-паралельного комп'ютера. Для зв'язку вузлів використовується одна із стандартних мережевих технологій (Fast/Gigabit Ethernet, Myrinet) на базі шинної архітектури чи комутатора. При об'єднанні в кластер комп'ютерів різної потужності чи різної архітектури, говорять про гетерогенні (неоднорідні) кластери. Вузли кластера можуть одночасно використовуватися в якості робочих станцій користувачів. У випадку, коли це не потрібно, вузли можуть бути істотно полегшені і встановлені у стійку. Приклади. • NT-кластер у NCSA; • Beowulf-кластери. Операційна система. Використовуються стандартні операційні системи для робочих станцій, частіше, вільно розповсюджувані - Linux/FreeBSD, разом зі спеціальними засобами підтримки паралельного програмування і розподілу навантаження. Модель програмування. Програмування, як правило, у рамках моделі передачі повідомлень (частіше - MPI). Дешевизна подібних систем обертається великими накладними витратами на взаємодію паралельних процесів між собою, що сильно звужує потенційний клас розв'язуваних задач. Відзначимо також два класи комп’ютерних систем, що іноді використовуються як паралельні комп’ютери: • локальні обчислювальні мережі (LAN), у яких комп’ютери знаходяться у фізичній близькості і з’єднані швидкою мережею; • глобальні обчислювальні мережі (WAN), що з’єднують географічно розподілені комп’ютери. Хоча системи цього виду вводять додаткові властивості, такі як надійність і захист, у багатьох випадках вони можуть розглядатися як MIMD комп’ютери, хоча і з високою вартістю віддаленого доступу. 3. Поняття і термінологія паралельного програмного забезпечення. Код, що виконується на одиночному процесорі паралельного комп’ютера, знаходиться в деякому ж програмному середовищі, що і середовище однопроцесорного комп’ютера з мультипрограмною операційною системою, тому й у контексті паралельного комп’ютера так само говорять про процеси чи задачі, посилаючись на код, що виконується всередині захищеного регіону пам’яті операційної системи. Багато дій паралельної програми включають звертання до віддалених процесорів чи комірок загальної пам’яті. Для виконання цих дій може бути необхідна суттєва затрата часу, особливо, стосовно часу виконання звичайних команд процесора. Тому більшість процесорів виконує більше одного процесу одночасно, і, отже, у програмному середовищі окремо узятого процесора паралельного комп’ютера використовуються звичайні методи мультипрограмування: • процеси блокуються, коли їм необхідно звернутися до віддалених ресурсів; • процеси готові продовжити роботу, якщо отримана відповідна відповідь. Виконання процесів паралельної програми переривається значно частіше, ніж процесів, що працюють у послідовному середовищі, тому що процеси паралельної програми виконують ще дії, пов’язані з обміном даними між процесорами. Маніпулювання повноваговими процесами у мультипрограмному середовищі є надто дорогим заняттям, оскільки воно тісно пов’язане з управлінням і захистом пам’яті. Внаслідок цього більшість паралельних комп’ютерів використовує легковагові процеси, що називаються нитками (threads) або потоками (streams) управління, а не повновагові процеси. Легковагові процеси не мають власних захищених областей пам’яті (хоча можуть володіти власними локальними даними), що в результаті дуже сильно спрощує маніпулювання ними. Більш того, їхнє використання більш безпечне. Щоб уникнути плутанини, використовують наступні терміни, що позначають різні варіанти процесів виконання програм: • легковагові процеси іменують нитками, потоками управління, співпроцесами; • задачі будуть вказувати на повновагові процеси, тобто процеси операційної системи, що володіють власними захищеними регіонами пам’яті. Процес використовується там, де поділ на легковагові і повновагові процеси несуттєвий і можна використовувати як ті, так і інші. Відповідно до можливостей паралельного комп’ютера, процеси взаємодіють між собою одним з наступних способів: • Обмін повідомленнями (message passing). Процес, що посилає, формує повідомлення з заголовком, у якому вказує, який процесор повинний прийняти повідомлення, і передає повідомлення в мережу, що з’єднує процесори. Якщо після передачі повідомлення у мережу процес, що посилає, продовжує роботу, то такий вид відправлення повідомлення називається неблокуючим (non-blocking send). Якщо ж процес, що посилає чекає, поки приймаючий процес не прийме повідомлення, то такий вид відправлення повідомлення називається блокуючим (blocking send). Приймаючий процес повинен знати, що йому необхідні дані і повинен вказати, що він готовий одержати повідомлення, виконавши відповідну команду прийому повідомлення. Якщо очікуване повідомлення ще не надійшло, то приймаючий процес припиняється доти, поки повідомлення не надійде. • Обмін через загальну пам’ять (Transfers through shared memory). В архітектурах із загальнодоступною пам’яттю процеси зв’язуються між собою через загальну пам’ять - процес, що посилає, поміщає дані у відомі комірки пам’яті, з яких приймаючий процес може зчитувати їх. При такому обміні складність представляє процес виявлення того, коли безпечно поміщати дані, а коли видаляти їх. Найчастіше для цього використовуються стандартні методи операційної системи, такі семафори (semaphore) або блокування процесів. Однак це дорого і сильно ускладнює програмування. Деякі архітектури надають біти зайнято/вільно, зв’язані з кожним словом загальної пам’яті, що забезпечує легкий та високоефективний спосіб синхронізації відправників і приймачів. • Прямий доступ до вилученої пам’яті (Direct remote-memory access). У перших архітектурах з розподіленою пам’яттю робота процесорів переривалася щораз, коли надходив який-небудь запит від мережі, що з’єднує процесори. У результаті процесор погано використовувався. Потім у таких архітектурах у кожному процесорному елементі стали використовувати пари процесорів - один процесор (обчислювальний), виконує програму, а іншої (процесор обробки повідомлень) обслуговує повідомлення, що надходять з мережі чи у мережу. Така організація обміну повідомленнями дозволяє розглядати обмін повідомленнями як прямий доступ до віддаленої пам’яті, до пам’яті інших процесорів. Така гібридна форма зв’язку, що застосовується в архітектурах з розподіленою пам’яттю, має багато властивостей архітектур із загальною пам’яттю. Розглянуті механізми зв’язку необов’язково використовуються тільки безпосередньо на відповідних архітектурах. Так легко промоделювати обмін повідомленнями, використовуючи загальну пам’ять, з іншої сторони можна змоделювати загальну пам’ять, використовуючи обмін повідомленнями. Останній підхід відомий як віртуальна загальна пам’ять. Найбільш бажаними (навіть скоріше обов’язковими) ознаками паралельних алгоритмів і програм є: • паралелізм – вказує на здатність виконання безлічі дій одночасно, що істотно для програм, які виконуються на декількох процесорах; • маштабованість – інша найважливіша ознака паралельної програми, що вимагає гнучкості програми стосовно зміни числа процесорів, оскільки найбільше ймовірно, що їх кількість буде постійно збільшуватися у більшості паралельних середовищ і систем; • локальність – характеризує необхідність того, щоб доступ до локальних даних був більш частим, чим доступ до віддалених даних. Важливість цієї властивості визначається відношенням вартості віддаленого і локального звертань до пам’яті. Воно є ключовим до підвищення ефективності програм на архітектурах з розподіленою пам’яттю; • модульність – відбиває ступінь розкладання складних об’єктів на більш прості компоненти. У паралельних обчисленнях це настільки ж важливий аспект розробки програм, як і в послідовних обчисленнях.

3.1. Процеси та співпроцеси.

У літературі пропонується багато визначень поняття процес, від формального в термінах безлічі станів обчислення до неформального поняття процесу як окремого виконання програми. Існує так само велика кількість уточнень виду процесу, режиму й умов роботи процесу: послідовний процес, паралельний процес, пакетний процес, інтерактивний процес, незалежний процес, взаємодіючий процес і т.д. Будемо розуміти під процесом послідовність дій, що складають деяке обчислення, що характеризується: • відповідною йому програмою/підпрограмою, тобто впорядкованою послідовністю операцій, що реалізують дії, які повинні здійснюватися процесом; • вмістом відповідної йому пам’яті, тобто безліччю даних, якими цей процес може маніпулювати; • дескриптором процесу, тобто сукупністю відомостей, що визначають стан ресурсів, наданих процесу. Розрізняють, де це необхідно, повновагові і легковагові процеси. • повновагові процеси (tasks) – це процеси, що виконуються всередині захищених ділянок пам’яті операційної системи, тобто такі, що мають власні віртуальні адресні простори для статичних і динамічних даних. У мультипрограмному середовищі управління такими процесами тісно пов’язане з управлінням і захистом пам’яті, тому переключення процесора з виконання одного процесу на виконання іншого є операцією, яка займає багато ресурсів. • легковагові процеси (threads, sreams), або ще співпроцеси, не мають власних захищених областей пам’яті. Вони працюють у мультипрограмному режимі одночасно із задачею, що їх активувала, і використовують її віртуальний адресний простір, у якому їм при створенні виділяється ділянка пам’яті під динамічні дані (стек), тобто вони можуть володіти власними локальними даними. Співпроцес описується як звичайна функція, що може використовувати статичні дані програми. Поняття легковагого процесу з’явилося не дуже давно, і за ним ще не закріпився досить вдалий термін. Прямий переклад thread як нитка (управління) не відображає суті повністю. Тому часто використовують термін співпроцес для позначення легковагого процесу. Така назва вказує на те, що це процес, причому в чомусь специфічний, співіснуючий одночасно з іншим процесом. Не слід плутати співпроцес із співпрограмою, хоча це досить близькі поняття. У механізмі співпрограм необхідно явно, за допомогою відповідного оператора, передавати управління від однієї співпрограми до іншої. Співпрограма викликається подібно підпрограмі, але на відміну від підпрограми кожен виклик (крім першого) співпрограми відновляє її виконання з місця останнього повернення (оператора, що безпосередньо слідує за оператором звертання до іншої співпрограми).

3.2. Канали.

Поняття каналу використовується для опису подій, або взаємодій, що виникають при передачі повідомлень між процесами. Канали використовуються для передачі повідомлень в одному напрямку і тільки між двома процесами. Канал, який використовується процесом тільки для виведення повідомлень, називається вихідним каналом цього процесу, а канал, що використовується лише для введення – вхідним каналом. Канал (pipe) – це однонаправлена двоточкова (з’єднує лише два процеси) “комунікаційна лінія”, що дозволяє процесам обмінюватися даними. Операції обміну повідомленнями досить тривалі за часом, тому в різних моделях, системах використовуються різні типи поведінки операцій прийому/передачі повідомлень. Розрізняють наступні види каналів: • синхронні. Передавальний процес, відправивши повідомлення, очікує від приймаючого підтвердження про прийом повідомлення перш, ніж послати наступне повідомлення, тобто приймаючий процес не виконується, поки не одержить дані, а передавальний - поки не одержить підтвердження про прийом даних; • асинхронно-синхронні. Операція передачі повідомлення асинхронна – вона завершується відразу (повідомлення копіюється в деякий буфер, а потім пересилається одночасно з роботою процесу-відправника), не очікуючи того, коли дані будуть отримані приймачем. Операція прийому повідомлення синхронна: вона блокує процес до моменту надходження повідомлення; • асинхронні. Обидві операція асинхронні, тобто вони завершуються відразу. Операція передачі повідомлення працює, як і в попередньому випадку. Операція прийому повідомлення, як правило, повертає деякі значення, що вказують на те, як завершилася операція - повідомлення було прийняте чи ні. У деяких реалізаціях операції обміну повідомленнями активують співпроцеси, що приймають чи відправляють повідомлення, використовуючи тимчасові буфери і відповідні синхронні операції. У цьому випадку існує також синхронізуюча операція, що блокує процес доти, поки не завершаться всі ініційовані операції каналу. При роботі з каналами необхідно стежити за тим, щоб не сталося блокування взаємодіючих процесів (deadlock). Наприклад, процес A не може передати повідомлення процесу B, оскільки процес B чекає, коли процес A прийме повідомлення від нього. Це одна з найпростіших ситуацій, у більш складних випадках циклічні залежності можуть охоплювати багато процесів, причому поява блокування може залежати від даних.

3.3. Семафори.

Семафори традиційно використовувалися для синхронізації процесів, що звертаються до поділюваних даних. Кожен процес повинний виключати для всіх інших процесів можливість одночасного з ним звернення до цих даних (взаємовиключення). Коли процес звертається до поділюваних даних, говорять, що він знаходиться у своїй критичній ділянці. Для вирішення задачі синхронізації необхідно, у випадку якщо один процес знаходиться в критичній ділянці, виключити можливість входження для інших процесів у їхні критичні ділянки. Хоча б для тих, котрі звертаються до тих же самим поділюваних даних. Коли процес виходить із своєї критичної ділянки, то одному з інших процесів, що очікують входу у свої критичні ділянки, повинно бути дозволено продовжити роботу. Процеси повинні якнайшвидше проходити свої критичні ділянки і не повинні в цей період блокуватися. Якщо процес, що знаходиться у своїй критичній ділянці, завершується (можливо, аварійно), то необхідно, щоб деякий інший процес міг скасувати режим взаємовиключення, надаючи іншим процесам можливість продовжити виконання і ввійти у свої критичні ділянки. Семафор – це захищених змінна, значення якої можна опитувати і змінювати тільки за допомогою спеціальних операцій wait і signal і операції ініціалізації init. Двійкові семафори можуть приймати тільки значення 0 і 1. Семафори з лічильниками можуть приймати невід’ємні цілі значення. Операції є неподільними. Критичні ділянки процесів позначаються операціями wait() і signal(). Якщо одночасно декілька процесів спробують виконати операцію wait(), то це буде дозволено тільки одному з них, а іншим прийдеться зачекати. Семафори з лічильниками використовуються, якщо деякий ресурс виділяється з множини ідентичних ресурсів. При ініціалізації такого семафора в його лічильнику вказується число елементів множини. Кожна операція wait() зменшує значення лічильника семафора на 1, показуючи, що деякому процесу виділений один ресурс із множини. Кожна операція signal() збільшує значення лічильника на 1, показуючи, що процес повернув ресурс у множину.

4. Моделі паралельних обчислень.

Паралельне програмування представляє додаткові джерела складності - необхідно явно управляти роботою тисяч процесорів, координувати мільйони міжпроцесорних взаємодій. Для того, щоб вирішити задачу на паралельному комп’ютері, необхідно розподілити обчислення між процесорами системи так, щоб кожен процесор був зайнятий вирішенням частини задачі. Крім того, бажано, щоб як можна менший обсяг даних пересилався між процесорами, оскільки комунікації значно повільніші операції, ніж обчислення. Часто виникають конфлікти між ступенем розпаралелювання й обсягом комунікацій, тобто чим між більшою кількістю процесорів розподілена задача, тим більший обсяг даних необхідно пересилати між ними. Середовище паралельного програмування повинне забезпечувати адекватне управління розподілом і комунікаціями даних. Через складність паралельних комп’ютерів і їх істотної відмінності від традиційних однопроцесорних комп’ютерів, не можна просто скористатися традиційними мовами програмування й очікувати отримання високої продуктивності. Основні моделі паралельного програмування: • процес/канал (Process/Channel); • обмін повідомленнями (Message Passing); • паралелізм даних (Data Parallel); • загальної пам’яті (Shared Memory).

4.1. Модель процес/канал.

У цій моделі програми складаються з одного чи більше процесів, розподілених між процесорами. Процеси виконуються одночасно, їхнє число може змінюватися протягом часу виконання програми. Процеси обмінюються даними через канали, що являють собою односпрямовані комунікаційні лінії, що з’єднують тільки два процеси. Канали можна створювати і видаляти Наведемо більш чіткі характерні властивості моделі процес/канал: • паралельне обчислення складається з одного чи більше одночасно виконуваних процесів, кількість яких може змінюватися протягом часу виконання програми; • процес - це послідовна програма з локальними даними. Процес має вхідні і вихідні порти, що служить інтерфейсом до середовища процесу; • на додачу до звичайних операцій процес може виконувати наступні дії: послати повідомлення через вихідний порт, одержати повідомлення з вхідного порту, створити новий процес і завершити процес; • посилаюча операція асинхронна – вона завершується відразу, не очікуючи того, коли дані будуть отримані. Вхідна операція синхронна – вона блокує процес до моменту надходження повідомлення; • пари з вхідного і вихідного портів з’єднуються чергами повідомлень, які називаються каналами(channels). Канали можна створювати і видаляти. Посилання на канали (порти) можна включати в повідомлення, так що зв'язність може змінюватися динамічно; • процеси можна розподіляти між фізичними процесорами довільним способом, причому використовуване відображення (розподіл) не впливає на семантику програми. Зокрема, безліч процесів можна відобразити на один процесор. Поняття процесу дозволяє говорити про місце розташування даних: дані, що містяться в локальній пам’яті процесу - розташовані “близько”, інші дані –“віддалені”. Поняття каналу забезпечує механізм для вказання того, що для продовження обчислення одному процесу вимагаються дані іншого процесу, тобто залежність між даними.

4.2. Модель обмін повідомленнями.

У цій моделі програми, можливо різні, написані на традиційній послідовній мові, виконуються процесорами комп’ютера. Кожна програма має доступ до пам’яті виконуючого її процесора. Програми обмінюються між собою даними, використовуючи підпрограми прийому/передачі даних деякої комунікаційної системи. Програми, що використовують обмін повідомленнями, можуть виконуватися тільки на MIMD комп’ютерах На сьогоднішній деньмодель обмін повідомленнями (message passing) є найбільше широко використовуваною моделлю паралельного програмування. Програми цієї моделі, подібно програмам моделі процес/канал, створюють безліч процесів, з кожним з який асоційовані локальні дані. Кожен процес ідентифікується унікальним ім’ям. Процеси взаємодіють, посилаючи й одержуючи повідомлення. У цьому відношенні модель обмін повідомленнями є різновидом моделі процес/канал і відрізняється тільки механізмом, який використовується при передачі даних. Наприклад, замість відправлення повідомлення в канал “channel 2” можна послати повідомлення процесу “process 3”. Модель обмін повідомленнями не накладає обмежень ні на динамічне створення процесів, ні на виконання декількох процесів одним процесором, ні на використання різних програм для різних процесів. Просто, формальні описи систем обміну повідомленнями не розглядають питання, пов’язані з маніпулюванням процесами. Однак, при реалізації таких систем доводиться приймати яке-небудь рішення в цьому відношенні. На практиці склалося так, що більшість систем обміну повідомленнями при запуску паралельної програми створює фіксоване число ідентичних процесів і не дозволяє створювати і видаляти процеси протягом роботи програми. У таких системах кожен процес виконує ту саму програму (параметризовану щодо ідентифікатора або процесу, або процесора), але працює з різними даними, тому про такі системи говорять, що вони реалізують модель програмування SPMD (single program multiple data - одна програма багато даних). SPMD модель прийнятна і досить зручна для широкого діапазону додатків паралельного програмування, але вона ускладнює розробку деяких типів паралельних алгоритмів.

4.3. Модель паралелізм даних.

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

4.4. Модель загальна пам’ять.

У цій моделі всі процеси спільно використовують загальний адресний простір. Процеси асинхронно звертаються до загальної пам’яті як із запитами на читання, так із запитами на запис, що створює проблеми при виборі моменту, коли можна буде помістити дані в пам’ять, а коли можна буде видалити їх. Для управління доступом до загальної пам’яті використовуються стандартні механізми синхронізації - семафори і блокування процесів. Перевага цієї моделі з погляду програмування полягає в тому, що поняття власності даних (монопольного володіння даними) відсутнє, отже, не потрібно явно задавати обмін даними між виробниками і споживачами. Ця модель, з одного боку, спрощує розробку програми, але, з іншого боку, ускладнює розуміння і управління локальністю даних, написання детермінованих програм. В основному ця модель використовується при програмуванні для архітектур із загальнодоступною пам’яттю. Висновок. Донедавна фірми-виробники суперкомп’ютерів, виконуючи державні замовлення, проектували унікальні архітектури. Однак, коли бюджетне фінансування різке скоротилося, цим фірмам довелося відмовитися від дорогих багатокомпонентних спеціалізованих процесорів на користь мікропроцесорів, що серійно випускаються. Це стало можливим завдяки прогресу мікроелектроніки, що перетворив у масово доступні інтелектуальні елементи – мікропроцесори, мікросхеми пам’яті й адаптери зовнішніх пристроїв із стандартними інтерфейсами. Це дозволяє концентрувати зусилля на розробці нових суперкомп’ютерних архітектур, створювати системи із найсучасніших компонентів, значно скоротити терміни і вартість розробки суперкомп’ютерів. Існують декілька класифікацій архітектури комп’ютерів, але традиційно використовують схему, представлену Michal J. Flynn, відповідно до якої паралельні обчислювальні системи поділяються на два великих класи: • SIMD (single instruction – multiple data); • MIMD (multiple instruction – multiple data). Розвиток паралельних обчислень пройшов етапи конвейєрно-векторних суперобчислень, паралельних обчислень на множині процесорів, зв’язаних комунікаційним середовищем передачі повідомлень і в даний час освоюються суперобчислення на системах з мікропроцесорів з кеш-пам’ятями і розділюваної (логічно – загальної) фізично розподіленою основною пам’яттю.

Існуючі паралельні обчислювальні засоби класу MIMD утворять три підкласи: 1. симетричні мультипроцесори (SMP); 2. кластери; 3. масово паралельні системи (MPP).

В основі цієї класифікації лежить структурно-функціональний підхід. Симетричні мультипроцесори складаються із сукупності процесорів, що мають однакові можливості доступу до пам’яті і зовнішніх пристроїв і функціонують під управлінням однієї операційної системи. Частинним випадком SMP є однопроцесорні комп’ютери. Усі процесори SMP мають розділювану загальну пам’ять з єдиним адресним простором. Використання SMP забезпечує наступні можливості: • маштабування додатків при низьких початкових витратах; • створення додатків у звичних програмних середовищах; • програмування на базі розділюваної пам’яті; • однаковий час доступу до всієї пам’яті; • можливість пересилання повідомлень з великою пропускною здатністю; • підтримку когерентності сукупності кешів і блоків основної пам’яті, неподільні операції синхронізації і блокування. Однак ступінь маштабованості SMP систем обмежений через неможливість технічної реалізації однакового для великої кількості процесорів доступу до пам’яті зі швидкістю, характерною для однопроцесорних комп’ютерів. Як правило, кількість процесорів у SMP не перевищує 32. Для побудови систем з великим числом процесорів застосовуються кластерний чи МРР підходи. Обидва ці напрямки використовують SMP як системоутворюючий обчислювальний модуль. Кластерна система утвориться з модулів, об’єднаних системою зв’язку чи розділюваними пристроями зовнішньої пам’яті, наприклад дисковими масивами. В даний час для cтворення кластерних систем використовуються спеціалізовані фірмові засоби (наприклад, MEMORY CHANNEL фірми DEC, AWS фірми NCR), або універсальні локальні і глобальні мережі такі, як Ethernet, FDDI (Fiber Distributed Data Interface), і інші мережі, наприклад, із протоколами TCP/IP (Transmission Control Protocol / Internet Protocol), або дискові масиви з високошвидкісними широкими подвійними (Wide/Fast) і квадро PCI SCSI контролерами. Розмір кластера варіюється від декількох модулів до декількох десятків модулів. Ознаками, характерними для кластерів, є: • побудова з компонентів високого ступеня готовності стандартних SMP конфігурацій і мережевих засобів; • побудова на основі стандартних програмно-апаратних парадигм: Open Software Foundation Distributed Computing Environment (OSF DCE) і Open Network Computing (ONC), що підтримують загальні імена і можливості доступу; • узгодженість наборів прикладних програм, форматів даних; • загальна для усіх обчислювальних модулів кластера організація інформаційної безпеки, загальний алгоритм виявлення несправностей і реконфігурації для забезпечення функціонування при наявності відмовлень; • обмежена маштабованість на число обчислювальних модулів. Масово паралельні системи, на відміну від кластерів, мають більш швидкісні, як правило спеціалізовані, канали зв’язку між обчислювальними модулями, а також широкі можливості з маштабування. Крім того, у МРР фіксується деякий досить високий рівень інтерфейсу прикладних програм (API), підтримуваний розподіленою операційною системою. Однак підтримка працездатності й оптимізація завантаження процесорів у МРР менш розвинута у порівнянні з кластерами в силу різноманітності виконуваних програм і відсутності функціональних зв’язків між програмами. Характерні вимоги до системи зв’язку МРР:

• висока пропускна здатність;

• маленька затримка;

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

• базування на стандартах;

• надійні протоколи з управлінням потоком;

• підтримка різних топологій;

• маштабованість;

• настроюваність.