Технологiї паралельних обчислень в методi групового урахування аргументiв

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

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

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

УДК 517.123.456

Технологiї паралельних обчислень в методi групового урахування аргументiв

01.05.02 - математичне моделювання та обчислювальнi методи

Автореферат

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

Кошулько Олексiй Анатолiйович

Київ 2007

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

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

Науковий керівник: доктор технічних наук, професор, член-кореспондент НАН України Мар'янович Тадеуш Павлович, Інститут кібернетики ім. В.М. Глушкова НАН України, головний науковий співробітник.

Офіційні опоненти:

доктор фізико-математичних наук, старший науковий співробітник Хіміч Олександр Миколаєвич, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу програмного забезпечення і рішення задач,

доктор технічних наук, доцент Казимир Володимир Вікторович, Інститут проблем математичних машин і систем НАН України, провідний науковий співробітник.

Провідна установа: Київський національний університет імені Т.Г. Шевченка, кафедра математичної інформатики факультету кібернетики.

Захист відбудеться 27 квітня 2007 р. о (об) “11” годині на засіданні спеціалізованої вченої ради Д. 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: 03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту кібернетики ім. В.М. Глушкова НАН України.

Автореферат розісланий “23” березня 2007 р.

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

паралельний обчислення комбiнаторний алгоритм

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

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

Як свiдчать плани провiдних виробникiв центральних процесорiв та прогнози спецiалiстiв, зокрема викладені у доповiді Д. Ратнера, 2005р., за декілька рокiв очікується припинення виробництва непаралельних (одноядерних) моделей для серверiв та персональних комп'ютерiв, тому паралельнiсть ресурсоємних програм стане повсякденною необхiднiстю.

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

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

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

Iз поширенням багатопроцесорних комп'ютерiв стала очевидною потреба адаптувати до них ресурсоємні алгоритми МГУА багаторядного та комбінаторного типів. Наприклад, у роботi Р. Васновського, 1995 р., описано паралельний варiант багаторядного алгоритму МГУА на базi бiблiотеки обмiну повiдомленнями PVM (Parallel Virtual Machine). Також у роботах голландських учених І. Кіргофа, П. Вєйтера, 2000 р., виконано розпаралелювання багаторядного алгоритму та його неевристичного варiанта.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертацiйна робота виконана в Iнститутi кiбернетики iм. В.М. Глушкова НАН України та згiдно держбюджетних тем: IП.160.11 “Дослiдження методiв автоматичного застосування оптимiстичних схем синхронiзацiї в розподiлених моделях” (2002 - 2004?рр.) та ВФ.160.10 “Розробити та реалізувати унiфiкованi схеми проектування програм розподiлених iмiтацiйних експериментів” (2002 - 2005?рр.). Результати дисертацiйної роботи використанi при виконанні НДР для ДГРП “Пiвнiчгеологiя” (реєстрацiйний номер УкрIНТЕI № 0105U001466).

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

Об'єкт дослідження - метод групового урахування аргументів.

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

Наукова новизна отриманих результатiв. У дисертацiйнiй роботi вперше запропоновані паралельні модифiкацiї комбiнаторного алгоритму МГУА i методика його адаптацiї до бiльшостi рiзновидiв сучасних паралельних комп'ютерних систем.

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

На основi програмного забезпечення паралельної модифікації комбiнаторного алгоритму МГУА та створеного автором макета FNN-мережi, а також використовуючи кластер Iнституту кiбернетики ім. В.М. Глушкова НАН України, розв'язано ряд практичних задач, пов'язаних iз моделюванням та прогнозуванням поведінки складних процесів за даними спостережень. Зокрема, продемонстрована можливiсть короткотермiнового прогнозування деяких характеристик світового списку найбiльших суперкомп'ютерiв, а також у новій постановці розв'язана задача аналiзу рядів гiдрометеорологiчних спостережень, для яких виявлено нові прихованi закономірності.

