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

У випадку ж вiдкладення передачi даних (рис. 3.3) до моменту

(3.10)

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

Рис. 3.2. Передача даних, якi не будуть використанi через скасування обчислень

Рiзниця часу очiкування введення та виведення становитиме

з урахуванням (2.9 ) отримаємо

або

звідки за визначенням (3.10 )

(3.11)

Рис. 3.3. Вiдкладення передачi даних при можливостi скасування обчислень

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

(3.12)

що можна скоротити до

(3.13)

Пiдставляючи (3.11), (3.13) до визначення коефiцiєнту ефективностi (3.5), отримаємо

(3.14)

тобто вiдкладення передачi даних збiльшило коефiцiєнт ефективностi.

Iншою типовою ситуацiєю, в якiй вiдкладання передачi даних на певний час може зменшити час очiкування введення та виведення, є використання обчислювальної системи, в якiй пiдтримується балансування навантаження. Розглянемо виконання обчислень на системi з трьома вузлами з локальною пам’яттю, якi попарно зв’язанi мiж собою. Вузол 1 виконує обчислення з генерацiї блокiв даних (1) та (2) одночасно = , а на вузлi 2 мають виконуватись обчислення над цими блоками даних послiдовно (рис. 3.4). Передача блоку даних (1) починається вiдразу по його готовностi = , пiсля завершення якої розпочинається передача блоку даних (2) = + . В деякий момент часу tB, такий що

= (3.15)

в обчислювальнiй системi вiдбувається балансування навантаження, пiсля якого обчислення, з використанням блоку даних (2) переносяться до вузла 3. При цьому, блок даних (2) має бути переданий повторно. Час очiкування введення та виведення даних в цьому випадку складатиме

(3.16)

причому на вузлi 2 було використано пам’ять для тимчасового збереження блоку даних (2), який фактично не використовувався на ньому.

У випадку відкладання передачі даних до часу

(3.17)

(рис. 3.5), тобто балансування навантаження відбудеться до початку передачі даних, можна встановити, що виконувати передачу даних необхідно одразу до вузла (3). В цьому випадку, відсутня необхiднiсть передавати дані на промiжковий вузол (2), та час очікування введення та виведення даних становитиме

(3.18)

Рис. 3.4. Повторна передача даних через балансування навантаження

Рис. 3.5. Вiдкладення передачi даних при балансуваннi навантаження

Розрахуємо рiзницю часу очiкування введення та виведення без вiдкладення обчислень та з таким

що з урахуванням (3.15 ) може бути перетворене на нерiвнiсть

а оскiльки за умови негайної передачi даних = + 2, можемо спростити до

Тобто рiзниця в часi очiкування введення та виведення даних залежить вiд значення виразу , а саме вiд рiзницi часу, що необхiдний на передачу блоку даних (2) з вузла 1 до вузла 3 через промiжковий вузол 2 або напряму. Причому час передачi розглядається на програмному рiвнi, тобто не обов’язково залежить вiд наявностi та параметрiв фiзичних зв’язкiв мiж вузлами. Обчислювальна система намагатиметься обрати такий шлях та спосiб передачi даних, який би мiнiмiзував час виконання передачi [18], тому для бiльшостi випадкiв за умови застосування вiдомих стратегiй органiзацiї обчислювального процесу ≥ 0, звiдки випливає

(3.19)

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

3.4. П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в до визначення цих значень. [66]

Пiдхiд 1: без в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д 2: передача даних по запитам. Цей пiдхiд є прямо протилежним до пiдходу без вiдкладення передачi даних, так як передбачає початок передачi даних одразу п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потеза 3. Застосування пiдходу передачi даних по запитам не знижує час очiкування введення та виведення даних за вiдсутностi балансування навантаження у випадках, коли запит на використання даних вiдбувся пiзнiше нiж вони були готовi (в цьому разi можна розпочати передачу у такий момент часу, щоб вона завершилась ранiше запиту на використання).