Ульяновський Державний Університет

2000

Записка по курсовій роботі

"Менеджер управління розподіленими обчисленнями в локальній мережі"

Виконав: студент групи ПМ -52

Никифоров Ю.В.

Викладач: Дулов Е.В.

2000

1. Модель середовища паралельного програмування

Як фізичної архітектури паралельного комп'ютера використовуєтьсялокальна мережа LAN Ethernet. Таким чином, паралельний комп'ютер складаєтьсяз деякої кількості процесорів P, з'єднаних між собою лінієюпередачі даних.

У моделі паралельного програмування використовуються дві абстракції:завдання (task) і канал (channel).

Дана модель характеризується такими властивостями:
1. Паралельне обчислення складається з одного або більше одночасно виконуються завдань (процесів), число яких може змінюватися протягом часу виконання програми.
2. Завдання - це послідовна програма з локальними даними. Завдання має вхідні і вихідні порти, які служать інтерфейсом до середовища процесу.
3. На додаток до звичайних операцій завдання може виконувати наступні дії: послати повідомлення через вихідний порт, одержати повідомлення з вхідного порту, створити новий процес і завершити процес.
4. Посилає операція асинхронна - вона завершується відразу, не очікуючи того, коли дані будуть отримані. Одержує операція синхронна: вона блокує процес до моменту надходження повідомлення.
5. Пари з вхідного і вихідного портів з'єднуються чергами повідомлень, що називаються каналами. Канали можна створювати і видаляти. Посилання на канали

(порти) можна включати в повідомлення, так що зв'язність може змінитися динамічно.
6. Процеси можна розподіляти за фізичними процесорам довільним способами, причому використовуване відображення (розподіл) не впливає на семантику програми. Зокрема, безліч процесів можна відобразити на одиночний процесор.

2. Тимчасові характеристики паралельної програми

Час виконання програми - час, що минув з моменту запуску першогопроцесора до моменту завершення виконання останнього (одержаннярезультату).

T = f (N, P, U, ...)

де N - розмірність задачі, P - кількість процесорів, U - кількістьзавдань паралельного алгоритму.

Під час виконання кожен процесор може перебувати у трьохстанах: обчислення (computation), обмін даними (communication) іочікування (idle). Відповідно, визначається час перебування процесора вкожному з них:
Отже, час виконання T може бути визначено таким чином:

або

Час обчислення алгоритму Tcomp може бути рівним часу виконаннявідповідного НЕ распараллеленного (послідовного) алгоритму ізалежить від розмірності N завдання. Якщо паралельний алгоритм вноситьдодаткові обчислення, тоді час обчислення залежить також і відкількості завдань U і процесорів P.

Час обміну даними алгоритму Tcomm цей час, витрачений на прийом іпередачу даних між завданнями. Існують два види обміну даними: міжпроцесорами і всередині процесора. Перший тип обміну здійснюється міжзавданнями що знаходяться на різних процесорах, тобто по каналу зв'язку. Другийтип обміну відбувається, якщо взаємодіючі завдання знаходяться на одномупроцесорі, тому в даному випадку обмін здійснюється набагато швидше,ніж у першому, і за експериментальними даними цим часом можна знехтувати.

Час передачі пакету даних між процесорами можна представити у виглядінаступного виразу:

де ts - час ініціалізації передачі, tw - час передачі одиниці (слова)даних. Таким чином, в ідеалі маємо лінійну залежність часу передачівід довжини даних.
Але в мережі типу Ethernet для обміну даними для всіх процесоріввикористовується єдиний канал зв'язку. Якщо два процесори хочуть передатидані в один і той же час, реально буде передавати тільки один з них, адругий буде чекати закінчення передачі першого. Тобто має місцерозділення каналу зв'язку в часі. Якщо S - кількість конкуруючихпроцесорів потребують передачі даних, то попередня формула змінитьсянаступним чином:

Таким чином, реальна пропускна здатність каналу дорівнює S-1.

Час очікування (простою) алгоритму Tidle. Процесор може простоювати водному з двох випадків:
. за відсутності завантажених на нього завдань;
. за відсутності вхідних даних задачі.

У другому випадку позбудеться від простоювання можна таким чином. Колизадача блокується в очікуванні вхідних даних можна на даному процесорізапустити іншу задачу, для якої є вхідні дані. Як тільки дляперше завдання надійдуть дані припинити виконання другої. Даний методвиправданий тільки при низькій вартості перемикання завдань. Також можнапідключати різні канали для однієї і тієї ж задачі при низькій вартостіданої операції.

Більш зручною мірою якості паралельної програми, ніж час виконання,є ефективність. Вона характеризує повноту використання алгоритмомресурсів паралельного обчислювального середовища незалежно від розмірності самоїзавдання. Відносна ефективність визначається як:

