Методика оцінювання ефективності однорідної обробки даних на кластерних комплексах

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

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

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 681.3.06

Автореферат

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

Методика оцінювання ефективності однорідної обробки даних на кластерних комплексах

01.05.03 - математичне та програмне забезпечення

обчислювальних машин та систем

Ющенко Руслан Андрійович

Київ - 2009

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий керівник: доктор фізико-математичних наук, професор, член-кореспондент НАН України ПЕРЕВОЗЧИКОВА Ольга Леонідівна Інститут кібернетики імені В.М. Глушкова НАН України.

Офіційні опоненти:доктор фізико-математичних наук, професор, член-кореспондент НАН України ЛЕТИЧЕВСЬКИЙ Олександр Адольфович, Інститут кібернетики імені В.М. Глушкова НАН України,

кандидат фізико-математичних наук, доцент ГОРОХОВСЬКИЙ Семен Самуїлович, Національний університет «Києво-Могилянська академія», директор Інформаційно-комп'ютерного центру.

Захист відбудеться 27.03. 2009 р. о(об) 11 годині на засіданні спеціалізованої вченої ради Д 26.194.02 Д 01.39.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:

03680, МСП, Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий 12 лютого 2009 р.

Учений секретар спеціалізованої вченої ради В.Ф. СИНЯВСЬКИЙ

імітаційний моделювання бібліотека кластер

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

-оптимізація розподілу ресурсів кластерного комплексу,

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

-оптимізація апаратно-програмного рішення під певний клас задач.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційну роботу виконано за планом наукових досліджень у рамках бюджетних науково_дослідних проектів Інституту кібернетики імені В.М. Глушкова НАН України «Паралельна система баз даних “МегаПошук” у складі системного програмного забезпечення родини кластерів» (номер держреєстрації 0105U001465, 2005 - 2006 рр.), «Створення вітчизняних суперЕОМ» (номер держреєстрації 0106U007829, 2006 р.); «Розробити методи інтелектуалізації інформаційних технологій для оптимізації паралельних обчислень і верифікації дедуктивними методами паралельних програм, що масштабуються» (номер держреєстрації 0105U001465, 2007 - 2011 рр.).

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

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

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

-проведено числові експерименти з використанням імітаційного моделювання мовою GPSS;

-результати досліджень випробувано на застосуваннях, розроблених у рамках наукової тематики Інституту кібернетики ім. В.М. Глушкова НАН України;

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

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

Об'єкт дослідження - паралельні обчислення на кластерних комплексах.

Предмет дослідження - час, прискорення та ефективність однорідної обробки даних великого об'єму.

Методи дослідження. Для розв'язання поставлених задач у роботі використано методи математичного аналізу, теорії стаціонарних потоків однорідних подій, теорії масового обслуговування, метод моделювання Монте-Карло.

Наукова новизна отриманих результатів. Отримані результати є новими. Зокрема:

– запропоновано нові математичні моделі обчислювального процесу на основі систем масового обслуговування;

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

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

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

Практичне значення наукових результатів. Запропоновані в дисертації математичні моделі та методика оцінювання ефективності однорідної обробки даних на кластерних комплексах можуть бути використані для таких задач:

– вибір архітектури кластерного комплексу під конкретний клас задач;

– оцінювання потенційних можливостей розпаралелення послідовного алгоритму;

– вибір найприйнятнішої схеми паралелізму для конкретного кластерного комплексу.

Результати теоретичних досліджень враховано у побудові та вдосконаленні кластерних комплексів Українського державного геолого-розвідувального інституту, кластерів Інпарком; а також при розробці системи керування кластером ACMS для кластерних комплексів Інпарком -32, -64, -128.

Особистий внесок здобувача. Всі наукові результати, подані в дисертації, одержані автором особисто або у співавторстві. У роботі [2] здобувачу належить розробка алгоритму та паралельної програми автоматичної морфологічної розмітки українських текстів; [3] -розробка методики оцінювання паралельних обчислювальних систем та оцінок для різних стратегій організації даних; [4] - розробка системи керування завданнями; [7] - опис системного програмного забезпечення та оптимізація компілювання; [8] - розробка функцій вимірювання завантаженості ресурсів та відлагодження MPI-програм.

