Русский   Deutsch
ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

При написанні даного реферата магистерська робота еще не завершена. Остаточне завершення: грудень 2014 року. Повний текст роботи та матеріали за темою можуть бути отримані у автора або його керівника після зазначеної дати.

Зміст

Вступ

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

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

Використання чисельних моделей і кластерних систем дозволяє значно зменшити вартість процесу наукового і технологічного пошуку. Кластерні системи в останні роки широко використовуються у всьому світі як дешева альтернатива суперкомпьютерам. Система необхідної продуктивності збирається з готових комп'ютерів, що серійно випускаються, об'єднаних, знову ж таки, за допомогою комунікаційного устаткування, що серійно випускається. Це, з одного боку, збільшує доступність суперкомп'ютерних технологій, а з іншого, підвищує актуальність їх освоєння, оскільки для всіх типів багатопроцесорних систем потрібно використання спеціальних технологій програмування для того, щоб програми могли повною мірою використовувати ресурси високопродуктивної обчислювальної системи [1].

Домінуюче положення при розробці паралельних програм для паралельних систем займає стандарт MPI (англ. Message Passing Interface). Програма, що розроблена в моделі передачі повідомлень, може бути представлена інформаційним графом, вершинам якого відповідають паралельні гілки програми, а ребрам – комунікаційні зв'язки між ними. Це можна використовувати для диспетчеризації завдань та їх обчислювальних потоків. Враховуючи гетерогенність обчислювальних ресурсів і середовищ передачі даних в кластері, можна здійснити розподіл обчислювальних потоків (гілок) з обчислювальних вузлів так, щоб мінімізувати накладні витрати на обмін даними між потоками і вирівняти обчислювальну навантаження між вузлами. Для цього необхідно володіти інформацією про потужність та завантаження вузлів та структуру паралельних програм, що очікують виконання [2].

1. Мета та задачі роботи магістра

Метою даної роботи є розробка паралельного MIMD-симулятора для МДО з розподіленими параметрами.

Головними задачами є:

2. Огляд існуючих розробок за даною темою

Шляхом співпраці факультету КНТ зі Штутгартським університетом розвивається тема дослідження розробки РПМС. Розроблені програми тестуються на кластерах ДонНТУ і HLRS.

На глобальному рівні: Німеччина (М. Resch, M. Zeitz — The University of Stuttgart) [3,4], США, Великобританія, Китай.

На національному рівні проблемами комп’ютерного моделювання займаються київські науковці: Томашевський В. М., Жданова О. Г. та Жолдаков А. А.

На локальному рівні проблемами розробки розподілених паралельних моделюючих середовищ займалися:

3. Розподілене паралельне моделююче середовище (РПМС)

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

Рисунок 1 – Структурна організація паралельного моделюючого середовища [6]

Рисунок 1 – Структурна організація паралельного моделюючого середовища [6]

У РПМС повинна бути забезпечена спадкоємність із засобами моделювання попередніх поколінь, які сьогодні реалізовані в ЕОМ SISD-структури. Тим самим паралельне розподілене моделююче середовище буде максимально дружнім до користувача, дозволить йому рости від моделей простих об'єктів до моделей складних ДС, що вимагають паралельної реалізації. Це означатиме відкритість середовища для користувачів і розробників моделей, що працюють як індивідуально, так і колективно, в залежності від складності проблеми моделювання. РПМС — це ще мало досліджений об'єкт розробки та реалізації. З метою систематизації розробок була запропонована декомпозиція середовища за наступними підсистемами [4]: діалогу (ПД), паралельних вирішувачів рівнянь (ППВР), обміну інформацією (ПОІ), балансування завантаження процесорів (ПБЗ), організації масивів даних (ПОМД), організації роботи у режимах теледоступу користувачів (ПОРТД).

Реалізація підсистем має принципове значення у визначенні покоління засобів моделювання, до якого належить пропоноване середовище. Можливість моделювати в рамках одного середовища системи з зосередженими і розподіленими параметрами об'єднує, з одного боку, ці дві галузі моделювання, які розвивалися відносно автономно. З іншого боку, це універсалізує і ускладнює РПМС. Враховуючи цю обставину набувають методичної ваги проблемномоделюючі середовища, побудова яких може розглядатися як складова частина загальної проблеми та набуття досвіду паралельного моделювання мережевої динамічної системи різної фізичної природи. Актуальною проблемою тут є об'єктно-орієнтована розробка моделюючих середовищ, яка найбільшою мірою дозволить використовувати загальні системно-програмні рішення в заданих предметних областях. Різні принципи дії та рівні розпаралелювання SIMD-та MIMD-систем [7] зумовлюють необхідність побудови SIMD-та MIMD-компонент РПМС, вирішення завдань їх взаємодії при реалізації моделей паралельних динамічних систем з зосередженими параметрами і моделей динамічних систем з розподіленими параметрами [8].