де T1 - час виконання на одному процесорі, Tp - час виконання на Pпроцесорах.
Відносне прискорення:

- це коефіцієнт зменшення часу виконання на P процесорах.

3. Методи вимірювання часових характеристик в реальному часі

Є три види методів збору інформації про продуктивність паралельноїпрограми:

. робочий профіль програми (execution profile) являє собою загальний час, проведений у різних ділянках програми;
. лічильники подій або сукупного часу;
. трасування подій.

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

Лічильник представляє собою змінну, яка може бути збільшена коженраз при настанні певної події. Лічильник може використовуватися дляпідрахунку кількості викликів цієї процедури, загальної кількості переданихабо прийнятих повідомлень, загального розміру переданих або отриманих даних длякожного процесора, завдання або каналу. Деякі лічильники вбудовані вбібліотеки середовища паралельного програмування, і можна заводить новішляхом вставки певних дзвінків бібліотеки у вихідний код завдань.
Інший варіант лічильника - інтервальний таймер. Він може використовуватися дляточного вимірювання часу виконання певних ділянок коду програми
(завдання). Тому за допомогою таймера можна вимірювати такий критичний ресурспроцесора як продуктивність.
Інформація, накопичена лічильниками, може використовуватися в робочих профіляхпрограми.

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

4. Реалізація

Метрики. Вимірювані параметри продуктивності програми будемо називатиметриками, по суті, вони ті ж лічильники. Кожна метрика являє собоюціле беззнакові 32-бітне число або unsigned long. Для кожного каналу,завдання і процесора є стандартний внутрішній набір метрик, якийобчислюється автоматично або за участю програміста завдань. Також єдодатковий масив комірок для нестандартних метрик, розмір його обмежений.
Посилання на клітинки здійснюється шляхом зазначення номера осередку, аналогічномасивів, починаючи з нуля.

Для обчислення метрик використовуються три абстракції:
. точки контролю - це місця виконання функцій збору даних про продуктивність (вхід/вихід процедури та ін);
. примітиви - функції зміни значень метрик, запуску/зупинки таймерів;
. предикати - умови виклику примітивів, засновані на метриках або локальних даних завдання.

Примітиви:
. установка лічильника тепер значення (setCounter);
. збільшення лічильника на задану величину (addCounter);
. зменшення лічильника на задану величину (subCounter);
. установка таймера на даний лічильник (setTimer);
. запуск таймера (startTimer);
. останов таймера (stopTimer).

Приклад: скільки часу ця функція проводить, посилаючи повідомлення?

void foo ()

(add (fooFlag);// fooFlag є ознакою входу у функцію

. . .

sub (fooFlag);

)

sendMessage ()

(if (fooFlag) startTimer ();

. . .

if (fooFlag) stopTimer ();

)

Ресурси - все, що цікавлять нас об'єкти паралельної системи (процесори,канали, завдання). Ресурси впорядковані в деяку кількість ієрархій. Укожній ієрархії представлені об'єкти певного типу. На нижньому рівніієрархії знаходяться конкретні об'єкти даного типу, що існують на даниймомент в системі. На наступному вищому рівні вони збираються запевною ознакою, наприклад в об'єкти, що їх містять.
Приклад ієрархії каналів показаний на малюнку.
Ієрархії ресурсів дозволяють визначити деталізацію інформації, що збирається пропродуктивності. Кожен більш високий рівень базується на інформаціїщо надається більш низьким рівнем. У прикладі з ієрархією каналів, нанайнижчому рівні обчислюються метрики конкретних каналів. На рівніпроцесорів обчислюються загальні метрики, такі як усереднені або сумарнізначення метрик всіх каналів на конкретному процесорі. На найвищомурівні - всієї системи - обчислюються загальні метрики для всіх каналів усистемі.

Крім ієрархії каналів визначені ієрархії ресурсів процесорів і завдань.

Ієрархічна організація інформації використовується при аналізі характеристикі продуктивності паралельних програм у реальному часі.

Для збору інформації використовується метод семплювання (від англійськогоsampling), тобто періодичного зчитування поточних даних. Надходженнячергового набору даних назвемо зразків (sample).

Кольцо службових каналів. Збір інформації про поточну продуктивностіпроводиться головним процесором (або завданням), званої диспетчером абоменеджером. Для цього використовуються службові канали, які рівноціннівизначеним раніше каналах. З можливих структур мережі службових каналів,два з яких показані на малюнку, обрано "кільце".

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

