Макашов А
Якщо у той самий час виконуються одночасно кілька операцій обробки даних, то такі обчислення називаються паралельними[1]. Потреба вирішення складних прикладних завдань з великим обсягом обчислень та принципова обмеженість максимальної швидкодії "класичних" - за схемою фон Неймана - ЕОМ призвели до появи багатопроцесорних обчислювальних систем. Використання таких засобів обчислювальної техніки дозволяє суттєво збільшувати продуктивність ЕОМ за будь-якого рівня розвитку комп'ютерного устаткування. При цьому, однак, необхідно "паралельне" узагальнення традиційної - послідовної технології вирішення завдань на ЕОМ. Так, чисельні методи у разі багатопроцесорних обчислювальних систем повинні проектуватися як системи паралельних та взаємодіючих між собою процесів, що допускають виконання на незалежних процесорах. Застосовувані алгоритмічні мови та системне програмне забезпечення повинні забезпечувати створення паралельних програм, організовувати синхронізацію та взаємовиключення асинхронних процесів.
Проблема створення високопродуктивних обчислювальних систем є одним із найбільш складних науково-технічних завдань сучасності і її вирішення можливе лише при концентрації зусиль багатьох талановитих вчених та конструкторів, що передбачає використання всіх останніх досягнень науки і техніки та потребує значних фінансових інвестицій.
1. Типові структури ліній зв'язку паралельних ВС
Топологія ЗС – це спосіб з'єднання комп'ютерів у єдину ЗС.
До типових топологій відносять[2]:
- Лінійка (linear array or farm) - являє собою лінійний масив процесорів (рис.1).
Система, в якій кожен процесор має лінії зв'язку тільки здвома сусідніми (з попереднім та наступним) процесорами; така схема є, з одного боку, просто реалізованої, з другого боку, відповідає структурі передачі при вирішенні багатьох обчислювальних завдань (наприклад, з організацією конвеєрних обчислень);
- Кільце (ring) – дана топологія аналогічна топології лінійка про те, що перший і останній комп'ютер з'єднані (рисунок 2). Зв'язки можуть бути односпрямованими або двоспрямованими. [6] Кільцева структура зберігає переваги, і навіть скорочує максимальну відстань між процесорами – n /2 [5].
- Грати (2D-решітка, матриця, сітка – mesh) – система, в якій граф ліній зв'язку утворює прямокутну сітку, тобто процесори розташовані у вигляді правильної двомірної решітки і кожен процесор (крім крайніх) з'єднаний з чотирма сусідами (рисунок 3)
Перевагою такої схеми є простота, а недолік полягає в тому, що при обміні між віддаленими процесорами дані повинні пройти через низку проміжних процесорів.
- Гіперкуб (hypercube) - дана топологія представляє окремий випадок решітки, коли по кожній розмірності сітки є тільки два процесори (тобто гіперкуб містить n = 2 N процесорів при розмірності N).
Також може бути схема з'єднання процесорів у чотиривимірному кубі. Ця схема наведена малюнку 5.
Топологія гіперкуб надає можливість моделювати деякі важливі типи зв'язків: лінійка, кільце, грати.
- Кліка або повний граф (completely - connected graph or clique) - система, в якій зв'язки процесорів утворюють повний граф.
- Зірка ( star ) – система, де всі процесори мають лінії зв'язку з деякими керуючим процесором (рисунок 7). Ця топологія є ефективноюз організацією централізованих схем паралельних обчислень.
- "Товсте дерево" ("fat-tree", hypertree) - архітектура процесори в якій локалізовані в листі дерева, тоді як внутрішні вузли дерева скомпоновані у внутрішню мережу. Піддерев'я можуть спілкуватися між собою, не торкаючись вищих рівнів мережі. (Рисунок 8, 9)
При цьому ця топологія є найбільш ефективною.
Реальні високопродуктивні паралельні обчислювальні системи зазвичай використовують кілька різних схем з'єднання процесорів. Це дозволяє поєднувати найкращі якості відомих топологій та мінімізувати недоліки. А також, оскільки спосіб з'єднання процесорів один з одним більше впливає на продуктивність кластера , ніж тип процесорів, що використовуються в ній, то може виявитися більш доцільним створити систему з більшої кількості дешевих комп'ютерів, ніж з меншої кількості дорогих [8].
Розв'язання різних прикладних завдань потребує вирішення звичайних диференціальних рівнянь чи систем звичайних диференціальних рівнянь високого порядку. Скорочення часу вирішення, отже, і часу моделювання, можливе під час використання паралельних обчислювальних систем, ефективність роботи яких істотно залежить від характеристик застосовуваних паралельних алгоритмів.
2. Численні методи вирішення завдань Коші для ОДУ
Звичайним диференціальним рівнянням (ОДУ) називається рівняння виду [3] (до нього входять: незалежна змінна t, невідома x та її похідні з t )
де, як правило, позначається значення невідомої функції літерою x, незалежної змінної - t (і інтерпретувати її як час), похідних від x до t - x', x'', . x(m). Також використовується скорочене позначення J(m)x = (x, x', .x(m))— цей вектор називають струменем або джетом m-го порядку функції x у точці t. До диференціальних рівнянь може входити також набір C = (C1, C2, .Cp) довільних постійних (параметрів) [9].
У свою чергу, порядком ОДУ називається порядок старшої похідної функції, що шукається.
тобто. рішення x(t) входить неявним чином, причому кількість констант інтегрування дорівнює порядку ОДУ
Загальним рішенням ОДУ називається функція
що зв'язує незалежну змінну t і n констант інтегрування C i , тобто. рішення x(t) визначається явним чином.
Для визначення констант інтегрування І задаються додаткові умови в кількості, що дорівнює кількості констант інтегрування або порядку ОДУ.
Якщо додаткові умови підставити вихідне рівняння і вирішити отриману систему щодо С i , а потім підставити в загальний інтеграл, отримаємо приватне рішення або приватний інтеграл
Аналогічні процедури із загальним рішенням (3) дають приватний інтеграл.
Якщо всі додаткові умови задаються в одній точці x 0 , то сукупність ОДУ та додаткових умов називають завданням Коші для ОДУ, що розглядається. І тут додаткові умови називають початковими умовами.
Якщо додаткові умови задаються більш ніж в одній точці, то сукупність ОДУ і додаткових умов називають крайовим завданням Коші для ОДУ, що розглядається, а додаткові умови називають граничними або крайовими умовами.
3. Багатокрокові методи вирішення завдань Коші для ОДУ
Методи рішення ОДУ бувають однокрокові та багатокрокові. До однокрокових відносяться: метод Ейлера, метод Рунге – Кутти та ін., а до багатокрокових: лінійні багатокрокові різницеві методи, у тому числі методи Адамса-Башфорту та методи Адамса-Мултона.
У багатокроковихМетоди підвищення точності обчислення відбувається за рахунок використання інформації про поведінку рішення на попередніх кроках.
Загальна схема побудови m-крокових різницевих методів, що використовуються для наближеного розв'язання задачі Коші [4]
виглядає наступним чином
Найпростіші та найчастіше зустрічаються обчислювальні правила для багатокрокових методів мають вигляд:
3.1 Явні багатокрокові методи Адамса-Башфорту
Розглянемо випадок за m =2. У цьому випадку відповідний багаточлен Ньютона матиме вигляд:
Підставивши його у формулу (7) ми отримаємо:
А після інтегрування формула для обчислення наближеного рішення матиме вигляд:
3. 2 Неявні багатокрокові методи Адамса-Мултона
Наведемо інтерполяційні формули Адамса різних порядків точності:
двокроковий неявний різницевий метод Адамса-Мултона
трикроковий неявний різницевий метод Адамса - Мултона
Визначення порядку апроксимації неявних методів Адамса-Мултона виконується аналогічно до визначення нев'язки методів Адамса-Башфорту.
Похибка апроксимації трьох крокового методу Адамса – Мултона дорівнює
Насправді зазвичай вирішують рівняння (9), а використовують спільно явну і неявну формули (метод Адамса-Бошфорта-Мултона), що зумовлює методу прогнозу і корекції. Одним із широко використовуваних методів прогнозу та корекції є об'єднання методів Адамса четвертого порядку точності.
За такої послідовності обчислень цей метод є явним
4 Паралельні методи чисельного розв'язання задачі Коші для ОДУ
У цьому розділі будуть розглянуті основи розпаралелювання однокрокових та багатокрокових алгоритмів методів вирішення задачі Коші для ОДУ [5].
Для простоти розуміння тависновку формул, розглядатимемо розв'язання задачі Коші для одного звичайного диференціального рівняння першого порядку
У загальному випадку рівняння багатокрокових різницевих методів для блоку k точок при використанні обчислених значень наближеного рішення в m попередніх блоку вузлах.
5 Оцінка паралелізму багатокрокових блокових методів
Для оцінки прискорення m-крокового k-точкового блочного методу порівняємо час його виконання на мультипроцесорній системі з часом виконання алгоритму m-крокового методу Адамса-Башфорту на однопроцесорній ЕОМ. [5] Метод Адамса-Башфорт можна розглядати як багатокроковий одноточковий блоковий метод. Послідовне k-кратне застосування формул Адамса-Башфорту дозволяє обчислити наближене рішення в тих же k вузлах блоку, в яких паралельно за k ітерацій може бути обчислено рішення m-кроковим k-точковим блоковим методом. У цьому випадку час обчислення приблизно дорівнює. Точність наближеного рішення, отриманого m -кроковим k -точковим блоковим методом, має порядок O(точність наближеного рішення, отриманого за m крокової формули Адамса-Башфорту, має порядок O(Тому для отримання рішення з однаковою точністю для методу Адамса-Башфорту треба, щоб кроки сітки для методу Адамса-Башфорту і m-крокового k-точкового блочного методу задовольняли умові
ЕОМ і порівняємо часи розв'язання задачі m-кроковим k-точковим блоковим методом на однопроцесорній лінійці k процесорів. Закріпимо за кожним вузлом блоку процесор. Використовуючи позначення, введені у п. 7.3. отримаємо для часу обчислення одному процесорі з локальної точністю O( у всіх k вузлах блоку за формулами
Час паралельного обчислення наближених значень рішення на лінійці з процесоріва точністю для всіх вузлів блоку складе
Прискорення паралельних багатоточкових алгоритмів можна обчислити за формулою
Якщо враховувати лише час обчислень правої частини рівнянь, т.к. часи виконання арифметичних операцій та обміну значно менше часу обчислення правої частини, то прискорення k точкового багатокрокового паралельного алгоритму можна вважати приблизно рівним
і ефективність дорівнюватиме
Звідси випливає, що при розв'язанні на однопроцесорній ЕОМ рішення m-кроковим k-точковим блоковим методом вимагатиме менше часу, ніж вирішення цього завдання відповідним методом Адамса - Башфорта.
Наразі все частіше і частіше доводиться торкатися питань обчислювальної потужності систем. Одним із способів підвищення цієї потужності є організація паралельних систем.
У цій роботі розглянуто паралельні алгоритми розв'язання задачі Коші, як багатокрокових, так і однокрокових. Підвищення продуктивності паралельних алгоритмів відбувається з допомогою одночасного обчислення кількох значень. У свою чергу, підвищення точності обчислень багатокрокових методів відбувається за рахунок обліку знайдених рішень у знаходженні нових. Т.о. паралельні багатокрокові методи мають високу продуктивність і високу точність обчислень.