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

Використання паралельних обчислювальних систем на даний момент є найбiльш загальновживаним пiдходом до побудови високопродуктивних обчислювальних систем. Бiльшiсть сучасних персональних та портативних ЕОМ мiстять декiлька процесорiв або багатоядернi процесори, що забезпечують пiдтримку виконання обчислень декiлькома потоками або процесами одночасно, а також бiльшiсть сучасних операцiйних систем побудовано за принципами подiлу часу. [18,12] Для виконання великих обсягiв обчислень здебiльшого використовують розподiленi систем з рiзною органiзацiєю, найбiльш популярними з яких є кластернi системи. [11] Значного розвитку останнiм часом отримали методи застосування додаткових обчислювальних елементiв та плат розширення, зокрема використання графiчних адаптерiв для виконання довiльних обчислень [62] та спец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 паралельну версiю пiдпрограми без змiни iнтерфейсу. [49] Новiтнi пiдходи дозволяють описувати обчислення в термiнах абстрактних задач та зв’язкiв мiж ними, з можливiстю паралельного виконання пiдзадач. [52,64] Однак, 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д час роботи програми засобами бiблiотек часу виконання. Бiльшiсть сучасних моделей програмування паралельних обчислювальних систем пiдтримує такий пiдхiд тим чи iншим образом. В цьому роздiлi розглядаються пiдходи до органiзацiї доступу до даних, що застосовуються в найбiльш широко розповсюджених моделях програмування паралельних обчислювальних систем.

1.13. Явне розпаралелювання з використанням директив компiлятора

На сьогоднiшнiй день, широкого застосування знайшла технологiя проектування та розробки програм для обчислювальних систем з спiльною пам’яттю OpenMP. [28] Завдяки вiдносно невеликим змiнам у вихiдних кодах програми, якi дозволяють органiзувати паралельнi обчислення, та реалiзацiї певного рiвня абстракцiї, ця технологiя здебiльшого застосовується для органiзацiї паралельного виконання iснуючих послiдовних реалiзацiй певних алгоритмiв. [68] Однак, її застосування передбачає, що користувач може самостiйно визначити наявнiсть або вiдсутнiсть залежностей мiж рiзними структурними частинами програми та помiстити у вихiдних кодах вiдповiднi анотацiї. В основу цiєї технологiї покладена адаптацiя компiляторiв мов С, С++ та Fortran для пiдтримки додаткових вказiвок компiлятору, якi реалiзованi за допомогою директив препроцесора у вищеперелiчених мовах програмування [69]. Цi вказiвки дозволяють користувачу обчислювальної системи явним чином видiлити у вихiдних кодах свого програмного забезпечення, якi допускають той чи iнший вид паралельного виконання. Вказiвки, як правило, вказуються для позначення незалежностi виконання певних частин програми, в тому числi можливостi паралельного виконання. Так, директива sections дозволяє вiдмiтити два або бiльше блоки коду, якi можуть бути виконанi незалежно один вiд одного, в тому числi паралельно, а директива parallel for вказує на незалежнiсть iтерацiй циклу одна вiд одної, що також допускає їх паралельне виконання. Вказiвки OpenMP також дозволяють явно вид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ї OpenMP 3.0. [70-72] Пiд час проектування елементiв специфiкацiї OpenMP було враховано статистичнi науковi данi про те, що виконання циклiчної обробки займає в середньому 80% вiд всього часу виконання програми. [73] Через це основна частина запропонованих в специфiкацiї вказiвок компiлятору призначена для органiзацiї паралельного обчислення циклiв. Окрiм модифiкацiї трансляторiв та пiдтримки з їх боку, технологiя OpenMP передбачає надання користувачу паралельної обчислювальної системи б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єї OpenMP-програми. Бiблiотека також включає прикладний iнтерфейс програмування, що дозволяє користувачу частково контролювати процес виконання, але це не є обов’язковою умовою паралельного виконання.

Органiзацiя доступу к даним, якi необхiднi для обчислення певної частини обчислювальної задачi в технологiї OpenMP виконується за допомогою спец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ях. [28] Одночасне звернення до даних, що використовуються спiльно багатьма потоками, без використання механiзмiв взаємного виключення призводить до невизначеної поведiнки: жодних гарантiй на коректнiсть результату такого звернення не надається, однак у деяких випадках зчитанi або записанi данi можуть бути коректними.