Апробація роботи. Результати роботи доповідалися на III Міжнародній науковій конференції «Теоретичні та прикладні аспекти побудови програмних систем» (TAAPSD-2006), IV Міжнародній науковій конференції «Теоретичні та прикладні аспекти побудови програмних систем» (TAAPSD-2008) у Києві; Міжнародній науково-практичній конференції «Штучний Інтелект» (ШІ-2007); та на наукових семінарах Інституту кібернетики ім. В.М. Глушкова НАН України та Національного університету «Києво-Могилянска академія».

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

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

ЗМІСТ РОБОТИ

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

Перший розділ присвячено постановці задачі дисертаційного дослідження. Оглянуто основні напрямки паралельних обчислень. Зокрема розглянуто підходи до вивчення ефективності як паралельних програм, так і паралельних обчислювальних систем. Основну увагу приділено кластерним комплексам, найбільш популярним сьогодні завдяки високій масштабованості, мобільності й інтероперабельності програмного забезпечення однорідної обробки даних. Вузьким місцем кластерів ранніх поколінь є комунікаційне середовище (мережа). Але, за останні роки розроблено нові надшвидкі мережні технології: Myrinet, InfiniBand, SCI тощо. Крім того, поява багатоядерних процесорів обумовила можливість дуже щільно компонувати обчислювальні пристрої. У результаті для багатьох задач однорідної обробки даних вузьким місцем став доступ до даних, які лежать на дискових носіях, швидкість доступу до яких на кілька порядків нижче за швидкість доступу до пам'яті й швидкості передачі даних по мережі.

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

Розглянуто механізм паралелізму за принципом макроконвеєрної обробки В.М. Глушкова, за якої кожний процес виконує свою задачу, а дані передаються між ними по спеціальних «каналах», які описує граф макроконвеєра. Згідно цього принципу паралельна програма представлена сукупністю процесів, кожний з яких складено з кількох блоків, що задають структуру процесу, топологію, динаміку й взаємодію процесів, розбиття даних і розподіл їх по процесах. Але проведене в університеті Базеля дослідження (BACS) свідчить, що на практиці існує всього кілька універсальних шаблонів паралельних алгоритмів, які досить точно визначають характер паралельних програм, використовуваних у системах із високою масштабованістю. Паралельні програми рідко використовують складну схему паралелізму, оскільки важко налагоджувати й масштабувати програму, яка працює на сотні обчислювальних пристроїв і має неоднорідності виконання процесів. Тому для оцінки ефективності доцільні моделі паралельної програми в рамках зазначених шаблонів.

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

Зокрема в роботі Метсона описано такі патерни:

-«майстер - робітник» (МР), коли один процес розподіляє завдання й призначає їх іншим вузлам, зазвичай збираючи результати від підлеглих процесів і з'єднуючи їх;

-«одна програма - багато даних» (ОПБД), розподіл даних по процесах визначає номер процесу, а розбиття залежить від кількості процесів;

-«розділяй і володарюй» (РВ), задачі рекурсивно ділять на підзадачі, які можна виконувати паралельно;

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

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

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

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

Нехай кластер складено з N обчислювальних пристроїв (ОП). Залежно від архітектури кластера такими пристроями можуть бути вузли, процесори, ядра процесора. Крім того, на кластері є S серверів, які постачають дані: дискове сховище, сервер баз даних, паралельна файлова система тощо (далі будемо називати їх серверами даних). Припустимо, що одиниця виконання (ОВ) на кожному вузлі складається з послідовності обчислень (тривалістю t_iⁿ), очікування даних (тривалістю ) і звертань до серверів даних (тривалістю ф_iⁿ ). Поведінка такої системи залежить від співвідношень t_iⁿ до ф_iⁿ.

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

Унаслідок однорідності даних знехтуємо різницю у часі виконання на i-му кроці розрахунку або звертання до даних залежно від номера процесу, тому опустимо зайвий індекс. Час, за який буде виконано i кроків процесу n, позначимо г_iⁿ. Тоді умови слабкого й повного завантаження можна переписати як і відповідно.

У разі централізованого доступу кількість обслуговуючих процесів S=1. Позначимо також накопичений до i-го кроку час очікування процесу n . Оскільки , то . Для зручності, не знижуючи загальності, вважаємо, що обчислювальні процеси впорядковано за зростаннням д₁: д₁ⁿ⁺¹ > д₁ⁿ. Тоді можна стверджувати, що Д ⁿ_i+1 ? ф_in (доведення див. у дисертації).

