ТРЕТІЙ РІВЕНЬ РОЗПАРАЛЕЛЮВАННЯ МДО-ТОПОЛОГІЇ

 

Лушпенко В. С., Святний В .А. Донецький національний технічний університет

 

 

У сучасних  умовах  темпи  технічного  прогресу  й  успіхи у вирішенні фундаментальних наукових проблем багато в чому визначаються рівнем розвитку обчислювальної техніки. У цей час загальновизнаним є клас фундаментальних наукових і інженерних проблем Grand challenges, ефективний розв'язок яких можливо тільки з використанням потужних обчислювальних ресурсів із продуктивністю сотень Gflops (~1012 операцій у секунду) і вище.

Щоб обґрунтувати потребу у вказаній продуктивності, наприклад, для завдань аерогазодінаміки, можна привести порівняно простий приклад розрахунку аеродинамічних характеристик ізольованого крила. Можна показати, що для здобуття стаціонарного вирішення рівнянь Навьє-Стокса необхідно виконати порядку 2·1013 арифметичних операції. При використанні сучасних персональних комп'ютерів на це буде потрібно десятки годин. На практиці аеродинамічного проектування зазвичай потрібний не окремий розрахунок, а систематичний перебір і аналіз багатьох варіантів. Звідси ясно, що лише за наявності ЕОМ з продуктивністю, що істотно перевищує показники персональних комп'ютерів, чисельне моделювання може стати реальним інструментом проектування літальних апаратів. Єдиним способом досягнення необхідної продуктивності в даний час є використання багатопроцесорних обчислювальних систем.

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

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

Стосовно  МДО  РП  можна  виділити  наступні  підходи  до

 

 

 

Рисунок 1 – Рівні розпаралелювання МДО

 

 

Таблиця 1 Порівняння двох варіантів третього рівня розпаралелювання

 

Крітерій	1 варіант	2 варіант
Рівномірність завантаження L — кількість рівнянь, вирішуваних в процесі; М — кількість гілок МДО; Δξ — крок за просторовою координатою	Завантаження (QP) j L =2M =l /Δξ j                j       j залежіть від кількості вирішуваних рівнянь і розбросу довжин l гілок. j Нерівномірність ΔL=L    -L    =2(M     - max        min                  jmax M    ) з огляду на jmin діапазон довжин виробок ШВМ буде суттєвою.	Кожен з N +1 pj процесів вирішує не менш ніж M    =l     / Δξ пар min       jmin рівнянь. Досягнуто формалізації планування та рівномірного розподілу завантажень процесів по запропонованому алгоритму. Алгоритм узагальнює дані щодо процесів всіх гілок ШВМ.
Співвідношення N  /N оо        обм	2M ≤N  /N    ≤4M j          оо        обм                j	2M    ≤N  /N    ≤4M min          оо        обм                min
Віртуальне прискорення з врахуванням операцій обміну

 

 

 

Таблиця 1 Порівняння двох варіантів третього рівня розпаралелювання

(продовження)

 

Крітерій	1 варіант	2 варіант
Т  — час циклу рішення; цр T     – тривалість QP-процесу для одного елемента апроксимації, QPj що залежить від вигляду рівнянь j-ї гілки   – віртуальне прискорення для рівня 3
Схема зв’язку між процесами	Запропановано віртуальні PQ- та QP- комутатори, работа яких організується таким чином: схема зв’язків між процесами реалізується до початку роботи і залишається незмінною на весь період моделювання; в i-му циклі обчислень запам’ятовіються компоненти векторів Q (ih) P (ih) і записуються в вихідні j                  j регістри Q- і P-процесів; всі процеси синхронізуються по моменту завершення самого довгого процесу, синхронно для всіх Q- і P-процесів активуються команди обміну, в один такт на входах Q- і P-процесів з’являються актуальні значення змінних і наступним тактом записуються в пам’ять; запускається i+1-й цикл обчислень. На всіх рівнях комутатори реалізуються однотипно на базі перемикачів 2х2.
Кількість Q- та P-процесів	N      =m ВПМЗ
NВПМЗ – кількість процесів віртуальної паралельної моделі mмд – кількість гілок мінімальної довжини

 

розпаралелювання:

1.    рівень процесів мінімальної зернистості;

2.    «один елемент – один процес»;

3.    «одна гілка – один процес»;

4.    декомпозиція графа МДО на підграфи.

На рис. 1 показано співвідношення між зазначеними рівнями розпаралелювання МДО.

На основі приведених чотирьох рівнів можливі різноманітні варіації способів розпаралелювання мережних динамічних об’єктів, які потребують проведення подальших досліджень. В даній роботі опрацьовується модифікацію рівня розпаралелювання 3, яку можна представити як «гілка мінімальної довжини – один процес».

Існує 2 варіанти реалізації третього рівню розпаралелювання. Їх порівняння наведене в табл. 1 за наступними крітеріями:

1.    Рівномірність завантаження.

2.    Співвідношення Nоо/Nобм   (кількість операцій обчис- лення/кількість операцій обміну).

3.    Віртуальне прискорення з врахуванням операцій обміну.

4.    Схема зв’язку між процесами.

5.    Кількість Q- та P-процесів.

 

Література

 

[1] Anoprienko A.J., Svjatnyj V.A., Bräunl T., Reuter A., Zeitz M.: Massiv parallele Simulationsumgebung für dynamische Systeme mit konzentrierten und verteilten Parametern. 9.

[2] Святний В.А., Молдованова О.В.,Чут А.М.: Стан та перспективи розробок паралельних моделюючих середовищ для складних динамічних систем з розподіленими та зосередженими параметрами.

[3] Schmidt B. Simulationssyteme der 5. Generation – SiP, Heft 1, 1994, S. 5–6.

[4] Аносов Д.В. Динамическая система // Математическая энциклопедия. М.: Сов. Энциклопедия,1979.