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

Особливiстю даної технологiї є порiвняно високий рiвень абстракцiї з точки зору користувача технологiї: TBB повнiстю скриває наявнiсть паралельного виконання, процес розпаралелювання та взаємодiю з потоками або процесами, пропонуючи натомiсть описувати задачу в термiнах структури даних та певного абстрактного набору дiй над нею. Необхiдними для коректної роботи дiями є способи розбиття структури на двi структури такого ж типу, тобто розбиття вихiдної задачi на двi пiдзадачi; обчислення часткового результату для певної пiдзадачi; та об’єднання ранiше розбитих структур в одну. Пiд час роботи програми бiблiотека часу виконання автоматично виконує розбиття вихiдної задачi на необхiдну кiлькiсть пiдзадач за визначеними критерiями, наприклад кiлькiсть наявних процесорiв. Вона також забезпечує паралельне виконання пiдзадач, якщо можливе, та об’єднання отриманих результатiв в один. Найбiльш ефективним такий пiдхiд виявився при застосуваннi до задач, яким властивий паралелiзм за даними (англ. data-parallel), однак є ефективним i для довiльних задач. Для органiзацiї паралельного виконання пiдзадач в рамках видiлених операцiйною системою ресурсiв (процесорiв, пам’ятi тощо) використовується адаптивний механiзм планування за запитами (англ. work-stealing scheduling). [98,99] Цей пiдхiд передбачає можливiсть динамiчного розбиття задачi на ряд пiдзадач та запити на делегування певної пiдзадачi на виконання iншим ресурсом.

Ця технологiя при органiзацiї паралельних обчислень явно використовує особливостi архiтектури систем зi спiльною пам’яттю, зокрема активно звертається до спiльних для всiх паралельних потокiв виконання даних, тому її адаптування для систем з локальною пам’яттю та розподiлених систем є досить складним. Однак, концепцiя опису довiльних задач в термiнах операцiй над ними може бути застосоване в будь-яких системах. Можливiсть динамiчного перерозбиття задачi на частини певного розмiру за допомогою визначеного користувачем алгоритму дає змогу контролювати зерно розпаралелювання, а можливiсть запитiв на делегування – виконувати балансування навантаження на рiзнi ресурси i роботу в гетерогенних системах. [100]

Технологiя TBB передбачає написання нових програм та проектування вiдповiдних структур даних i операцiй над ними, однак не перешкоджає використанню iснуючих бiблiотек математичних алгоритмiв, в тому числi паралельних, при виконаннi цих операцiй.

Iдею використання високорiвневих абстракцiй задач та пiдзадач, до складу яких входить набiр даних, над якими необхiдно виконати обчислення, було пiзнiше розширено таким чином, щоб забезпечити пiдтримку обчислювальних систем з локальною пам’яттю. [52,53] Однiєю з основних задач, яку необхiдно вирiшити при цьому, є забезпечення передачi даних мiж вузлами обчислювальної системи. При цьому, завдяки використанню абстракцiй пiдзадач, iснує можливiсть оцiнити швидкiсть передачi даних, необхiдних для виконання пiдзадачi та безпосередньо час виконання пiдзадачi за умови вiдносної рiвномiрностi навантаження, що в цiлому дозволить визначити час, до якого необхiдно виконати передачу даних.

1.16. Технологiя вiдкладених обчислень

Iдея вiдкладених обчислень з’явилася в процесi еволюцiї обчислювальних систем, що керуються потоком даних. Створення обчислювальних систем такого роду почалося з реалiзацiї концепцiї, що протиставляється традиц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 алгоритми та структури даних. [101] Таким чином, запропонована в якостi апаратного розширення, концепцiя обчислень, що керуються потом даних знайшла подальший розвиток як модель програмування. Наразi активно розглядається можливiсть адаптацiї цiєї концепцiї для використання в обчислювальних системах з локальною пам’яттю, зокрема кластерних обчислювальних системах, однак вiдкритими залишаються ряд питань, такi як невiдповiднiсть зерна розпаралелювання мiж оригiнальною концепцiєю та реально iснуючими обчислювальними системами, можливiсть параметризацiї графу програми розмiром ярусу, обробка зовнiшнiх подiй тощо. Цi питання розглядаються в циклi робiт [102,103].

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

Iдеї, що були запропонованi при розробцi концепцiї обчислень, що керуються по запитам, також широко застосовуються в сучасних моделях програмування, та отримали назву лiнивих обчислень (англ. lazy evalutaion). Концепцiя лiнивих обчислень складається з наступних частин:

–  обчислення виконуються лише тодi, коли його результат буде явно запитано (вiдкладенi обчислення, англ. deferred evalutaion);

–  обчислення виконуються рiвно в тому обсязi, який є достатнiм для отримання результату (мiнiмальнi обчислення, англ. short-circuit evaluation);

–  кожний значення обчислюється не бiльше одного разу (iнкрементальнi обчислення, англ. incremental evaluation).

Ключове значення з вищеперелiчених мають вiдкладенi обчислення, в основу яких покладено принцип обчислювальних систем, що керуються по запитам, але реалiзований на програмному рiвнi. Програмна реалiзацiя такого пiдходу потребує значної кiлькостi обчислень для обробки виконуваної програми в процесi її роботи, тому в повному обсязi реалiзується лише в декiлькох високорiвневих мовах програмування. Поодинокi принципи однак реалiзованi в бiльшостi мов програмування, так зокрема бiльшiсть мов, похiдних вiд мови С, включаючи Java та C# реалiзують принцип мiнiмальних обчислень при роботi з даними булевого типу наступним чином: якщо пiсля обчислення чергової частини булевого виразу можливо визначити результат виразу, то обчислення iнших частин виразу не виконується. Наприклад, якщо при обчисленнi логiчного ТА отримано значення «хиба», результат обчислення ТА також «хиба» i подальшi обчислення не можуть його змiнити.

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

У деяких функцiональних мовах програмування сiмейства ML, зокрема у сучасних мовах програмування, орiєнтованих на проведення дослiджень в данiй областi, Haskell [104] та Coq [105] iдею вiдкладених обчислень втiлено програмним чином. В цих мовах застосовується обширний математичний апарат [106] для представлення так званих чистих функцiй та опису взаємодiї мiж ними та оточенням, у якому виконується програма. Концепцiя чистої функцiї має на метi наблизити поняття процедури, яке використовується в програмуваннi, до поняття математичної функцiї. Пiд чистою функцiєю розумiють таку процедуру, яка має одне результуюче значення, при цьому це значення залежить лише вiд вхiдних значень процедури та не залежить вiд оточення, в якому виконується програма, наприклад вiд часу, дати, розташування вихiдного файлу тощо. Це дозволяє застосувати принцип iнкрементальних обчислень, оскiльки результат обчислення чистої функцiї для однакових вхiдних даних буде однаковим за визначенням. При адаптацiї даної моделi до обчислювальних систем з локальною пам’яттю слiд урахувати вищеназвану властивiсть, оскiльки передача певного обсягу даних в локальну пам’ять iншого вузла може вимагати бiльше часу анiж повторне обчислення таких самих даних, а дана властивiсть гарантує, що обчислення призведуть до однакових результатiв незалежно вiд обчислювального вузла, на якому вони виконується.