Алгоритмічні методи підвищення ефективності паралельних обчислювальних систем при вирішенні багатомірних динамічних задач

Размещено на http://www.allbest.ru/

Донецький національний технічний університет

УДК 519.711.3:681.5.01

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Алгоритмічні методи підвищення ефективності паралельних обчислювальних систем при вирішенні багатомірних динамічних задач

05.13.13 - Обчислювальні машини, системи та мережі

Дмитрієва Ольга Анатоліївна

Донецьк 2001

Загальна характеристика роботи

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

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

Потрібно зазначити, що великий внесок в розв'язання проблем створення нових багатопроцесорних архітектурних реалізацій внесли такі відомі у нас в країні і за рубежем вчені, як Самофалов К.Г., Забродін О.В., Котов В.Є. Питанням розпаралелювання обчислень присвячені роботи Ortega J., Воєводіна В.В, Worland Р. Методи підвищення ефективності паралельних обчислювальних систем досліджувалися в роботах Dongarra J., Боюна В.П., Маліновського Б.М. та б. інш. Однак, в зв'язку з масовим поширенням паралельних обчислювальних систем, роботи в цьому напрямі не втрачають своєї актуальності і вимагають подальшого розвитку. Цим зумовлено і те, що дослідження, проведені в дисертаційній роботі, сприяють підвищенню ефективності паралельних обчислювальних систем при вирішенні задач великої розмірності за рахунок реалізації нових чисельних багатокрокових блокових методів рішення систем звичайних диференціальних рівнянь, використання запропонованих і обгрунтованих рекомендацій по оптимальному розміщенню даних по процесорних елементам, впровадження алгоритмів, що дозволяють провести обчислення на паралельних обчислювальних структурах з різними топологічними характеристиками, типами пам'яті і способами обробки інформації.

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалась протягом 1997-2001 рр. відповідно до планів науково-дослідних робіт ДТ-14-97 “Наукові основи аналізу та оптимізації структур комп'ютерних систем і способів управління паралельними обчислювальними процесами” № держ. реєстрації 0197U008267, (1997-2000), Н-18-95 “Алгоритмічне і програмне забезпечення обчислювальних систем і інформаційних технологій” (1995-2000), ДТ-11-2000 “Наукові основи оптимізації структур високопродуктивних обчислювальних систем і методи реалізації паралельних алгоритмів”, Н-13-2000 “Алгоритмічне і програмне забезпечення високопродуктивних і інтелектуальних обчислювальних систем і мереж” (діють з 2000 р.).

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

Задачі дослідження:

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

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

відображення отриманих методів на паралельні обчислювальні системи SIMD (single instruction multiple data) і MIMD (multiple instruction multiple data) типів з різними топологічними характеристиками, типами пам'яті, розмірами процесорних полів;

Об'єктом дослідження є високопродуктивні паралельні обчислювальні системи з розподіленою пам'яттю, та пам'яттю, що розділяється, базовими топологічними характеристиками яких є 1D, 2D, 3D - тори, гіперкуби та квазіматриці.

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

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

Наукова новизна одержаних результатів полягає в наступному:

узагальнені і обгрунтовані багатокрокові багатоточкові блокові методи рішення задачі Коши для звичайних диференціальних рівнянь;

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

розроблені ітераційні паралельні алгоритми рішення нелінійних різницевих задач, що дозволяють отримувати результати із заданою мірою точності;

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

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

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

Практичне значення одержаних результатів полягає у використанні для розрахунків в багатопроцесорних обчислювальних системах з різними топологічними характеристиками, типами пам'яті і способами обробки інформації багатокрокових багатоточкових блокових методів і алгоритмів відображення. Застосування запропонованих методів для розрахунків дозволяє отримувати більш точне рішення в порівнянні з існуючими методами при однаковому часі рахунку або, при фіксованій точності, значно швидше знаходити рішення. Отримані ефективні паралельні алгоритми визначення початкового відрізка, прискорення і ефективність яких близькі до потенційних, можуть бути рекомендовані для визначення стартових значень в будь-яких системах, які використовують багатокрокові методи. Розроблені методи і математичні моделі були використані при розрахунку динаміки багатоканатних підіймальних установ з метою скорочення часу визначення величин амплітуд і швидкостей коливань динамічних навантажень на шахтах виробничого об'єднання “Красноармійськвугілля”. Також розроблені методи використовуються в учбових процесах кафедри прикладної математики і інформатики Донецького національного технічного університету при викладанні курсів “Високопродуктивні обчислювальні мережі”, “Чисельні методи і пакети” і кафедри математичної фізики Донецького національного університету в курсах “Рівняння математичної фізики” і “Диференціальні рівняння”.

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

