Підвищення ефективності кластерних обчислювальних систем на основі аналітичних моделей

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Вступ

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

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

У зв'язку з великою кількістю створюваних паралельних ОС, роботи в цьому напрямі вимагають подальшого розвитку, не втрачають своєї актуальності. Великий внесок в рішення проблем створення нових багатопроцесорних архітектурних реалізацій і оцінки їх ефективності внесли Лебедєв С.А., Глушков В.М., Капитонова Ю.В., Самофалов К.Г., Забродін А.В., Бурцев В.С., Малиновський В.В., Боюн В.П., Митрофанов Ю.І., Бошарин Г.П., Коган Я.О., Сааті Т., Менаске Д. і Алмейда В., Кемені Дж., Снелл Дж. і ін.

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

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

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

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

Задачі дослідження:

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

- розробка марківських моделей функціонування сучасних кластерних систем з урахуванням особливостей їх структури і класу вирішуваних на них задач;

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

1. Сучасний стан проблеми аналізу і оптимізації кластерних систем

Приведена класифікація структур кластерних систем і методів, що дозволяють досліджувати ефективність цих систем.

На основі огляду відомих робіт зроблені висновки про стан проблеми в досліджуваній області, обґрунтований прийнятий напрям розробок, сформульована мета і задачі досліджень.

2. Аналіз ефективності кластерних систем з використанням дискретних моделей Маркова

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

Тривалості часу обслуговування заявок на керуючому вузлі, сервері додатків і дисковому масиві, відповідно, мають геометричний розподіл з середнім, рівним Ti (). Тоді qi - ймовірність завершення в черговий такт обслуговування задачі на керуючому вузлі, сервері додатків і дисковому масиві, відповідно (), ri=1-qi. Вектор визначає кількість пристроїв в кожному вузлі ОС.

Стан системи - розміщення М заявок по трьох вузлах , де - кількість задач в -ому вузлі (). Число станів системи для однієї і тієї ж кількості задач j= дорівнює числу розміщень j задач по N вузлах, тобто . Загальна кількість станів моделі обчислюється як: .

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

,

де:

,

,

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

Вектор стаціонарної ймовірності станів визначаємо як рішення системи лінійних рівнянь (СЛАУ) .

Для тимчасової трудомісткості послідовного алгоритму побудови дискретної марківської моделі однорідного кластера отримана оцінка:

 (1)

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

З (1) видно, що послідовний алгоритм має комбінаторну складність, тому пропонується паралельний алгоритм розрахунку характеристик функціонування кластерної системи на решітках процесорних елементів (ПЕ) типу двовимірної решітки-тора.

При рішенні на решітках процесорів p=nxn кожний з них може виконати розрахунок одного або декількох елементів матриці перехідної ймовірності. СЛАУ (для розрахунку стаціонарної ймовірності) розв'язується блоковим методом Фокса.

Отримана тимчасова трудомісткість паралельного алгоритму побудови моделі Маркова однорідного кластера:

(2)

яка показує, що кількість операцій у порівнянні з (1) зменшується на кількість процесорів, що дозволяє розраховувати складніші моделі.

Трудомісткості послідовного і паралельного алгоритмів побудови дискретної марківської моделі кластера рівні, відповідно:

Ефективність паралельного алгоритму розрахунку моделі Маркова на решітках процесорів залежно від кількості вирішуваних задач М, пристроїв і процесорів не змінюється і рівна 0.99 при М>20. Пояснюється це тим, що основний об'єм обчислень займає розрахунок матриці ймовірності переходів, який не вимагає міжпроцесорних обмінів.

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

Для , К=2, М=20 завантаження змінюється від 0.3 до 0.92. Похибка тимчасових характеристик і середньої кількості задач в черзі складає 30% при завантаженні, рівному 0.9. При (завантаження не перевищує 0.4) похибка менше 5%.

Отримані результати моделювання за допомогою дискретної і безперервної моделей дозволяють зробити висновки: характеристики, одержувані обома моделями ідентичні у випадках, якщо всі обчислювальні вузли (модулі) містять один пристрій. Якщо кількість обчислювальних модулів у вузлах більш одного, характеристики дискретної і безперервної моделей співпадають, якщо кількість оброблюваних задач в обчислювальному середовищі менш кількості пристроїв у вузлі кластера. У випадку, якщо завантаження вузлів невеликі, тобто , тимчасові характеристики дискретної і безперервної моделей розходяться не більш, ніж на 5%. В цьому випадку ефективно для дослідження ОС використовувати безперервні моделі, оскільки вони менш трудомісткі. У випадку, якщо завантаження пристроїв більше 0.4 і менше 0.9, похибка тимчасових характеристик складає 30%. В цих випадках доцільно використовувати дискретні марківські моделі, оскільки вони точніше відображають роботу ОС, проте можна використовувати і безперервні моделі, якщо припустима похибка або треба отримати характеристики, обумовлені завантаженням.