Практичне значення одержаних результатiв. У роботi розробленi методи, комп'ютернi алгоритми та програмний iнструментарiй, якi дозволяють швидше та ефективнiше вирiшувати складнi задачi моделювання та прогнозування в усiх галузях де вже застосовується МГУА. Використання паралельних обчислень у комбiнаторному алгоритмi МГУА є принциповим вдосконаленням, оскiльки цей алгоритм у поєднаннi з сучасними паралельними комп'ютерами отримує нову якiсть, за рахунок суттєвого розширення класу розв'язуваних ним задач.

Запропонованими методами розв'язанi прикладнi задачi (роздiл 4), а також розробленi практичнi методи i програмне забезпечення для побудови топологiчних структур FNN-мереж.

Такі результати дисертаційного дослідження, як прикладна програма і методика багатопараметричного прогнозування на основі МГУА були впроваджені в Науково-технічному підприємстві “Геосфера”, яке разом з організацією, в якій виконана дисертаційна робота, брало участь у виконанні НДР для ДГРП “Пiвнiчгеологiя”.

Особистий внесок здобувача. Основні результати дисертаційної роботи отримані автором самостійно. У роботі [1], написаній у співавторстві з науковим керівником, здобувачу належить розробка методу побудови FNN-конструкцiй, а у роботах [2, 3] виконано дослідження за допомогою МГУА.

Апробацiя результатiв дисертацiї. Результати досліджень, які включенi до дисертації були представленi на міжнародних конференціях: “21st International Supercomputer Conference” (Germany, Dresden, 2006); “Second International Conference on Computational Harmonic Analysis in conjunction with the 19th Annual Shanks Lecture” (Vanderbilt University, Nashville, TN, USA, 2004), та на мiжнародному симпозiумi “Питання оптимiзацiї обчислень”, (Кацивелi, 2001).

Результати роботи неодноразово доповiдались на семiнарах вiддiлу № 160 Iнституту кiбернетики ім. В.М. Глушкова НАН України та на семiнарi у Мiжнародному науково-навчальному центрi iнформацiйних технологiй та систем НАН та МОН України за участю академiка О.Г. Iвахненко.

Результати аналiзу гiдрометеорологiчних рядiв спостережень, проведеного у четвертому роздiлi, використано при виконаннi НДР для ДГРП “Пiвнiчгеологiя”.

Публiкацiї. Результати дисертацiйної роботи опублiкованi у п'яти журнальних статтях [1-5] та тезах двох конференцiй [6, 7].

Структура та обсяг дисертації. Робота складається із вступу, чотирьох розділів, висновків, списку використаних джерел, що містить 51 найменування, додатку А - 24 сторінки, що є діючим варіантом програми побудови FNN-конструкцій, додатку В з трьома таблицями даних та додатку С, що містить акт про впровадження результатів дисертаційного дослідження. Повний обсяг дисертаційної роботи 96 сторінок, із них шість сторінок списку використаних джерел.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

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

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

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

Комбiнаторний алгоритм методу групового урахування аргументiв призначений для структурно-параметричної iдентифiкацiї складних процесiв i об'єктiв за даними спостережень в умовах перешкод. Вхiдними даними є результати m спостережень за об'єктом з входами та одним виходом, представлені у вигляді матриці та вектора . Згідно принципам роботи комбінаторного алгоритму МГУА, що описані у роботах О.Г. Івахненко, В.С. Степашко, вiдшукується оптимальна за зовнішнім критерiєм модель об'єкта в заданому класi моделей, лiнiйних за коефiцiєнтами. Для цього проводиться повний комбiнаторний перебiр структур часткових моделей побудованих iз частин базисної функції. Найбільш поширеною базисною функцією є поліном Колмогорова-Габора:

, (1)

де всі - коефіцієнти моделі, - степінь полінома.

Кількість членів полінома (1):

. (2)

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

Використовуються наступні зовнішні критерії описані у О.Г. Івахненка:

Критерій регулярності, значення якого залежить від середньоквадратичного відхилення моделі на частині даних В:

, (3)



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

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

, . (4)

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

, (5)

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