4. Мінімальні вимоги до моделюючого середовища

Процес проектування повинен включати три складові: декомпозиція, зв'язки, синхронізація.

Декомпозиція — це процес розбиття задачі та її рішення на частини [7]. Декомпозиція програмних модулів визначає, які функції вони повинні виконувати. Процес моделювання становить процес перекладу формул і алгоритмів в набір інструкцій. Метою моделювання є копіювання характеристик об'єкта та аналіз його станів при різних умовах. Декомпозиція визначає зв'язки окремих частин завдання. Для коректної роботи модельованого об'єкта частини задачі повинні бути пов'язані і синхронізовані.

Важливою складовою процесу розробки симулятора є вибір рівня розпаралелювання.

5. Топологічний аналіз МДОРП

Структура складних динамічних систем характеризується нелінійністю характеристик, великою розмірністю та розподіленістю параметрів процесів, тому майже не піддається аналітичному аналізу. Основним методом вирішення завдань автоматизації та технологічного проектування є математичне моделювання. Формальний опис МДО складається з двох важливих частин: опису топології і опису рівнянь фізичних процесів, які мають місце в гілках і вузлах мережі [10]. Мережеві динамічні об'єкти бувають двох типів: з розподіленими параметрами (МДОРП) та концентрованими (МДОКП). МДОРП може являти собою гідравлічну, електричну або вентиляційну мережу. Топологія динамічного об'єкта представляється у вигляді графа G(u,v) з безліччю вузлів u = n і гілок v = m. Аеродинамічні процеси можуть характеризуватися струмами або тисками і описуватися системою рівнянь. Як приклад на рисунку 2 представлена топологія мережевого динамічного об'єкта вентиляційної мережі.

Рисунок 2 – Топологія МДОРП

де Bj — вузли, Qj — повітряні потоки, H(Q1) — вентилятор
Рисунок 2 — Топологія МДОРП

Дискретною Simulation-моделлю (DSM) гілки будь-якого об'єкта є система рівнянь, яка виходить в результаті застосування деякого чисельного методу для розв'язання системи рівнянь. Симулятор — це програмно-апаратна реалізація DSM. Для j-гілки мережі (рис. 3) можна скласти DSM (формула 1).

Рисунок 3 – Граф МДОРП у лінійному вигляді

Рисунок 3 — Граф МДОРП у лінійному вигляді

Формула,    (1)
де Формула

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

Формула     (2)

Розпаралелювання обчислень правої частині вектора Х задачі Коші недоцільно у зв'язку зі збільшенням обсягу операцій обміну. Віртуальна паралельна DSM — це сукупність MIMD-процесів мінімальної гранулярності. Проблемою є відображення 1:1 процесів мінімальної гранулярності на цільовий паралельної обчислювальної системі.

6. Рівні розпаралелювання

Паралельну модель можна представити на чотирьох рівнях, які зображені на рисунку 4.

Рисунок 4 – Рівні розпаралелювання

Рисунок 4 — Рівні розпаралелювання
(анімація: 7 кадрів, 3 циклів повторення, 16 килобайт)

Перший рівень: 1 рівняння — 1 процес. Рівень мінімальної гранулярності.

Другий рівень: 1 елемент — 1 процес.

Третій рівень: 1 гілка — 1 процес. На рисунку 5 представлена схема DSM на третьому рівні розпаралелювання.

Четвертий рівень: 1 підграф - 1 процес. Граф декомпозується на підграфи, що мають найменшу кількість зв'язків один з одним. У цьому випадку кількість процесів залежить від числа подграфов, на які розбивають СДОРП [11].

Рисунок 5 - DSM на третьому рівні розпаралелювання

Рисунок 5 - DSM на третьому рівні розпаралелювання

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

  1. Рівномірність завантаження
  2. Співвідношення Nоо/Nобм
  3. Віртуальне прискорення з урахуванням операцій обміну
  4. Схема зв'язку між процесами
  5. Кількість Q- та P- процесів