3. Методи оцінки ефективності кластерних систем з використанням сіткових моделей

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

Неоднорідний кластер обробляє М заявок користувачів і складається з керуючого серверу, N1 серверів, що виконують різні додатки, N2 дисків.

Кожний з М призначених для користувача запитів з ймовірністю pN1+2,i звертається до i-го серверу, який, у свою чергу, обробляючи цей запит звертаються до одного з N2 дисків з ймовірністю pi, N1+1.

Функціонування даної обчислювальної системи представлено замкнутою стохастичною мережею, яка містить N1+2 системи масового обслуговування, в якій циркулює М заявок. Граф передач на якому введені наступні позначення: SN1+2 - СМО, відповідна головному серверу, S1,...,SN1 - СМО, відповідні серверам; SN1+1 - СМО, відповідна дисковим просторам.

Вектор визначає кількість пристроїв в кожній СМО (kN1+2=1, kN1+1=N2).

Стан системи визначається наступним розміщенням заявок за всіма СМО =(mN1+2,m1,...,mN1,mN1+1), де mN1+2+m1+...+mN1+mN1+1=M. Вирішуючи СЛАР:

,

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

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

Кластер топології NxN з сумісним використовуванням дискового простору містить керуючий сервер, N1 серверів, що виконують різні додатки, N2 диска. Відмінність від попереднього кластера полягає в тому, що дисковий простір неоднорідний.

Функціонування даної системи представлено замкнутою стохастичною мережею, містить N1+N2+1 СМО. Граф передач цієї мережі зображений на рис.9, на якому наступні позначення: SN1+N1+1 - СМО, відповідна керуючому серверу, S1,...,SN1 - СМО, відповідні серверам; SN1+1,...,SN1+N2 - СМО, відповідні дисковим просторам.

Кожна з М задач з ймовірністю pN1+N2+1,i () посилає запит до i-го серверу, який, у свою чергу, оброблюючи цей запит звертаються до j-го диска з ймовірністю pi,N1+j (,).

Стан системи визначений розподілом заявок за всіма СМО =(mN1+N2+1, m1,..., mN1,mN1+1,mN1+N2), де mN1+N2+1+m1+...+mN1+mN1+1.+mN1+N2=M.

За графом передач складається СЛЗР для визначення коефіцієнтів відвідин і обчислюється стаціонарна ймовірність станів моделі.

Кластер проаналізований при виконанні на ньому різних класів задач (щодо кількості звернень до дисків кожного серверу і керуючого серверу до серверів-додатків).

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

