Щеглов Максим Ігорович

Реферат

1. Введення
2. Актуальність теми
3. Мета й задачі розробки та дослідження
4. Предмет розробки та дослідження
5. Практичне значення отриманих результатів
6. Паралельні багатокрокові блокові методи чисельного рішення задачі Коші для ОДУ
• Опис паралельних багатокрокових блокових методів чисельного рішення завдання Коші для ОДУ
• Погрішність апроксимації блокових методів
• Оцінка ефективності паралельних багатокрокових блокових методів чисельного рішення завдання Коші для ОДУ
7. Висновки
8. Список використаної літератури

Аналіз та оцінка ефективності паралельних багатокрокових блокових методів розв’язання ЗДР на кластері

Введення

      Одним з найважливіших напрямків розвитку обчислювальних технологій є паралельні обчислення. В останні роки максимальна продуктивність існуючих паралельних обчислювальних систем істотно зросла. Радикально змінилася технологічна база й архітектура. Але головною перешкодою до впровадження практично всіх паралельних архітектур є відсутність паралельних алгоритмів. Доводиться шукати зовсім нові методи для рішення різних завдань, які орієнтовані на ефективне використання в багатопроцесорних системах, або модернізувати існуючі алгоритми. Вже в найближчому майбутньому перспективи розвитку суперкоппьютерів будуть визначатися успіхами не стільки електроніки, скільки обчислювальної математики.
      Мова, у першу чергу, іде про звичайні диференціальні рівняння та системи диференціальних рівнянь, які є основою сучасних наукових і інженерних завдань. Багато чисельних методів рішення доводиться переглядати, а від деяких повністю відмовлятися. У той же час, цілий ряд питань, які були несуттєві або взагалі не виникали при проведенні послідовних обчислень, придбали виняткову важливість для ефективного й правильного використання обчислювальних систем.
      Досвід експлуатації сучасних високопродуктивних комп'ютерних систем показав, що ефективність їхнього застосування істотно залежить від узгодження структури паралельних обчислювальних систем із класом розв'язуваних завдань і використовуваних чисельних методів. Ці обставини послужили основою для адаптації відомих і пошуку нових методів рішення систем звичайних диференціальних рівнянь на паралельних системах з MІMD архітектурою.
      

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

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

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

      Ціль роботи: аналіз рішення задачі Коші багатокроковим паралельним блоковим методом на обчислювальному кластері, розробка й реалізація програмної системи, що дозволяє одержати рішення даної задачі.
      Задачі: вивчення багатокрокових паралельних блокових методів рішення задачі Коші, рішення задачі Коші багатокроковим паралельним блоковим методом на обчислювальному кластері з використанням Microsoft Visual Studio 2005 і технології Message Passing Interface (MPI).

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

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

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

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

Паралельні багатокрокові блокові методи чисельного рішення завдання Коші для ОДУ

      У даній главі розглядаються основи розпараллелювання багатокрокових алгоритмів рішення завдання Коші для ОДУ. Виведемо формули й знайдемо наближене рішення завдання Коші для диференціального рівняння першого порядку:
яке задовольняє початковій умові
      Розіб'ємо множину M точок рівномірної сіткиt_m, m=1,2,…,M и t_M=T із кроком τ на N блоків, що містять по k k точок, при цьому kN ≥ M. Нехай:

• i =0,1,…,k   - номер точки для кожного блоку;
• t_n,i - точка n –го блоку з номером i;
• крапка t_n,0  - початок блоку n, а t_n,k – кінець блоку;
• t_n,k = t_n+1,0 .;
• початкова точка в блок не включається.

      При чисельному рішенні завдання Коші для кожного наступного блоку нові k значень функції обчислюються одночасно. Ця особливість методів погодиться з архітектурою паралельних обчислювальних систем, а також дозволяє обчислювати коефіцієнти різницевих формул не в процесі інтегрування, а на етапі розробки методу, що значно збільшує ефективність рахунку[3,5].

Опис паралельних багатокрокових блокових методів чисельного рішення завдання Коші для ОДУ

      У випадку багатокрокового блокового методу початковий блок буде містити крапки сітки, у яких початкові значення наближеного рішення необхідні для продовження розрахунків.
      Схема розбивки на блоки для m-крокового k-точкового методу представлена на рисунку 1.1.



      У загальному випадку рівняння багатокрокових різницевих методів для блоку з k точок при використанні обчислених значень наближеного рішення в m попередньому блоку вузлах, можна записати у вигляді:

      Визначити коефіцієнти a_i,j и b_i,j можна апроксимуючи подінтегральну функцію з одним змінним f(x,y(x)) алгебраїчним інтерполяційним багаточленом Лагранжа Lk(t), що у вузлах x_n,j-m приймає значення f(x_n,j-m,y(x_n,j-m)), j=1,2,...,m+k. Далі необхідно проінтегрівати його в межах (tn, tn+iτ), i=1,k

