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

У якостi критерiю ефективностi використовується коефiцiєнт ефективностi KE, який визначається вiдношенням прискорення паралельної реалiзацiї обчислень у порiвняннi з послiдовною реалiзацiєю до кiлькостi процесорiв N. [1]

Розглянемо декiлька варiантiв cпiввiдношень , та :

а) < – усi вхiднi данi були переданi до початку обчислень. Обчислення проходять у звичному режимi. настане пiсля виконання усiх i конвеєрiв у момент .

б) ≤ <– частина даних, що є достатньою для початку обчислень була передана.

Позначимо час, коли буде обчислений l ∈ рiвень конвеєрiв, для яких прийшли вхiднi данi як.

Позначимо час, коли буде обчисленi конвеєри, для яких прийшли вхiднi данi як, де s ∈ – кiлькiсть конвеєрiв, для яких прийшли вхiднi данi.

Позначимо час, за який прийде Kmin наборiв вхiдних даних для конвеєрiв як .

Позначимо час, за який прийде Dl+1,shrd як Ttransf_shrd,l+1, де l – рiвень конвеєра, який обробляється у даний момент.

Тодi можна оцiнити за формулами:

(3.22)

Ця система ставить умову – обробка пакета може бути вiдкладеною, якщо час виконання конвеєрiв, для яких було прийнято вхiднi данi менший за час, який потрiбен для прийому вхiдних даних для Kmin конвеєрiв, за умови що залишилося обробити бiльше нiж Kmin конвеєрiв, або час прийому спiльних даних для l + 1 рiвня конвеєрiв бiльший нiж час обчислення l-го рiвня конвеєрiв.

в) >– вхiдних даних недостатньо для початку обчислень. У

цьому випадку ми вiдкладаємо обчислення до .

Для варiантiв 1 та 2 можуть виникати черги на процесорнi ресурси i потрiбно обирати полiтику очiкування.

Питання визначення оптимального маршруту для передачi даних мiж вузлами обчислювальної системи з точки зору швидкостi такої передачi вiдноситься до розв’язання задачi маршрутизацiї, для якої запропоновано ряд ефективних алгоритмiв. [100]

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

3.6. Динамiчна зм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)  Вертикальне роздiлення

Нехай маємо пакет Psource, який складається з i конвеєрiв по j задач у кожному. Позначимо tsplit момент часу, в який необхiдно здiйснити роздiлення, при чому в цей момент часу нi одна з задач пакету не виконується. Тодi стан пакету Psource у момент часу tsplit можна описати множиною

де lq – рiвень конвеєра, на якому знаходиться q-тий конвеєр.

Вертикальне роздiлення пакету Psource на два пакети Pdest, n та Pdest, i–n (рис. 3.7) – це перетворення, що описується системою

Таким чином, недолiком при вертикальному роздiленнi є необхiднiсть копiювання спiльних для конвеєрiв даних.

2)  Горизонтальне роздiлення

Нехай маємо пакет Psource, який складається з i конвеєрiв по j задач у кожному. Позначимо tsplit момент часу, в який необхiдно здiйснити роздiлення, при чому в цей момент часу нi одна з задач пакету не виконується. Тодi стан пакету Psource у момент часу tsplit можна описати множиною

де lq – рiвень конвеєра, на якому знаходиться q-тий конвеєр.

Рис. 3.7. Вертикальне роздiлення пакету

Горизонтальне роздiлення пакету Psource на два пакети Pdest, n та Pdest, j–n (рис. 3.8) – це перетворення, що описується системою

Рис. 3.8. Горизонтальне роздiлення пакету

Описанi способи роздiлення у рамках прийнятої структури пакетiв мають декiлька важливих практичних застосувань:

а) Вертикальне роздiлення пакетiв може бути використане як метод балансування навантаження у рамках алгоритмiв планування за запитом.

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

в) Горизонтальне роздiлення пакетiв дає можливiсть зупиняти виконання пакету за умови, що нi один конвеєр не знаходиться у процесi виконання задачi у момент зупинки.

3.7. Оцiнка швидкостi вводу-виводу

Оцiнка швидкостi вводу-виводу – це складна задача, яка потребує комплексного ряду факторiв, зв’язаних з мережевими каналами, дисковими системами, системами пiдкачки даних та iншими.

Загальна швидкiсть вводу-виводу обчислювальних систем з локальною пам’яттю Позначимо Psys, i/o пропускну здатнiсть мережевого каналу обчислювальної системи з локальною пам’яттю, через який вона отримує пакети на обробку та вхiднi данi. Ця величина є константою та визначається апаратними та програмними ресурсами обчислювальної системи.

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

Швидкiсть вводу-виводу для всiєї системи визначається як

Швидкiсть вводу-виводу для всiєї системи є iнтегральним показником утилiзацiї каналу вводу-виводу. Справедливо буде сказати, що для даної величини критерiй оптимiзацiї буде виглядати як

Якщо Vsys, i/o << Bsys, i/o – це означає, що мережевий канал не використовується з максимальною ефективнiстю. Причиною цього може бути як мала кiлькiсть пакетiв у системi або вiдносно малий об’єм вхiдних та вихiдних даних для них, так i неефективнiсть обробки пакетiв у системi, що призводить до малої кiлькостi активних пакетiв, що не дозволяє використовувати мережевий канал у повному обсязi.

Якщо Vsys, i/o > Bsys, i/o, то має мiсце перевантаження мережевого каналу, що призведе до зниження ефективностi обчислювальної системи за рахунок довгого простою обчислювальних ресурсiв в очiкуваннi вхiдних даних.

Швидкiсть вводу-виводу для окремого пакету Швидкiсть вводу-виводу для окремого пакету є ключовою метрикою, яку можна використовувати для корекцiї лiмiту часу виконання цього пакету в автоматичному режимi.

Будемо вiдрiзняти три складовi швидкостi вводу-виводу:

Vbatch_remote, i/o – середня швидкiсть вводу-виводу даних з дистанцiйного мережевого сховища.

Vbatch_storage, i/o – середня швидкiсть вводу-виводу з локального дискового сховища (включаючи сторiнки пам’ятi, що потрапили до файлу пiдкачки).