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

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

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

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

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

– Клас реалізацій алгоритмів без блокування (англ. lock-free) надає гарантії щодо прогресу в паралельній системі в цілому.

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

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

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

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

Як ще одне підтвердження проблеми складності моделей пам’яті можна привести той факт, що перша модель пам’яті для мови Java мала численні недоліки та фактично не відповідала жодній з реалізацій. [39] Ці недоліки були виправлені тільки в 2005 році. [40] Крім того, усунення недоліків потребувало використання зовсім іншого математичного апарату.

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

1.11. Порівняння моделей програмування

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

– Більшість розглянутих підходів розраховані тільки на системи зі спільною пам’яттю.

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

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

– можливість виникнення тупиків;

– можливість голодування потоків;

– відсутність гарантій того, що зрештою обчислення будуть завершені.

– Моделі програмування з явним створенням потоків притаманна складність написання коректних та ефективних програм. Індикатором цього є наявність великої кількості інструментів для пошуку тупиків та гонок, а також відсутність падіння інтересу до даної тематики досліджень.

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

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

– В моделі програмування зі структурним створенням потоків створені необхідні передумови для зміни зерна паралелізму на етапі виконання. Але прийняття рішення про зміну зерна покладено на програміста. Тому відкритим залишається наступне питання: на основі якої інформації можна прийняти таке рішення?

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

– В моделі програмування з неявним поділом задачі можлива автоматична зміна зерна паралелізму.

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

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

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

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

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

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

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

1.12. Загальний огляд пiдходiв до органiзацiї збереження даних при паралельних обчисленнях

Iнформатика та засоби обчислювальної технiки є однiєю з найбiльш швидко розвиваючихся областей сучасної науки. З моменту початку її активного розвитку зберiгається позитивна динамiка такого розвитку, що стає очевидним при розглядi таких експоненцiйних залежностей як закон Мура та похiдних вiд нього. Це також пiдкреслюється великою кiлькiстю наукових та державних органiзацiй, якi декларують розвиток обчислювальної технiки як один з найбiльш прiоритетних напрямкiв розвитку. [58,59] Постiйне зростання вимог до обчислювальних ресурсiв для розв’язку найбiльш важливих наукових задач сучасностi призвiв до створення цiлої лiнiйки технологiй, що дозволяють науковцям отримувати доступ для обчислювальних ресурсiв з цiллю розв’язання прикладних задач. Найбiльш яскравими прикладами таких технологiй є гетерогеннi електронно-обчислювальнi машини або ЕОМ кластерного типу та створення мiжнародної iнфраструктури для використання розподiлених обчислень в науковому середовищi. [60]

Традицiйним пiдходом до збiльшення продуктивностi обчислювальних систем та комплексiв впродовж тривалого часу було удосконалення часових, частотних, електричних властивостей апаратних компонентiв ЕОМ шляхом збiльшення тактової частоти роботи логiчних вентилiв, збiльшення ступеню iнтеграцiї елементiв в схемi та iншими методами на кшталт збiльшення обсягу елементiв електронiки на одиницю простору. Однак, впродовж останнього десятирiччя зростання продуктивностi обчислювальних машин та систем, що забезпечувалось застосуванням подiбних методiв, майже зупинилось [8], у зв’язку з чим основним шляхом збiльшення продуктивностi обчислювальних систем стало застосування паралельних та розподiлених обчислень [61]. Воно набуло ще бiльш широкого i масового застосування та призвело до появи нових архiтектур паралельних та розподiлених обчислювальних систем, розробки систем з масовим паралелiзмом [62] тощо.

Таблиця 1.1.	Переваги, недоліки та особливості моделей програмування паралельних ЕОМ	Модель програмування	без блокувань	так	ні	Апаратні операції, неподільність яких гарантується на апаратному рівні	можливий, розмір зерна обирається програмістом	не можлива	ні
низькорівне-ва передача повідомлень	так	так	Спільні ресурси відсутні	не можлива	ні
транзак-ційна па-м’ять	так	ні	Апаратні транзакції	не можлива	ні
з неявним поділом задачі	так	ні	Прихована від програміста, виконується бібліотекою	можлива, розмір зерна на-лаштовується автоматично	так
зі структурним створенням потоків	так	ні	Задача взаємного вклю­чен­ня: застосовуються сема­фори, м’ю-текси, монітори	можлива, але потребує окремого підходу для кож-ної задачі	ні
з явним створенням потоків	так	ні	не можлива	ні
Характеристика моделі програмування	Можлива реалізація для паралельної ЕОМ зі спільною пам’яттю	Можлива реалізація для паралельної ЕОМ з локальною пам’яттю	Робота зі спільними ресурсами	Статичний вибір зерна паралелізму	Динамічна зміна зерна паралелізму	Автоматична зміна зерна паралелізму

Незважаючи на потенцiйно значне збiльшення продуктивностi при розглядi математичного апарату та теорiї паралельних обчислень, в практичному застосуваннi вони не завжди забезпечують необхiдний рiвень ефективностi в термiнах вiдношення коефiцiєнту пришвидшення до кiлькостi одночасно працюючих процесорiв ЕОМ. Детальний аналiз вищеперелiчених факторiв приводить до висновку, що при розв’язку складних обчислювально-навантажених задач, таких як сучаснi науковi розрахунки, на паралельних та розподiлених обчислювальних системах на швидкiсть отримання результатiв впливає не тiльки апаратне забезпечення, але й програмне забезпечення, зокрема прикладне програмне забезпечення, що розв’язує задачу користувача [63].