Смекни!
smekni.com

Розробка алгоритму та програми чисельного розвязку систем лінійних алгебраїчних рівнянь з розрідженою (стр. 7 из 9)

Остаточно з урахуванням (2.7) уся сума S5 має такий вигляд:

Із представленого вище алгоритму видно, що обчислювальні витрати на побудову сум добутків

і
різні. Друга сума будується значно швидше. Це пов'язано з тим, що при побудові першої суми необхідно проводити додатковий порівняльний аналіз номерів вузлів, розміщених у векторі
. При розгляді процедур алгоритму передбачалося, що всі необхідні дані розташовуються в оперативній пам'яті комп'ютера. Довжина одномірних масивів, у яких розміщаються вектори
,
і
, залежить від структури розглядаємої кінцево-елементної моделі. У табл. 2.3 представлені дані по розмірності цих векторів для трьох типів кінцево-елементних моделей, побудованих у результаті розбивки одиничного куба на 20-вузлові квадратичні елементи. Куб розбивався в наступних пропорціях: 5:5:5 (КЕМ № 1), 10:10:10 (КЕМ № 2) і 20:20:20 (КЕМ № 3).

Таблиця 2.3 – Розмірність векторів КЕМ

Номер КЕМ Число вузлів Число елементів
1 756 125 16079 16071 16079
2 4961 1000 121709 121691 121709
3 35721 8000 946619 946619 946619

Порівняння даного алгоритму з алгоритмами, розглянутими в роботах [17–19], показує наступне. Для реалізації запропонованого алгоритму потрібно більше оперативної пам'яті, оскільки для координування ненульових елементів використовуються не два масиви (вектори номерів рядків і стовпців), а чотири. Додаткові вектори

і
, розмірності яких не перевищують числа діагональних елементів, дозволяють локалізувати зони пошуку елементів-співмножників при побудові сум (2.6) і (2.8). За рахунок цього досягається економія часових витрат на розв’язок СЛАР.

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


3 Оптимізація обчислень

Задача вирішення систем рівнянь виду

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

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

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

Пропонується будувати взаємодію між процесами по наступному принципу. Є деякий процес, який одержує дані від користувача. Він проводить попередню обробку цих даних. Потім процес формує повідомлення і розсилає їх необхідному числу допоміжних процесів, які виконують безпосередні обчислення. Відповідь повертається першому процесу у вигляді повідомлень від допоміжних процесів. Тут відбувається аналіз результатів обчислень і, при необхідності, процедура повторюється. Такий принцип взаємодії процесів зветься «керуючий-робітники». Перший процес є керуючим, допоміжні процеси – це робітники [23].

Існує кілька технологій побудови розподілених обчислювальних систем. Одна з перших, технологія RPC (Remote Procedure Call), заснована на віддалених викликах процедур. Процесу дозволяється викликати процедури, реалізовані на іншому, віддаленому комп'ютері. При цьому параметри процедури передаються на віддалений комп'ютер, там здійснюється виконання процедури і результати вертаються в місце виклику.

Технологія COM (Component Object Model) – це об'єктна модель компонентів. Вона застосовується для зв'язку між компонентами і програмами, а також при описі API і взаємодії різних мов і середовищ програмування. Одним з головних аспектів технології COM є реалізація клієнт-серверних додатків за допомогою інтерфейсів. В COM-програму входять COM-сервер, COM-клієнт і COM-інтерфейс.

COM-сервер – програма або бібліотека, яка надає деякі служби програмі-клієнтові. COM-сервер містить один або кілька COM-об'єктів. Кожний COM-об'єкт реалізує одну або кілька служб. Кожна служба описується інтерфейсом.

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

COM-інтерфейс – абстрактний клас, що описує властивості і методи COM-об'єкта. Клієнт через інтерфейс об'єкта може використовувати його методи і властивості як свої власні.

Існує також технологія CORBA (Common Object Request Broker Architecture) – узагальнена архітектура брокера об'єктних запитів. Дана технологія також заснована на ключовому понятті інтерфейсу. Об'єкт надає службу. Клієнт звертається до неї, використовуючи інтерфейс.

У технологіях COM і CORBA реалізована ідея розподілених об'єктів (distributed objects). При цьому інтерфейс служить універсальним засобом взаємодії. Розподілені об'єкти розміщаються на різних комп'ютерах. Коли процес викликає метод, реалізація інтерфейсу на машині з процесом перетворює виклик методу в повідомлення, передане об'єкту. Об'єкт виконує запит і повертає результати. Реалізація інтерфейсу перетворює відповідне повідомлення в повертаєме значення, яке передається викликаючому процесу.

Реалізація розподіленої системи, що розв’язує систему рівнянь виду

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

У свою чергу, COM-сервера містять COM-об'єкти, які і реалізують функціональність, що забезпечує розв’язок систем виду

ітераційними методами.

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


4. Чисельні експерименти

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

Таблиця 4.1 – Конфігурація тестового комп'ютера

Мікропроцесор Intel Core 2 Duo E7200 (Socket LGA775, 3172 МГц)
Оперативна пам'ять 4*(Kingston ValueRAM KVR667D2N5/1G) (4 ГБ)
Системна плата ASUS P5K (Socket LGA775, Intel P35+ICH9)
ОС Microsoft Windows Vista Ultimate x64 SP1

4.1 Пружне деформування тонкостінної просторової рами