Паралельні обчислення

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

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

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

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

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

Багатоядерні обчислення

Багатоядерний процесор – це процесор, що містить декілька ядер. Ці процесори відрізняються від суперскалярних процесорів, які можуть виконувати декілька інструкцій за такт з одного потоку інструкцій (нитки) ; на відміну від багатоядерних, які можуть за такт виконувати декілька інструкцій з різних ниток. Кожне ядро багатоядерного процесора потенційно може бути суперскалярним, тобто виконувати по декілька інструкцій з одної нитки.

Синхронна багатонитевість (найвідомішою з яких є технологія HyperThreading від Intel) була ранньою формою псевдо-багатоядерності. Процесор, який здатен до синхронної багатонитевості має всього одне ядро, але при простоях ядра (наприклад під час очікування підвантаження даних в стек), використовує це ядро для роботи з іншою ниткою. Мікропроцесор Cell від IBM, що створений для використання в консолях Sony PlayStation 3 є іншим прикладом багатоядерного процесора.

Симетрична багатопроцесорність

Симетричний мультипроцесор (SMP) це комп’ютерна система з багатьма ідентичними процесорами, що поділяють пам’ять, та з’єднуються через шину. Шинна суперечка (en: Bus contention) перешкоджає маштабуванню шинних архітектур. В результаті, SMP зазвичай не містить більше 32-x процесорів. «Через малий розмір процесорів, та значне зменшення вимог до пропускної здатності шини, що досягається завдяки великим кешам, такі симетричні багатопроцесорні системи є дуже рентабельними за умови, якщо існує достатня кількість пропускної здатності у пам’яті».

Розподілені обчислення

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

Кластерні обчислення

Кластер – це група слабо зв’язаних комп’ютерів, що тісно співпрацюють, так що в певною мірою, вони можуть розглядатись як один комп’ютер. Кластери складаються з багатьох окремих машин, з’єднаних мережею. І хоча машини в кластері не мають бути симетричними, якщо вони не є, то це ускладнює балансування навантаження. Найпоширенішим типом кластера є кластер Beowulf, який є кластером, реалізованим на багатьох ідентичних фабричних комп’ютерів з’єданих в локальну мережу TCP/IP Ethernet. Вперше технологію Beowulf розробили Томас Стерлінг та Дональд Беккер. Більшість суперкомп’ютерів зі списку TOP500 є кластерами.

Масово паралельні обчислення

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

Обчислення Ґрід

Обчислення Ґрід – найбільш розподілена форма паралельних обчислень. Вона використовує для розв’язання задачі, комп’ютери з’єднані мережею Інтернет. Через низьку швидкість передачі даних, та надзвичайно високий час доступу до даних в Інтернет, ґрід обчислення проводять тільки для проголомшливо паралельних задач. Створена багато застосувань ґрід системам, найвідомішими з яких є SETI@home та Folding@Home [2].

Більшість програм ґрід обчислень використовують проміжне програмне забезпечення, що слугує інтерфейсом між операційною системою, та програмою, та керує ресурсами мережі, і стандартизує інтерфейс. Найпоширенішим програмним забезпеченням цього типу є Berkeley Open Infrastructure for Network Computing (BOINC). Часто програми ґрід обчислень користуються «запасними циклами», виконуючи обчислення під час простою системи. Тому їхні реалізації під виглядом екранних заставок доволі поширені.

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

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

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

При будь-якому вигляді взаємодії процесів необхідна взаємна синхронізація. Існують два основних види синхронізації – взаємне виключення і умовна синхронізація [4]. Взаємне виключення забезпечує, щоб критичні секції операторів не виконувалися одночасно. Умовна синхронізація затримує процес до тих пір, поки не виконається певну умову. Наприклад, взаємодія процесів виробника і споживача часто забезпечується за допомогою буфера в пам’яті, що розділяється. Виробник записує в буфер, споживач читає з нього. Щоб запобігти одночасне використання буфера і виробником, і споживачем, використовується взаємне виключення. Умовна синхронізація використовується для перевірки, чи було лічено споживачем останнє записане в буфер повідомлення.

Як і інші прикладні галузі комп’ютерних наук, паралельне програмування пройшло ряд стадій. Воно виникло завдяки новим можливостям, наданим розвитком апаратного забезпечення, і розвинулося у відповідності з технологічними змінами. Через деякий час спеціалізовані методи були об’єднані в набір основних принципів і загальних методів програмування. Паралельне програмування виникло у 1960-і роки у сфері операційних систем. Причиною став винахід апаратних модулів, названих каналами, або контролерами пристроїв. Вони працюють незалежно від керуючого процесора і дозволяють виконувати операції введення-виведення паралельно з інструкціями центрального процесора. Канал взаємодіє з процесором з допомогою переривання – апаратного сигналу, який говорить: «Зупини свою роботу і розпочни виконувати іншу послідовність інструкцій». Результатом появи каналів стала проблема програмування (справжня інтелектуальна проблема) – тепер частини програми могли бути виконані в непередбачуваному порядку. Отже, поки одна частина програми оновлює значення деякої змінної, може виникнути переривання, що приводить до виконання іншої частини програмами, яка теж спробує змінити значення цієї змінної. Ця специфічна проблема називається задачею критичної секції.

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

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

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

 

 

1. Воеводин В. В. Математические основы параллельных вычислений / В. В. Воеводин. – М. : Изд-во МГУ, 1991.

2. Программирование на параллельных вычислительных системах под ред. Р. Бэбба, – М. : Мир, 1991.

3. СуперЭВМ. Аппаратная и программная организация / Под. Ред. С. Фернбаха М. : Радио связь, 1989.

4. Тербер К. Дж. Архитектура высокопроизводительных вычислительных систем / К. Дж. Тербер. – М. : Наука, 1985.