Методи та засоби ефективної обробки паралельних задач в комп’ютерних кластерних системах (стр. 6 )

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

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

1.3. Загальна характеристика технологій програмування паралельних комп’ютерних систем

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

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

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

1.4. Моделі взаємодії паралельних процесів

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

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

– передача даних;

– синхронізація.

Існує дві основні моделі взаємодії паралельних процесів: модель, що базується на спільних змінних, та модель, що базується на відправці повідомлень.

Модель, що базується на спільних змінних

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

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

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

Модель, що базується на відправці повідомлень

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

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

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

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

Спільні змінні: а, захищена семафором Sa = 1;

b, захищена семафором Sb = 1

1 Потік T1 begin
2	P(Sa);
3	P(Sb);
4	a ← a + b;
5	V(Sb);
6	V(Sa);
7 end
8 Потік T2 begin
9	P(Sb);
10	P(Sa);
11	b ← a + b;
12	V(Sa);
13	V(Sb);
14 end

________________________________________________________________

Рис. 1.3. Приклад паралельної програми, в якій можливий тупик

1.5. Модель програмування з явним створенням потоків

Модель програмування з явним створенням потоків виконання орієнтована на паралельні ЕОМ зі спільною пам’яттю. В даній моделі програмісту доступні засоби для створення та завершення потоків безпосередньо. Звичайно доступні наступні операції:

– створення потоку в робочому стані;

– створення потоку в тимчасово зупиненому стані;

– продовження роботи потоку;

– тимчасова зупинка роботи потоку;

– зупинка роботи потоку;

– перевірка, чи закінчив роботу потік;

– очікування закінчення роботи потоку.

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

– Тупиком називається взаємне очікування двох потоків, яке не може завершитись.

Так, наприклад, на рис. 1.3 наведено програму, яка використовує дві спільні змінні. Для вирішення задачі взаємного виключення використовуються семафори Sa та Sb. Над семафорами визначені операції:[18]

– P(S): перевіряє значення семафора S; якщо S > 0, то виконує
S ← S – 1, інакше – блокує потік виконання;

– V(S): перевіряє, чи є потоки виконання, які заблоковані по даному семафору; якщо є, то розблокує один з них, що дозволяє йому увійти в критичну ділянку; інакше виконує S = S +1.

Але в цій програмі є можливість виникнення тупика, наприклад, при такій послідовності дій потоків:

– Т1: Р(Sa) – успіх, S ← S – 1;

– Т2: Р(Sb) – успіх, S ← S – 1;

– Т2: Р(Sa) – S = 0, блокування;

– Т1: Р(Sb) – S = 0, блокування.

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