У комбінаторному алгоритмі МГУА досліджені блоки, якi можуть обчислюватись паралельно.

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

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

I. SMP, ссNUMA, однорідний Mosix-кластер.

II. MPI-кластер та MPP система

III. Неоднорідний Mosix-кластер.

IV. Неоднорідна розподілена мережа.

Якщо ми маємо n доданкiв у полiномi (1) - вiльний член та степенi вихiдних змiнних, то обсяг повного перебору часткових моделей дорівнює

. (6)

Нехай доступно процесорiв, потужнiсть яких (у мiльйонах операцiй на секунду або у iнших одиницях вимiру) задана вектором . Тодi розпаралелювання обчислень пропонується органiзувати наступним чином:

Паралельно має обраховуватись G груп моделей. У тому випадку, коли обчислювальне середовище однорiдне кiлькiсть груп моделей

G=. (7)

У противному випадку, обчислювальне середовище гетерогенне i кiлькiсть груп моделей

, (8)

де LCD - найбiльший спiльний дiльник.

Iстотною проблемою є те, що моделi в групi мають рiзний час обрахунку, оскiльки кiлькiсть їх аргументiв неоднакова i дорiвнює числу вiд одного до n. Але, як зазначалось, генерування нових моделей в комбінаторному алгоритмі залежить від стану двiйкового n-розрядного регiстру зсуву, тому розглядатимемо двійкове доповнення регiстру зсуву (як компенсатор складностi) невiдривно вiд розгляду початкової моделi. Наприклад, якщо розглядається модель зi станом двiйкового лiчильника 0100, то разом з нею буде розглянуто модель 1011 (доповнення). Необхідно зазначити, що при використаннi розгляду моделей парами, достатньо розпаралелити обрахунок лише першої половини моделей, а всi iншi моделi будуть автоматично розглянутi як доповнення. Тодi кiлькiсть моделей треба прийняти рiвною .

Отже, у кожнiй з G груп буде мiститися

(9)

моделей, де [ ] - цiла частина числа.

Кожен з G паралельних процесiв повинен мати власний дiапазон змiни регiстра зсуву. Початковому стану регiстра зсуву i-го обчислювального процесу вiдповiдає десяткове число:

. (10)



Кiнцевому стану регiстра зсуву i-го обчислювального процесу вiдповiдає десяткове число:

. (11)

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

На основi викладеної методики утворено модифiкацiї алгоритму (способи обрахунку S_i та E_i), призначені для наступних груп сучасних паралельних систем:

I. Для SMP, ссNUMA та однорiдних Mosix-кластерiв

, . (12)

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

II. Для MPP-систем та МРI-кластерiв формули розрахунку завдань iдентичнi попередньому випадку, але програма має бути написана з використанням бiблiотеки обмiну повiдомленнями МРI.

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

III. Неоднорiднi Mosix-кластери:

, . (13)

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

IV. Формули для розподiлених обчислень в локальнiй мережi або Iнтернет. Як єдина обчислювальна система можуть використовуватись розрізнені комп'ютери у локальній або глобальній мережі:

, . (14)

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

Запропонована методика розпаралелювання комбiнаторного алгоритму МГУА реалiзована у виглядi паралельного доопрацьованого варіанта програми комбiнаторного алгоритму пiд назвою COMBI, лістинги якої доступнi на мовi Алгол у довіднику з типових програм моделювання під редакцією О.Г. Івахненко, Ю.В. Коппа, В.С. Степашко. Створений нами пакет програмного забезпечення на мовi програмування “С” отримав назву “Parallel COMBI”. До його складу входять програми комбiнаторного алгоритму призначенi для роботи в рiзних ОС та паралельних середовищах. Програми даного пакету використовують єдине унiверсальне ядро розрахунку завдань, яке ураховує всі перелічені модифікації. “Parallel COMBI” має наступнi важливi вiдмiнностi у порiвняннi з програмою СОМВI: 64-бiтне внутрiшнє представлення даних; доступнiсть нового критерiю околу; доступнiсть вiд'ємних степенiв у базовiй функцiї; вiзуалiзацiя результатiв моделювання (для ОС Windows).

