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

Значної популярностi набув пiдхiд збiльшення продуктивностi розподiлених обчислювальних систем за допомогою спецiалiзованих плат розширення, так званих акселераторiв (англ. accelerator). Широко вiдома технологiя CUDA [62], яка дозволяє виконувати обчислення загального призначення на платах розширення з графiчними процесорами, поступово вiдiграє все бiльшу роль у проектуваннi розподiлених обчислювальних систем. Однак програмний iнтерфейс CUDA має ряд особливостей, якi значно ускладнюють програмування таких гетерогенних систем: фактично, будь-яка система, що використовує таку технологiю, стає системною з локальною пам’яттю, оскiльки необхiдно явно переносити данi з основної пам’ятi обчислювальної системи в пам’ять акселератора; крiм того, якщо система i ранiше була розподiленою, перенесення даних мiж акселераторами може потребувати декiлькох iтерацiй копiювання, що значно негативно впливає на загальний час розв’язку задачi. З iншого боку, апаратне забезпечення акселератора на базi графiчного процесора оптимiзоване для синхронного виконання однакових команд над рiзними даними, тобто вiдноситься до систем класу SIMD за класифiкацiєю Флiна. Обчислювальнi системи такого класу створювалися i ранiше, зокрема iснує багато прикладiв матричних систем, якi найбiльш ефективно розв’язують задачi з малим зерном паралелiзму або з так званим природним паралелiзмом. В той час як сучаснi паралельнi обчислювальнi систем орiєнтованi на розв’язок задач з середнiм або крупним зерном розпаралелювання, а розподiленi системи, зазвичай, неефективнi для паралельних реалiзацiй алгоритмiв з малим зерном. Тому використання акселераторiв на базi графiчних процесорiв значно ускладнює процес програмування складних наукових та прикладних задач для їх паралельного розв’язку та вимагає вiд користувача глибокого та детального розумiння принципiв побудови розподiлених систем з їх використанням.

Основною складнiстю у використаннi обчислювальних систем, що включають в себе акселератори на графiчних картах, є складна iєрархiя пам’ятi. Один акселератор може мiстити декiлька видiв пам’ятi, доступної користувачу, а саме:

–  файл регiстрiв;

–  невеликий обсяг спiльної пам’ять в рамках одного обчислювального елементу;

–  невеликий обсяг iндивiдуальної пам’ятi кожного обчислювального потоку;

–  глобальну пам’ять;

–  пам’ять для зберiгання констант з можливiстю кешування;

–  так звану пам’ять структур, яка зазвичай має великий обсяг;

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

У разi використання акселераторiв на базi графiчних карт в системах з локальною пам’яттю, задача забезпечення передачi даних цiльовому обчислювальному пристрою ще бiльше ускладнюється через необхiднiсть передачi даних мiж основною (локальною) пам’яттю вузлiв обчислювальної системи. Найбiльш тривiальний пiдхiд включає в себе використання низькорiвневого iнтерфейсу передачi повiдомлень для передачi даних мiж вузлами, пiсля чого, за необхiдностi, виконується передача даних в пам’ять акселератора. Будучи вiдносно простим у реалiзацiї, цей пiдхiд вимагає тим не менш достатнiх обсягiв основної пам’ятi та декiлькох додаткових операцiй копiювання, що збiльшує загальний час передачi даних. [92] Тому було запропоновано [93] спецiалiзовану версiю низькорiвневого iнтерфейсу передачi повiдомлень, яка враховує наявнiсть акселераторiв i дозволяє виконувати копiювання мiж двома акселераторами, встановленими в рiзних вузлах обчислювальної системи з локальною пам’яттю, що дозволило скоротити час передачi даних. Можливiсть передачi даних одночасно з виконанням попереднього етапу обчислень, тим не менш, не була в значнiй мiрi дослiджена.

