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

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

Зміст

Вступ

Сучасний стан розробок і досліджень в області математичного моделювання відзначається широким застосуванням паралельних обчислювальних систем. Стрімкий розвиток паралельного моделювання стимулюється необхідністю розв’язання проблем моделювання складних динамічних об’єктів, описуваних системами звичайних диференційних рівнянь (СЗДР), що характеризуються високими розмірностями, жорсткістю, поганою обумовленістю, обліком великої кількості параметрів [1].

Не зважаючи на те, що на сучасному стані розвитку технічного прогресу існує багато високопродуктивних обчислюваних систем, є багато задач, в яких гостро відчувається проблема нестачі обчислювальних ресурсів, при тому, що сучасні високопродуктивні кластери перебороли рубіж у петафлопс, а кількість ядер, що нараховують такі системи, десятків і сотень тисяч. Ефективність паралельних додатків на подібних системах за різними оцінками не перевищує 15%, а в деяких випадках або навіть 3–5% від пікової продуктивності [2].

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

На протязі багатьох років чисельний розв‘язок задачі Коші був об’єктом пильної уваги науковців, оскільки він широко застосовується в різних галузях науки і техніки. Тому і кількість розроблених для нього методів дуже велика. Одним із важливіших чисельних методів розв’язання задач Коши є екстраполяційні методи Річардсона, які призначені для отримання високоточного розв’язання задачі Коші і інтеграції систем звичайних диференціальних рівнянь із складними правими частинами. Практичне застосування екстраполяційних методів ускладнене у зв’язку з великою обчислювальною складністю їх послідовних реалізацій. Крім того, використання технології локальної екстраполяції на основі явних опорних схем обмежує використання методів областю нежорстких задач. Тому побудова ефективних паралельних блокових неявних методів локальної екстраполяції Річардсона – одна з найбільш актуальних тем на теперішній час.

2. Мета і задачі дослідження та заплановані результати

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

Основні задачі дослідження:

  1. Розглянути підходи до паралельної реалізації методів розв’язання багатовимірних задач Коші, що ґрунтуються на використанні екстраполяції Річардсона.
  2. Удосконалити паралельний екстраполяційний алгоритм.
  3. Проаналізувати результати, що будуть отримані під час проведення експериментів на паралельній обчислювальній системі.

Об’єкт дослідження: підтримка паралельних обчислень при моделюванні складних динамічних об’єктів.

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

В рамках магістерської роботи планується отримання актуальних наукових результатів по наступним напрямкам:

  1. Удосконалення паралельного екстраполяційного алгоритму.
  2. Розробка тестових задач для оцінки ефективності удосконалення.

Плановані практичні результати:

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

3. Огляд досліджень та розробок

3.1 Огляд міжнародних джерел

Хайрер Е. і Ваннер Г., відомі математики Швейцарії та Норвегії, у своїх працях [3–4] надають повну картину сучасного стану теорії і практики чисельного рішення звичайних диференціальних рівнянь, основні теоретичні результати, представляють найбільш уживані чисельні методи, дають велику кількість прикладів практичних застосувань у фізиці і прикладних науках. І що не менш важливо, представляють тексти програм на Фортрані.

У книзі Дж.Холла [5] представлено повний набір кращих з існуючих алгоритмів розв’язання, а також огляд останніх досягнень теорії як для початкових, так і для крайових задач. Розглянуто рівняння з запізнілим аргументом, інтегродиференціальних рівняння Вольтерра, задача Коші для жорстких систем рівнянь. Книга адресована широкому колу фахівців з обчислювальної математики, що цікавляться чисельними методами.

Вдале поєднання навчального посібника і довідника по методам чисельної алгебри являє собою книга [6] відомих американських математиків-обчислювачів Голуба Дж. та Ван Лоун Ч. Виклад стислий, в рецептурної формы, без доказів. Книгу відрізняють методичні переваги: кожен розділ містить завдання для читачів – студентів, та огляд наукової літератури – для фахівців. Для математиків-обчислювачів, інженерів, студентів математичних і технічних спеціальностей.

3.2 Огляд національних джерел

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

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

3.3 Огляд локальних джерел

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