Версія програми з графічним інтерфейсом для ОС Windows доступна у Інтернет за адресою http://www.icyb.kiev.ua/~kai/oleksiy/gmdh/page3.htm

У третьому роздiлi пропонується метод побудови вартiсно-ефективних МГУА-орiєнтованих топологічних конструкцiй паралельного комп'ютера, що найкращим чином вiдповiдає вимогам комбiнаторного алгоритму МГУА до обчислювальних систем. Виходячи з будови комбінаторного алгоритму та способу його розпаралелювання, ці вимоги сформульовані наступним чином:

- максимальна сумарна продуктивнiсть довiльної кiлькостi процесорів;

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

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

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

Найкращим чином цим вимогам задовольняють кластернi системи. А у вартiсному вiдношеннi їх застосування буде тим ефективніше, чим краще спiввiдношення цiни та продуктивності iнтерфейсу сполучення процесорiв конкретного кластера. Однорiвневi FNN-мережi для побудови вартісно-ефективних обчислювальних кластерів використовують розв'язки математичної задачі покриття множин для розпаралелювання комутації у стандартному мережевому обладнанні, що описано у роботі Г. Дітца, Т. Маттокса, 1998?р.

Топологічна будова мережі з кількістю вузлів v і k-портовими мережевими комутаторами є задачею знаходження покриття множин A(v, k, 2) - такого сiмейства k-елементних пiдмножин, що називають блоками, взятих iз v-елементної вибiрки таким чином, що кожна двоелементна пiдвибiрка мiститься хоча б в одному блоцi.

У роботі Д. Гордона, Г. Куперберга, О. Поташніка, 1995 р., наведено дев'ять методів побудови покриттів, але жоден з методів не дає оптимальних конструкцій для всіх наборів параметрів. Тому існує депозитарій найменших за розміром (оптимальних) покриттів http://www.ccrwest.org, що отримані різними методами. В тому числі, депозитарій містить розв'язки еквівалентні FNN-конструкціям, у яких кількість вузлів менша 32.

Для пошуку більших конструкцій у роботі пропонується модифікований метод циклічного зсуву (ММЦЗ) який здатен будувати FNN-конструкції більших розмірів.

Розглянемо звичайний метод циклiчного зсуву (МЦЗ), як метод знаходження покриття множини. Для побудови покриття потужності v беруть деяку k-елементну підвибірку як 1-й блок та v-1 її циклічних зсувів як наступні блоки. Спробувати це для всіх можливих k-елементних підвибірок практично просто і часто це дає покриття.

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

Через умови, що накладаються на параметри FNN-конструкції, всі можливі перші блоки покриттів з s=1 можна дати у вигляді табл. 1, та ряд виключень в табл. 2, що мають місце лише при деяких комбінаціях n та С(v,k,2). У випадку, якщо потрібного блоку не існує, слід використовувати наступний існуючий блок та відповідний йому розмір покриття.

Припустимо, що відомо: довжина блоків - k (кількість портів комутатора); бажана потужність покриття - v (кількість вузлів кластера); значення n - кількість мережевих адаптерів одного вузла. Шукатимемо оптимальне покриття для перелічених параметрів.

Розрахуємо розмір покриття за формулою

, (15)

де [ ] - ціла частина числа, а { } - дробова.

Після розрахунку розміру покриття потрібно звернути увагу на необхідну умову існування FNN-конструкції:

. (16)

Якщо умова (16) порушується, то шуканої FNN-конструкції не існує.

Співвідношення (16) випливає із наступних міркувань:

Елементи покриття при заданому n можуть брати участь лише у n блоках довжини k, тому потужність покриття не може перевищувати кількість елементів, які можна розмістити в цих блоках. Кількість цих елементів, ураховуючи те, що один елемент розташовано в усіх n блоках, становить . Оскільки побудова будь-якого покриття за ММЦЗ починається з побудови покриття МЦЗ при s=1, в якому n=k та С(v,k,2)=v, то матимемо, що максимальний розмір покриття залежить лише від n, причому у вигляді співвідношення