Таблиця 1 — Варіанти реалізації третього рівня розпаралелювання

Критерій Варіант 1 Варіант 2
Рівномірність загрузки
L – кількість рівнянь, вирішуваних в процесі;М – кількість гілок МДО;крок за просторовою координатою 		Загрузка (QP)j процесыв Lj=2Mj=lj/Δξ залежить від кількості вірішуваних рівнянь та розбросу довжини lj гілок. Неравномерність ΔL=Lmax-Lmin=2(Mjmax-Mjmin), з диапазоном довжини [100..2000], буде великою. Кожен з Npj+1 процесів вирішує не менш, ніж Mmin=ljmin/Δξ пар рівнянь. Достигнута формалізація планування та рівномірного розподілення загрузок процесів за алгоритмом.
Співвідношення Nоо/Nобм
Віртуальне прискорення з урахуванням операцій обміну
Схема зв'язку між процесами Запропоновані віртуальні PQ - і QP-комутатори, робота яких організовується таким чином: схема зв'язків між процесами реалізується до початку роботи і залишається незмінною на весь період моделювання; у i-му циклі обчислень запам'ятовуються компоненти векторів Qj(ih) Pj(ih) і записуються у вихідні регістри Q - і P-процесів; всі процеси синхронізуються з моменту завершення самого довгого процесу, синхронно для всіх Q - і P-процесів активуються команди обміну, в один такт на входах Q - і P-процесів з'являються актуальні значення змінних і наступним тактом записуються в пам'ять; запускається i+1-й цикл обчислень. На всіх рівнях комутатори реалізуються однотипно на базі перемикачів 2х2.
Кількість Q- та P- процесів

Перелік посилань

  1. Букатов А. А., Дацюк В. Н., Жегуло А. И. Жегуло Программирование многопроцессорных вычислительных систем. – Ростов-на-Дону: ООО «ЦВВР», 2003. – 208 с.
  2. Высокопроизводительные параллельные вычисления на кластерных системах – Материалы Седьмой Международной конференции-семинара, Нижний Новгород, 26–30 ноября 2007 г.
  3. Forschungsgebiet: parallele Simulationstechnik [Электронный ресурс] / L. P. Feldmann, V.A. Svjatnyj, M. Resch, M. Zeitz – Режим доступа: http://www.nbuv.gov.ua/, вільний
  4. Svjatnyj V.A., Nadeev D.V., Solonin O.M., Rothermel K., Zeitz M.: Subsysteme einer verteilten parallelen Simulationsumgebung fur dynamische Systeme. 16. Symposium ASIM 2002, Tagungsband, 2002.
  5. Святний B.A., Молдованова O.B., Перерва А.О. Проблемно-орієнтоване паралельне моделююче середовище для динамічних мережних об'єктів. Наукові праці ДонНТУ, серiя «Проблеми моделювання та автоматизації проектування» (МАП-2001). Випуск: 29 – Донецьк: ДонНТУ. – 2001.
  6. Святний В.А. Проблеми паралельного моделювання складних динамічних систем. Наукові праці ДонДТУ, Серія «ІКОТ», вип. 6, 1999.
  7. Хьюз Т., Хьюз К. Параллельное и распределенное программирование на С++. : Пер. с англ. – М. : Издательский дом «Вильямс», 2004 – 672с.
  8. Скворцов П.В. Разработка и исследование решателя уравнений параллельной моделирующей среды на основе OpenMP-стандарта [Электронный ресурс]. — Режим доступа:http://masters.donntu.ru, свободный.
  9. Anoprienko A.J., Svjatnyj V.A., Braunl T., Reuter A., Zeitz M.: Massiv parallele Simulationsumgebung fur dynamische Systeme mit konzentrierten und verteilten Parametern. 9. Symposium ASIM’94, Tagungsband, Vieweg, 1994, S. 183-188.
  10. Гусєва Г.Б., Молдованова О.В. MIMD-паралельний вирішувач рівнянь для мережного динамічного об’єкту з розподіленими параметрами. Проблемы моделирования и автоматизации проектирования динамических систем: Сборник научных трудов ДонНТУ, вып. 6, 2007.
  11. Скорич В.И. Априорный анализ виртуальных параллельных моделей управляемого сетевого динамического объекта с распределенными параметрами [Электронный ресурс]. — Режим доступа:http://masters.donntu.ru, свободный.