Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Математическое моделирование, численные методы и комплексы программ

Диссертационная работа:

Жидченко Виктор Викторович. Программный комплекс моделирования и анализа алгоритмов параллельных вычислений : диссертация ... кандидата технических наук : 05.13.18 / Жидченко Виктор Викторович; [Место защиты: Сам. гос. аэрокосм. ун-т им. С.П. Королева].- Самара, 2007.- 189 с.: ил. РГБ ОД, 61 07-5/5304

смотреть содержание
смотреть введение
Содержание к работе:

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ 5

ВВЕДЕНИЕ 6

1 ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ НА ЭВМ 13

  1. Классификация параллельных вычислительных систем 13

  2. Явный параллелизм и автоматическое распараллеливание 17

  3. Графические модели параллельных процессов 20

  4. Взаимодействие параллельных процессов 27

  1. Механизмы синхронизации параллельных процессов 28

  2. Проблема тупиков в параллельных алгоритмах 36

Выводы и основные результаты 38

2 ГРАФИЧЕСКАЯ МОДЕЛЬ АЛГОРИТМОВ ПАРАЛЛЕЛЬНЫХ
ВЫЧИСЛЕНИЙ 39

  1. Концептуальное описание граф-модели 39

  2. Синхронизация между параллельными ветвями граф-модели 43

  3. Создание граф-моделей параллельных вычислений ...46

  4. Реализация вычислений, описанных граф-моделью 52

Выводы и основные результаты 56

3 СИНХРОНИЗАЦИЯ В МОДЕЛИ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА.. 57

3.1 Простейший метод поиска критических данных в модели
параллельного алгоритма 59

3.2 Метод поиска критических данных на основе алгебры над
способами использования данных 63

3.3 Пример применения формулы над способами использования данных
для поиска критических данных 74

3.4 Алгоритм построения и вычисления формул над способами
использования данных 75

3.5 Проверка корректности синхронизации граф-модели 87

3.5.1 Метод проверки корректности синхронизации граф-модели 89

3.5.2 Метод поиска тупиков 93

3.6 Пример использования методов поиска критических данных и
проверки корректности синхронизации 102

  1. Параллельная модель RS-триггера 102

  2. Модель RS-триггера без синхронизации 109

Выводы и основные результаты 112

4 ПРОГРАММНЫЙ КОМПЛЕКС МОДЕЛИРОВАНИЯ И АНАЛИЗА
АЛГОРИТМОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ 113

  1. Архитектура программного комплекса моделирования и анализа алгоритмов параллельных вычислений 113

  2. Программный комплекс моделирования и анализа алгоритмов параллельных вычислений PGRAPH 1.0 116

  1. Создание моделей параллельных алгоритмов в программном комплексе PGRAPH 1.0 119

  2. Генерация исходных текстов параллельных программ на языке C++ 123

  3. Межмодульный информационный интерфейс 124

  4. Обмен данными между параллельными процессами 126

4.2.5 Модуль передачи сообщений 128

Выводы и основные результаты 129

5 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПРАКТИЧЕСКОЙ
ЗНАЧИМОСТИ МОДЕЛИ 130

5.1 Решение уравнения Лапласа 130

  1. Постановка задачи и последовательный алгоритм решения уравнения Лапласа 130

  2. Параллельный алгоритм решения уравнения Лапласа 132

5.1.3 Экспериментальная проверка эффективности параллельного
алгоритма 138

5.2 Распараллеливание алгоритма решения системы дифференциальных
уравнений Навье-Стокса 143

5.3 Распараллеливание многосеточных методов 149

Выводы и основные результаты 161

ЗАКЛЮЧЕНИЕ 163

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 167

ПРИЛОЖЕНИЕ 1. Тексты программ и примеры моделей 177

СПИСОК УСЛОВНЫХ СОКРАЩЕНИЙ

БМ - базовый модуль

ВМ - вычислительный модуль

ВС - вычислительная система

ГСП - графо-символическое программирование

ДПУ - диаграмма потоков управления

ДПД -диаграмма потоков данных

ОС - операционная система

ПО - предметная область

MIMD - Multiple Instruction stream I Multiple Data stream -множественный поток команд и данных

MISD - Multiple Instruction stream I Single Data stream -

множественный поток команд и одиночный поток данных

MPI - Message Passing Interface - интерфейс передачи сообщений

SIMD - Single Instruction stream I Multiple Data stream -

одиночный поток команд и множественный поток данных

SISD - Single Instruction stream I Single Data stream -

единственный поток команд и единственный поток данных

Введение к работе:

Актуальность темы

Развитие моделей описания алгоритмов параллельных вычислений происходит с середины XX века одновременно со становлением теории последовательных вычислений

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

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

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

В области теории и практики моделирования параллельных вычислений существенный вклад внесли такие ученые как С М Абрамов, Г Буч, В В Воеводин, Вл В Воеводин, В П Гергель, Э Дейкстра, И Б Задыхайло, В Е Котов, К Петри, Р Г Стронгин, Ч Хоар, И Якобсон и др

