МЕТОДИ РОЗПАРАЛЕЛЮВАННЯ ВИРІШУВАЧА РІВНЯНЬ MIMD - МОДЕЛІ МЕРЕЖНОГО ДИНАМІЧНОГО ОБ'ЄКТА

Святний В.А., Смагін О.М., Солонін О.М.
кафедра ЕОМ ДонНТУ,
mailto:ninolos@ukrtop.com solonin@cs.donntu.ru smagin@cs.donntu.ru

Abstract

Svjatnij V., Smagin O., Solonin O. Methods of parallelisation for the equations solver of MIMD – model of net dynamic object. Various approaches to processes of devitualisation of MIMD - models of net objects are considered. Two new methods of distribution of virtual processes of MIMD - model between accessible processors are described.

1. Вступ

У рамках наукового співробітництва кафедри ЕОМ ДонНТУ з інститутом паралельних і розподілених обчислювальних систем (IPVS) Штуттгартського університету розроблена версія розподіленого паралельного моделюючого середовища (РПМС) для динамічних систем з зосередженими (ДСЗП) і розподіленими (ДСРП) параметрами [1]. Основною задачею, що вирішується на обчислювальних ресурсах РПМС, є розробка та використання паралельних моделей ДСЗП, ДСРП і зокрема – мережних динамічних об'єктів (МДО). Формальний опис МДО різної фізичної природи є основою для побудови математичних моделей і складається з опису топології і рівнянь динамічних процесів [2, 3].

Топології мережних об'єктів представляються орієнтованими графами G(U,V), що кодуються наступною таблицею:
NUJ KUJ QI PAR KOM, (1)
де NUJ, KUJ- номери початкових і кінцевих вузлів орієнтованих гілок; QI – номери гілок, PAR – параметри гілок, КОМ – коментарі; |V|=m – кількість гілок, |U|=n – кількість вузлів.

Для мережних об'єктів із зосередженими параметрами вузлові рівняння нерозривності мають вигляд:
AQ=0, (2)
де А – матриця інциденцій, Q - вектор потоків повітря.

Моделююче програмне забезпечення, що реалізує моделі мережних об'єктів, розділяють на три послідовні частини [2]:
Топологічний аналізатор (ТА). Основним результатом роботи ТА є дерево та антидерево графа, матриця інциденцій А та матриця контурів S, що зв'язують топологічний опис з рівняннями процесів.
Генератор рівнянь (ГР), що приводить систему (2), (3) у вигляд, зручний для чисельного вирішення [1, 2]: Y = Hu – Ru*Z (4) X = - W*Y (5) W = Ax-1*Ay Hu = (Sy*Ky – Sx*Kx*W )-1*S*H = TP*H=HU Ru = (Sy*Ky – Sx*Kx*W )-1*S*R = TP*R=RU

Вирішувач рівнянь (ВР), що реалізує обраний алгоритм чисельного пошуку невідомих векторів X, Y системи (4), (5).

Вирішувач рівнянь є найбільш вимогливим до продуктивності доступних обчислювальних ресурсів. Питання побудови паралельних ВР залишаються актуальними для всіх предметних областей та динамічних систем різних топологій [2, 4].

В статті пропонуються два методи розпаралелювання алгоритмів функціонування вирішувача рівнянь MIMD – моделі МО, з використанням бібліотеки MPI.

2. Віртуальна паралельна модель мережного об'єкта

На рис.1 приведено граф тестового мережного об'єкта (m=117, n=61). Блок-схема послідовного алгоритму функціонування вирішувача рівнянь (4) – (5) представлена на рис.2. Аналізуючи можливості розпаралелювання операцій по обчисленню компонентів векторів X, Y, можна запропонувати ряд варіантів віртуальної MIMD – моделі мережних об'єктів. При цьому під віртуальною будемо розуміти модель, у якій виділені паралельно функціонуючі відносно автономні процеси, що спільно можуть забезпечити рішення задачі (4), (5).

Схему віртуальної моделі, що розпаралелена за SPMD – принципом відповідно до кількості гілок, приведено на рис. 3. У цій моделі передбачено m віртуальних процесів, кожний з яких веде обчислення з визначеними рядками матриць X, Y і W. Після обчислення поточних значень векторів Y відбувається обмін інформацією між процесами, далі компонується вектор Q = (X, Y)T і знову відбувається обмін. Порядок обчислень і обмінів ведеться відповідно до системи (4), (5).

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

Девіртуалізацією назвемо процес відображення віртуальної моделі (рис. 3) на цільову паралельну обчислювальну систему (ЦПОС), тобто ту обчислювальну систему, що є в розпорядженні користувача.

