RUS | ENG || ДонНТУ > Портал магістрів ДонНТУ Магістр ДонНТУ Морозов Роман Миколайович

Морозов Роман Миколайович

Тема випускної роботи:

Розподілені алгоритми рішення завдань високої розмірності на обчислювальному кластері

Кер_вник: к.т.н. доцент Ладиженський Юрiй Валентинович


Материалы по теме выпускной работы: Про автора

Автореферат

Вступ

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

        Обчислювальні кластери (High Performance Computing Cluster) забезпечують підвищення продуктивності цільових додатків, якщо функції цих додатків — ресурсномісткі обчислення. Ріст продуктивності прямо пов'язаний з розподілом одного обчислювального процесу по всіх доступних вузлах кластера.

        Свою версію кластера в 2005 році випустила компанія Microsoft. Цей продукт одержав назву Microsoft Windows Compute Cluster Server 2003 (WCCS 2003).Технологічно Microsoft Windows Compute Cluster Server 2003 [8] базується на стандартній версії Microsoft Windows Server 2003. У поставку продукту входять: модифікована версія Windows Server 2003 x64 Standard Edition і пакет, називаний Compute Cluster Pack.

        Модифікована версія Windows Server 2003 дозволяє істотно знизити вартість кінцевого вузла, оскільки обмежує можливість роботи тільки в ролі вузла обчислювального кластера. Компоненти, що входять в Compute Cluster Pack [8], - це набір сервисов, утиліт і протоколів. Цей набір являє собою роль «обчислювальний кластер» для установки на базову операційну систему. Для спеціально розроблених обчислювальних завдань користувачі можуть застосовувати стандартну поставку WCCS 2003.

        Убудованим засобом програмування на кластері є MS MPI. Message Passing Interface (MPI) - один зі стандартів розробки додатків HPC.

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

Актуальність теми

       Дослідження паралельного багатосіткового методу Федоренко на обчислювальному кластері Microsoft Windows Compute Cluster Server 2003 актуально, тому що такі дослідження ще не проводилися.

Мета й завдання розробки й дослідження

Ціль роботи

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

Основні завдання розробки й дослідження

Головними завданнями досліджень є:

Предмет розробки й дослідження

       Предметом досліджень є технології паралельного рішення рівнянь у частинних похідних на обчислювальному кластері Microsoft Windows Compute Cluster Server 2003 із застосуванням багатосіткових методів.

Наукова новизна

       Дані дослідження виконуються вперше в зазначених умовах.

Практичне значення отриманих результатів

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

Апробація роботи

       За результатами виконаних досліджень автором зроблений доповідь, на міжнародній науково-технічній конференції "Інформатика й комп'ютерні технології" 12-15 травня 2009 відбулася в м. Донецьку в стінах Донецького Національного Технічного Університету

Основний зміст роботи

Паралельні обчислення

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

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

       Одним з найбільш ефективних підходів до рішення диференціальних рівнянь у частинних похідних є багатосітковий підхід. Головною особливістю є те, що рішення виробляється спочатку на грубій(великої) сітці, а потім переноситься на більше дрібну сітку. Початкове рішення для сітки Nx, де N - кількість вузлів, будується за допомогою апроксимуючої сітки (N/2)x(N/2), одержуваної збереженням кожного другого вузла вихідної сітки Nx. Більше груба сітка (N/2)х(N/2), у свою чергу, апроксимується сіткою (N/4)х(N/4) і так далі. Потім у приватній області погрішність представляється як сума синусоїд з різними частотами. Тоді робота, виконувана на конкретній сітці, зменшує половину частотних компонентів погрішності, для яких зменшення не було досягнуто на більше грубих сітках. Тому робота, вироблена для усереднення рішення в кожному вузлі сітки, робить наближене рішення, що еквівалентно придушенню високочастотних компонентів погрішності.

       Наближений алгоритм рішення розглянемо на сітковому рівнянні Пуассона:

       Розглянемо сіткове рівняння Пуассона на п'ятиточковому шаблоні різницевої схеми "хрест"[10]:

Формула1

і, крім того, рівняння

Формула2

де

Формула3

Формула4

h – крок по координатах,

u – шукане рішення,

u' – наближене рішення (1),

r — нев'язання,

