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

В останньому стандартi мови програмування С++ [29] введено ряд значних змiн в органiзацiю стандартної бiблiотеки. Зокрема, до стандартної бiблiотеки було включено модуль Futures, який забезпечує п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сля запиту починаються посл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йної роботи з потоками, не дозволяє керувати доступом до даних п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льних даних може бути забезпечена завдяки використанню арифметики покажчикiв (рис. 1.10), однак взаємне виключення такого доступу не може бути перевiрене на етапi трансляцiї, а призведе до невизначеної поведiнки пiд час виконання (рис. 1.11).

Рис. 1.10. Безконфлiктний доступ за одним покажчиком з використанням арфiметики

Рис. 1.11. Конфл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дбувся запис в дiлянки пам’ятi, що перетинаються, поведiнка програми не є визначеною згiдно стандарту, тому може бути будь-якою.

1.17. Пор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 системи з локальною пам’яттю, – кожна з яких має свої особливост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рку пам’ят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ї доступу до даних зведенi до табл. 1.2 . Можна вiдмiтити, що бiльшiсть розглянутих широко застосовуваних у високопродуктивних обчисленнях технологiй програмування орiєнтованi лише на обчислювальнi системи зi спiльною пам’яттю або лише на обчислювальнi системи з локальною пам’яттю. Також слiд зазначити, що ряд технологiй додатково пiдтримують використання так званих акселераторiв для виконання довiльних обчислень.

Таблиця 1.2

Порiвняння обраних моделей та технологiй програмування паралельних обчислювальних систем

Технологiя	Цiльова система	Особливостi доступу до даних
Вказiвки компiлятору (OpenMP)	Обчислювальна система зi спiльною пам’яттю	Копiювання автоматичне вiдповiдно до вказiвок; додатковi вказiвки для взаємного виключення; лише спiльна пам’ять.
Низькорiвневий iнтерфейс передачi повiдомлень (MPI)	Обчислювальна система з локальною пам’яттю	Обов’язкове явне копiювання даних мiж вузлами; можливiсть програмованої буферизацiї пiд час передачi.
Низькорiвневий iнтерфейс передачi повiдомлень з оптимiзацiєю (MPI-2/3)	Обчислювальна система з локальною пам’яттю, вузли якої мiстять спiльну пам’ять	Те ж саме, що MPI, та додатково використання спiльної пам’ятi в рамках вузла за можливостi, технологiї прямого дос-тупу у вiддалену пам’ять.
Iнтерфейс програмування графiчних акселераторiв CUDA	Обчислювальна система зi спiльною пам’яттю та застосу-ванням графiчних акселераторiв nVidia	Обов’язкове явне копiю-вання даних в пам’ять акселератора. Багато-рiвнева iєрархiя пам’ятi.
Низькорiвневий iнтерфейс передачi повiдомлень з ура-хуванням графiчних акселераторiв (CUDA-MPI)	Обчислювальна сис-тема з локальною пам’яттю та застосу-ванням графiчних акселераторiв nVidia	Те ж саме, що CUDA, та додатково можливiсть явного копiювання у пам’ять акселератора в iншому вузлi.
1	2	3
Технологiя Array Building Blocks	Обчислювальна сис-тема зi спiльною пам’яттю	Автоматичне взаємне виклю-чення в екземплярах спе-цiально структурованих типiв; лише спiльна пам’ять.
Технологiя Threading Building Blocks	Обчислювальна система зi спiльною пам’яттю та застосу-ванням акселераторiв типу Xeon Phi	Автоматичне копiювання на акселератор та взаємне вик-лючення в екземплярах спе-цiально структурованих типiв; лише спiльна пам’ять.
Стандартна бiблiотека Futures мови C++	Обчислювальна система зi спiльною пам’яттю	Можливiсть вiдкладеного обчислення та доступу (за без-посереднiм запитом), зокрема паралельного. Лише спiльна пам’ять.
Стандартна техно-логiя вiдкладених обчислень мови Haskell	Обчислювальна система зi спiльною пам’яттю	Можливiсть вiдкладеного обчислення та доступу. Лише спiльна пам’ять.

Висновки до першого розділу

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

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

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

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

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

– відсутність явної роботи зі спільними ресурсами, що мінімізує помилки програмування, які з цим пов’язані;