Вопросам разработки графических моделей вычислительных алгоритмов посвящены работы И.В Вельбицкого, А Н Коварцева, Д Харела и др

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

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

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

графической модели алгоритмов параллельных вычислений, базирующейся на модели ГСП-технологии, а также методов и средств автоматического анализа предложенной модели, способствующих повышению качества параллельных вычислений В результате работы создан программный комплекс, реализующий указанные методы и средства, предназначенный для построения моделей алгоритмов параллельных вычислений и автоматического синтеза параллельных программ на их основе

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

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

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

  1. Анализ существующих подходов к моделированию параллельных алгоритмов и организации параллельных вычислений на ЭВМ,

  2. Разработка графической модели алгоритмов параллельных вычислений, ориентированной на использование конечными пользователями в различных предметных областях,

  3. Разработка методов автоматического поиска критических данных и анализа корректности синхронизации в алгоритмах параллельных вычислений, описываемых предлагаемой моделью,

  4. Создание программного комплекса, предназначенного для построения моделей алгоритмов параллельных вычислений и их реализации на ЭВМ с параллельной архитектурой;

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

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

Научная новизна В результате проведенных исследований был получен ряд новых научных результатов

  1. Разработана новая модель описания алгоритмов параллельных вычислений, ориентированная на их наглядное графическое представление,

  2. Разработаны и реализованы метод и алгоритм автоматического поиска критических данных в предложенной модели,

  3. Предложен метод анализа корректности синхронизации в модели параллельного алгоритма,

  4. Разработаны и реализованы метод и алгоритм поиска тупиков в алгоритмах параллельных вычислений, описываемых предложенной моделью,

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

На защиту выносятся

графическая модель алгоритмов параллельных вычислений,

метод и алгоритм автоматического поиска критических данных в предложенной модели,

метод анализа корректности синхронизации в параллельном алгоритме,

метод и алгоритм поиска тупиков в алгоритмах параллельных вычислений, описываемых предложенной моделью

Практическая ценность работы заключается в разработке программного комплекса моделирования алгоритмов параллельных вычислений и их реализации на ЭВМ с параллельной архитектурой Использование программного комплекса не требует от пользователя глубоких познаний в теории параллельного программирования, что позволяет применять его для создания эффективных параллельных программ конечными пользователями, специалистами в различных предметных областях Программный комплекс обеспечивает возможность автоматического синтеза параллельных программ на основе построенных моделей

Реализация результатов работы. Результаты диссертационной работы нашли применение при выполнении работ по тематическому плану научно-исследовательских работ в Самарском государственном аэрокосмическом университете, финансируемых из федерального бюджета по единому заказ-наряду в 1998 г , утвержденному министерством общего и профессионального образования РФ Результаты диссертационной работы внедрены в учебный процесс специальности 230102 - Автоматизированные системы обработки информации и управления -Самарского государственного аэрокосмического университета, что подтверждено актом внедрения

Публикации и апробация работы Основные положения диссертационной работы, научные и практические результаты докладывались на двух всероссийских и трех международных конференциях IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 1998), Второй Всероссийской научной конференции «Методы

и средства обработки информации» МСО-2005 (Москва, 2005); Международном симпозиуме «Надежность и качество» (Пенза, 2002), Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2002), Первой международной конференции «Системный анализ и информационные технологии» САИТ-2005 (Переславль-Залесский, 2005)

Публикации Всего по теме диссертации опубликовано И печатных работ Список опубликованных работ приведен в заключении

Структура и объем работы Диссертация состоит из основной части и приложений Основная часть содержит введение, пять глав, заключение, список использованных источников из 104 наименований. Приложение содержит тексты программ и примеры моделей Объем диссертации - 176 страниц (без приложений), она содержит 67 рисунков и 4 таблицы

Подобные работы
Панфилов Сергей Александрович
Методы и программный комплекс моделирования алгоритмов управления нелинейными динамическими системами на основе мягких вычислений
Селиванова Надежда Александровна
Математическое моделирование, анализ и прогнозирование развития национального гражданского авиационного комплекса
Магомедов Курбан Ахмедович
Математическое моделирование и анализ электрических и тепловых процессов в технических комплексах
Слетков Денис Викторович
Математическое моделирование и фрактальный анализ роста колоний биологических объектов с использованием программного комплекса
Шубович Валерий Геннадьевич
Анализ, классификация и моделирование алгоритмов сжатия
Мансуров Алмаз Ингелович
Разработка и моделирование алгоритмов мягкого декорирования блоковых кодов в каналах со стиранием элементов и использованием процедуры кластерного анализа
Удод Евгений Васильевич
Исследование и разработка прецизионных математических моделей преобразования и алгоритмов вычислений значений давления
Янович Денис Александрович
Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений
Порецков Олег Александрович
Алгоритмы и методы вычисления первого регуляризованного следа оператора Лапласа-Бельтрами с негладким потенциалом на единичной двумерной сфере
Ковшов Николай Вадимович
Разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net