Апробація результатів дисертації. Основні положення і результати роботи доповідалися, обговорювалися і дістали позитивну оцінку на

X Міжнародній конференції по обчислювальній механіці та сучасним прикладним програмним системам (ВМСППС'99), присвяченій 275-річчю Російської академії наук, м. Переславль-Залеський, Росія, 7-12 червня 1999 р.;

I Всеросійській конференції “Науковий сервіс в мережі Інтернет”, м. Новоросійськ, 23-27 вересня 1999 р.;

II Всеукраїнській науково-практичній конференції з міжнародною участю “Людина i космос”, м. Дніпропетровськ, 12-15 квітня 2000 р.;

III Міжнародній конференції по нерівновагим процесам в соплах і струменях (NPNJ-2000), присвяченої 70-річчю Московського авіаційного інституту, м. Істра Московської обл., 3-7 липня 2000 р.;

II Всеросійській конференції “Науковий сервіс в мережі Інтернет”, м. Новоросійськ, 18-23 вересня 2000 р.;

- III Мiжнародній молодiжній науково-практичній конференцiї “Людина i космос”, м. Днiпропетровськ.: 18-21 квітня 2001 р.;

семінарах факультету обчислювальної техніки і інформатики Донецького національного технічного університету.

Публікації. За результатами дисертаційної роботи опубліковано 12 друкованих робіт, з них 5 статей опубліковані у виданнях, затверджених ВАК України, і 7 доповідей та тез доповідей в трудах міжнародних наукових конференцій і семінарів.

Структура і обсяг роботи. Дисертаційна робота обсягом 150 машинописних сторінок складається з вступу, п'яти розділів, висновків, списку використаних джерел, який складається зі 126 найменувань і міститься на 14 сторінках, додатка. Дисертація містить 49 рисунків, 4 таблиці.

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

У вступі обґрунтована актуальність теми, сформульовані мета і задачі досліджень, викладені основні наукові і практичні результати, отримані в роботі, наведено відомості про випробування роботи, а також основні положення, які виносяться на захист.

У першому розділі приведені основні принципи організації високопродуктивних обчислювальних структур і систем, орієнтовані на рішення задач великої розмірності. Виконані аналіз і класифікація архітектури паралельних обчислювальних систем. Розглянуті класифікації на основі числа потоків команд і потоків даних, на основі ознак розрядності слів, кількості арифметико-логічних пристроїв і пристроїв управління. Виявлені особливості побудови і базові топологічні характеристики структур багатопроцесорних обчислювальних систем. Проведений аналіз існуючих принципів розпаралелювання математичних моделей для вирішення задач великої розмірності. Оцінені існуючі підходи і стилі паралельного програмування. Проаналізовани існуючі методи рішення задачі Коши для звичайних диференціальних рівнянь (ЗДР) і для систем (СЗДР).

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

Вказані обставини зумовили актуальність питання і стали обгрунтуванням для вибору теми дисертаційної роботи.

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

У другому розділі розроблені і досліджені однокрокові і багатокрокові паралельні алгоритми чисельного рішення систем ЗДР, що використовуються для моделювання складних динамічних систем із зосередженими параметрами і дозволяють значно скоротити час рішення, а, отже, і час моделювання. Алгоритми, що пропонуються, орієнтовані на використання в багатопроцесорних обчислювальних системах SIMD структур з матрицею або лінійкою процесорних елементів (ПЕ), при цьому кожний процесорний елемент може виконати будь-яку арифметичну операцію. У розділі пропонується підхід, що дозволяє розпаралелювати відомі послідовні методи і здійснювати їх відображення на сучасні обчислювальні структури. Алгоритми, що розроблялися, орієнтовані на використання в багатопроцесорних обчислювальних системах SIMD структур типу MasPar 2000/3000.

Якщо математичну модель динамічної системи можна представити у вигляді системи ЗДР з постійними коефіцієнтами і початковими умовами

(1)

де - вектор невідомих,

- заданий вектор, ,

- матриця коефіцієнтів,

то рішення можна отримати послідовно, по крокам, за допомогою наступної формули Рунге-Кутти з контролем погрішності на кроці

N (2)

де - погрішність на кроці

, , (3)

,

,

,

- вибраний крок інтегрування

Тут обчислення значення вектора невідомих вимагає попереднього визначення значень , . Ці вектора, як випливає з формул (3), повинні обчислюватися послідовно. Для однорідної системи можна виразити на черговому кроці повний оператор, що дозволяє визначити значення вектора невідомих на наступному кроці. За допомогою засобів системи Mathematica для однородної системи отримана наступна залежність

(4)

або (5)

де - оператор переходу,

E - одинична матриця.

Отриманий оператор переходу G, який необхідно визначити один раз, до початку обчислень, дозволяє знаходити значення вектора невідомих паралельно. Для визначення операцій, які можуть виконуватись паралельно, будується граф впливу алгоритму. Спочатку виконується множення g_i,j * x_jⁿ у всіх процесорних елементах. Потім здійснюється циклічний зсув отриманих значень і їх складання. Кількість позицій, на яку проводиться черговий зсув, визначається елементами наступного ряду: , де k = найближче ціле зверху []. В результаті в кожному осередку i-го рядка набувається нового значення . Використання систолічного алгоритму множення дозволяє вдвічи скоротити кількість зсувів.

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

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

У підрозділі 3.1 приведене обгрунтування побудови багатокрокових блокових методів. Розглядається задача Коши для ЗДР

f(t,x), x(t₀) = x_0, (6)

рішення якого можна записати у вигляді

(7)

де n - номер блоку, u_n,0 - значення функції в останній точці попереднього блоку,

i - порядковий номер точки в блоці,

значення правої частини

Отримана оцінка для погрішності апроксимації різницевого методу (7), що розглядається на рішенні рівняння (6), яка має вигляд

(8)

Погрішність апроксимації має порядок р, якщо виконані наступні умови

(9)

Система рівнянь (9) для кожного фіксованого i містить р рівнянь і 2k невідомих . При р=2k можна визначити всі невідомі коефіцієнти з системи. Найвищий порядок апроксимації багатокрокового k - точкового блокового методу рівний 2k. Його погрішність у відповідності з (8) визначається формулою

(10)

Елементи bij и ai,j ,i,j=1,2,…,k матриць B и A для будь якої розмірності блоку обчислюються за допомогою пакету Mathematica .

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

Теорема. Нехай права частина рівняння (6) f(t,х) задовольняє умові Ліпшица по другому аргументу з константою L, і r_n - нев'язка багатокрокового - k-точкового блокового методу (7) визначена згідно (8) з оцінкою

. (11)

Тоді при і для погрішності методу має місце оцінка

(12)

Слідство. Якщо різницеве рівняння (7) виконує апроксімацію вихідного рівняння (6), то рішення різницевої задачі (7) сходиться при до рішення вихідної задачі (6), причому порядок точності співпадає з порядком апроксимації.

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

(13)

який дозволяє провести обчислення паралельно для кожного вузла блоку, або за допомогою метода Н'ютону. Після виконання k кроків обчислень по формулах (13) локальна помилка у вузлах блоку буде мати порядок .

Підрозділ 3.3. присвячений проблемі знаходження стартових значень. Для цієї мети розроблені комбіновані алгоритми, засновані на подвоєнні допоміжних кроків. Виходячи з цього, коефіцієнт, зв'язуючий розмірність кроків блокових методів, що використовуються, повинен бути пропорційний ступеню двійки, оскільки простіше зробити зайву ітерацію на етапі розгонки, чим потім виконувати розрахунки з кроком, який значно менше допустимого. За допомогою комбінованих підходів кількість точок, в яких значення функції будуть обчислюватися послідовно, можна скоротити до величини , або ж зовсім позбутися послідовних обчислень. Також необхідно брати до уваги той факт, що значення функції в кожній точці блоку обчислюються одночасно, це ще приблизно в k раз прискорює обчислення початкових значень.

При цьому обчислювальний процес на паралельній SIMD структурі з найпростішим способом комутації процесорних елементів - лінійка (1D-тор) може бути представлений за допомогою схеми. Розмірність обчислювального поля співпадає з розмірністю блоку або перевищує його.

Ефективність процесу визначення початкових значень, що досягається комбінованими алгоритмами при зростанні розмірності блоку k, представлена на рис. 6. Показники ефективності використання паралельної обчислювальної SIMD структури для комбінованих алгоритмів із зростанням кількості процесорних елементів (інакше - із зростанням розмірності блоку) прагнуть до одиниці. У комбінованого метода, що використовує метод Рунге-Кутти, цей показник декілька гірше, що пояснюється наявністю дільниці, на якій обчислення проводяться послідовно. Отримані характеристики паралелизму досить переконливо свідчать про високу ефективність запропонованих методів.

У четвертому розділі розроблена методика, що здійснює відображення блокових методів рішення задачі Коши для систем ЗДР на сучасні паралельні обчислювальні структури SIMD і MIMD типів з топологічними характеристиками 1D -, 2D -, 3D- тори, гіперкуби, квазіматриці. Для ефективної реалізації запропонованих алгоритмів на масивно-паралельних комп'ютерах з розподіленою пам'яттю вибиралася стратегія розподілу даних по процесорам, визначалися властивості (ступені паралелизму, масштабованість, час роботи) основних частин задачі.

Для SIMD структур кращі показники рішення нелінійних СОДУ по алгоритму (13), були досягнуті в моделях з обчислювальним полем кільце (1D- тор), розмірність яких співпадала з розмірністю блоку k або перевищувала її.

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

Для нелінійних систем в залежності від трудомісткості обчислення правих частин на SIMD структурах отримані наступні характеристики паралелизму блокових алгоритмів.

Для способів комутації 2D-, 3D -тор і гіперкуб прийнятні показники прискорення і ефективність блокових алгоритмів досягалися тільки для випадку лінійних систем в зв'язку з неможливістю виконання різнотипових операцій.

Значення граничних показників прискорення (S) і ефективності (Е) наведені в таблиці 1.

Таблиця 1. Основні показники паралелизму реалізованих методів для SIMD систем

	Топологічне з'єднання	Нелінійні системи	Лінійні системи
		S	E	S	E
1.	1D- тор (pk)	~k	~1	~k	~1
2.	1D- тор (pm)	~k	~k/m (m?k)	~m	~1
3.	2D- тор (pkk)	~k	~1/k	~kk/log2k	~1/log2k
4.	2D- тор (pmk)	~k	~1/m	~mk/log2m	~1/log2m
5.	3D- тор (pkkm)	~k	~1/(mk)	~ ~kkm/log2(k+m)	~1/log2(k+m)
6.	Гіперкуб (pkk)	~k	~1/k	~kk/log2(k-1)	~1/log2(k-1)

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

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

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

паралельна обчислювальна система

(14)

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

Досліджена динаміка шахтних підіймально-транспортних установ. Побудовані і реалізовані математичні моделі, що описують роботу багатоканатних підіймальних установок з гасителями і без гасителів коливань, для визначення зміни амплітуд і швидкостей коливань в системах типу ЦШ44, МК44. Підтверджена правильність всіх побудованих моделей і алгоритмів.

У висновках сформульовані наукові результати і практична значущість виконаної роботи.

У додатку приведені документи про використання результатів дисертаційної роботи.

Висновки

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

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

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

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

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

Розроблена паралельна реалізація ітераційних методів і методів Н'ютона для вирішення нелінійної різницевої задачі. Гранична точність отриманих методів значно перевершує точність відомих методів рішення при тих же значеннях кроку інтегрування.

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

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

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

Розроблені методи, алгоритми і моделі реалізовані у вигляді комплексу програм. Результати дисертаційних досліджень були використані у виробничому об'єднанні “Красноармійськвугілля” для розрахунку динаміки роботи шахтних багатоканатних установ для підйому корисних копалин, при цьому стало можливим отримання точних оцінок динамічних навантажень при значному скороченні часу розрахунків. Також отримані результати впроваджені в учбовий процес ДНТУ і ДНУ як методичні вказівки по курсах “Теорія обчислювальних систем”, “Високопродуктивні обчислювальні мережі”, “Звичайні диференціальні рівняння”.

По темі дисертації опубліковані наступні роботи

Дмитриева О.А. Анализ параллельных алгоритмов численного решения систем обыкновенных дифференциальных уравнений методами Адамса-Башфорта и Адамса-Моултона.// Математическое моделирование. - 2000. - Т. 12, № 5. - С. 81-86.

Дмитриева О.А. Параллельные блочные многошаговые алгоритмы численного решения систем обыкновенных дифференциальных уравнений большой размерности. //Научные труды Донецкого государственного технического университета. Серия: Информатика, кибернетика и вычислительная техника (ИКВТ-2000), выпуск 15: - Донецк: ДонГТУ, 2000. - С. 53-58.

Дмитриева О.А. Анализ параллельных алгоритмов численного решения дифференциальных уравнений в частных производных эллиптического типа. //Научн. тр. ДонГТУ. Серия: Информатика, кибернетика и вычислительная техника (ИКВТ-99), выпуск 6: - Донецк:ДонГТУ, 1999. - С. 56-61.

Дмитриева О.А. Повышение эффективности вычисления начального отрезка для блочных многошаговых методов решения задачи Коши на SIMD-структурах. //Научн. тр. Донецкого государственного технического университета. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. - Севастополь: “Вебер”, 2001. - С. 121-128.

Дмитриева О.А. Анализ параллельных алгоритмов численного решения систем линейных уравнений итерационными методами.//Научн. тр. ДонГТУ. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, випуск 10: - Донецк: ДонГТУ, 2000. - С. 50-55.

Фельдман Л.П., Дмитриева О.А. Параллельные блочные методы решения обыкновенных дифференциальных уравнений.// Известия ТРТУ - ДонГТУ. Материалы второго международного научно-технического семинара “Практика и перспективы развития институционного партнерства”. - 2001. - №1. - С. 28-35.

Дмитриева О.А. Параллельные блочные методы моделирования динамических объектов, описываемые системами обыкновенных дифференциальных уравнений. //II Всеукраїнська науково-практична конференція з міжнародною участю “Людина і космос”. Збірник тез. - Дніпропетровськ.: НЦАОМУ, 2000. - С. 282.

Дмитриева О.А. Оценка погрешности и эффективность параллельных многошаговых блочных методов решения задачи Коши.// III международная конференция по неравновесным процессам в соплах и струях NPNJ. Тезисы докладов.- М.: МГИУ, 2000. - С. 151-153.

Дмитриева О.А. Отображение параллельных алгоритмов моделирования на структуры современных параллельных вычислительных систем. //III Мiжнародна молодiжна науково-практична конференцiя “Людина i космос”. Збiрник тез. - Днiпропетровськ.: НЦАОМУ, 2001. - С. 299.

Фельдман Л.П., Дмитриева О.А. Распределенное численное решение систем обыкновенных дифференциальных уравнений блочными многошаговыми алгоритмами// Тезисы докладов Всероссийской научной конференции “Научный сервис в сети Интернет”. - М.: Из-во МГУ, 2000. - С.36-39.

Фельдман Л.П., Дмитриева О.А., Михайлова Т.В. Аспекты дистанционного обучения в курсе “Численные методы и пакеты”. // Тезисы докладов Всероссийской научной конференции “Научный сервис в сети Интернет”. - М.: Из-во МГУ, 1999.- С.293-297.

Фельдман Л.П., Дмитриева О.А. Оценки эффективности параллельных алгоритмов численного решения систем обыкновенных дифференциальных уравнений методами Адамса-Башфорта и Адамса-Моултона. //Тезисы докладов Десятой Юбилейной международной конференции по вычислительной механике и современным прикладным программным средствам. - М.:МГИУ,1999. - С.15-17.

Анотація

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

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

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

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

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

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

Abstract

Dmitrieva О.А. Algorithmic methods of parallel calculable systems effectiveness rise attached to decision of multidimensional dynamic tasks. - Manuscript.

Thesis for candidate's degree (technical sciences) by specialty 05.13.13 computers, systems and networks. Donetsk National Technical University, Donetsk, 2001.

Thesis sacred to elaboration of methods and algorithms directed to rise of exploitation effectiveness of parallel calculable systems.

Multistep block methods for decision Cauchy problem for usual differential equations, that are competent on realization in calculable systems with parallel architecture, are worked up. Theoretical convergence basing is done. Steadiness of worked up methods is proved. The effective parallel finding algorithms of elementary significances for block methods backing up necessary calculations exactness are brought. The methods related to single transition operator calculation are worked up. Reflection of these algorithms on structures of contemporary highly productive calculable systems is realized.

Methods, algorithms and models that are worked up, are used for modeling of conducts of multicable lifting installations, during implementation of research chair works of Applied mathematics and informatics department of DNTU, and inculcated in educational processes of DNTU and DNU also.

Key words: parallel calculable systems, topology, processor element, effectiveness, acceleration, multidimensional dynamic tasks, systems of usual differential equalizations.

Аннотация

Дмитриева О.А. Алгоритмические методы повышения эффективности параллельных вычислительных систем при решении многомерных динамических задач. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - вычислительные машины, системы и сети. - Донецкий национальный технический университет, Донецк, 2001.

Диссертация посвящена разработке методов и алгоритмов, направленных на повышение эффективности эксплуатации параллельных вычислительных систем.

Проведенный сравнительный анализ численных методов решения систем обыкновенных дифференциальных уравнений по ряду признаков (возможности и особенностям распараллеливания, предельной точности алгоритмов, области использования, ускорению и т. д.) показал, что для эффективной реализации на параллельных вычислительных структурах необходимо либо специальным образом реструктуризировать известные численные методы, либо, что предпочтительнее, разрабатывать новые, которые были бы изначально ориентированы на системы с многопроцессорной архитектурой.

Разработаны многошаговые многоточечные блочные методы решения задачи Коши для ОДУ, изначально ориентированные на реализацию в вычислительных системах с параллельной архитектурой. Произведено теоретическое обоснование сходимости и устойчивости разработанных методов. Сформулирована и доказана теорема об оценке погрешности приближенного решения. Построены итерационные параллельные алгоритмы решения нелинейной разностной задачи и оценена их предельная точность. Выполнено обобщение предложенных методов на решение систем ОДУ. Приведены эффективные параллельные алгоритмы нахождения разгоночных значений для многошаговых многоточечных блочных методов, поддерживающих требуемую точность.

Для случая однородных систем ОДУ предложены методы, связанные с однократным вычислением оператора перехода, что позволило значительно сократить число матричных операций на каждом шаге. Решение тестовых задач подтвердило, что оценки параллелизма предложенных методов близки к потенциальным. Осуществлено отображение разработанных алгоритмов на структуры современных высокопроизводительных вычислительных систем. Приведены иллюстративные примеры.

Разработанные методы, алгоритмы и модели были использованы в п/о “Красноармейскуголь” при моделировании поведения многоканатных подъемных установок с целью сокращения времени определения величин амплитуд и скоростей колебаний динамических нагрузок работы подъема, а также повышения точности искомого решения. Основные результаты работы использовались в процессе выполнения научно-исследовательских работ кафедры прикладной математики и информатики ДНТУ по гостемам ГТ-14-97 “Научные основы анализа и оптимизации структур компьютерных систем и способов управления параллельными вычислительными процессами” (выполнялась в 1997-1999 гг.), Н-17-95 “Алгоритмическое и программное обеспечение вычислительных систем и информационных технологий” (выполнялась в 1995-2000 гг.), ГТ-11-2000, Н-13-2000 (выполняются с 2000 г.). Предложенные методы внедрены в учебные процессы ДНТУ и ДНУ.

Ключевые слова: параллельные вычислительные системы, топология, процессорный элемент, эффективность, ускорение, многомерные динамические задачи, системы обыкновенных дифференциальных уравнений.

Размещено на Allbest.ru