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

(3.6)

де Mi – обсяг пам’ятi, використаної в i-тому вузлi зi спiльною пам’яттю, Mi, l – обсяг пам’ятi, використаної в l-тому процесi, що виконується на i-тому вузлi, a Mi, 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 показники MΣ – сумарний обсяг пам’ятi, який було видiлено пiд час виконання обчислень; – середнiй обсяг пам’ятi, який було видiлено пiд час виконання обчислень; M* – пiковий обсяг пам’ятi, який одночасно було видiлено пiд час виконання обчислень. Для характеристики роботи системи пiдкачки даних в основну пам’ять також необхiдно аналiзувати кiлькiсть сторiнок пам’ятi, якi були збереженi поза основною пам’яттю та пiзнiше були завантаженi за запитом. Це типово характеризується кiлькiстю так званих кеш-промахiв (англ. cache miss), тобто кiлькiстю звернень до сторiнок пам’ятi, якi не були розмiщенi в основнiй пам’ятi на момент звернення. Пiд час такого промаху виконується очiкування пiдкачки даних в основну пам’ять, яке впливає на час очiкування tw, swap. Позначимо загальну кiлькiсть кеш-промахiв C, та кiлькiсть кеш-промахiв за одиницю часу .

Ряд характеристик варто також розглядати не лише для обчислювальної системи в цiлому, а також для кожного процесу окремо. До таких характеристик вiдносяться час очiкування введення та виведення в j-тому процесi, час очiкування пiдкачки даних в j-тому процесi, а також час виконання введення та виведення та час безпосередньо обчислення в кожному процесi. Це також дозволяє розглядати ряд статистичних значень, якi загалом характеризують процес виконання обчислень, таких як середнi за процесами значення часу очiкування введення та виведення часу очiкування пiдкачки даних або максимальнi значення цих характеристик . Першi впливають на загальний час виконання обчислень в цiлому, в той час як останнi вiдiграють роль обмежуючого фактора [112].

Розглянутi вище характеристики мають опосередкований вплив на результуючий коефiцiєнт ефективностi, шляхи цього впливу показанi на рис. 3.1. Тобто обсяг використаної в кожному вузлi пам’ятi Mi впливає на кiлькiсть кеш-промахiв C, однак не є єдиним фактором, що її визначає. Кiлькiсть кеш-промахiв впливає на час очiкування пiдкачки даних , який в свою чергу впливає на загальний час виконання обчислень. З iншого боку, час очiкування введення та виведення безпосередньо впливає на загальний час виконання обчислень. На рис. 3.1 рамкою видiленi двi характеристики, Mi та , якi можна змiнювати при рiзних пiдходах до органiзацiї пересилання даних.

Однак, данi характеристики також впливають одна на одну, що вiдмiчено пунктирною лiнiєю на рис. 3.1. Так, зменшення часу очiкування передачi даних, тобто введення та виведення, може бути досягнуте завдяки буферизацiї k-го блоку даних на вузлi j, в якому будуть виконуватись обчислення, перед тим, як вони будуть запитанi

однак це призведе до збiльшення обсягiв використаної пам’ятi

.

Рис. 3.1. Вплив динамiчних характеристик на коефiцiєнт ефективностi

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

(3.7)

В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.3. Вiдкладення передачi даних

Для виконання оптимiзацiї вiдповiдно до (3.7) пропонується вiдкладати початок передачi даних на певний промiжок часу, тобто ≥ . Як розглянуто у роздiлi 3.1., (а), це доцiльно лише за умови що данi пiдготовленi ранiше нiж запитане перше звернення до них < . [65] Зокрема, можна вiдкласти передачу даних до такого моменту часу, у який звiльниться якнайменш mk пам’ятi на вузлi j, за умови якщо зберiгання цього обсягу на вузлi i не матиме негативного впливу на ефективнiсть. Пропонується не вiдкладати передачу даних, якщо її зберiгання на вузлi i має негативний вплив на ефективність:

(3.8)

Вибiр моменту часу, у який буде розпочата передача даних, має бути виконаний з цiллю оптимiзацiї виразiв (3.7) за умови виконання (3.8). Оскiльки на час прийняття рiшення t ≤ в динамiцi вiдомi лише оцiненi значення та (реальнi значення можуть вiдрiзнятися через вплив багатьох факторiв та будуть вiдомi лише пiсля завершення передачi даних та початку обчислень над k-тим блоком даних, тому їх використання неможливе), необхiдно запропонувати евристичнi пiдходи до визначення моменту початку передачi даних. [113-116]

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

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

У момент часу = починається передача блоку даних (1) даних, яка триває , пiсля чого у вузлi 2 можуть бути розпочатi обчислення. Одночасно з цим може виконуватись передача блоку даних (2) = + . У певний момент часу

(3.9)

закiнчуються обчислення над блоком даних (1), якi призвели до рiшення, що виконувати обчислення над блоком даних (2) не потрiбно (наприклад, результат вже достатньо точний). Тому наступними на вузлi 2 будуть виконанi обчислення з блоком даних (3). Однак, вони ще не переданi на цей вузол i не можуть бути переданi, оскiльки виконується передача блоку даних (2). Лише пiсля закiнчення його передачi можна буде розпочати передачу блоку даних (3) = + + . Таким чином, час очiкування введення та виведення у вузлi 2 складатиме .