Аналогічно будується модель без ресурсів, що розділяються (сервери не мають ніяких загальних ресурсів, а у кожного процесора в кластері своя власна пам'ять і своя власна копія мережної ОС). В ній М призначених для користувача запитів, N1 серверів, виконуючи різні функції, кожний з яких має свій дисковий простір (всього N1 дисків).

Функціонування даної системи представлено стохастичною мережею, яка містить N1+N1+1 системи масового обслуговування, в якій циркулює М заявок.

Для графа передач цієї мережі введені наступні позначення: SN1+N1+1 - СМО, відповідна керуючому серверу, S1,...,SN1 - СМО, відповідні серверам; SN1+1,..,SN1+N1 - СМО, відповідні дисковим просторам.

Керуючий сервер з ймовірністю pN1+N1+1,i (i=1..N1) посилає запит до i-того серверу, який, у свою чергу, обробляючи цей запит звертається до свого диска з ймовірністю pi,j (i=1..N1, j=N1+1...N1+N2 ), а з ймовірністю pi,N1+N1+1 (i=1..N1) - повертаються на керуючий сервер.

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

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

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

(3)

де Т-термін експлуатації кластера, di-штраф за затримку на одиницю часу рішення задачі в i-й СМО, si-вартість i-ої СМО - інтенсивність обслуговування i-ої СМО.

Складові критерію -ціна простою устаткування (лівий доданок виразу (3)) і штраф за затримку виконання запиту (правий доданок виразу (3)).

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

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

2. Розраховуються основні характеристики обчислювальної системи: завантаження СМО, час відгуку, вартість, починаючи з М=1, 2 і т.д. Параметр М фіксується, якщо завантаження хоча б однієї із СМО досягне порогового значення. Звичайно “ідеальне завантаження” устаткування коливається від 0.6 до 0.9. Якщо завантаження менше цих величин, то експлуатація обчислювальної системи вважається неефективною, а якщо більше - ускладнюється система керування цим пристроєм.

3. Для значення М збільшується кількість устаткування (серверів або/і дисків) для СМО з граничним завантаженням. При цьому обчислюють значення критерію ефективності С (3). Те значення кількості устаткування, при якому С досягне мінімуму, вважається ефективним.

4. Методи оптимізації складу і структури паралельних обчислювальних систем

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

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

1. Вибирається початковий вектор продуктивності пристроїв (k=1,...,N+1) з обмеження за вартістю для задачі мінімального часу відгуку (вибирається (k=1,...,N+1) з умови обмеження за часом відгуку для задачі мінімальної вартості). Задаються початкові значення величини кроку по кожній координаті , часу відгуку Uopt=? для задачі мінімального часу відгуку заданої вартості (Sopt=? для задачі мінімальної вартості заданого часу відгуку), ознака визначення кращої крапки flag=0 (flag=1, якщо визначена краща крапка, flag=0, інакше).

2. Методом середніх вважаються основні характеристики: середні часи перебування у i-ій СМО, середнє число задач, що знаходяться в i-ій СМО, час відгуку задачі U(M).

3. Якщо U(M)< Uopt, для задачі мінімального часу відгуку заданої вартості (S(M)<Sopt, для задачі мінімальної вартості заданого часу відгуку), запам'ятовуємо новий вектор (k=1.,N+1), новий рекорд за часом відгуку Uopt=U(M), для задачі мінімального часу відгуку заданої вартості (новий рекорд по вартості Sopt= S(M), для задачі мінімальної вартості заданого часу відгуку), flag=1 (визначена краща крапка на даному кроці).

4. Якщо немає кращої крапки з кроком (flag=0), зменшуємо його ==/2.

5. Якщо > , переходимо до п.6, інакше, кінець алгоритму.

6. Будуємо новий вектор (k=1,...,N1) за умов обмеження з вартості задачі мінімального часу відгуку (будуємо (k=1.,N+1) з умови заданого часу відгуку для задачі мінімальної вартості). Переходимо до п.2.

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

Висновок

дискретний марківський однорідний кластер

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

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

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

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

Проведений порівняльний аналіз дискретної і безперервної марківських моделей, який показав, що результати обох моделей співпадають у разі мережі, що містить одноканальну СМО і у разі мережі з багатоканальною СМО при невеликих навантаженнях (). Якщо мережа містить багатоканальну СМО і завантаження більше 0.4 і менше 0.9 дискретні і безперервні моделі розходяться не більше ніж на 30% (залежно від кількості пристроїв у вузлі і від величини інтенсивності обслуговування і інтенсивності надходження).

Порівняльний аналіз результатів моделювання однорідного кластера з використанням дискретної і безперервної моделей Маркова показують розбіжність тимчасових характеристик до 30% при завантаженні пристроїв від 0.4 до 0.9. Однак безперервні моделі менш трудомісткі, тому їх доцільно використовувати для дослідження складніші структур при малих і середніх завантаженнях.

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

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

Запропонована методика оцінки ефективності кластера з використанням критерію збалансованості, яка дозволяє обрати оптимальну кількість устаткування мінімальної вартості.

Поставлена і вирішена аналітично задача оптимізації замкнених багатопроцесорних ОС (задача синтезу ОС з мінімальним часом відгуку заданої вартості і задача синтезу ОС мінімальної вартості із заданим часом відгуку) на прикладі системи клієнт-сервер.

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

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

Література

Фельдман Л.П., Михайлова Т.В. Методы оптимизации состава и структуры высокопроизводительных вычислительных систем // Научные труды Донецкого государственного технического университета. Серия: Информатика, кибернетика и вычислительная техника, выпуск 15: - Донецк: ДонГТУ, 2000. - С. 40-45

Фельдман Л.П., Михайлова Т.В. Способы оптимизации состава и структуры высокопроизводительных вычислительных систем. // Научные труды Донецкого государственного технического университета. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. - Севастополь: “Вебер”, 2001. - С. 80-85.

Фельдман Л.П., Михайлова Т.В. Оптимизация состава и структуры высокопроизводительных вычислительных систем с использованием метода средних // Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка, випуск 39: - Донецьк, ДонНТУ. - 2002. - С. 53-58.

Фельдман Л.П., Михайлова Т.В. Дискретная модель Маркова однородного кластера // Искусственный интеллект. - Донецк: ІПШІ МОН і НАН України “Наука і освіта”. №3.- 2006. - С. 79-91.

Михайлова Т.В. Оценка точности непрерывной и дискретной моделей Маркова // Научные труды Донецкого государственного технического университета. Серия “Информатика, кибернетика и вычислительная техника” (ИКВТ-2005), выпуск 93.- Донецк: ДонГТУ. - 2005.- C. 114-122

Труб И.И., Михайлова Т.В. Об одном алгоритме генерации разбиений натуральных чисел на слагаемые //Сборник трудов факультета вычислительной техники и информатики.- Донецк: ДонГТУ. - 1996.- C. 195-197.

Размещено на Allbest.ru