ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИСТЕТ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД“
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ”
МИХАЙЛОВА ТЕТЯНА ВАСИЛІВНА
УДК 681.5:519.7
ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ КЛАСТЕРНИХ ОБЧИСЛЮВАЛЬНИХ
СИСТЕМ НА ОСНОВІ АНАЛІТИЧНИХ МОДЕЛЕЙ
05.13.13 - ОБЧИСЛЮВАЛЬНІ МАШИНИ, СИСТЕМИ ТА МЕРЕЖІ
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
ДОНЕЦЬК 2007
Дисертацією є рукопис
Робота виконана в Державному вищому навчальному закладі „Донецький національний технічний університет” Міністерства освіти і науки України
Науковий керівник: доктор технічних наук, професор
Фельдман Лев Петрович,
ДВНЗ „Донецький національний технічний університет”, професор кафедри прикладної математики і інформатики
Офіційні опоненти: доктор технічних наук, професор
Святний Володимир Андрійович, завідувач кафедри електроних обчислювальних машин, ДВНЗ „Донецький національний технічний університет”,
м. Донецьк
кандидат фізико-математичних наук, старший науковий співробітник
Горошко Іван Олегович,
інститут проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України, м. Київ
Провідна організація: Харківський національний університет радіоелектро-ніки Міністерства освіти і науки України, кафедра автоматизації проектування обчислювальної техніки, м. Харків
Захист відбудеться “22” березня 2007 р. о 14 годині на засіданні спеціалізованої вченої ради К.11.052.03 Донецького національного технічного університету за адресою:
83000, м. Донецьк, вул.Артема, 58, уч.корпус 8, ауд.704
З дисертацією можна ознайомитися в бібліотеці Донецького національного технічного університету за адресою:
83000, м. Донецьк, вул.Артема, 58, уч.корпус 2.
Автореферат розісланий “21” лютого 2007 р.
Вчений секретар
спеціалізованої вченої
ради Г.В.Мокрий
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Створення і застосування сучасних суперкомп'юте-рів стало в даний час одним з основних напрямів в провідних країнах світу. Стимулом розвитку паралельних обчислювальних систем було і залишається підвищення ефективності процесів рішення великих задач. Ефективність їх ви-користовування залежить від продуктивності процесорів, що входять до складу системи, пропускної спроможності її каналів зв'язку. Тому, розробка, всесторон-ній аналіз ефективності функціонування мультипроцесорних систем є однією з найважливіших робіт щодо розвитку паралельних обчислювальних технологій.
Об'єднання великої кількості комп'ютерів в єдиний обчислювальний комплекс породило такі задачі як збалансованість навантаження, виявлення вузьких місць в обчислювальній системі, забезпечення заданого часу відповіді при роботі великої кількості користувачів, вибір устаткування при максимальній продуктивності при обмеженій заданій вартості і інші.
У зв'язку з великою кількістю створюваних паралельних ОС, роботи в цьому напрямі вимагають подальшого розвитку, не втрачають своєї актуальності. Великий внесок в рішення проблем створення нових багатопроцесорних архітектурних реалізацій і оцінки їх ефективності внесли Лебедєв С.А., Глушков В.М., Капитонова Ю.В., Самофалов К.Г., Забродін А.В., Бурцев В.С., Малиновський В.В., Боюн В.П., Митрофанов Ю.І., Бошарин Г.П., Коган Я.О., Сааті Т., Менаске Д. і Алмейда В., Кемені Дж., Снелл Дж. і ін.
Однією з переваг різновиду MIMD – систем, кластерних систем, є побудо-ва високопродуктивного обчислювального комплексу заданої конфігурації. Для ефективності функціонування кластерної системи потрібна відповідність класу вирішуваних задач структурі, на якій проводять обчислення.
Розроблений апарат аналітичного моделювання обчислювальних структур не дозволяє проектувати сучасні паралельні структури зважаючи на велику розмірність поставлених задач, які на однопроцесорних ЕОМ не можуть бути ефективно реалізовані через недостатню кількість обчислювальних ресурсів.
Цим обумовлено, що дослідження, проведені в дисертаційній роботі, направлені на аналіз, підвищення ефективності, оптимізацію кластерних систем, відповідності класу вирішуваних задач архітектурі ОС за рахунок модифікації методів аналізу і синтезу ОС.
Зв'язок роботи з науковими програмами, планами, темами. Запро-поновані в роботі методи використовувалися в процесі виконання науково-дослідних робіт за держтемами, які включені до плану фундаментальних тем, затверджених МОН України: ГТ-14-97 “Наукові основи аналізу і оптимізації структур комп'ютерних систем і способів управління паралельним обчислю-вальним процесом”, Н-18-95 “Алгоритмічне і програмне забезпечення обчислю-вальних систем і інформаційних технологій”, ГТ-11-2000 “Наукові основи оптимізації структур високопродуктивних обчислювальних систем і методи реалізації паралельних алгоритмів”, Н-13-2000 “Алгоритмічне і програмне забезпечення високо-продуктивних і інтелектуальних обчислювальних систем і мереж”, Д-1-03 “Методи алгоритмізації, топологічного відображення і опти-мізації структур паралельних і розподілених обчислювальних систем”, Д-1-06 “Розробка алгоритмічних методів підвищення ефективності моделювання складних систем в паралельних обчислювальних середовищах” (діє з 2006р.).
Мета роботи полягає в розробці методів підвищення ефективності функціонування кластерних систем на основі використовування результатів аналітичних моделей з урахуванням відповідності класу вирішуваних задач вибраної топології кластера.
Задачі дослідження:
-розробка марківських моделей функціонування кластерних систем і удосконалення існуючих методів розрахунку основних характеристик функціонування кластерних систем, розробка паралельних алгоритмів їх реалізації для задач великої розмірності;
-розробка марківських моделей функціонування сучасних кластерних сис-тем з урахуванням особливостей їх структури і класу вирішуваних на них задач;
-узагальнення методів синтезу мультипроцесорних обчислювальних систем на основі використовування методу середніх, які дозволяють скоротити час розв`язання задачі оптимізації складу і структури високопродуктивних кластерних систем сучасної конфігурації.
Об'єктом дослідження є кластерні системи різної топології.
Предметом дослідження є аналітичні методи аналізу і синтезу високопродуктивних обчислювальних систем.
Методи досліджень. Рішення сформульованих в дисертаційній роботі задач базувалося на використовуванні методів теорії випадкових процесів, обчислювальної математики, теорії графів. Перевірка отриманих результатів здійснювалася шляхом проведення обчислювальних експериментів на ОС в системах імітаційного моделювання.
Наукова новизна отриманих результатів полягає в наступному:
-розроблено дискретну модель кластера з дисками, що розділяються, для оцінки ефективності його роботи, за допомогою якої можна отримати основні характеристики обчислювального середовища;
-запропоновано новий паралельний алгоритм реалізації дискретної марківської моделі однорідного кластера на решітках процесорів, отримані основні характеристики розпаралелювання;
-визначені межі використовування дискретної і безперервної марківської моделей однорідного кластера, що забезпечують необхідну достовірність результатів;
-запропоновано безперервні марківські моделі різних кластерних структур для отримання оцінки ефективності їх роботи при реалізації на них класів задач з різними характеристиками використовування ресурсів;
-запропоновано і обгрунтовано модифікований алгоритм рішення задачі синтезу кластерних структур для замкнутих систем з використанням методу середніх, який дозволяє оптимізувати обчислювальні структури, мережні моделі яких мають кількість станів, що перевищує майже на два порядки кількість станів моделей, досліджуваних класичними методами.
Обгрунтованість і достовірність наукових положень, висновків і рекомендацій. Обгрунтованість і достовірність результатів, отриманих у дисертації, підтверджується коректним застосуванням теорії випадкових процесів, чисельних методів, теорії ймовірностей.
Практичне застосування розроблених моделей обчислювальних кластерів підтверджує його достовірність.
Наукове значення роботи. За новизною наукових результатів робота має бути визначена як внесок в теорію та практику побудови кластерних систем, що інтенсивно розвиваються та застосовуються для надшвидких обчислень.
Практичне значення отриманих результатів полягає у використовуванні розроблених методів для аналізу і синтезу високопродуктивних обчислювальних систем з різними топологічними характеристиками. Отримані алгоритми можна використовувати для оцінки ефективності паралельних обчислювальних систем на стадії проектування, експлуатації і модернізації. В даний час розроблені методи і моделі використовуються в навчальному процесі кафедри прикладної математики і інформатики Донецького національного технічного університету при читанні курсу “Структури обчислювальних систем і паралельні обчислення”, кафедри технічної інформатики Донецького інституту штучного інтелекту при читанні курсу “Структури і моделі високопродуктивних обчислювальних систем”.
Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно та опубліковано у 19 наукових працях. Роботи [5,7,13,14] написано самостійно. В роботі [1] поставлена і вирішена задача синтезу ОС мінімальної вартості із заданим часом відповіді і задача синтезу ОС заданої вартості з мінімальним часом відповіді. В роботі [2] запропоновані модифіковані алгоритми рішення задачі синтезу, в роботі [3] використаний метод середніх для задачі оптимізації, дозволяючий вирішувати задачі на порядок більший, ніж інші наявні методи. В [4] запропонована дискретна марківська модель кластера із загальними дисковими носіями, в [11] отримані оцінки ефективності паралельної реалізації цієї моделі. В роботі [5] приведені оцінки точності дискретної і безперервної моделей Маркова, а також межі використовування цих моделей.
Апробація результатів дисертації. Основні положення і результати доповідалися, обговорювалися і отримали позитивну оцінку на наступних конференціях і семінарах:
-1 Всеросійська конференція “Науковий сервіс в Інтернет”, м. Новоросійськ, 23-27 вересня, 1999р.;
-V Міжнародна науково-практична конференція студентів, аспірантів та молодих вчених, 1–3 липня 2003 р., м. Київ, Україна;
-II Міжнародний науково-практичний семінар “Високопродуктивні паралельні обчислення на кластерних системах”, Нижній Новгород (Росія), 26-29 листопаду 2002 р.;
-Всеросійська науково-технічна конференція з міжнародною участю “Комп'ютерні технології в інженерній і управлінській діяльності”. м. Таганрог, Росія. 12–16 липня 2001 р.;
-Четвертий Міжнародний науково-практичний семінар і Всеросійська молодіжна школа “Високопродуктивні паралельні обчислення на кластерних системах” (НРС-2004), м. Самара, Росія, 30 вересня – 2 жовтня 2004 року;
-Міжнародна наукова конференція “Моделювання - 2006”, м. Київ, 16-18 травня 2006р.;
- VI міжнародна конференція по нерівноважним процесам в соплах і струменях (NPNJ-2006), 26 червня – 1 липня 2006 р., м.Санкт-Петербург;
-Міжнародна науково-практична конференція “Сучасні проблеми і досягнення в області радіотехніки, телекомунікацій і інформаційних технологій”, 13-15 квітня 2006р., м. Запоріжжя;
-III Міжнародна конференція “Паралельні обчислення і задачі управління”, 2-4 жовтня 2006р., м.Москва;
-семінари факультету обчислювальної техніки і інформатики Донецького національного технічного університету.
Публікації. За матеріалами дисертаційної роботи опубліковано 19 друкарських робіт, з них 5 статей опубліковано у виданнях, затверджених ВАК України, і 14 в працях міжнародних наукових конференцій і семінарів.
Структура і об'єм роботи. Дисертаційна робота обсягом 157 сторінок складається з вступу, 4 розділів, висновків, списку використаних джерел із 110 найменувань і розташованого на 10 сторінках, додатку. Дисертація містить 84 рисунки, 14таблиць.
ОСНОВНИЙ ЗМІСТ
У вступі обгрунтована актуальність теми, сформульована мета і задачі досліджень, висловлені основні наукові і практичні результати, отримані в роботі, відомості про апробацію роботи, а також основні положення, які виносяться на захист.
В першому розділі „Сучасний стан проблеми аналізу і оптимізації кластерних систем” приведена класифікація структур кластерних систем і методів, що дозволяють досліджувати ефективність цих систем.
На основі огляду відомих робіт зроблені висновки про стан проблеми в досліджуваній області, обгрунтований прийнятий напрям розробок, сформульована мета і задачі досліджень.
В другому розділі „Аналіз ефективності кластерних систем з використанням дискретних моделей Маркова” розроблена дискретна марківська модель однорідного кластера, оцінена трудомісткість алгоритму розрахунку характеристик функціонування кластерної системи, запропонований паралельний алгоритм розрахунку характеристик функціонування кластерної системи, приведена оцінка його складності, досліджена ефективність і прискорення паралельного алгоритму дискретної моделі Маркова однорідного кластера, проведений порівняльний аналіз дискретної і безперервної марківської моделей і визначені межі їх використовування.
Структурна схема марківської моделі однорідного кластера з сумісним використовуванням дискового простору приведена на рис.1. Кількість вузлів кластера – N. Задачі, оброблювані на такому кластері - однорідні і мають наступні характеристики: p12 – ймовірність запиту до одного з N1 серверів, p23 - ймовірність запиту серверу до одного з N2 дисків, p21 – ймовірність завершення обслуговування одним з N1 серверів, p10 – ймовірність завершення обслуговування задачі, q0 – ймовірність появи нової задачі. Кількість задач, оброблювана такою обчислювальною системою не більш М. Тривалісті часу обслуговування заявок на керуючому вузлі, сервері додатків і дисковому масиві, відповідно, мають геометричний розподіл з середнім, рівним Ti (). Тоді qi – ймовірність завершення в черговий такт обслуговування задачі на керуючому вузлі, сервері додатків і дисковому масиві, відповідно (), ri=1-qi. Вектор визначає кількість пристроїв в кожному вузлі ОС.
Рис. 1. Структурна схема марківської моделі однорідного кластера з сумісним використовуванням дискового простору
Стан системи - розміщення М заявок по трьох вузлах , де – кількість задач в -ому вузлі (). Число станів системи для однієї і тієї ж кількості задач j= дорівнює числу розміщень j задач по N вузлах, тобто . Загальна кількість станів моделі обчислюється як: .
Для кожної пари станів визначені умови переходу і перехідна ймовір-ність, тобто матриця перехідної ймовірності , елемент якої у разі переходу для кожної пари , при якому не змінюється кількість задач рівний
,
де ,
,
і -індикатори станів на серверній групі і дисках, відповідно,
- вектор, що визначає кількість працюючих пристроїв.
Вектор стаціонарної ймовірності станів визначаємо як рішення системи лінійних рівнянь (СЛАУ) .
Для тимчасової трудомісткості послідовного алгоритму побудови дискретної марківської моделі однорідного кластера отримана оцінка
(1)
де - загальна кількість ненульових елементів для всієї матриці перехідної ймовірності, обчислювана як
З (1) видно, що послідовний алгоритм має комбінаторну складність, тому пропонується паралельний алгоритм розрахунку характеристик функціонування кластерної системи на решітках процесорних елементів (ПЕ) типу двовимірної решітки-тора.
При рішенні на решітках процесорів p=nxn кожний з них може виконати розрахунок одного або декількох елементів матриці перехідної ймовірності. СЛАУ (для розрахунку стаціонарної ймовірності) розв'язується блоковим методом Фокса.
Отримана тимчасова трудомісткість паралельного алгоритму побудови моделі Маркова однорідного кластера
(2)
яка показує, що кількість операцій у порівнянні з (1) зменшується на кількість процесорів, що дозволяє розраховувати складніші моделі.
Прискорення паралельного алгоритму (рис.2) близько до кількості проце-сорів і не залежить від кількості пристроїв (серверів та/чи дисків) у вузлах дос-ліджуваного кластера. Тому у формулах оцінки трудомісткості (1) і (2) алгорит-му будування дискретної марківської моделі можна відкинути доданки, відпо-відні кількості пристроїв у вузлах.
а) б)
в)
Рис. 2. Прискорення паралельного алгоритму розрахунку моделі Маркова на решітках процесорів залежно від кількості вирішуваних задач М. Кількість процесорів: а)-16, б)-64; в)-256.
Трудомісткості послідовного і паралельного алгоритмів побудови дискретної марківської моделі кластера рівні, відповідно
Ефективність паралельного алгоритму розрахунку моделі Маркова на решітках процесорів залежно від кількості вирішуваних задач М, пристроїв і процесорів не змінюється і рівна 0.99 при М>20 (рис.3). Пояснюється це тим, що основний об'єм обчислень займає розрахунок матриці ймовірності переходів, який не вимагає міжпроцесорних обмінів.
Проведений порівняльний аналіз характеристик функціонування обчислю-вального середовища (час обслуговування задачі, середня кількість задач в черзі, завантаження), одержуваних дискретною і безперервною моделями Маркова при зміні інтенсивності вхідного потоку і фіксованих даних: кількість задач (не більш М), кількість пристроїв – К, інтенсивність обслуговування .
Рис. 3. Ефективність паралельного алгоритму розрахунку моделі Маркова на решітках процесорів залежно від кількості вирішуваних задач М. Кількість процесорів: а)-16, б)-64; в)-256.
Для , К=2, М=20 завантаження змінюється від 0.3 до 0.92. Похибка тимчасових характеристик (рис.4) і середньої кількості задач в черзі (рис. 5) складає 30% при завантаженні, рівному 0.9. При (завантаження не перевищує 0.4) похибка менше 5%.
Рис. 4.Залежність часу виконання задачі при , К=2, М=20
Рис. 5. Залежність середньої кількості задач в черзі при , К=2, М=20
Отримані результати моделювання за допомогою дискретної і безперервної моделей дозволяють зробити висновки: характеристики, одержувані обома моделями ідентичні у випадках, якщо всі обчислювальні вузли (модулі) містять один пристрій. Якщо кількість обчислювальних модулів у вузлах більш одного, характеристики дискретної і безперервної моделей співпадають, якщо кількість оброблюваних задач в обчислювальному середовищі менш кількості пристроїв у вузлі кластера. У випадку, якщо завантаження вузлів невеликі, тобто , тимчасові характеристики дискретної і безперервної моделей розходяться не більш, ніж на 5%. В цьому випадку ефективно для дослідження ОС використовувати безперервні моделі, оскільки вони менш трудомісткі. У випадку, якщо завантаження пристроїв більше 0.4 і менше 0.9, похибка тимчасових характеристик складає 30%. В цих випадках доцільно використовувати дискретні марківські моделі, оскільки вони точніше відображають роботу ОС, проте можна використовувати і безперервні моделі, якщо припустима похибка або треба отримати характеристики, обумовлені завантаженням.
В третьому розділі „Методи оцінки ефективності кластерних систем з використанням сіткових моделей” проведений аналіз однорідних і неоднорідних кластерних систем з сумісним використовуванням дискового простору і без надання доступу до ресурсів з використанням мережних моделей, розроблена методика оцінки ефективності кластерів на основі критерію збалансованості.
Неоднорідний кластер (рис.6) обробляє М заявок користувачів і складається з керуючого серверу, N1 серверів, що виконують різні додатки, N2 дисків.
Кожний з М призначених для користувача запитів з ймовірністю pN1+2,i звертається до i-го серверу, який, у свою чергу, обробляючи цей запит звертаються до одного з N2 дисків з ймовірністю pi,N1+1.
Рис. 6. Структурна схема неоднорідного кластера з сумісним використовуванням дискового простору
Функціонування даної обчислювальної системи представлено замкнутою стохастичною мережею, яка містить N1+2 системи масового обслуговування, в якій циркулює М заявок. Граф передач цієї мережі зображений на рис.7, на якому введені наступні позначення: SN1+2 – СМО, відповідна головному серверу, S1,...,SN1 – СМО, відповідні серверам; SN1+1 – СМО, відповідна дисковим просторам.
Вектор визначає кількість пристроїв в кожній СМО (kN1+2=1, kN1+1=N2).
Рис. 7. Граф передач моделі неоднорідного кластера з сумісним використовуванням дискового простору
Стан системи визначається наступним розміщенням заявок за всіма СМО =(mN1+2,m1,...,mN1,mN1+1), де mN1+2+m1+...+mN1+mN1+1=M. Вирішуючи СЛАР
,
складену за графом передач можна визначити коефіцієнти відвідин кожній СМО. За теоремою Джексона обчислюється стаціонарна ймовірність, яка дозволяє обчислити характеристики обчислювального середовища.
Визначені класи задач, які ефективно вважаються на таких кластерах. По критерію мінімального часу виконання найпереважнішими є класи задач з наступними характеристиками (рис.8): відношення суми ймовірності звернення до першого серверу і ймовірності обігу першого серверу до диска до відповідної суми для другого диска повинна бути менше двох і більше 0.6. У противному разі час виконання задачі збільшується на порядок через нерівномірне завантаження устаткування, що вабить небажані великі черги.
Рис.8. Залежність часу відгуку від ймовірності звернення до диска і до серверу
Кластер топології 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 (,).
.
Рис. 9. Граф передач моделі кластера з сумісним використовуванням дискового простору
Стан системи визначений розподілом заявок за всіма СМО =(mN1+N2+1, m1,..., mN1,mN1+1,mN1+N2), де mN1+N2+1+m1+...+mN1+mN1+1.+mN1+N2=M.
За графом передач складається СЛЗР для визначення коефіцієнтів відвідин і обчислюється стаціонарна ймовірність станів моделі.
Кластер проаналізований при виконанні на ньому різних класів задач (щодо кількості звернень до дисків кожного серверу і керуючого серверу до серверів-додатків) (рис. 10).
Рис.10. Залежність часу відгуку при різній ймовірності звернення до дисків
Отримані оцінки ефективного використовування кластера за критерієм часу для наступних класів задач: ймовірність звернення до одного з серверів менше 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) – повертаються на керуючий сервер.
Аналіз ефективності такого кластера показав, що збільшення інтенсив-ності обслуговування на серверах (в два і чотири рази) трохи впливає на зміну часу відгуку, а збільшення інтенсивності обслуговування на дискових масивах істотно збільшує час виконання задачі в обчислювальному середовищі (рис.11).
Для оцінки продуктивності кластера використовується критерій збалансованості, яким враховує виграш, отриманий за рахунок малого часу відгуку, і ціну втрат, що виникають через недовантаження устаткування.
Рис. 11. Залежність часу відгуку від різних інтенсивностей обслуговування серверів і дисків
При обслуговуванні на кластері однорідних заявок, критерій приймає вигляд: |
(3)
де Т–термін експлуатації кластера, di-штраф за затримку на одиницю часу рішення задачі в i-й СМО, si-вартість i-ої СМО - інтенсивність обслуговування i-ої СМО.
Складові критерію –ціна простою устаткування (лівий доданок виразу (3)) і штраф за затримку виконання запиту (правий доданок виразу (3)).
Запропонована наступна методика оцінки ефективності кластерів з сумісним використовуванням дискового простору, яка дозволяє визначати мінімальну вартість кластера і відповідний мінімальний час відгуку.
1.Проектується марківська модель кластера, тобто визначаються стани проектованої моделі, матриця переходів для них і обчислюється стаціонарна ймовірність.
2.Розраховуються основні характеристики обчислювальної системи: завантаження СМО, час відгуку, вартість, починаючи з М=1, 2 і т.д. Параметр М фіксується, якщо завантаження хоча б однієї із СМО досягне порогового значення. Звичайно “ідеальне завантаження” устаткування коливається від 0.6 до 0.9. Якщо завантаження менше цих величин, то експлуатація обчислювальної системи вважається неефективною, а якщо більше – ускладнюється система керування цим пристроєм.
3. Для значення М збільшується кількість устаткування (серверів або/і дисків) для СМО з граничним завантаженням. При цьому обчислюють значення критерію ефективності С (3). Те значення кількості устаткування, при якому С досягне мінімуму, вважається ефективним.
В четвертому розділі „Методи оптимізації складу і структури паралельних обчислювальних систем” запропоновані і обгрунтовані модифіковані алгоритми синтезу складу і структури обчислювальних структур (мінімального часу рішення при обмеженій вартості кластерної системи, мінімальної вартості системи при обмеженому часі відповіді ) з використанням методу середніх.
Алгоритм оптимізації складу і структури високопродуктивних обчислювальних систем.
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**).
ВИСНОВОК
Дослідження, проведені в дисертаційній роботі є теоретичним обгрунтовуванням і новим рішенням наукової задачі, що полягає в підвищенні ефективності кластерних систем за рахунок використовування результатів аналітичних моделей для визначення відповідності класу вирішуваних задач вибраної топології кластера, а також за рахунок рішення задач синтезу кластера для визначення його складу і структури.
1.
Розроблена дискретна марківська модель однорідного кластера з сумісним використовуванням дискового простору з обмеженою кількістю задач, яку можна застосовувати для оцінки ефективності обчислювальних паралельних структур, у тому числі, обчислювати основні характеристики обчислювального середовища: завантаження пристроїв; середнє число зайнятих пристроїв в s-му вузлі; середнє число задач, що знаходяться в s-му вузлі; середнє число задач, що знаходяться у черзі до s-го вузла; середні часи перебування і очікування у s-му вузлі; середні часи перебування і очікування в системі.
2.
Отримані оцінки трудомісткості дискретної марківської моделі кластера з сумісним використовуванням дискового простору, які залежать від структури обчислювального середовища, від кількості оброблюваних задач і від особливостей матриці перехідної ймовірності, мають комбінаторну складність.
3.
Запропонований паралельний алгоритм дискретної марківської моделі однорідного кластера на структурі типу решітки і отримані характеристики па-ралелізму: прискорення, що наближається до кількості процесорів, що не зміню-ється для різної кількості пристроїв у вузлі кластера, і ефективність, значення якого більше 0.85, залежно від різних значень параметрів структури моделі.
4.
Проведений порівняльний аналіз дискретної і безперервної марківських моделей, який показав, що результати обох моделей співпадають у разі мережі, що містить одноканальну СМО і у разі мережі з багатоканальною СМО при невеликих навантаженнях (
). Якщо мережа містить багатоканальну СМО і завантаження більше 0.4 і менше 0.9 дискретні і безперервні моделі розходяться не більше ніж на 30% (залежно від кількості пристроїв у вузлі і від величини інтенсивності обслуговування і інтенсивності надходження).
5.
Порівняльний аналіз результатів моделювання однорідного кластера з використанням дискретної і безперервної моделей Маркова показують розбіжність тимчасових характеристик до 30% при завантаженні пристроїв від 0.4 до 0.9. Однак безперервні моделі менш трудомісткі, тому їх доцільно використовувати для дослідження складніші структур при малих і середніх завантаженнях.
6.
Запропоновані сіткові моделі кластерів різної топології. Для неоднорідних кластерів ефективними за критерієм мінімального часу виконання є класи задач з наступними характеристиками: відношення суми ймовірності звернення до першого серверу і ймовірності обернення першого серверу до диска у відповідній сумі для другого диска повинна бути менше двох і більше 0.6. При недотриманні цих умов час виконання задачі збільшується на порядок через нерівномірне завантаження устаткування, що вабить небажані черги.
7.
Для кластерів топології NxN при рішенні класу задач з рівноімовірним зверненням до серверів і дисків час рішення задачі практично не змінюється при зміні у декілька разів інтенсивності обслуговування на серверах (при постійній інтенсивності обслуговування на дисках), а при збільшенні інтенсивності обслуговування на дисках у декілька разів, час рішення задачі істотно збільшується.
8.
Запропонована методика оцінки ефективності кластера з використанням критерію збалансованості, яка дозволяє обрати оптимальну кількість устаткування мінімальної вартості.
9.
Поставлена і вирішена аналітично задача оптимізації замкнених багатопроцесорних ОС (задача синтезу ОС з мінімальним часом відгуку заданої вартості і задача синтезу ОС мінімальної вартості із заданим часом відгуку) на прикладі системи клієнт-сервер.
10.
Запропонований метод оптимізації складу і структури обчислювальних мереж з використанням градієнтного методу і покоординатного спуску, який дозволяює прискорити рішення задачі оптимізації.
11.
Запропонований і реалізований алгоритм оптимізації складу і структури обчислювальних мереж з використанням методу середніх, який дозволяє прискорити рішення задачі оптимізації в порівнянні з наближеними методами і методами, заснованими на теоремі Джексона.
Список опублікованих праць здобувача за темою дисертації:
1.
Фельдман Л.П., Михайлова Т.В. Методы оптимизации состава и структуры высокопроизводительных вычислительных систем // Научные труды Донецкого государственного технического университета. Серия: Информатика, кибернети-ка и вычислительная техника, выпуск 15: - Донецк: ДонГТУ, 2000. – С. 40-45
2.
Фельдман Л.П., Михайлова Т.В. Способы оптимизации состава и структуры высокопроизводительных вычислительных систем. // Научные труды Донецкого государственного технического университета. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. – Севастополь: “Вебер”, 2001. – С. 80–85.
3.
Фельдман Л.П., Михайлова Т.В. Оптимизация состава и структуры высокопроизводительных вычислительных систем с использованием метода средних // Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка, випуск 39: – Донецьк, ДонНТУ.- 2002. - С. 53–58.
4.
Фельдман Л.П., Михайлова Т.В. Дискретная модель Маркова однородного кластера // Искусственный интеллект.- Донецк: ІПШІ МОН і НАН України “Наука і освіта”. №3.- 2006. - С. 79-91.
5.
Михайлова Т.В. Оценка точности непрерывной и дискретной моделей Маркова // Научные труды Донецкого государственного технического университета. Серия “Информатика, кибернетика и вычислительная техника”(ИКВТ-2005), выпуск 93.- Донецк: ДонГТУ.-2005.- C. 114-122
6.
Труб И.И., Михайлова Т.В. Об одном алгоритме генерации разбиений натуральных чисел на слагаемые //Сборник трудов факультета вычислительной техники и информатики.- Донецк: ДонГТУ.- 1996.- C. 195-197
7.
Михайлова Т.В. Анализ оценки эффективности кластерных систем с ис-пользованием вероятностных моделей //Системний аналіз та інформаційні тех-нології. Тези доповідей учасників Міжнародної науково-практичної конференції студентів, аспирантів та молодих вчених. 1-3 липня 2003р., м.Київ.-С.83-85
8.
Фельдман Л.П., Михайлова Т.В. Вероятностные модели анализа оценки эффективности кластерных систем // Материалы II Международного научно-практического семинара “Высокопроизводительные параллельные вычисления на кластерных системах” - Нижний. Новгород: Изд-во НГУ, 2002. – С. 301-307
9.
Фельдман Л.П., Михайлова Т.В. Анализ эффективности кластерных систем с использованием вероятностных моделей //Донбас – 2020: Наука і техніка – виробництву: Матеріали II науково-практичної конференції. м. Донецьк, 3-4 лютого 2004 р. – Донецьк, ДонНТУ, 2004. – С. 506-513
10.
Фельдман Л.П., Михайлова Т.В. Оценка эффективности кластерных систем с использованием моделей Маркова //Известия ТРТУ. Тематический выпуск: Материалы Всероссийской научно-технической конференции с международным участием “Компьютерные технологии в инженерной и управленческой деятельности”. – Таганрог: ТРТУ, 2002. – №2 (25). – С. 50–53
11.
Фельдман Л.П., Михайлова Т.В. Параллельный алгоритм построения дис-кретной марковской модели //Высокопроизводительные параллельные вычис-ления на кластерных системах. Материалы четвертого Международного на-учно-практического семинара и Всероссийской молодежной школы. /Под редак-цией член-корреспондента РАН В.А. Сойфера. – Самара, 2004. – С. 249–255
12.
Фельдман Л.П., Дмитриева О.А., Михайлова Т.В. Аспекты дистанционного обучения в курсе “Численные методы и пакеты” // Тезисы докладов Всероссийской научной конференции “Научный сервис в сети Интернет”. – М.: Из-во МГУ.- 1999. - С.293-297
13.
Михайлова Т.В. Оценка эффективности кластерных систем с использованием вероятностных моделей //Моделирование и компьютерная графика 2005 (МКГ-2005). Материалы первой международной научно-технической конференции 4- 7 октября 2005г., Донецк, ДонНТУ,.-С.141- 145
14.
Михайлова Т.В. Распараллеливание алгоритма построения дискретной Марковской модели // Интеллектуальные и многопроцессорные системы 2005. Материалы научно-технической конференции. Геленджик, 26 сентября-1 октября 2005г.- Таганрог-Донецк-Минск, 2005, т.1.-С.215-217
15.
Фельдман Л.П., Михайлова Т.В. Оптимизация структуры вычислительных систем с использованием метода средних // Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій. Тези доповідей Міжнародної науково-практичної конференції. 13-15 квітня 2006р., м.Запоріжжя.-С.192-194
16.
Фельдман Л.П., Михайлова Т.В. Оценка эффективности кластерных систем с использованием аналитических методов // Сборник трудов конференции ”Моделирование 2006” (Simulation-2006), 16-18 мая 2006. г.Киев.-С.465-468
17.
Фельдман Л.П., Михайлова Т.В. Параллельный алгоритм построения дискретных марковских моделей высокопроизводительных систем// Материалы VI Международной конференции по неравновесным процессам в соплах и струях (NPNJ-2006), 26 июня – 1 июля 2006 г., Санкт-Петербург.-С. 318-319
18.
Фельдман Л.П., Михайлова Т.В. Параллельный алгоритм построения диск-ретной модели Маркова // Искусственный интеллект. Интеллектуаьные и много-процессорные системы. Материалы Международной научно-технической кон-ференции, 25-30 сентября 2006г., Таганрог-Донецк-Минск, 2006. – С. 275–279
19.
Фельдман Л.П., Михайлова Т.В. Эффективность параллельного алгоритма построения дискретных марковских моделей// Материалы III Международной конференции “Параллельные вычисления и задачи управления” , 2-4 октября 2006г., Москва.-С.160-165.
У роботі, що написано у співавторстві автору належать: [1] постановка і розв`язка задачі синтезу ОС мінімальної вартості із заданим часом відповіді і задача синтезу ОС заданої вартості з мінімальним часом відповіді; [2]- запропоновано модифіковані алгоритми рішення задачі синтезу; [3]- використання методу середніх для задачі оптимізації; [15] – узагальнення модифікованих методів оптимізації кластерних систем із використанням чисельних методів та методу середніх, [4] – розробка дискретної марківської моделі однородного кластеру; [8,9,10] – розробка неперервних моделей кластерних систем; [11] – розробка паралельного алгоритму побудови дискретної марківської моделі; [17,18] – аналіз ефективності складових частин паралельного алгоритму побудови дискретної марківської моделі; [19] – аналіз ефективності паралельного алгоритму побудови дискретної марківської моделі; [12]- розробка чисельних алгоритмів розв`язання систем нелінейних рівнянь.
АНОТАЦІЯ
Михайлова Т.В. Підвищення ефективності кластерних обчислювальних систем на основі аналітичних моделей. – Рукопис
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 - обчислювальні комплекси, системи та мережі. - Донецький національний технічний універсистет, Донецьк, 2007.
Дисертація присвячена розробці методів підвищення ефективності функціонування кластерних систем на основі використовування результатів запропонованих аналітичних моделей з урахуванням відповідності класу вирішуваних задач вибраної топології кластера. Розроблена дискретна модель кластера з дисками, що розділяються, для оцінки його ефективності роботи, за допомогою якої можна отримати основні характеристики обчислювального середовища: завантаження вузлів, кількість заявок у вузлах, час виконання в кожному з вузлів. Запропонований паралельний алгоритм реалізації дискретної марківської моделі однорідного кластера на решітках процесорів, отримані характеристики розпаралелювання (прискорення і ефективність), що дозволяють реалізовувати цей алгоритм на паралельних структурах. Проведений порівняльний аналіз дискретної і безперервної марківської моделей однорідного кластера, визначені межі використовування цих двох моделей, що забезпечують необхідну достовірність результатів. Розроблені безперервні марківські моделі різних кластерних структур для отримання оцінки ефективності їх роботи при реалізації на них різних класів задач. Запропонований модифікований алгоритм рішення задачі синтезу кластерних структур для замкнутих систем з використанням методу середніх, який дозволяє оптимізувати обчислювальні структури, мережні моделі яких мають кількість станів, що перевищує майже на два порядки кількість станів моделей, досліджуваних класичними методами.
Ключові слова: кластерні системи, дискретні і безперевні марківські моделі, ефективність і прискорення паралельного алгоритму, методи аналізу і синтезу обчислювальних систем, метод середніх, критерій ефективності.
ANNOTATION
Mikhaylova T.V. Rise of the efficiency of the cluster computer systems on the basis of analytical models. – Manuscript
Thesis for candidate’s degree in technical science by specialty 05.13.13-computer, computing systems and networks. - Donetsk National Technical University, Donetsk, 2007.
Dissertation is dedicated to development of the methods of increasing of the efficiency of the cluster systems on the basis of using offered analytical models with accordance of the class of the solved tasks of the chosen topology of cluster. The discrete model of cluster with the divided disks for estimation of its works efficiency is designed. It is possible to get basic descriptions of calculable environment: loads of knots, quantity of requests in knots, times of implementation in each of knots. The parallel algorithm of the discrete Markov’s model of the homogeneous cluster on the mesh of processors is offered, characteristics of parallelism (speedup and efficiency) allowing realizing this algorithm on parallel structures are got. The comparative analysis of discrete and continuous models of Markov of the homogeneous cluster is conducted; the range of applicability for these two models providing necessary authenticity of the results is defined. The continuous Markov’s model of the different cluster structures are developed, for the estimations of the efficiency of their work during realization on them of different classes of tasks. The modified algorithm of the decision of the task of the synthesis of the cluster structures for the closed systems with the using of the method of the middle, which allows to optimize calculable structures which network models have the quantity of the states, exceeding almost on two orders the quantity of the states of the models explored by classic methods is offered.
Keywords: cluster systems, discrete and continuous models of Markov, efficiency and speedup of parallel algorithm, methods of analysis and synthesis of the computer systems, method of middle, criterion of efficiency.
АННОТАЦИЯ
Михайлова Т.В. Повышение эффективности кластерных вычислительных систем на основе аналитических моделей. – Рукопись
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - вычислительные комплексы, системы и сети. - Донецкий национальный технический универсистет, Донецк, 2007.
Диссертация посвящена разработке методов повышения эффективности функционирования кластерных систем на основе использования результатов предложенных аналитических моделей с учетом соответствия класса решаемых задач выбранной топологии кластера.
Разработана дискретная модель кластера с разделяемыми дисками для оценки его эффективности работы, с помощью которой можно получить основные характеристики вычислительной среды: загрузки узлов, количество заявок в узлах, времена выполнения в каждом из узлов.
Предложен параллельный алгоритм реализации дискретной марковской модели однородного кластера на решетке процессоров, получены характеристики распараллеливания (ускорение и эффективность), позволяющие реализовывать этот алгоритм на параллельных структурах.
Проведен сравнительный анализ дискретной и непрерывной марковской моделей однородного кластера, определены границы использования этих двух моделей, обеспечивающих необходимую достоверность результатов.
Разработаны непрерывные марковские модели различных кластерных структур для получения оценки эффективности их работы при реализации на них различных классов задач.
Предложен модифицированный алгоритм решения задачи синтеза кластерных структур для замкнутых систем с использованием метода средних, который позволяет оптимизировать вычислительные структуры, сетевые модели которых имеют количество состояний, превышающее почти на два порядка количество состояний моделей, исследуемых классическими методами.
Предложенные в работе методы использовались в процессе выполнения научно-исследовательских работ по гостемам ГТ-14-97 “Научные основы анализа и оптимизации структур компьютерных систем и