У статті [9] професор Дмитрієва О.А. пропонує нові колокаційні блокові методи розв’язання жорстких систем звичайних диференціальних рівнянь з автоматичним управлінням розміром кроку, які спочатку орієнтовані на паралельну архітектуру. Основна ідея, на якій базується конструювання пропонованих методів, полягає в одночасному отриманні наближень точного рішення у всіх розрахункових точках блоку.

У [10] професор Лев Петрович Фельдман і доцент Ірина Акопівна Назарова (ДонНТУ) розглянули паралельний алгоритм розв’язання систем ЗДР, орієнтований на системи з SIMD–архітектурою. Були отримані характеристики алгоритму такі як час виконання, прискорення та ефективність паралельної реалізації.

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

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

4.Класифікація архітектур з паралельної обробки даних

У 1966 році М.Флінном був запропонований надзвичайно зручний підхід до класифікації архітектур обчислювальних систем. В основу було покладено поняття потоку, під яким розуміється послідовність елементів, команд або даних, обробляється процесором. Відповідна система класифікації заснована на розгляді числа потоків інструкцій і потоків даних, і описує чотири архітектурні класи [14]. (див. рис.1):

1) SISD – Single Instruction (1) Single Data (3);

2) MISD – Multiple Instruction(2) Single Data;

3) SIMD – Single Instruction Multiple Data (4);

4) MIMD – Multiple Instruction Multiple Data.

Класифікація архітектур обчислювальних систем за М.Флінном

Рисунок 1 – Класифікація архітектур обчислювальних систем за М.Флінном (анімація: 12 кадрів, 5 циклів повторення, 100 Кб)

SISD – одиночний потік команд і одиночний потік даних. До цього класу належать послідовні комп’ютерні системи, які мають один центральний процесор, здатний обробляти тільки один потік послідовно виконуваних інструкцій. В даний час практично всі високопродуктивні системи мають більше одного центрального процесора, однак, кожен з них виконують незв’язані потоки інструкцій, що робить такі системи комплексами SIMD–систем, що діють на різних просторах даних. Для збільшення швидкості обробки команд і швидкості виконання арифметичних операцій може застосовуватися конвеєрна обробка. У разі векторних систем векторний потік даних слід розглядати як потік з одиночних неподільних векторів. Прикладами комп’ютерів з архітектурою SISD є більшість робочих станцій Compaq, Hewlett–Packard і Sun Microsystems.

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

SIMD – одиночний потік команд і множинний потік даних. Ці системи зазвичай мають велику кількість процесорів, в межах від 214 до 16384, які можуть виконувати одну і ту ж інструкцію щодо різних даних в жорсткій конфігурації. Єдина інструкція паралельно виконується над багатьма елементами даних. Прикладами SIMD машин є системи CPP DAP, Gamma II і Quadrics Apemille. Іншим підкласом SIMD–систем є векторні комп’ютери. Векторні комп’ютери маніпулюють масивами схожих даних подібно до того, як скалярні машини обробляють окремі елементи таких масивів. Це робиться за рахунок використання спеціально сконструйованих векторних центральних процесорів. Коли дані обробляються за допомогою векторних модулів, результати можуть бути видані на один, два або три такти частотогенератора (такт частотогенератора є основним тимчасовим параметром системи). При роботі у векторному режимі векторні процесори обробляють дані практично паралельно, що робить їх у кілька разів швидшими, ніж при роботі в скалярному режимі. Прикладами систем подібного типу є, наприклад, комп’ютери Hitachi S3600.

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

5.Екстраполяційні алгоритми

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

Розв’язання задачі Коши для систем звичайних диференціальних рівнянь першого порядку [13]:

ДР першого порядку

розглядається при переході з точки Xn в точку Xn+H, де H – базова довжина шагу.

За рекурентними співвідношеннями визначають значення для довільних i, j за схемою локальної поліноміальної екстраполяції Ейткена–Невіла.

Обчислення за схемою поліноміальної екстраполяції Ейткена–Невіла

Рисунок 2 – Обчислення за схемою поліноміальної екстраполяції Ейткена–Невіла

Існуює декілька варіантів обчислень елементів екстраполяційної таблиці Эйткена-Невіла. Перший полягає у обмеженні розмірності СЗДР, тобто кожен процесор групи передає відповідному процесору сусідньої групи усі компоненти свого вектору апроксимації розв’язання. Другий варіант полягає в наступному: в кожній групі процесорів рівно один процесор відповідатиме за передачу даних між групами [13].