Доцільність використання кільця службових каналів (у порівнянні з
"Віником"):
1. Невелика загальна кількість односторонніх каналів (N +1 замість 2N);
2. Як наслідок, розвантаження каналу обміну диспетчера (навантаження розподіляється між усіма процесорами системи);
3. Більш низькі вимоги до продуктивності диспетчера (є час на обробку інформації між сусідніми семплами);
4. Простота контролю завантаженості каналу семплювання (поряд зі стандартними метриками каналів введені лічильники посланих і прийнятих запитів за допомогою диспетчера, в заголовок запиту включено полі - час відправлення, за яким при поверненні запиту визначається час його здійснення);
5. Контроль потоку службової інформації (легко регулюється періодичність запитів);
6. Простота збору даних.

У кожному запиті вказується об'єкт певної ієрархії і запитуванаметрика:
. вид ресурсів;
. рівень ієрархії;
. номер об'єкта на даному рівні ієрархії;
. код запитуваної метрики для даного об'єкта.

Структура одержуваної інформації однозначно визначається типом об'єктівзазначених у запиті.
Можливо отримання інформації відразу по всіх об'єктах і/або всім метрика --за умов згадування спеціальних значень останніх двох полів. В даному випадку ввідповідь на запит повертається масив однотипних структур.

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

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

Для процесора обчислюються, наприклад, наступні параметри: завантаженість,кількість пам'яті, час простою та ін
Для завдань обчислюються загальний час обчислення, час обміну даними та ін
Для каналів: лічильники входів до процедури обміну send/recv, обсягпереданих/прийнятих даних, середній час перебування в режиміприйому/передачі та ін

5. Контроль продуктивності.

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

Накопичена диспетчером інформація - робочий профіль - може використовуватисядля аналізу виконання паралельної програми. Далі описаний зразковийсценарій аналізу.

Нехай задано питання: чи працює програма ефективно.
Гіпотеза H0: програма працює ефективно.
Гіпотеза H1: програма працює неефективно.

Перевірку гіпотез виробляємо з таких міркувань. Виділимо основні типинеефективної роботи паралельної програми, одна з них:

. велика частка часу простою завдань від загального часу роботи.

Спрощено це виражається наступним виразом:

Можна взяти критерій: Eп <0,8.
Отже, якщо час простою займає більше 20 відсотків загального часу роботипрограми, то є підстави вважати роботу програми неефективною.

Підтвердивши дану гіпотезу - першого рівня, - переходимо до аналізу гіпотездругого рівня. Припустимо, в програмі є «вузьке місце» у планіобміну даних. Розглянемо ділянку графа потоків даних програми,показаний на малюнку.
Взаємодіють два завдання через канал. Завдання T1 генерує дані, вонипередаються по каналу, який є вихідним для T1, а завдання T2 приймає їхна свій вхідний порт і обробляє.
Існує два типи «вузьких місць»:

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

a) завантаженість T2 висока (> 90%), завантаженість T1 низька (<50%), b) кількість згенерованих L1 і оброблених L2 даних перебувають у відношенні L1 - L2> d> 0 , c) довжина черги даних вхідного каналу для T2 велика.

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

a) завантаженість T1 висока (> 90%), завантаженість T2 низька (<50%), b) довжина черги даних вхідного каналу для T2 мала.

В даному випадку можна висунути два відповідні гіпотези. Їх перевіркуможна здійснити з таких міркувань.

Розглянемо метрику каналу зв'язку процесорів - середній час обміну. Дляперше завдання це функція send, для другої - recv.
Нехай процес зміни цих метрик в часі виглядають приблизно так, якпоказано на малюнку.

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

Висновок

Описана система паралельного програмування є основою длястворення програм візуалізації, аналізу продуктивності, оптимальногоначального розподілу завдань, динамічної оптимізації виконанняпаралельних програм.
Програми візуалізації та аналізу продуктивності можуть використовуватисядля вивчення паралельних алгоритмів, як таких.
У майбутньому, закінчена система може використовуватися для здійсненняпрактичних обчислювальних задач великої складності та оперують великимиоб'ємами даних.
Перевага цієї системи полягає в тому, що вона не вимагає застосуванняпотужних комп'ютерних систем, замість цього вона повноцінно використовує ресурсибудь-яких локальних мереж на базі ОС Windows 95.

Література:

1. Сервер ВЦ РАН http://www.ccas.ru/paral/
2. Ian Foster, "Designing and Building Parallel Programs", 1995
3. Barton P. Miller and others, "The Paradyn Parallel Performance

Measurement Tools" Computer Sciences Department, University of Wisconsin-

Madison. http://www.cs.wisc.edu/paradyn/
4. Бертекас, Галлагер, "Мережі передачі даних", 1989.

-----------------------< br>