(16).

Якщо k кратне n, модифікація МЦЗ полягатиме лише в тому, що у випадку некратності v до k, місця більших за v елементів у блоках необхідно заповнити порожніми елементами (позначаються як “0”).

Якщо k некратне до n, тимчасово замінимо довжину блоків на k_temp - найменше кратне до n число, що більше k. Тоді матимемо в кожному блоці k_temp-k тимчасових елементів. Заповнимо отриману тимчасову конструкцію згідно з МЦЗ.

Задамо вектор X довжини С(v,k,2), всі елементи якого рівні k_temp-k. Виконаємо наступну процедуру зменшення кількості тимчасових елементів, викладену нижче.

Проглядаючи покриття, оберемо блок b_i з таким індексом i, що x_i>0. Знайдемо в ньому елемент e_j, вага якого w_j найбільша поміж інших (або перша з найбільших):

. (17)



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

Повторюватимемо процедуру зменшення кількості тимчасових елементів доти, поки існуватиме x_i >0. Тоді в кожному блоці з'явиться не менше порожніх елементів, ніж було додано тимчасових. Прибравши з покриття всі порожні елементи та блоки з одним непорожнім елементом, отримаємо розв'язок задачі.

У випадку, коли потужність отриманого покриття менше запланованої, слід збільшити на одиницю С(v,k,2) і, якщо умова (16) не порушується, повторити побудову покриття з моменту “якщо k некратне до n...”.

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

1) нехай для кожної пари вузлів підраховано кількість маршрутів, що їх зв'язує, і результат занесено в матрицю зв'язності G розміром . Тоді можемо підрахувати нормоване квадратичне відхилення від середньої попарної зв'язності вузлів U:

, (18)

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

Критерій є важливим для FNN-кластерів з системним програмним забезпеченням, що використовує мережеві адаптери паралельно.

2) надлишковість попарної зв'язності вузлів R:



, (19)

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

, (20)

де N - кількість вузлів мережі.

Значення цього критерію фактично є більш точною характеристикою оптимальності ніж С(v,k,2). Він покращується разом із зменшенням С при фіксованому v, але для покриттів однакового розміру дає менше значення там, де менше n.

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

Для практичної перевiрки ефективностi пiдходiв до розпаралелювання, запропонованих у другому і третьому роздiлах, ми вiдтворили елементарну однорiвневу мережу на основi трьох двоядерних комп'ютерiв. Отримано дiючий макет МГУА-орiєнтованої паралельної обчислювальної системи, який задовольняє вимогам сформульованим у третьому роздiлi i який, на рiвнi користувача, виглядає як MPI-кластер. Данiй обчислювальнiй системi присвоєно кодову назву BESM-6 (Best Ef?ciency for Scienti?c Modeling).

Система BESM-6 мiстить три вузли, в кожному з яких є два мережевих iнтерфейси, що мiнiмально необхiдно для реалiзацiї однорiвневої мережi FNN. Така ланка FNN повнiстю вiтворює роботу однорiвневої мережi навiть без комутаторiв, оскiльки займає в кожному комутаторi лише два порти, що еквiвалентно прямому з'єднанню. Тестова перевiрка швидкодiї BESM-6 за допомогою “High Performance Linpack” показала максимальну продуктивність 20 GFLOPS при розв'язку системи лiнiйних рiвнянь з 18000 змiнних, що зайняло 194 секунди.

Робота паралельного варіанта комбінаторного алгоритму МГУА продемонстрована на кількох практичних задачах з ресурсоємністю на рівні перебору 300 мільйонів часткових моделей для кожного обчислювального експерименту. Тому окрім BESM-6 були задіяні обчислювальні ресурси кластера СКІТ-1, опис якого міститься в роботі В.М. Коваля, С.Г. Рябчуна, І.В. Сергієнка, А.О. Якуби, 2006 р., і який встановлено в Інституті кібернетики ім. В.М. Глушкова. Крім того, для розподілених обчислень використовувалась локальна мережа з чотирьох однопроцесорних комп'ютерів.