Пропонуються наступні етапи девіртуалізації:

Рисунок. 2 - Блок-схема алгоритму функціонування вирішувача рівнянь

Рисунок. 3 - Схема розпаралелювання програми за SPMD-принцип ом

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

Аналізуючи схему рис.3, можна запропонувати наступні варіанти підходів до розпаралелювання:

Об’єднання віртуальних процесів з метою вирівнювання завантаження: як можна побачити з рис.3, Х – процеси простоюють істотну частину часу, крім того кількість операцій, що виконується цими процесами, менша, ніж у Y – процесів. Є сенс виконати об'єднання деяких Х – процесів з метою вирівняти навантаження на процесори, попередньо визначивши критерії складності процесів;

Об'єднання Х – процесів з Y – процесами: при EMBED Equation.3 = n-1 об'єднання Х – і Y – процесів здійснюється природно, тобто в i – му віртуальному процесі обчислюються Xi, Yi. У ситуації EMBED Equation.3 n-1 доцільно прив'язувати кількість процесів до величини EMBED Equation.3 , а ті X EMBED Equation.3 +1, …,Xn-1, що залишилися до обчислення, концентрувати в одному чи декількох Х – процесах. При EMBED Equation.3 n-1 можна допустити роботу частини Y - процесів без обчислення компонентів вектора Х.

Відмовлення від Х – процесів: випадок схожий на попередній, відмінність полягає у відсутності в явному вигляді Х – процесів, при цьому Y – процеси містять масиви зі значеннями вектора Х.

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