У підсумку будуть отримані необхідні формули.
      Для обчислення наближених значень рішення завдання Коші коллокаціонним багатокроковим блоковим методом необхідно вирішити нелінійну систему рівнянь (1.3). Можна для цього використати наступний ітераційний процес:

      Закріпимо кожний процесорний елемент за точкою n-го блоку, що обчислюється. Тоді кожний з k процесорів спочатку буде обчислювати значення початкового вектора за методом Адамса-Башфорта.
      Далі кожний процесор буде знаходити відповідного вектора зі значеннями правих частин f_n,j=f(t_n+jτ,u_n,j)) . Після чого буде здійснюватися обмін між процесорними елементами для виконання подальших обчислень. Потім по заданим формулам будуть визначатися значення вектора наближеного рішення. Якщо кількість процесорів буде менше, ніж розмірність блоку, то деякі процесорні елементи будуть послідовно обчислювати значення декількох крапок блоку, що в підсумку збільшить загальний час обчислень.
      При рішенні системи диференціальних рівнянь можливі два варіанти розподілу процесорів:

• для кожного рівняння виділяється P₁=P/k процесорів, де P- загальне число процесорів, а k- число рівнянь у системі. P₁ процесорів беруть участь у паралельному обчисленні значень блоку: m/P₁ значень крапок блоку обчислюються на кожному із процесорів
• для кожного блоку виділяється P₁=P/m процесорів, де P- загальне число процесорів, а m- число крапок у блоці. k/P₁ рівнянь системи обчислюються на кожному із процесорів

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

• вектор початкових наближень функції U_i,j;
• вектор значень ОДУ для сіткових функцій у вузлах попереднього блоку F_i,j;
• вектор значень елементів ψ i,j , що є і-им стовпцем матриці Ψ;
• вектор значень елементів φ i,j , що є і-им стовпцем матриці Φ;
• вектор значень елементів F i,j , що є і-ом рядком матриці F.

Погрішність апроксимації блокових методів

      Коефіцієнти a_i,j и b_i,j вибираються таким чином, щоб різницеве рівняння (1.3) апроксимувало диференціальне рівняння з досить гладкою правою частиною з деяким порядком s. Це означає, що нев'язання ρ , що виходить після підстановки точного рішення y(x) диференціального рівняння в різницеве рівняння (1.3).

Величина

      Називається погрішністю апроксимації диференціального рівняння різницевим рівнянням (1.3).
      Якщо скористатися формулою Тейлора для y(x_n+i) и y'(x_n+i) , то погрішність апроксимації буде мати вигляд:

      З (1.8) видно, що для того, щоб величина r_n,i мала порядок O(h⁵) необхідне виконання умов

Оцінка ефективності паралельних багатокрокових блокових методів чисельного рішення завдання Коші для ОДУ

      Критеріями оцінки паралельних алгоритмів, як правило, виступають дві величини:

• прискорення S_p
• ефективність E_p

Уведемо наступні позначення:

• T₁- час виконання послідовного алгоритму;
• T_p – час виконання паралельного алгоритму на k процесорів;
• T_f – час обчислення значення функції f(t,x);
• T_сл – час виконання операції додавання;
• T_ум – час виконання операції множення;
• T_об – час передачі числа сусідньому процесору.

      Прискорення (speedup), одержуване при використанні паралельного алгоритму для p процесорів, у порівнянні з послідовним варіантом виконання обчислень визначається величиною тобто як відношення часу рішення завдань на скалярної ЕОМ до часу виконання паралельного алгоритму (величина n застосовується для параметризації обчислювальної складності розв'язуваного завдання й може розумітися, наприклад, як кількість вхідних даних завдання).
      Ефективність (effіcіency) використання паралельним алгоритмом процесорів при рішенні завдання визначається співвідношенням (величина ефективності визначає середню частку часу виконання алгоритму, протягом якої процесори задіяні для рішення завдання).
      Для оцінки прискорення m-крокового k-точкового блокового методу зрівняємо час його виконання на мультипроцесорній системі з часом виконання алгоритму m-крокового методу Адамса-Башфорта на однопроцесорній ЕОМ. Метод Адамса-Башфорта можна розглядати як багатокроковий однокрапковий блоковий метод. Послідовне k-кратне застосування формул Адамса-Башфорта дозволяє обчислити наближене рішення в тих же k вузлах блоку, у яких паралельно за k ітерацій може бути обчислене рішення m-кроковим k-крапковим блоковим методом. У цьому випадку час обчисленнь буде приблизно однаковим. Точність наближеного рішення, отриманого m-кроковим k-крапковим блоковим методом, має порядок O(τ^m+k), а точність наближеного рішення, отриманого по m кроковій формулі Адамса-Башфорта, має порядок O(τ^m+1).
      Для того, щоб одержати рішення з однаковою точністю для методу Адамса-Башфорта необхідно, щоб кроки сітки для методу Адамса-Башфорта й m-крокового k-крапкового блокового методу задовольняли умові
      де τ_A,B крок сітки рішення задачі методом Адамса-Башфорта, а τ_m,k крок сітки рішення цієї ж задачі багатокроковим блоковим методом.
       Наприклад: для рішення завдання 4-кроковим 4-крапковим блоковим методом обраний крок τ_m,k =0.01, тоді для забезпечення тієї ж точності рішення методом Адамса-Башфорта необхідно взяти крок τ_A,B =0.0063.
      Час виконання послідовного алгоритму у всіх k вузлах:

      Час паралельного обчислення наближених значень рішення на лінійці процесорів:

      Слід зазначити, що на динамічні характеристики паралелізму впливають латентність і час передачі одного слова. Отримана залежність коефіцієнта ефективності від латентності є обратнопропорційною (при зменшенні величини латентності збільшується эффективнность алгоритму рішення завдання) і наведена на рисунку 1.2.
      З ростом величини латентності час, затрачуваний на обмін даними між процесами збільшується, а ефективність паралельних обчислень зменшується. При розрахунку прискорення й ефективності багатокрокового блокового методу найбільший вплив на показники робить час обчислень правої частини рівнянь, тому що час виконання арифметичних операцій і обміну значно менше часу обчислення правої частини. Залежність коефіцієнтів прискорення й ефективності від часу обчислення правої частини рівняння Tf і числа точок блоку k наведені на рисунках 1.3, 1.4.

Прискорення k-точкового багатокрокового паралельного алгоритму можна вважати приблизно рівним

      а ефективність буде дорівнювати

      При цьому характеристики паралелізму в системах з кільцевою структурою виявляються гірше, ніж у системах з топологією гіперкуб і тор, що свідчить про сильний вплив час обміну даними між процесорами в паралельних обчислювальних системах. Між часом обчислення правої частини й ефективністю існує пряма залежність: при збільшенні трудомісткості обчислень правих частин, ефективність розглянутих методів збільшується. Також слід зазначити, що у зв'язку з тим, що число точок блоку пов'язане із числом використовуваних процесорів, при збільшенні числа крапок у блоці зростає коефіцієнт прискорення S і зменшується коефіцієнт ефективності E[4].

Висновки

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

Список використаної літератури

1. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, 2001

http://window.edu.ru/window_catalog/pdf2txt?p_id=6579

2. Хайрер Э., Нёрсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи: Пер. с англ. – М.: Мир, 1990. – 512с.
3. Фельдман Л.П. Сходимость и оценка погрешности параллельных одношаговых блочных методов моделирования динамических систем с сосредоточенными параметрами // Научные труды ДонНТУ. Серия: Информатика, моделирование и вычислительные методы, (ИКВТ-2000), выпуск 15: Донецк: ДонНТУ, 2000, с. 34-39.

   scg.donntu.ru/2005/scg_2005.pdf

4. Дмитриева О.А. Модели отображения многошаговых алгоритмов на параллельные вычислительные системы с топологией гиперкуб//Науковi працi Донецького державного технiчного унiверситету. Серiя: Проблеми моделювання та автоматизації проектування динамічних систем, випуск 46: – Донецк:, 2002. с. 154-161.
5. Фельдман Л.П., Дмитриева О.А. Разработка и обоснование параллельных блочных методов решения обыкновенных дифференциальных уравнений на SIMD-структурах. //Научн. тр. Донецкого государственного технического университета. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. – Севастополь: «Вебер», 2001. – с. 70-79.
6. Kazufumi OZAWA, Susumu YAMADA “Parallel block methods for solving nonstiff equations with stepsize control“,Graduate school of information science, Tohoku University, 2006

http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/60205/1/0944-2.pdf

7. Воеводин В.В.,"Вычислительная математика и структура алгоритмов.".-М.: Изд-во МГУ, 2006.-112 с.

http://www.parallel.ru/info/parallel/voevodin/

8. van der Houwen P.J.,“Parallel Step-by-Step Methods”, CWI Amsterdam, 1991

http://ftp.cwi.nl/CWIreports/1991/NM-R9116.pdf

9. Самарский А.А., Гулин А.В. Численные методы.- М.: Гл. ред. физ.-мат. лит., 1989.– 432 с.
10. Воеводин В.В. Математические основы параллельных вычислений. - М.: Изд-во МГУ, 1991. - 345 с.