Позначимо максимальний час виконання звертання до пам'яті . Унаслідок слабкого завантаження Nф_i<t_i+1, тобто черга не накопичується. Тому загальний час виконання задачі г_У обчислимо як час виконання найдовшого потоку

.

Із позицій практики цю формулу переписано для спрощення оцінки параметрів. Нехай у разі N=1 загальні витрати на обробку даних , у тому числі витрати на читання R₁, а розрахунки виконуються за час C=T₁-D₁. Позначимо долю чистих розрахунків и=C/T₁, а долю розпаралеленої частини розрахунків - 0<з<1. Параметр з визначимо експериментально (використовуючи МКФ) за серією запусків однієї задачі з різним числом ОП N. Позначимо сумарний час виконання обов'язкових для кожного процесу (не розпаралелених) операцій читання ф^W_sec, записування - ф^R_sec, максимальний час однієї операції читання/записування - ф_max, середній час операції доступу до даних - м(ф), дисперсію - м(ф²). Частка розрахункової частини послідовної програми становить и=(T₁-D₁)/T₁, частка читання - с=R₁/D₁.

Для патерну «майстер - робітник» задача ділиться на атомарні блоки. Зазвичай кількість таких блоків (N_b) відома заздалегідь перед початком обчислень. Уважаємо, що один із процесів («майстер») передає на обробку іншим («підлеглим») процесам параметри обчислювальних блоків і очікує підтвердження про отримання результатів від цих процесів. Цей процес повторюється, поки не оброблено всі обчислювальні блоки. Такий спосіб декомпозиції даних і алгоритму застосовано у повнохвильовому моделюванні, коли блоком є сейсмограма, побудована від одного конкретного джерела сейсмічних коливань.

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

Для патерну «розділяй і володарюй» один процес розбиває задачу на підзадачі, розсилає їх іншим процесам і рекурсивно повторюється, доки розмір задач досить малий, щоб їх виконувати паралельно, але досить великий, щоб нівелювати накладні витрати на обмін повідомленнями та об'єднання результатів. Позначимо ширину розбиття w та глибину рекурсії d. Такий патерн використано у побудові паралельного генетичного алгоритму кластеризації даних, наприклад, у задачах Data Mining, розпізнавання образів та стискання даних.

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

«Майстер - робітник», повна завантаженість

,(1)

«Майстер - робітник», централізація та дублювання, слабке завантаження

,(2)

«Майстер - робітник», розчленування, слабке завантаження

,(3)

де .

«Одна програма - багато даних», централізація та дублювання, повне завантаження

, где .(4)

«Одна програма - багато даних», централізація та дублювання, слабке завантаження

(5)

«Одна програма - багато даних», розчленування, повне завантаження

(6)

«Одна програма - багато даних», розчленування, слабке завантаження

, (7)

де , .

«Розділяй і володарюй», повне завантаження

(8)

«Розділяй і володарюй», дублювання, слабке завантаження

,(9)

«Розділяй і володарюй», розчленування, слабке завантаження:

.(10)

Тут б знаходимо за формулою

.

Методика оцінювання ефективності обчислень на кластері з урахуванням оцінок (1) -(10) складається з послідовного виконання таких дій.

1.Оцінити частку чистих розрахунків и, частку розпаралеленої частини розрахунків з, частку операцій записування/модифікації серед операцій доступу до даних с, частку комунікаційних витрат о, максимальну тривалість операції доступу до даних ф_max, середню тривалість операції доступу до даних м(ф), дисперсію тривалості операцій доступу до даних м(ф²) і час виконання послідовної програми або час розрахунку на одному вузлі T₁ для кількох типових програм базового комп'ютера (звичайного або кластера).

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

3.Оцінити середнє відношення швидкості доступу з одного вузла системи зберігання даних базового комп'ютера до швидкості доступу аналізованого кластера K_D.

4.Оцінити середнє відношення швидкості записування даних із одного вузла системи зберігання даних базового комп'ютера до швидкості записування аналізованого кластера K_W.

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

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

7.Підставивши обчислені на кроці 6 коефіцієнти у формули

-(1) - (3) для патерну «майстер - робітник»,

