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

Оцiнка часу запиту k-го блоку даних береться як сума випадкових значення з нормальним розподiлом (μ,σ) для всiх пiдзадач, що мають бути виконанi j-тим вузлом. Аналогiчним чином визначається нормальний розподiл для оцiненого часу передачi даних (μ,σ), за яким вибирається оцiнка часу передачi даних . Пiсля чого час затримки початку передачi даних визначається як

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

Спосiб 4.2 Виконувати передачу в серединi промiжку [,], тобто

При цьому оцінка часу, у який відбудеться запит на використання даних виконується з використанням нормального розподілу аналогічно до попереднього способу.

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

Для бiльш точних оцiнок часу майбутнього запиту на використання даних та часу передачi даних мiж вузлами, iснує можливiсть в рамках даного пiдходу використати рiзнi ймовiрнiснi моделi, зокрема графовi. Крiм того, для визначення параметрiв цих моделей можна застосувати широко вивченi на даний момент методи машинного навчання [108,109].

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

3.5. Пакетна системи виконання задач

Формулювання задачi

Будемо розглядати паралельне обчислення деякого набору B задач (послiдовних чи паралельних), на гетерогеннiй розподiленiй системi, що мiстить S вузлiв. Гетерогеннiсть системи може полягати у рiзнiй продуктивностi вузлiв системи, рiзнiй пропускнiй здатностi мережевих зв’язкiв та рiзних апаратних та програмних можливостях конкретних вузлiв. Мережа мiж ними органiзована таким чином, що кожен вузол такої розподiленої системи може обмiнюватися даними з деяким центральним вузлом, але не обов’язково з усiма вузлами в системi. Вузли такої системи у загальному випадку не обмiнюються даними в процесi виконання певної однiєї задачi.

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

Кожен вузол такої системи є у загальному випадку гетерогенною обчислювальною системою з локальною пам’яттю, що мiстить K вузлiв та N процесорiв. Один вузол може мiстити вiд 1 до (N – K + 1) процесорiв. Гетерогеннiсть системи може полягати в рiзнiй продуктивностi обчислювальних вузлiв або у рiзнiй пропускнiй здатностi мережевих зв’язкiв мiж ними, при чому мережа органiзована таким чином, щоб забезпечити можливiсть зв’язку мiж будь-якою парою вузлiв.

Згiдно з деталiзованою структурою пакету, (рис. 3.6), позначимо:

Dinp, i – вхiднi данi для i-го конвеєра.

D out, i – вихiднi данi i-го конвеєра.

D j, i – промiжнi данi, отриманi пiсля виконання j-ї задачi i-го конвеєра.

D j, shrd – спiльнi данi для j-го ярусу усiх конвеєрiв.

T j, i – задача, що виконується на j-тому ярусi i-того конвеєра.

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

Конвеєри, що розташовуються у черзi можуть працювати у двох режимах:

– Конвеєри виконуються послiдовно t0,0 → tj,0…t0,m → tj,m, де m ∈ – кiлькiсть конвеєрiв, що виконується на одному процесорi.

– Конвеєри виконуються паралельно t0,0… t0,m → tj,0… tj,m.

Рис. 3.6. Деталiзована структура пакету

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

а) Пересилання вхiдних даних задачi з деякого зовнiшнього сховища до вузла розподiленої системи та передача вихiдних даних з вузла розподiленої системи до деякого зовнiшнього сховища. Позначимо Dbatch_input, nodei обсяг вхiдних даних, який передається до кожного вузла розподiленої системи, де nodei ∈ — номер вузла розподiленої системи. Причому, Dbatch_input, nodei = , де i – кiлькiсть конвеєрiв у пакетi, а j – довжина конвеєра. Зi структури на рис. 3.6 видно, що для початку обчислення пакету необхiдний i достатнiй набiр даних Dminimum_input,nodei =, де Kmin – це деяка кiлькiсть завантажених процесорiв, при якiй ми вважаємо що доцiльно починати виконувати пакет. Позначимо момент часу, коли в вузол розподiленої системи переданий набiр даних , де q ∈ – номер пакету. Також позначимо момент часу, коли в вузол розподiленої системи переданий набiр даних , де q ∈ – номер пакету.

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

– Якщо iснує семантичний зв’язок Ds, p → Ds+1,shrd, або ts, p → Ds+1,shrd, то необхiдно забезпечити когерентнiсть спiльних даних Ds+1,shrd, де s ∈  – рiвень конвеєра, задача на якому була обчислена, p ∈ – номер вузла. Позначимо час готовностi s-го блоку даних в p-тому вузлi, необхiдних для обчислення в певному iншому q-тому вузлi, такому що p≠q.

–  Якщо з якихось причин, виконання пакету було призупинено i вiдновлено через деякий перiод часу на iншому наборi вузлiв, або один з вузлiв звiльнився i хоча б один iз вузлiв, що виконують даний пакет, мають бiльше нiж один конвеєр у черзi, то необхiдна процедура мiграцiї конвеєра на новий вузол. Позначимо Mq обсяг пам’ятi, що використано в q-тому вузлi, де q ∈ , причому Ds–1,p ≤ Mq ≤ Ds–1,p + , де s ∈  — наступний рiвень конвеєра, задача на якому буде обчислена наступною, p ∈ – номер вузла. Вiдмiтимо, що у загальному випадку, обсяг пам’ятi, що буде використано, може залежати вiд значень вхiдних даних та вiд результатiв обчислень на попереднiх кроках, тому його необхiдно враховувати динамiчно, тобто в процесi виконання обчислень.

Тодi необхiдно визначити моменти часу призупинення та вiдновлення роботи задачi q ∈, а також стратегiю функцiонування черги для пакетiв, такi що максимiзують ефективнiсть використання обчислювальної системи KE → max та мiнiмiзують обсяг даних, що передаються пiд час мiграцiї при вiдновленнi роботи пакету → min.