Наприкiнцi 2012 року, компанiя Intel, виробник найбiльш широко використовуваних мiкропроцесорiв, представила акселератор Xeon Phi. На вiдмiну вiд акселераторiв на базi графiчних карт, дана плата розширення мiстить процесор з великою кiлькiстю ядер (до 80), який пiдтримує традицiйну x86 архiтектуру процесора та типовий набiр iнструкцiй. [94,95] Це дозволяє використовувати под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в, є Intel Array Building Blocks (ArBB). Ця технологiя, що має спiльну з багатьма бiблiотеками паралельних математичних алгоритмiв iдеологiю, призначена для паралельного виконання операцiй над масивами в мовi С++. Технологiя ArBB включає в себе бiблiотеку часу виконання та реалiзує iдею JIT-компiляцiї [96], тобто трансляцiї вихiдних кодiв з мови високого рiвня в певне промiжне представлення статично, пiсля чого трансляцiю з промiжного представлення в вiдповiдний об’єктний код безпосередньо перед початком виконання програми, або навiть пiд час виконання програми. Такий пiдхiд дозволяє генерувати об’єктнi коди, оптимiзованi для конкретного апаратного забезпечення, яке використовується в обчислювальнiй системi без явної перекомпiляцiї програми. Це дозволяє розробнику iгнорувати певнi низькорiвневi особливостi роботи обчислювальних систем i сфокусуватися на обчислювальному алгоритмiв. Однак, JIT-компiляцiя не може використовувати представлення вихiдних кодiв у виглядi повного синтаксичного дерева складної мови та використовувати коштовнi алгоритми оптимiзацiї через те, що час її виконання враховується в загальний час роботи програми. Для деяких, невеликих за обсягом розрахункiв, задач такий процес може призвести для зайвих часових витрат i збiльшенню використання системних ресурсiв.

Однiєю з значних переваг даної технологiї, завдяки спецiалiзацiї для виконання операцiй над масивами та наявностi етапу JIT-компiляцiї, є можливiсть автоматичної векторизацiї циклiв. Бiльшiсть операцiй над масивами виконуються циклiчно, але припускають високорiвневий опис, наприклад «скласти елементи масивiв попарно». Такi операцiї представленi в бiблiотецi часу виконання ArBB, та їх семантика чiтко визначена в документацiї, що дає змогу однозначно визначити чи можлива векторизацiя для даної операцiї та яким чином її найкраще виконати. На вiдмiну вiд векторизацiї довiльних циклiв, ArBB виконує векторизацiю лише операцiй з чiтко заданими вiдношеннями елементами масиву, тобто мiж iтерацiями циклiчної обробки таких масивiв, тому цей процес вiдбувається досить швидко, оскiльки не потребує значного аналiзу. Використання JIT-компiляцiї дозволяє генерувати об’єктнi коди з використанням розширень iнструкцiй SSE4, AVX та iнших, в залежностi вiд їх наявностi в поточному апаратному забезпеченнi. [97]

Технологiя ArBB пропонує користувачу механiзми для роботи з одно-, двох - та трьохвимiрними масивами, якi представленi як шаблони класiв на мовi С++, тобто допускають використання будь-яких типiв, якi носять семантику елементiв певної алгебри та мають визначенi вiдповiднi операцiї, зокрема вбудованих типiв цiлих, рацiональних або комплексних чисел. [74] З точки зору ArBB цi об’єкти семантично еквiвалентнi алгебраїчним векторам, матрицям та тензорам третього порядку. Для представлення алгебраїчних об’єктiв вищого порядку, iснує можливiсть визначати користувацькi операцiї над цими об’єктами. Оскiльки будь-який об’єкт буде представлений в пам’ятi лiнiйно, достатньо використовувати одновимiрнi масиви та операцiї, якi враховують необхiднiсть перетворення з одновимiрного масиву в об’єкт визначеної за деякими правилами структури.

Ця технологiя має спiльний з бiблiотекою Ouverture недолiк – необхiднiсть адаптування прикладних задач та алгоритмiв їх розв’язку до математичних абстракцiй, що наявнi в ArBB. Це потенцiйно знижує ефективнiсть розпаралелювання через необхiднiсть додаткових обчислень при змiнi представлення та ускладнює вихiднi коди, створюючи додаткову можливiсть помилки. ArBB дозволяє генерувати потiк векторних iнструкцiй для процесорiв, якi мають їх пiдтримку, однак працює лише в рамках однiєї системи зi спiльною пам’яттю. З iншого боку, наявнiсть векторизацiї дає змогу розв’язувати задачi, яким властивий дрiбнозернистий паралелiзм, на типових системах зi спiльною пам’яттю, якi загалом не дозволяють ефективно використовувати такi властивостi.

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

Технологiя Intel Threading Buidling Blocks (TBB) [85] представляє бiльш узагальнений пiдхiд до програмування систем зi спiльною пам’яттю для паралельного розв’язання обчислювальних задач. Основою даної бiблiотеки є програмний iнтерфейс, який широко застосовує можливостi метапрограмування на мовi С++, та додатковий планувальник в бiблiотецi часу виконання для забезпечення ефективного розпаралелювання. Останнiй не замiщує частину операцiйної систем, а керує виконанням частин задачi, яка розв’язується за допомогою TBB, в рамках видiлених операцiйною системою ресурсiв.