-(4) - (8) для патерну «одна програма - багато даних»,

-(8) - (10) для патерну «розділяй і володарюй»,

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

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

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

Відповідність теоретичних оцінок практиці перевірено експериментально порівнянням аналітичних даних із результатами імітаційного моделювання систем масового обслуговування (СМО) в середовищі GPSS World, а також виконанням моделюючих програм на комплексі Інрарком-64. Програма, що імітує виконання обчислень за патернами «майстер - робітник», «одна програма - багато даних» і «розділяй і володарюй», написана мовою C++ із використанням бібліотеки MVAPICH (OSU MPI for InfiniBand). Для кожного набору значень параметрів виконано 5 прогонів програми. На графіках показано середні за прогонами значення. Результати експериментів наведено на рис. 2 - 7.

Імітаційне моделювання дало змогу одержати одразу кілька корисних оцінок паралельного алгоритму: час виконання для різної розмірності задач й кількості ОП, середній час очікування даних, завантаженість ОП і серверів даних. У проведених експериментах кількість серверів D=4. Отримано експериментальні оцінки часу виконання, часу очікування даних і частки втрат від очікування даних для різної кількості ОП. Для патерна «майстер - робітник» графіки відповідних залежностей показано на рис. 2 і 3, для патерна «одна програма - багато даних» - на рис. 4, 5. На рис. 6 і 7 показано залежність часу виконання обчислень від кількості серверів даних (D).

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

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

Таблиця 1. Ефективність патернів з різних позицій обчислень

№ п/п	За вимогами до дискової пам'яті	За балансуванням завантаження	За комуніка-ційними витратами	За масштабованістю
1.	РВ	МР	ОПБД	МР
2.	МР	ОПБД	МР	ОПБД
3.	ОПБД	РВ	РВ	РВ

Третій розділ дисертації присвячено розробці системи керування кластером для комплексів Інпарком, які Інститут кібернетики ім В.М. Глушкова НАН України розробляє разом із ДНВП «Електронмаш». Специфіка комплексів Інпарком полягає у тому, що крім загальносистемного забезпечення до комплекту входить програмне забезпечення, що дає змогу розв'язувати типові дослідницькі й інженерні задачі прямо в інтерфейсі користувача.

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

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

-моніторинг завдань і вузлів;

-моніторинг мережних інтерфейсів (Gigabit Ethernet і InfiniBand);

-моніторинг апаратури (температури процесора, систем вентиляції тощо);