Розглянуто наступні прикладні задачі.

1. Прогнозування показникiв продуктивностi окремих позицiй списку “Top500” найбiльших суперкомп'ютерiв свiту (www.top500.org) на основi багаторiчних рядiв спостережень.

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

До розгляду взято шість параметрiв процесу, що описують змiни пiкової та максимальної продуктивностi комп'ютерiв списку, кiлькостi процесорiв, пропорцiйнiсть архiтектурної будови. Було виявлено, що для отримання прогнозiв важливi не всi параметри запропонованi алгоритму, водночас, параметр - “сумарна теоретична продуктивнiсть всiх комп'ютерiв списку” приймає участь в усіх моделях. Отримано незначні похибки прогнозів - 1,5?%, 2,5?%, 2,3?% відповідно для 25-ї, 26-ї i 27-ї редакцій спискiв суперкомп'ютерів, що складені групою авторів: Г. Моєр, Д. Донгара, Е. Строумаєр, Х. Саймон.

2. Дослiджено часові гiдрометеорологiчні ряди. Розв'язано задачу структурної ідентифікації для часових гiдрометеорологiчних рядiв з метою багатопараметричного короткотермiнового прогнозування рiчного стоку рiки Днiпро. Використовуються ряди середньорiчних спостережень з 1856 по 1975 рiк за стоком рiки Днiпро у пунктi спостережень “Лоцманська кам'янка” та метеоспостереження у м.?Києві за кiлькiстю опадiв та середньорiчною темперетурою повiтря (первинне дежерело даних - “Гидрологический ежегодник Гидрометеорологической службы СССР”). Крiм того використовуються данi спостережень за сонячною активнiстю - числа Вольфа (з джерела “Solar In?uences Data analysis Center at Royal Observatory of Belgium”, http://www.sidc.be).

Для з'ясування кiлькiсних характеристик запiзнення вiдгуку та з метою аналiзу причинно-наслiдкової залежностi природних явищ на основi комбiнаторного алгоритму МГУА, досліджено перелічені часовi ряди та їх зсуви в часі на 1-3 роки вперед i назад, щодо початку спостережень за стоком Дніпра - разом 22 вхiдних параметри процесу, ураховуючи часову вісь (рік реєстрації спостереження).

За методикою описаною у роботі В.С. Степашка, Ю.В. Коппи визначено кориснiсть вхiдних аргументiв, за частотним аналізом їх участi у формуваннi структур кращих за критерiєм регулярностi часткових моделей. Виявлено дев'ять “важливих” параметрів процесу, на основi яких проведено аналiз взаємозалежностей у гiдрометеоспостереженнях та продемонстровано побудову оптимальної за критерієм регулярності моделі, яка знайдена на основi 19-ти рокiв спостережень і зберiгає актуальнiсть на чотирьох спостереженнях тестової вибірки даних, для яких вiдхилення вiд фактичних даних у вiдсотковому вiдношеннi становить вiдповiдно: 7,1 %, 7,5 %, 0,9 % та 5,2 %.

3. Оцінено міру подібності для геологічних структур за існуючою постановкою задачі, поданою у роботі В.П Коболева, А.І. Кошулька, Р.І. Кутаса, 1983 р., з новими вхідними умовами, коли всі вхідні дані ураховуються в одному обчислювальному експерименті, що було неможливо раніше через високу обчислювальну ресурсоємність. Показано, що одночасне урахування всіх параметрів дозволяє зменшити кількість експериментальних даних у існуючій постановці задачі.

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

Для системи BESM-6 ефективність розпаралелювання склала 99,2?% вiд розрахункового ідеального значення, для 26 процесорів СКІТ-1 ефективність склала 95,6 %, для розподіленої гетерогенної мережі з чотирьох процесорних елементів - 98,7 %.

Досліджено вплив нерівномірної ресурсоємності обрахунку часткових моделей на розпаралелювання без застосування структурних доповнень описаних у другому розділі. Такий вплив знижує ефективність розпаралелювання на 26-ти процесорах до 71?%, а експериментальна оцінка мінімального впливу для 100 процесорів показує зниження ефективності до 32 %.

ВИСНОВКИ

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

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

Розв'язано такi основнi завдання:

1. Запропоновано методику розпаралелювання комбiнаторного алгоритму методу групового урахування аргументів та створено програмне забезпечення, в якому реалiзовано методичнi пiдходи для рiзних архiтектур паралельних комп'ютерiв.

2. Розроблено новий метод побудови топологiй однорiвневих FNN-мереж для кластерних комп'ютерiв, що задовольняють вимогам до вартiсно-ефективної МГУА-орiєнтованої обчислювальної системи.

3. Побудовано дiючий макет FNN-мережi який реалiзує архітектуру МГУА-орiєнтованої обчислювальної системи.

4. За допомогою створеного програмного забезпечення i обчислювальної ланки МГУА-орiєнтованої мережевої топологiї, а також iз застосуванням обчислювального кластеру Iнституту кiбернетики iм. В.М. Глушкова НАН України, отримано чисельнi результати розв'язання задач короткотермiнового прогнозування деяких характеристик списку найбiльших суперкомп'ютерiв Top500, а також проаналiзовано часовi гiдрометеорологiчнi ряди, що дало можливiсть вивчити новi прихованi залежностi. Крім того, робота програмного забезпечення продемонстрована на прикладі розв'язання задачі оцінки міри подібності для геологічних об'єктів.

У четвертому роздiлi дисертацiї досліджено алгоритмічну ефективнiсть розпаралелювання створеної програмної реалiзацiї комбiнаторного алгоритму МГУА на рiзних паралельних обчислювальних системах. У порiвняннi з теоретично найкращим розпаралелюванням досягнуто 96?% ефективностi при випробуваннi алгоритму на 26-и процесорах. Це стало можливим завдяки вирішенню проблеми компенсацiї неоднакової складностi часткових моделей, шляхом запровадження структурних доповнень.

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

СПИСОК ОПУБЛІКОВАНИХ НАУКОВИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Мар'янович Т.П., Кошулько О.А. Застосування мережевої топологiї Flat Neighborhood Network для побудови кластерних суперкомп'ютерiв // Математичнi машини i системи. - 2004. - № 4. - С. 3-12.

2. Кошулько А.A., Кошулько A.И. Тестирование полигармонического алгоритма МГУА // Управляющие системы и машины. - 2003. - № 2. - С. 87-92.

3. Кошулько A.И., Брайко Ю.A., Кошулько А.A. Модели оптимальной сложности природных процессов // Комп'ютерна математика. Оптимiзацiя обчислень. Зб. наук. праць. Том. 2. - Київ. - 2001. - С. 186-196.

4. Кошулько А.A. Сравнительный анализ топологических конструкций Sparse Flat Neighborhood Network для кластерных суперкомпьютеров // Кибернетика и системный анализ. - 2004. - № 6. - С. 87-92.

5. Кошулько О.A. Розпаралелювання операцiй в комбiнаторному алгоритмi методу групового урахування аргументiв // Доп. НАН України. - 2005.- № 2. - С. 65-69.

6. Koshulko О.A. Forecasting The Top500 List of Supercomputers // Proceedings of the 21st International Supercomputer Conference, Dresden, Germany, 2006.

7. Koshulko О.A. The polyharmonyc algorithm of GMDH for time series analysis // Abstracts of the Second International Conference on Computational Harmonic Analysis in conjunction with the 19th Annual Shanks Lecture, Vanderbilt University, Nashville, TN, USA, 2004.

АНОТАЦІЇ

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

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

Розроблено унiверсальне паралельне ядро комбiнаторго алгоритму придатне для використання з різними класами сучасних багатопроцесорних обчислювальними систем. Запропоновано новий метод розробки топологiй однорiвневих FNN-мереж для побудови вартiсно-ефективної МГУА-орiєнтованої обчислювальної системи.

Створено діючий макет програмно-апаратного комплексу на основі комбінаторного алгоритму МГУА та FNN-мережі для математичного моделювання багатопараметричних процесів та продемонстровано його роботу шляхом розв'язання практичних задач.

Ключові слова: МГУА, FNN, багатопараметричне моделювання, вартісно-ефективний обчислювальний кластер, паралельні обчислення.

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

Диссертационная работа посвящена исследованию проблемы параллельных вычислений в методе группового учета аргументов (МГУА) и эффективному распараллеливанию комбинаторного алгоритма МГУА. Важно, что понятие эффективности определяется как совокупность эффективности алгоритмического распараллеливания и цено-эффективности параллельных вычислений, что достигается при работе с некоторыми классами параллельных компьютеров, которые удовлетворяют сформулированным в работе требованиям к МГУА-ориентированной параллельной вычислительной системе.

В первом разделе выполнен обзор современных программных и аппаратных технологий параллельных вычислений с точки зрения возможности их использования для распараллеливания МГУА. Исследована вычислительная ресурсоемкость алгоритмов МГУА и состояние проблемы распараллеливания для них. Обосновано направление работы по распараллеливанию МГУА комбинаторного типа, который является наиболее ресурсоемким по сравнению с остальными. С помощью оценочных расчетов затрат времени для некоторых типов вычислительных задач, показано, что отсутствие распараллеливания в алгоритмах МГУА комбинаторного типа, является преградой для их продуктивного использования.

Во втором разделе описывается комбинаторный тип алгоритмов МГУА и предлагается методика распараллеливания. Выполняются модификации алгоритма ориентированные на разные архитектуры параллельного компьютера. Разработано универсальное параллельное ядро комбинаторного алгоритма пригодное для использования с разными классами современных многопроцессорных вычислительных систем.

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

В четвертом разделе с помощью созданного программного обеспечения и вычислительного звена МГУА-ориентированной сетевой топологии, а также с применением вычислительного кластера Института кибернетики им. В.М. Глушкова НАН Украины, получены численные результаты решения задач короткосрочного прогнозирования некоторых характеристик списка крупнейших суперкомпьютеров Top500, а также проанализированы временные гидрометеорологические ряды, что дало возможность изучить новые скрытые закономерности.

Оценивается эффективность алгоритмического распараллеливания при роботе на разных параллельных вычислительных системах. В сравнении с теоретически наилучшим стопроцентно-эффективным распараллеливанием достигнута эффективность 96?% при испытании алгоритма на 26 процессорах. Это стало возможным благодаря решению проблемы компенсации неодинаковой сложности частичных моделей, путем использования структурных дополнений.

Ключевые слова: МГУА, FNN, многопараметрическое моделирование, цено-эффективный вычислительный кластер, параллельные вычисления.

Koshulko O.A. Technologies of parallel processing in the Group Method of Data Handling. - Manuscript. Thesis for a candidate degree by speciality 01.05.02 - the mathematical simulation and computational methods. - V.M. Glushkov Institute of Cybernetics of The National Academy of Sciences of Ukraine, Kyiv, 2007.

The dissertation is devoted to investigation of parallel processing in The Group Method of Data Handling (GMDH) and implementation of effective parallelization in the combinatorial algorithm of GMDH. It is important that effectiveness was defined as combination of algorithmic parallelization effectiveness and cost-effectiveness that can be reached with certain parallel hardware architectures.

A universal parallel software of the combinatorial algorithm capable of working with various multiprocessor computers is designed.

A new method of construction of the Flat Neighborhood Networks for cost-effective GMDH-oriented computer is proposed.

An example of the GMDH-oriented system based on FNN and combinatorial algorithm software is built for mathematical modeling of multiparametric processes and its use demonstrated though the salvation of practical tasks.

Key words: GMDH, FNN, multiparametric modeling, cost-effective compute cluster, parallel processing.

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