Библиотечный каталог авторефератов Украины

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

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

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

                                                                                                                         (14)

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

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

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

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

ВИСНОВКИ

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

1. Отримані оцінки ефективності використання оператора переходу, побудованого для методів з контролем погрішності на кроці, який дозволяє здійснювати розпаралелювання алгоритмів чисельного рішення лінійних систем звичайних диференціальних рівнянь. Оператор переходу для систем генерується до початку розрахунку і дозволяє в 5 разів скоротити число матричних операцій і вдвічи число зсувів, що виконуються на кожному кроці.
2. Розроблені алгоритми, що визначають коефіцієнти формул прогнозу і корекції для багатокрокових методів чисельного рішення систем лінійних диференціальних рівнянь при будь-якому співвідношенні опорних і розрахункових точок, що дозволяє отримувати рішення системи із заданою мірою точності для будь-якої конфігурації процесорного поля паралельного комп'ютера.
3. Узагальнені паралельні багатокрокові багатоточечні методи вирішення задачі Коши для звичайних диференціальних рівнянь. Доведена збіжність чисельного рішення, отримані апріорні оцінки погрішності апроксимації. Визначений критерій вибіру кроку інтегрування, який забезпечує максимальну швидкість збіжності чисельного рішення.
4. Запропоновані ефективні паралельні алгоритми отримання стартових значень, засновані на комбінуванні однокрокових і багатокрокових блокових методів. Визначені оптимальні співвідношення між розмірністю кроків блокових методів на етапі розгонки. Доведено, що показники паралелизму запропонованих алгоритмів: прискорення і ефективність, близькі до потенційних, тому розроблені алгоритми можуть бути рекомендовані для визначення початкових значень в будь-яких системах, що використовують для рішення багатокрокові методи.
5. Розроблена паралельна реалізація ітераційних методів і методів Н’ютона для вирішення нелінійної різницевої задачі. Гранична точність отриманих методів значно перевершує точність відомих методів рішення при тих же значеннях кроку інтегрування.
6. Формалізована процедура вибору паралельних обчислювальних структур SIMD і MIMD типів з різними топологічними характеристиками і  розмірностями процесорних полів, що змінюються, при реалізації багатокрокових багатоточечних блокових методів. Отримані порівняльні характеристики запропонованих способів відображення, і приведені рекомендації по вибору розроблених алгоритмів для різних типів систем звичайних диференціальних рівнянь, що дозволяють досягати значень показників паралелизму, близьких до потенційних.
7. Реалізовані математичні моделі шахтних вентиляційних мереж на основі запропонованих в дисертаційній роботі методів, що орієнтовані на обчислювальні системи з паралельною обробкою, це дозволяє одночасно моделювати динаміку зміни значень у всіх гілках і вузлах мережевого об'єкта.
8. Проведене порівняльне моделювання динамічних навантажень шахтних підіймальних установ з гасителями і без гасителів коливань за допомогою блокових методів, розроблених в дисертаційній роботі. Час, затрачений на отримання результатів моделювання із заданою мірою точності, значно менше, ніж при використанні відомих чисельних методів рішення, що забезпечується не тільки паралельною реалізацією, але і збільшенням довжини кроку інтегрування блокових методів.

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

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

1. Дмитриева О.А. Анализ параллельных алгоритмов численного решения систем обыкновенных дифференциальных уравнений методами Адамса-Башфорта и Адамса-Моултона.// Математическое моделирование. – 2000. – Т. 12, № 5. - С. 81-86.
2. Дмитриева О.А. Параллельные блочные многошаговые алгоритмы численного решения систем обыкновенных дифференциальных уравнений большой размерности. //Научные труды Донецкого государственного технического университета. Серия: Информатика, кибернетика и вычислительная техника (ИКВТ-2000), выпуск 15: - Донецк: ДонГТУ, 2000. – С. 53-58.
3. Дмитриева О.А. Анализ параллельных алгоритмов численного решения дифференциальных уравнений в частных производных эллиптического типа. //Научн. тр. ДонГТУ. Серия: Информатика, кибернетика и вычислительная техника (ИКВТ-99), выпуск 6: - Донецк:ДонГТУ, 1999. - С. 56-61.
4. Дмитриева О.А. Повышение эффективности вычисления начального отрезка для блочных многошаговых методов решения задачи Коши на SIMD-структурах. //Научн. тр. Донецкого государственного технического университета. Серия:  Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. - Севастополь: “Вебер”, 2001. - С. 121-128.
5. Дмитриева О.А. Анализ параллельных алгоритмов численного решения систем линейных уравнений итерационными методами.//Научн. тр. ДонГТУ. Серия:  Проблемы моделирования и автоматизации проектирования динамических систем, випуск 10: - Донецк: ДонГТУ, 2000. - С. 50-55.
6. Фельдман Л.П., Дмитриева О.А. Параллельные блочные методы решения обыкновенных дифференциальных уравнений.// Известия ТРТУ – ДонГТУ. Материалы второго международного научно-технического семинара “Практика и перспективы развития институционного партнерства”. - 2001. – №1. - С. 28-35.
7. Дмитриева О.А. Параллельные блочные методы моделирования динамических объектов, описываемые системами обыкновенных дифференциальных уравнений. //II Всеукраїнська науково-практична конференція з міжнародною участю “Людина і космос”. Збірник тез. - Дніпропетровськ.: НЦАОМУ, 2000. – С. 282.
8. Дмитриева О.А. Оценка погрешности и эффективность параллельных многошаговых блочных методов решения задачи Коши.// III международная конференция по неравновесным процессам в соплах и струях NPNJ. Тезисы докладов.- М.: МГИУ, 2000. - С. 151-153.
9. Дмитриева О.А. Отображение параллельных алгоритмов моделирования на структуры современных параллельных вычислительных систем. //III Мiжнародна молодiжна науково-практична конференцiя “Людина i космос”. Збiрник тез. - Днiпропетровськ.: НЦАОМУ, 2001. - С. 299.
10. Фельдман Л.П., Дмитриева О.А. Распределенное численное решение систем обыкновенных дифференциальных уравнений блочными многошаговыми алгоритмами// Тезисы докладов Всероссийской научной конференции “Научный сервис в сети Интернет”. – М.: Из-во МГУ, 2000. - С.36-39.
11. Фельдман Л.П., Дмитриева О.А., Михайлова Т.В. Аспекты дистанционного обучения в курсе “Численные методы и пакеты”. // Тезисы докладов Всероссийской научной конференции “Научный сервис в сети Интернет”. – М.: Из-во МГУ, 1999.-  С.293-297.
12. Фельдман Л.П., Дмитриева О.А. Оценки эффективности параллельных алгоритмов численного решения систем обыкновенных дифференциальных уравнений методами Адамса-Башфорта и Адамса-Моултона. //Тезисы докладов Десятой Юбилейной международной конференции по вычислительной механике и современным прикладным программным средствам. - М.:МГИУ,1999. - С.15-17.

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

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