-тестування кластера (тестування пам'яті, жорстких дисків, мережних інтерфейсів);

-моніторинг активності користувачів (поточні сеанси роботи з ACMS і системним терміналом).

На комплексі Інпарком-128 досліджено ефективність різних комунікаційних середовищ і мережних топологій. За показники ефективності використано латентність л, пропускну здатність р і навантаженість мережі Л. Крім стандартних топологій, створено експериментальну апаратну топологію гіперкуб на мережі Ethernet як альтернативу дорогої мережі InfiniBand. Крім того, на підставі серії експериментів, автоматичного моніторингу завдань і моделей, описаних у розділі 2 дисертації, у системі ACMS можна отримати прогнози часу обчислень для різної кількості процесорів (рис. 9).

Четвертий розділ дисертації присвячено прикладам задач обробки даних та їх оцінюванню з позицій ефективності паралельного виконання. Усі експерименти проведено на кластерних комплексах СКІТ Інституту кібернетики ім. В.М. Глушкова НАН України та на комплексі Інпарком-128.

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

Для побудови Національного корпусу української мови Інститутом української мови НАН України разом з Інститутом кібернетики виконано роботи зі створення словників морфологічного розбору слів. До складу електронних словників включено понад мільйон словоформ української мови. Результати експериментів показано на рис. 10. Оцінки при повному та слабкому завантаженні відповідають реальному обчислювальному процесу. Точка перетину показує момент, коли подальше збільшення ОУ не приводить до збільшення швидкості - час обчислень визначають тільки дискові операції.

Друга задача - це універсальна кластеризація (рекласифікація) даних для задач Data Mining, розпізнавання образів і стискання даних із використанням модифікованого генетичного алгоритму. Кластеризація - це автоматичне розбиття елементів певної множини на групи (кластери) за принципом схожості. Далі термін кластер вжито у двох значеннях: як паралельний обчислювальний комплекс і як певне відношення еквівалентності на заданій множині. Область застосування кластеризації: розпізнавання образів, класифікація й необоротне стискання даних. Розмаїття алгоритмів розв'язання задачі кластеризації обумовлено її широким формулюванням. Для задачі кластеризації потрібні міри близькості об'єктів і кластерів та функціонал якості розбиття.

Нехай навчальну вибірку задає множина N об'єктів X={X₁,…,X_N}. Кожний об'єкт описує вектор n дійсних атрибутів X_i=(x_i1,…,x_in), . Нехай у просторі задано метрику dist(Xi, Xj), а - одне з можливих розбиттів навчальної вибірки. Значення c_i=j вказує на те, що i-й елемент належить j-му кластеру, . Нехай задана функція розкиду об'єктів у кластері D(C), функціонали втрат від розкиду елементів усередині кластера L(D(C_i)) і якості розбиття W(K,C). Кластеризація зводиться до мінімізації функціоналу

.(11)

Кожний ген хромосоми кодують відповідно до конкретної задачі; він залежить від вхідної вибірки (c_i=). Величину, протилежну значенню функціонала (11), що визначає якість розв'язку C, використано як функціонал придатності хромосоми.

Класичну схему генетичного алгоритму доповнимо оператором розвитку. Задамо функцію H(C₁,C₂) як відстань за Хеммінгом між розбиттями C₁ і C₂:

(12)

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

У разі відомого K можна прийняти W(K,C)=const, тоді функція придатності зпроститься до Pr=-L[D(X)]. Нехай оператори мутації, відбору, заміщення та кросовер не застосовуються для однієї особини з максимальним для покоління значенням функції придатності. Ця вимога гарантує, що розв'язок не погіршуватиметься незалежно від параметрів операцій генетичного алгоритму. Оскільки простір пошуку скінченний, то класичний і модифікований генетичні алгоритми збігаються за скінченне число кроків.

Основна проблема кластеризації у разі невідомого K - це вибір підходящої функції W(K,C). Урахуємо, що кластеризацію зазвичай виконують для класифікації, тобто віднесення невідомих об'єктів до виділених кластерів. Виходячи з подання виділених кластерів своїми центрами, метод класифікації - за найближчими сусідами, або одна з його модифікацій, а кількість ядер дорівнює кількості кластерів. Міра Вапніка-Червоненкіса для методу найближчого сусіда дорівнює кількості ядер (h=K).

Для K кластерів емпіричний ризик співпадає з мінімальними втратами L(D(C)), тому за F доцільно вибрати істинний ризик невірної класифікації для заданого рівня вірогідності 1-з. У якості W(K,C) використано зазор, як у методі структурної мінімізації ризику. Підставивши в класичну формулу емпіричний ризик, імовірність і розмірності, маємо вираз:

, де .(13)

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

Модифікований генетичний алгоритм застосовано для аналізу даних фабрики, що виробляє 50 одиниць лінолеумового покриття з номенклатури продукції. Проаналізовано більше 5000 фактів замовлень продукції та визначено три кластери. Дані отримано з автоматизованої системи обліку на підприємстві «Регістри» ТОВ «Прайд» (www.pride.kiev.ua). Для аналізу даних за критерій якості розбиття використано дисперсію, а за метрику - відстань за Хемінгом. Правило визначення відстані між кластерами - повне з'єднання (далеких сусідів).

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

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

результаті при використанні понад 50 ВУ. На старті програми дані повністю завантажено в пам'ять, тому стратегія організації даних не впливає на результат обчислень, а формула оцінки ефективності спрощена (рис. 11).

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

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

ВИСНОВКИ

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

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

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

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

- експериментально досліджено вплив архітектури паралельного комп'ютера на ефективність виконання паралельних програм обробки однорідних даних;

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

– використовуючи методику отримані оцінки ефективності готових застосувань для задач, які Інститут кібернетики ім. В.М. Глушкова виконує згідно наукових тематик;

– для комплексів Інпарком-16, -32, -64, 128, -256 розроблено систему керування кластером, призначену оцінити ефективність паралельної програми після серії експериментів.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО В ТАКИХ ПРАЦЯХ

Ющенко Р.А. Генетические алгоритмы для решения задачи кластеризации // Компьютерная математика. - Киев. - 2004. - № 2. - С. 55 - 62.

Гудзенко В.В., Ющенко Р.А. Оценка производительности параллельных и непараллельных СУБД в задачах корпусной разметки текстов // Искусственный интеллект. - Донецк. - 2005. - № 4. - С. 575 - 581.

Перевозчикова О.Л., Тульчинский В.Г., Ющенко Р.А. Построение и оптимизация параллельных компьютеров для обработки больших объемов данных // Кибернетика и системный анализ. - 2006. - № 4. - С. 117 - 129.

Семеренко В.Р., Фальфушинский В.В., Ющенко Р.А. Построение системы управления заданиями для кластеров семейства Инпарком // Тр. Междунар. конф. TAAPSD'2006. - Киев, 2006. - С. 65 - 69.

Ющенко Р.А. Оценка эффективности суперкомпьютерных архитектур для различных паттернов параллельного программирования // Искусственный интеллект. - Донецк. - 2007. - № 3. - С. 447 - 453.

Ющенко А.К., Ющенко Р.А. Интеграция системного программного обеспечения в системе управления кластером для комплексов Инпарком // Тр. Междунар. конф. TAAPSD'2008, Киев. - 2008. - Т. 1. - С. 192 - 196.

Химич А.Н., Молчанов И.Н., Мова В.И. и др. Численное программное обеспечение MIMD-компьютера Инпарком. - Киев: Наук. думка, 2007. - 221 с.

Библиотека параллельных программ для исследования и решения задач вычислительной математики с приближенно заданными исходными данными / Т.О. Герасимова, В.С. Зубатенко, О.С. Майстренко, Р.А. Ющенко та ін. - Сертифікат авторського права від 11.07.2006, № 17213.

АНОТАЦІЯ

Ющенко Р.А. Методика оцінювання ефективності однорідної обробки даних на кластерних комплексах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин та систем. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2009.

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

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

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

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

Зазначена методика вбудована в систему керування комплексами Інпарком- 8-256, що дозволяє планувати й виділити ресурси для виконання завдання в пакетному режимі, виконувати моніторинг устаткування й завдань, контролювати й ураховувати час виконання.

Ключові слова: високопродуктивні обчислення, ефективність обчислень, однорідна обробка, дані великого об'єму, кластерні комплекси, паралельні програми, патерни паралельного програмування.

АННОТАЦИЯ

Ющенко Р.А. Методика оценивания эффективности однородной обработки данных на кластерных комплексах. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2009.

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

Значительную долю параллельных вычислений, выполняемых на компьютерных комплексах кластерной архитектуры, занимают задачи однородной обработки данных большого объема. Но поскольку для таких задач объем исходных, промежуточных и выходных данных как правило не помещаются в оперативную память полностью, необходимо интенсивно задействовать дисковые носители. Прогнозирование эффективности в этом случае существенно затрудняется, так как классические методики оценивания эффективности не учитывают этот фактор. Для преодоления трудностей при работе с данными большого объема используют разные стратегии организации данных на дисковых носителях.

Но для прогнозирования рассмотреть эти стратегии недостаточно, так как разные параллельные алгоритмы задействуют дисковые носители с разной интенсивностью. Во многих исследованиях показано, что применение сложных алгоритмов распараллеливания затрудняет масштабирование и понимание параллельной программы, поэтому на практике параллельные программы разрабатываются исходя из простых шаблонов. В диссертации исследование эффективности проводится в разрезе наиболее полной классификации шаблонов параллельных алгоритмов, предложенной Мэттсоном и называемой паттернами. Подмножество этих паттернов, связанных с декомпозицией по данным, успешно применяются для распараллеливания задач однородной обработки данных.

В диссертации показано, что при использовании в расчете достаточно большого количества процессоров поведение вычислительного процесса однородной обработки данных хорошо описывается системой массового обслуживания, в которой потоком заявок является поток запросов к серверу-поставщику данных. Для получения оценок в аналитическом виде рассмотрены два предельных случая: при слабой и полной загрузке. При слабой загрузке время доступа к данным намного меньше времени расчетов на одном процессоре, поэтому очередь к дисковым массивам не возникает. При полной загрузке время вычисления меньше времени доступа к данным, поэтому очередь возникает в начале вычисления и не рассасывается до его завершения.

В результате исследований получены оценки при слабой и полной загрузке для паттернов параллельных алгоритмов: «мастер - рабочий», «одна программа - много данных», «разделяй и властвуй» в разрезе стратегий организации данных: «централизация», «дублирование» и «расчленение». Экспериментально показано, что точка пересечения кривых оценок при слабой и полной загрузке является хорошей оценкой момента достижения максимальной эффективности. Используемые в оценках параметры сведены к таким, которые известны исходя из схемы распараллеливания и к таким, которые можно получить экспериментально на последовательном компьютере. В результате разработана методика, которая позволяет на основе небольшого числа экспериментов на базовом компьютере получить оценку эффективности данной задачи при использовании данной схемы распараллеливания и данной стратегии организации данных на произвольном кластерном комплексе исходя из его технических характеристик.

Результаты исследований использованы при проектировании и совершенствовании архитектуры и системного программного обеспечения кластеров семейства Инпарком (разработанным Институтом кибернетики им. В.М. Глушкова НАН Украины совместно с ГНПП «Электронмаш»), а так же кластеров в Украинском государственном геолого-разведывательном институте. Полученная методика использована для исследования эффективности задач автоматической разметки национального корпуса украинского языка, генетического алгоритма кластеризации, сейсмического конечно-разностного моделирования, миграции сейсмических волн. Численные эксперименты проведены на кластерных комплексах семейства СКИТ и Инпарком.

Элементы указанной методики встроены в систему управления кластером ACMS, разработанную в рамках диссертационного исследования. Эта система позволяет планировать и выделять ресурсы для выполнения задания в пакетном режиме, осуществлять мониторинг системы и оборудования, контролировать и учитывать время выполнения. Система управления кластером ACMS включена в состав программного обеспечения комплексов семейства Инпарком-8-256.

Ключевые слова: высокопродуктивные вычисления, эффективность вычислений, данные большего объема, кластерные комплексы, параллельные программы, паттерны параллельного программирования.

ANNOTATION

Yushchenko R.A. Technique for estimation of uniform data processing efficiency on cluster computers. - Manuscript.

Thesis for Candidate Degree in Physics and Mathematics; specialty 01.05.03 - mathematical and program software for computers and system. V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2009.

Modern high performance cluster computers being extremely scalable and rather cheap are successfully used for processing of large volumes of data in a many research and industrial areas. A lot of the problems solved by such computers are related to uniform data processing. This includes data mining, simulation, exploration and prospection problems. High efficiency, however, is not always achieved especially on large clusters with hundreds of CPUs. The purpose of the thesis is to analyze efficiency of uniform data processing on cluster computers and develop a technique for predicting performance of such processing on a cluster based on it's technical specification.

The result of the research is a set of estimates for a different patterns of parallel programming (Mattson et al.) and data storage and delivery strategies based on queueing theory. Such estimates can help in the parallel program development planning and the data distribution optimization. Besides, the formulas can support decisions on planning the hardware upgrades or selecting more efficient cluster architecture under the budget limitations. A crosspoint of the weak and full load diagrams can be used as a first approximation of the best process number for the specific program run. Using the estimates a technique was developed to provide an evaluation of parallel software performance on an arbitrary cluster given it's processor, storage and network specification by conducting several experiments on a single or multiple processor basic computer.

The technique was successfully used for evaluating performance of automatic markup of text corpora, genetic algorithm for data clustering, finite-difference seismic wave propagation modeling and seismic data migration. As the result the technique was embedded in cluster management system ACMS for series of Inparcom cluster computers, that was developed by V.M. Glushkov Institute of Cybernetics together with Government scientific and industrial organization Electronmash.

Key words: high performance computing, data processing efficiency, large volume of data, cluster systems, parallel programs, patterns of parallel programming.

Підп. до друку 26.01.2009. Формат 60х84/16. Офс. друк. Папір офс. Ум. друк. арк. 1,16. Ум. фарбо-відб. 1,39. Обл.-вид. арк. 1,0.

Зам. 7. Тираж 100 прим.

Редакційно видавничий відділ з поліграфічною дільницею Інституту кібернетики імені В.М. Глушкова НАН Украйни03680, МСП, Київ-187, проспект Академіка Глушкова, 40

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

...