e — погрішність рішення.

       Якщо відомо наближене рішення першого завдання, те, вирішуючи другу, можна знайти рішення вихідної системи по формулі, Формула4,

але рішення завдання (2) по складності точно таке ж, як і рішення вихідного завдання.

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

Алгоритм:

  1. Робимо кілька ітерацій, для знаходження рішення, обчислюємо нев'язання

    Формула4

    на дрібній сітці.
  2. На великій сітці вирішуємо спеціальне рівняння (2) для нев'язання у вузлах, що збігаються з вузлами дрібної сітки.
  3. Виконуємо інтерполяцію нев'язання на вузли дрібної сітки.
  4. Переходимо на пункт 1.

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

Приклад реалізації багато сіткового методу на трьох сітках наведений на анімаційному малюнку 1.

Реализации много сеточного метода

Рис. 1. Багатосітковий метод на трьох сітках (анімованний малюнок складаєтся з 12 кадрів, затримка 1,5 сек.(після останнього кадру 3 сек), зроблений в Adobe ImageReady CS2 і розмір 27 КВ)

       Позначення наведеного на анімованному малюнку приклада:

h – крок сітки(відстань між двома сусідніми вузлами).

стрелки - рішення отриманих рівнянь.

стрелки - інтерполяція отриманих значень на більше дрібну сітку.

стрелки - перенос, отриманих при рішенні, значень на більшу (дрібну) сітку.

Опис наведеного на анімованному малюнку приклада:

  1. Робимо кілька ітерацій на дрібній сітці h.
  2. Переносимо нев'язання на більше грубу сітку.
  3. Вирішуємо на сітці 2h рівняння для нев'язання.
  4. Отримане нев'язання на сітці 2h переносимо на сітку 4h.
  5. Вирішуємо отримані рівняння.
  6. Переносимо отримані значення на більше дрібну сітку.
  7. Інтерполюємо значення на більше дрібну сітку.
  8. Вирішуємо на сітці 2h отримані рівняння.
  9. Переносимо отримані значення на сітку із кроком h.
  10. Інтерполюємо отримані значення.
  11. Вирішуємо отримані рівняння на сітці h.

Типові топології зв'язків

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

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

подсистем

Рис. 7. Підсистеми програмою системи

       Підсистема уведення інформації - призначена для уведення інформації, необхідної для рішення.

       Необхідно ввести:

       Підсистема обробки даних:

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

       Підсистема паралельних обчислень:

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

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

       Підсистема виводу результатів - відповідає за зручне для вивчення подання отриманих результатів.

       Необхідно вивести:

       Така структура забезпечує керування даними, отриманими на кожній ітерації в процесі рішення завдання.

Висновки

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

Література

  1. Гергель В.П. Теория и практика параллельных вычислений. – СПб.: Бином, 2007. – 424с.: ил.
  2. Шпаковский Г.И. Программирование для многопроцессорных систем в стандарте MPI. – СПб.: Минск, 2002. – 323с.: ил.
  3. Антонов А.С. Введение в параллельные вычисления. – СПб.: Москва, 2002. – 69с.: ил.
  4. Федоренко Р. П. Введение в вычислительную физику: Учеб. Пособие: Для вузов. — М.: Изд-во Моск. Физ.-техн. Ин-та, 1994. — 528 с.
  5. Hackbusch V., Trottenberg U. Multigrid Methods. - Lecture Notes in Math. 960, Springer Verlag, 1982., Сайт - http://torrents.ru/forum/viewtopic.php?t=1500630
  6. Бахвалов Н.С. Численные методы – Изд.:Лаборатория Базовых Знаний, 2003.– 632 с.
  7. Забродин А.В., Луцкий А.Е. Параллельные вычисления при решении современных задач науки и техники, Сайт - http://compmech.math.msu.su/kaf_paral.php
  8. Windows HPC Server 2008 , Сайт - http://www.microsoft.com/windowsserver2003/ccs/
  9. PCWeek Review №3 (3) 2008 , Сайт - http://pcweek.com.ua
  10. Лобанов А.И., Петров И.Б. Численное решение уравнений в частных производных эллиптического типа на примере уравнений Лапласа и Пуассона [Электронная лекция], Сайт - http://www.intuit.ru/department/calculate/nmdiffeq/6

ДонНТУ > Портал магистров ДонНТУ >|| Автореферат | Про автора