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

Vbatch_transfer, i/o – середня швидкiсть передачi даних мiж вузлами обчислювальної системи з локальною пам’яттю у разi

Нехай маємо пакет P. Позначимо Dreq – об’єм даних, який необхiдний для початку обробки пакету P.

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

Тодi

(3.23)

Оскiльки в сучасних високопродуктивних обчислювальних системах з локальною пам’яттю використовується швидкiснi мережi для зв’язку мiж вузлами (наприклад, Infiniband), то, з урахуванням малої зв’язностi задач в рамках прийнятої структури пакету, ми будемо вважати, що Vbatch_transfer, i/o >> Vbatch_storage, i/o. Таким чином цей параметр не буде значно впливати на ефективнiсть обчислювальної системи у рамках дослiджуваних характеристик.

Тодi рiвняння 2.9 можна записати як

(3.24)

C – деяка вiдносно мала константа, яку ми не будемо дослiджувати у рамках цiєї роботи.

Необхiдно також сформулювати методику обчислення середнiх значень швидкостi вводу-виводу. Будемо обчислювати середню швидкiсть вводу-виводу як вiдношення кiлькостi прийнятої iнформацiї до часу її передачi.

де D – кiлькiсть прийнятих або переданих даних, t – час, витрачений на ввод-вивiд даних.

В рамках цiєї метрики важливим є контекст вимiрювання середнiх швидкостей передачi даних:

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

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

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

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дходiв до обчислення необхiдних значень i стратегiй поведiнки при змiнi зернистостi.

Пiдхiд 1: без динамiчної змiни зернистостi. Цей пiдхiд пропонується для доведення сумiсностi динамiчної змiни зернистостi з iснуючими пiдходами до планування у пакетних системах. Вiн не передбачає змiну зернистостi як такої, тобто tpause = tcontinue. Реалiзацiя пiдходу без динамiчної змiни зернистостi може застосовуватись для перевiрки працездатностi програмної реалiзацiї та коректностi проведення обчислень. У цьому пiдходi рiшення про змiну зернистостi завжди має негативний результат.

Гiпотеза A. Застосування пiдходу без динамiчної змiни зернистостi знизить загальний коефiцiєнт ефективностi через наявнiсть додаткових розрахункiв, спрямованих на збiр статистики параметрiв вводу-виводу та обчислення критерiїв необхiдностi змiни зернистостi.

Пiдхiд 2: вертикальне роздiлення пакету в умовах недостатньої кiлькостi вузлiв. Цей пiдхiд спрямований на пiдвищення значення прiоритетiв при заповненнi промiжкiв у плануваннi.

Припустимо, що ми маємо систему з N процесорiв. Нехай на нiй виконується m задач, кожна з яких займає процесорiв у вiдповiдностi з запитами користувачiв, де q – номер пакета.

Таким чином, кiлькiсть вiльних процесорiв у системi:

Припустимо, що наступний пакет P у прiоритетнiй черзi потребує K процесорiв, де K > N. Тодi ми можемо здiйснити вертикальне роздiлення пакету P на два пакети PN та PK–N та розпочати виконання пакету PN, повернувши пакет
PK–N у прiоритетну чергу вiдповiдно до прiоритету пакету P.

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

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

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

Пiдхiд 3: горизонтальне роздiлення пакету для заповнення промiжкiв Нехай маємо два пакети P1 та P2, з прiоритетами R1 та R2 вiдповiдно, такими що R1 > R2, пакет P1 потребує K1 процеорних елементiв, пакет P2 потребує K2 процесорних елементiв, причому K2 ≤ K1. Також нехай було здiйснено оцiнку часу вводу-виводу для пакетiв P1 та P2 – та вiдповiдно.

Тодi, якщо

де texec – оцiнений лiмiт виконання пакету P2, i конвеєри P2 мають бiльше нiж один рiвень, то доцiльно виконати горизонтальне проздiлення пакету P2 на пакети P2,used та P2,delayed таким чином, щоб

де texec – оцiнений лiмiт виконання пакету P2, – час, який було витрачено на горизонтальне роздiлення пакету (включаючи час на прийняття рiшення). Пiсля цього доцiльно призупинити виконання пакету P1, зарезервувати процесорнi ресурси для нього на момент часу через та почати виконання пакету P2,used.

Пiдхiд 4: затримка запуску задачi з резервуванням на основi статистики вводу-виводу Цей пiдхiд спрямований на пiдвищення загальної системної ефективностi комп’ютерної системи з локальною пам’яттю.

Нехай маємо два пакети P1 та P2, з прiоритетами R1 та R2 вiдповiдно, такими що R1 > R2, пакет P1 потребує K1 процеорних елементiв, пакет P2 потребує K2 процесорних елементiв, причому K2 ≤ K1. Також нехай було здiйснено оцiнку часу вводу-виводу для пакетiв P1 та P2 – тавiдповiдно.

Тодi, якщо

де texec – оцiнений лiмiт виконання пакету P2, то доцiльно призупинити виконання пакету P1, зарезервувати процесорнi ресурси для нього на момент часу через та почати виконання пакету P2.

Гiпотеза D. Ефективнiсть затримки запуску буде залежати вiд точностi оцiнки лiмiту часу виконання пакета, що використовується для заповнення утвореного промiжку, а також вiд вiдношення . Максимальне завантаження обчислювальної системи буде досягнуто при → 0.