З двох розглянутих варіантів отримання екстраполяційної таблиці, саме другої підходить для пропорційного розбиття процесорів, оскільки не вимагає додаткового сортування даних із–за нерівномірності їх розподілу. У загальному вигляді проблема розбиття процесорного поля на групи, що забезпечують оптимальне розв’язання задачі балансування завантаження багатопроцесорної системи сформульована в термінах комбінаторної оптимізації. Точне розв’язання задач цього класу за прийнятний час неможливе, оскільки задача являється NP-складною, тому пропонуються близькі до оптимального раціональні розв’язання наближеними евристичними методами.

Висновки

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

  1. Розглянуті підходи до паралельної реалізації методів розв’язання багатовимірних задач Коші, що ґрунтуються на використанні екстраполяції Річардсона.
  2. Удосконалено паралельний екстраполяційний алгоритм.

Подальші дослідження направлені на наступні аспекти:

  1. Якісне вдосконалення паралельного екстраполяційного алгоритму.
  2. Аналіз результатів, що будуть отримані під час проведення експериментів на паралельній обчислювальній системі.

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

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

  1. Grand Challenges: Science, Engineering and Societal Advances Requiring Networking and Information Technology Research and Development [Электронный ресурс] // Report by Interagency Working Group on Information the Technology Research and Development. – Режим доступа: http://www.nitrd.gov/pubs/200311_grand_challenges.pdf
  2. The Networking and Information Technology Research and Development Program fy 2013. [Электронный ресурс] // Reports National Coordination Office for Networking and Information Technology Research and Development. – Режим доступа: http://www.nitrd.gov/pubs/2013supplement/FY13NITRDSupplement.pdf
  3. Хайрер Э. Решение обыкновенных дифференциальных уравнений. Жесткие задачи. // Э. Хайрер, Г. Ваннер. – М.: Мир, 1999. – 685с. – ISBN 5–03–003117.
  4. Хайрер Э., Нерсетт С., Ваннер. Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи. // Э. Хайрер, С. Нерсетт, Г. Ваннер. – М.: Мир, 1990. – 512с. – ISBN 5–03–001179–X.
  5. Холл Дж. Современные численные методы решения обыкновенных дифференциальных уравнений // Дж.Холл. – М.: Мир, 1979. – 312 с.
  6. Голуб Д. Ван Лоун Ч. Матричные вычисления // Д.Голуб, Ван Лоун Ч. – М.: Мир, 1999. – 548 с.
  7. Гергель В.П. Теория и практика параллельных вычислений // В.П. Гергель – М.: Мир, 2007 – 424 c.
  8. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления // В.В. Воеводин, Вл.В. Воеводин – БХВ–Петербург, 2004 – 160 с.
  9. Дмитриева О.А. Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов/ О.А. Дмитриева // Искусственный интеллект, 2012. – № 4. – С. 77–88.
  10. Фельдман Л.П., Назарова И.А. Применение технологии локальной экстраполяции для высокоточного решения задачи Коши на SIMD–структурах / Л.П. Фельдман, И.А. Назарова // Научные труды Донецкого национального технического университета. Выпуск 70. Серия: «Информатика, кибернетика и вычислительная техника» (ИКВТ–2003) – Донецк: ДонНТУ, 2003.
  11. Дмитриева О.А. О приведении матриц расчетных коэффициентов коллокационных методов со старшими производными к диагональному виду/ О.А. Дмитриева // Наукові праці – Донецк: ДонНТУ, 2013.
  12. Михайлова Т.В. Оценка эффективности высокопроизводительных вычислительных систем с использованием аналитических методов/Т.В. Михайлова// Материалы 2–й международной научно–технической конференции "Моделирование и компьютерная графика", г. Донецк, 10–12 октября 2007 г.
  13. Фельдман Л.П., Назарова І.А. Паралельні однокрокові методи чисельного розв’язання задачі Коші/Л.П. Фельдман, І.А. Назарова. – Донецьк: «ДВНЗ» ДонНТУ, 2011. – 185 с.
  14. Emerson D.R. Introduction to Parallel Computers: Architecture and Algorithms / D.R. Emerson // High Performance Computing in Fluid Dynamics – London, 1996. – 42 p.