Вибір ЦПОС, характеристика наявних ресурсів (доступна кількість процесорів, схема зв'язків між ними, операційна система і засоби паралельного програмування).

Великий вплив на процес девіртуалізації йде збоку реалізації комунікаційної бібліотеки MPI, що використовувається. Від типу застосовуваної бібліотеки залежить можливість запуску декількох віртуальних процесів на одному процесорі [3].

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

Програмна реалізація варіантів віртуальних моделей в умовах обраної ЦПОС.

4. Методи девіртуалізації моделей мережних об'єктів

На етапах 1, 2, 4 важливо формалізувати процес розпаралелювання моделей і їх відображення на ЦПОС. Пропонуються наступні методи девіртуалізації моделей МДО, що модифікують схему рис. 3.

Метод рівномірного розподілу полягає в наступному:

Нехай m – кількість гілок МО, n – кількість вершин, (n-1) – кількість гілок дерева, EMBED Equation.3 = m – (n-1) – цикломатичне число (кількість незалежних контурів), що дорівнює кількості гілок антидерева, Р - кількість віртуальних процесів (Р = m = EMBED Equation.3 +(n-1)), NCPU - кількість доступних процесорів (1 EMBED Equation.3 NCPU EMBED Equation.3 P).

Необхідно рівномірно розподілити Р віртуальних процесів ([n-1] і EMBED Equation.3 ) між NCPU доступними процесорами, тобто створити розпаралелювання, яке можна масштабувати. Будемо розподіляти віртуальні процеси відповідно гілкам дерева P1=n-1 і антидерева P2= EMBED Equation.3 , де Р=Р1+Р2, між двома групами процесорів N1 і N2 відповідно, де NCPU=N1+N2.

Позначимо quot[F] – цілу частину числа F, а rem[F] – дробову частину, тоді:

N1=quot EMBED Equation.3 ; N2= EMBED Equation.3 ;
Р1 можна представити формулою:
Р1=F1 *N1+E1; (E1<N1; N1=D1+E1).

Розподілимо Р1 віртуальних процесів на N1 процесорах у такий спосіб:
на D1 процесорах – F1 віртуальних процесів,
на E1 процесорах – (F1 +1) віртуальних процесів, тобто
D1*F1+E1*(F1+1)=n-1=P1.

Р2 можна представити як : Р2=F2 *N2+E2; (E2<N2; N2=D2+E2).

Таким чином, розподіл процесів віртуальної MIMD – моделі на процесори ЦПОС визначається параметрами m, n, EMBED Equation.3 , D1, D2, E1, E2, F1, F2, P1, P2 .

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

Як можна побачити з рис.3, віртуальні процеси Хi велику частину роботи програми простоюють, а при обчисленнях істотний час витрачається на обмін за матрицею комутації W. Сутність методу рівномірного розподілу по гілках антидерева полягає у відсутності в явній формі групи віртуальних Х –процесів. У програмі присутні тільки Y – процеси, кожний з яких містить свою копію даних, відповідних Х – процесам, тобто обчислення вектора Y розподілено між EMBED Equation.3 віртуальними процесами
EMBED Equation.3 , (6)
кожний з яких обчислює свою складову вектора Х (X=-W*Y)
X= EMBED Equation.3 , (7)
тобто у віртуальному процесі Yi знаходиться масив доданків вектора Х:
Yi : {X1(Yi)=W1 EMBED Equation.3 *Y EMBED Equation.3 ; X2(Yi)=W2 EMBED Equation.3 *Y EMBED Equation.3 ; . . . ;Xn-1(Y1)=Wn-1, EMBED Equation.3 *Y EMBED Equation.3 ;} (8)

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

Нехай Р - кількість віртуальних процесів (Р = EMBED Equation.3 ), NCPU - кількість доступних процесорів (1 EMBED Equation.3 NCPU EMBED Equation.3 P).

Тоді Р можна представити формулою:
Р=F *NCPU+E; (E<NCPU; NCPU=D+E).

Розподілимо Р віртуальних процесів на NCPU процесорах у такий спосіб:
на D процесорах – F віртуальних процесів,
на E процесорах – (F +1) віртуальних процесів, тобто
D*F+E*(F+1)= EMBED Equation.3 = P.

Таким чином, розподіл процесів віртуальної MIMD – моделі на процесори ЦПВС визначається параметрами m, n, EMBED Equation.3 ,D, E, F2, P.

5. Імплементація та порівняльний аналіз моделей

Модель мережного об'єкта з m=117, n=61 (рис.1) реалізована авторами на ЦПОС CRAY T3E обчислювального центру Штутгартського університету [4]. У моделі використано 117 процесорів за схемою рис.3, час моделювання естественного воздухораспределения склав 2,2 секунди,. У даному підході було проведено (1:1) - відображення віртуальної моделі на реальну MIMD – систему.

Авторами створено програмне забезпечення, що реалізує запропоновані методи розподілу і проведені експерименти на ЕОМ CRAY T3E стосовно до мережі рис. 1. Залежність часу моделювання від кількості використовуваних процесорів показано на рис.4. Чорним кольором відзначені значення для рівномірного методу, сірим – для методу розподілу по антидереву. По осі ординат показаний час роботи програми, а по осі абсцис – кількість застосовуваних процесорів. Мінімум часу моделювання для методу рівномірного розподілу приходиться на 24 процесора і складає 0,42 секунди.

Для методу розподілу по гілках антидерева мінімум часу моделювання приходиться на 22 процесора і складає 0,34 секунди.

Таким чином, розроблені методи розподілу можуть масштабуватись, мають більшу швидкодію і вимагають застосування меншої кількості процесорів порівняно з (1:1) – відображенням (рис.3). Необхідно відзначити, що зі збільшенням кількості використовуваних процесорів понад 30 відбувається поступове збільшення часу моделювання, процесори починають «заважати» один одному, і час, затрачуваний на обмін даними між процесорами, збільшується.

Висновки та перестпективи подальшої роботи

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

Рис. 4 – Порівняльний аналіз методів розпаралелювання

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

У процесі досліджень досягнута усталена робота версії РПМС [4], що дозволяє продовжити експериментальне вивчення ефективності методів на моделях МДО високої складності у таких напрямках:
За результатами отриманим при дослідженні розроблених методів можна зробити наступні висновки:

• отримані методи мають більш висока швидкодія чим раніше відомі;
• вимагають меншої кількості процесорів;
• метод розподілу по галузях антидерева представляється більш кращим;
• необхідна перевірка методів на моделях реальних МО аналогічної складності;
• необхідна перевірка методів на моделях МО високої складності;
• представляється необхідним розробка генератора тестових МО високої складності (m>>1000)

Література

1. Абрамов Ф.А., Фельдман Л.П., Святный В.А. Моделирование динамических процессов рудничной аэрологии. Киев, Наукова думка, 1981г. 283с.
2. Святний В.А. Проблеми паралельного моделювання складних динамiчних систем.- Науковi працi ДонДТУ, серiя IКОТ, вип. 6, Донецьк, 1999, С. 6-14.
3. MPI: A Message-Passing Interface Standart Esprit Project P6643 (PPPE), 1994, 227p.
4. Святний В.А., Солонін О.М., Надєєв Д.В., Степанов І., Ротермель К., Цайтц М. Розподілене паралельне моделююче середовище.- Наукові праці ДонДТУ. Серія “Проблеми моделювання та автоматизації проектування динамічних систем”. Випуск 29:-Донецьк, ДонДТУ, 2001. – С.229 – 234.