ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

ДМИТРІЄВА ОЛЬГА АНАТОЛІЇВНА

УДК 519.711.3:681.5.01

АЛГОРИТМІЧНІ МЕТОДИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ ПРИ виРІШЕННІ БАГАТОМІРНИХ ДИНАМІЧНИХ ЗАДАЧ

05.13.13 - ОБЧИСЛЮВАЛЬНІ МАШИНИ, СИСТЕМИ та МЕРЕЖІ

Автореферат

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

кандидата технічних наук

ДОНЕЦЬК 2001

Дисертацією є рукопис.

Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України

Науковий керівник: | доктор технічних наук, професор,

Фельдман Лев Петрович,

Донецький національний технічний університет, професор кафедри прикладної математики і інформатики

Офіційні опоненти: |

доктор технічних наук,

Боюн Віталій Петрович, зав. відділом керуючих машин Інституту кібернетики ім. В.М. Глушкова НАН України, м. Київ,

кандидат технічних наук,

Скобцов Вадим Юрійович, науковий співробітник відділу теорії керуючих систем Інституту прикладної математики і механіки НАН України, м. Донецьк

Провідна установа: |

Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, відділ моделювання динамічних систем, м. Київ.

Захист відбудеться “11” жовтня 2001 р. о 14 годині на засіданні спеціалізованої вченої ради К11.052.03 Донецького національного технічного університету за адресою:

83000, м. Донецьк, вул. Артема, 58, учб. корпус 1, ауд. 201.

З дисертацією можна ознайомитись у бібліотеці Донецького національного технічного університету за адресою:

83000, м. Донецьк, вул. Артема, 58, учб. корпус 2.

Автореферат розісланий “6” вересня 2001 р.

Вчений секретар

спеціалізованої вченої

ради Мокрий Г. В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

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

-

-

-

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

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

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

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

-

-

-

-

-

-

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

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

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

-

-

-

-

-

- 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)

,

,

,

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

Рис. 1. Схема рішення ЗДР методом Рунге-Кутти з контролем погрішності

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

(4)

або (5)

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

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

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

Рис. 2. Граф впливу алгоритму множення матриці на вектор

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

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

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

f(t,x), x(t0) = x0, (6)

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

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

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

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

Рис. 3. Схема розділення на блоки

Рис. 4. Схема обчислень багатокроковим блоковим методом

Отримана оцінка для погрішності апроксимації різницевого методу (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, і rn – нев’язка багатокрокового – k-точкового блокового методу (7) визначена згідно (8) з оцінкою

. (11)

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

(12)

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

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

(13)

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

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

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

Рис. 5. Відображення алгоритму на SIMD структуру з топологією 1D-тор

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

Рис. 6 Характеристики ефективності комбінованих методів обчислення початкового відрізка на SIMD структурах.

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

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

Рис. 7 Схема відображення блокового алгоритму рішення СЗДР на 1D- тор

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

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

а) розмірність системи фіксована (m=const)

б) розмірність блоку фіксована (k=const)

Рис. 8 Оцінки ефективності багатокрокових блокових методів на SIMD структурах з топологією (1D - тор).

Для способів комутації 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. Підтверджена правильність всіх побудованих моделей і алгоритмів.

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

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

ВИСНОВКИ

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

1.

2.

3.

4.

5.

6.

7.

8.

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

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

У роботі [6] здобувачем досліджені питання збіжності і стійкість багатокрокових блокових методів, отримані оцінки погрішностей. У [10] багатокрокові багатоточкові блокові методи були узагальнені для рішення систем звичайних диференціальних рівнянь, і отримані показники паралелизму при відображенні алгоритмів на структури типу SIMD. У роботі [11] автором була розроблена підсистема чисельного рішення задачі Коши для звичайних диференціальних рівнянь. У [12] досліджені питання розпаралелювання послідовних алгоритмів, здійснене відображення рішення систем на топології 1D- і 2D-тори SIMD структур.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 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 г.). Предложенные методы внедрены в учебные процессы ДНТУ и ДНУ.

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