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

На правах рукописи

ЖИДЧЕНКО Виктор Викторович

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

Специальность 05 13 18-Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Самара 2007

19

003175219

Работа выполнена в Самарском государственном аэрокосмическом университете имени академика С П Королева

Научный руководитель доктор технических наук, профессор Коварцев А Н

Официальные оппоненты

доктор технических наук, доцент Смирнов С В кандидат технических наук, доцент Попов С Б

Ведущая организация

Центр компьютерного моделирования Нижегородского государственного университета им Н И Лобачевского

Защита состоится 09 11 2007 г в_часов на заседании диссертационного совета

Д 212 215 05 в Самарском государственном аэрокосмическом университете им академика С П Королева по адресу 443086, г Самара, Московское шоссе, д 34

С диссертацией можно ознакомиться в библиотеке Самарского государственного аэрокосмического университета

Автореферат разослан 08 10 2007 г

Ученый секретарь диссертационного совета

д т н , профессор

А А Капентьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

модели,

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

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

описываемых предложенной моделью

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность темы диссертации, дана общая характеристика работы, определены цели и задачи исследования Приведены структура и краткое содержание диссертации, основные положения, выносимые на защиту

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

Построение эффективных параллельных вычислительных процессов невозможно без учета специфики ЭВМ, на которой будут выполняться вычисления. Рассмотрена широко применяемая классификация архитектур вычислительных систем, предложенная М Флинном В соответствии с ней вычислительные системы делятся на четыре класса 8180, ЭМО, М1ЭО и М1МО Подробно рассмотрен наиболее многочисленный класс М1МВ систем, в котором выделены три подкласса симметричные мультипроцессоры, кластеры и массово-параллельные системы Приведены примеры существующих систем каждого класса

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

(неявный параллелизм) и создание параллельных алгоритмов в явном виде (явный параллелизм) Дано описание основных результатов работ и существующих систем, реализующих оба способа

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

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

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

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

Модель представляется четверкой <0, Р, Р, й>, где Э - множество данных некоторой предметной области, Р - множество операторов, определенных над данными предметной области, Р - множество предикатов, действующих над структурами данных предметной области, й = {А, Ф, 11} - ориентированный помеченный граф, называемый агрегатом А = {Аь А2, , А„} - множество вершин графа Каждая вершина А, помечена локальным оператором ^ф) е ? На графе задано множество дуг управления ¥ = { |Ь ,2, , и множество дуг синхронизации Ф = {Ф|,,ь Ф.,,2, , Ф;,/} Я - отношение над множествами вершин и дуг, определяющее способ их связи Дуга управления, соединяющая любые две вершины А, и имеет три метки предикат р./Э) е Р, приоритет к(Фч) е N и тип дуги Т(¥ч) б N

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

одновременно становятся истинными, переход осуществляется по наиболее приоритетной дуге.

Тип дуги % определяется как функция Т(^ч) е {1,2,3}, значения которой имеют следующую семантику:

= 1 - последовательная дуга (описывает передачу управления на последовательных участках алгоритма);

Т(¥у) = 2 - параллельная дуга (обозначает начало нового параллельного фрагмента алгоритма);

Т(ФЦ) = 3 - терминирующая дуга (завершает параллельный фрагмент алгоритма).

Для описания параллелизма вводится понятие параллельной ветви (3 - подграфа графа в, начинающегося параллельной дугой и заканчивающегося терминирующей дугой. (3 = <Ар, Яр> , где Ар - множество вершин ветви, ^р - множество дуг управления ветви, Яр - отношение над множествами вершин и дуг ветви, определяющее способ их связи. На рис. 1 параллельные ветви обведены пунктиром.

| Ар Тш—

:...... Кг ч

\ Аз ...........'.,........... А< |................

% А5

Рис. 1 - Пример граф-модели параллельного алгоритма

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

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

Функционирование модели начинается с запуска единственной ветви, называемой мастер-ветвью (мастер-процессом) р0. Мастер-ветвь начинается с корневой вершины (вершина А0 на рис. 1) и заканчивается в одной из конечных вершин (на рис. 1 вершины мастер-ветви имеют жирную границу). В вершинах мастер-ветви, имеющих исходящие параллельные дуги, порождаются новые параллельные ветви. Вершины этих ветвей также могут иметь параллельные дуги, таким образом, допускается вложенность параллельных ветвей.

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

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

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

В граф-модель, содержащую вершины и дуги управления, добавляются дуги синхронизации Ф = {Ф^и, Ф^д, > Ф>,;} Направление дуг синхронизации определяет передачу сообщений между различными вершинами модели Каждая дуга Фи помечена сообщением цц, которое отправляется вершине после выполнения оператора в вершине А, Сообщение в общем случае предназначено лишь для передачи информации о том, что оператор в вершине А, завершил работу Вершины отправляют и принимают сообщения, соответственно записывая и удаляя их из почтового ящика, который представляет собой список Ьр05, = [ц.ооо, , м.,топ], где - сообщение, посылаемое от вершины А, вершине А,

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

Возможна ситуация, при которой в одну вершину AJ граф-модели входит более одной дуги синхронизации В этом случае вычисления в вершине Aj начинаются после завершения вычислений в каждой из вершин А„ соединенных с ней дугами Фц Тем не менее, не всегда целесообразно ожидать завершения вычислений в каждой из вершин А, Например, если решается одна и та же оптимизационная задача различными численными методами, и каждый из них представлен отдельной параллельной ветвью В этом случае, следует продолжить вычисления после получения результата в одной из ветвей, не дожидаясь окончания работы остальных.

Для предоставления такой возможности вводится понятие семафорного предиката Семафорный предикат = г (Ь^, . , Ь1Пу), представляет собой правильно построенную формулу относительно булевых переменных Ь,^, связанных логическими связками типа Л, V Булевы переменные определяются следующим образом

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

тождественно истинным Вычисление значения семафорного предиката осуществляется перед запуском вершины AJ на исполнение Если его значение ложно, то происходит циклическая проверка Яд, до тех пор, пока он не станет истинным После этого вершина А) запускается, и выполняется оператор {¡(Б)

Механизм семафорных предикатов позволяет строить гибкие условия запуска вершин, определяемые видом логической формулы предиката Использование операции «или» в семафорных предикатах повышает надежность и быстродействие программ, создаваемых с использованием модели за счет введения в нее дублирующих параллельных ветвей, работающих по различным алгоритмам на различных процессорах вычислительной системы Если операция «или» используется в семафорном предикате вершины А„ в которую входят терминирующие дуги нескольких параллельных ветвей, то в случае прихода сообщения от вершины одной из ветвей, остальные ветви принудительно завершаются, а управление передается вершине А, Благодаря этому исключается возможность нахождения модели одновременно в двух вершинах одной параллельной ветви

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

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

а - объект граф-модели, в качестве которого может выступать отдельный

оператор, подграф агрегата (ветвь) или целый агрегат, с] - данное предметной области

Функция Н(а|с1) показывает, каким образом данное с1 используется объектом а

Вводится следующая семантика для значений функции Н

Н(а|с1) = 0 - с! не используется объектом а,

Н(а|с1) = 1 - с1 используется для чтения объектом а,

Н(а|с1) = 2 - й используется для записи объектом а,

Н(а|с1) = 3 - <1 - критическое данное (конфликт совместного использования

данного с! в объекте а) Способ использования каждого данного, используемого локальным оператором ЦБ) в вершине А„ определяется разработчиком при создании оператора Оператор £(0) может использовать данное либо для чтения, либо для записи При исполнении оператора все операции в нем выполняются последовательно Конфликт

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

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

Определение: Данное с! является критическим, если оно используется несколькими вершинами граф-модели, которые в процессе вычислений могут исполняться одновременно При этом хотя бы одна из этих вершин помечена объектом, использующим данное с! для записи

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

Введем операции следования (обозначается символом Д), ветвления (V) и параллельного исполнения (#) над способами использования данных, определяющие способ использования данного с1 некоторым подграфом в,, состоящим из вершин А| и А2 граф-модели в Указанные операции определены для трех возможных способов взаимного расположения вершин А1 и А2 в графе Б, показанных на рис 2

с, Нв-^и .

о, И

Н(©1И) = Н(А,|(1) Д Н(Аг|с1) Н(С2|с1) = НКА^с!) V Н(А2|с1) Н(С3|с1) = Н(А1|с1) # Н(А2|с1) Операция следования Операция ветвления Операция паралл исполнения

Рис 2

Таблица истинности для введенных операций приведена в таблице 1 Табл 1

Н(А1|с1) Н(А2|С1) Н(А1|с1) Д Н(А2|с)) Н(А,|с!) V Н(А2|с1) Н(А1 ¡«) # Н(А2[С1)

0 0 0 0 0

0 1 1 1 1

0 2 2 2 2

0 3 3 3 3

1 0 1 1 1

1 1 1 1 1

1 2 2 2 3

1 3 3 3 3

2 0 2 2 2

2 1 2 2 3

2 2 2 2 3

2 3 3 3 3

3 0 3 3 3

3 1 3 3 3

3 2 3 3 3

3 3 3 3 3

Ниже приведены основные свойства введенных операций (для сокращения записи способ использования данного d в вершине А - H(A|d) - заменим обозначением самой вершины А)

1) АДВ = ВДА

2) АДВДА = АДВ

3) АД (ВДС) = (АДВ) ДС

4) АДВ = AVB

5) А#В = В#А

6) А#(В#С) = (А#В)#С

7) А#А#А = А#А

8) А#А * А

9) А#В#А * А#В

10) А#(ВДС) = (А#В) Д (А#С), A#(BVC) = (А#В) V (А#С)

(дистрибутивность операции # относительно Д и V)

11) АД (В#С) * (АДВ) # (АДС)

12) (А#В) Д (А#С) Д (В#С) = А#В#С

Введенные операции позволяют определить алгебру над способами использования данных в граф-модели алгоритма. Для граф-моделей с произвольной структурой, не содержащих иерархии и кратных дуг, алгебра над способами использования данных позволяет строить формулу для вычисления способа использования каждого данного произвольным объектом модели (отдельным оператором подграфом граф-модели или целым агрегатом) Если для какого-то данного результат вычисления его способа использования агрегатом равен 3, то в рассматриваемом агрегате возможен конфликт совместного использования этого данного Следовательно, разработчику модели необходимо позаботиться об устранении конфликта путем изменения графа модели, переименования данных или введения в модель дуг синхронизации

В главе описан алгоритм автоматического построения и вычисления формул на основе введенной алгебры

Наличие в модели критических данных требует от разработчика определения порядка их совместного использования с помощью механизмов синхронизации Однако после введения дуг синхронизации и назначения семафорных предикатов могут возникнуть 2 ошибочные ситуации

1) Введение дуг синхронизации не разрешает конфликта по данным,

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

Для обнаружения подобных ситуаций разработаны методы, анализирующие как дуги управления, так и дуги синхронизации

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

(коммутативность операции следования) (поглощение операции следования) (ассоциативность операции следования) (эквивалентность операций следования и ветвления)

(коммутативность операции паралл исполнения) (ассоциативность операции паралл исполнения) (поглощение операции параллельного исполнения)

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

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

Такое изменение позволяет привести семафорный предикат каждой вершины граф-модели к следующему универсальному виду Я(А,) = (V Ьр) Л (г(Ьк1,„ , Ьш,|) )>

1

где , }п - номера вершин, из которых исходят дуги управления, входящие в А„ к1, ,кМ - номера вершин, из которых исходят дуги синхронизации, входящие в А„ а г(Ьк!,1, > Ьш,,) - логическая функция

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

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

Я'(А0 = ( V (Ья Л Я'(А^) ) Л ( г( (Я'(Ак1) ЛЬк1,,), , (Я'(АШ) ЛЬШ,)) ), 11'(Ао) = «истина»,

где _)1, , до - номера вершин, из которых исходят дуги управления, входящие в А„ к1, ,кМ - номера вершин, из которых исходят дуги синхронизации, входящие в А„ а г(Ьк1 „ , Ьш,) - логическая функция

Введенное условие запуска оператора вершины на исполнение назовем обобщенным семафорным предикатом.

В работе сформулировано и доказано следующее утверждение Утверждение I Критическое данное с), используемое вершинами А|, , Ап, не приводит к конфликту тогда и только тогда, когда для любых двух вершин А„ А, е { А], , Ап }, обобщенный семафорный предикат одной вершины содержит сообщение от другой вершины

Метод проверки корректности синхронизации множества вершин А' = {А,,, , А,,,}, использующих некоторое критическое данное с1, заключается в построении обобщенного семафорного предиката для каждой из вершин А,ь , А,п и анализе содержимого полученных семафорных предикатов Если существует такая

пара вершин {А,, А^ с А1, для которой семафорный предикат вершины А, не содержит сообщения от вершины А], и при этом семафорный предикат вершины А; не содержит сообщения от вершины А,, то конфликт совместного использования данного с! вершинами А,,, ..., А,„ не разрешен.

Метод поиска тупиков (взаимных блокировок) использует понятие состояния модели алгоритма параллельных вычислений как множества вершин, в которых происходят вычисления в момент времени V. Б, = {А,..., А, }.

В работе предложен алгоритм построения покрывающего дерева, определяющего множество возможных состояний модели алгоритма. Каждая вершина дерева описывает одно состояние, которое представляется множеством

вгЦ.....

Метод поиска тупиков заключается в анализе покрывающего дерева модели. Если покрывающее дерево содержит вершину без потомков (лист), множество 5, которой не равно {Ам}, где Ам - конечная вершина граф-модели, это означает, что из состояния Б, невозможен переход в другое состояние, т.е. модель содержит тупик. Вершины, в которых остановятся вычисления при возникновении этого тупика, определяются значением множества Б;.

Если все вершины покрывающего дерева, не имеющие потомков, содержат множество = {Ам}, где Аы - конечная вершина граф-модели, то в модели не может возникнуть состояния, из которого не возможен переход в другое состояние, т.е. в модели нет тупиков.

В четвертой главе приводится описание программного комплекса, предназначенного для моделирования алгоритмов параллельных вычислений с использованием предлагаемой модели. В ходе работы создан программный комплекс РСЯАРН 1.0, который позволяет строить граф-модель параллельного алгоритма и на основе этой модели автоматически синтезировать и запускать на исполнение параллельные программы. Структура программного комплекса приведена на рис 3.

Рис. 3 - Структура программного комплекса РОЯАРН 1.0

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

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

Подсистема компиляции позволяет на основании описания объектов модели, хранящегося в информационном фонде системы, генерировать исходные тексты на языке С++, предназначенные для компиляции в среде программирования Microsoft Visual С++ 6 0В качестве компилятора исходных текстов используется программный продукт Microsoft Compiler, входящий в состав указанной среды программирования

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

Подсистема управления параллельными вычислениями осуществляет запуск скомпилированной параллельной программы на исполнение

Программный комплекс PGRAPH 1 0 ориентирован на работу в модели передачи сообщений Генерируемые программы могут исполняться как на ЭВМ с общей памятью, так и в распределенных системах Механизм передачи сообщений между параллельными процессами базируется на технологии MPI (Message Passing Interface) Программный комплекс работает под управлением операционной системы семейства Microsoft™ Windows (98, 2000) Вместе с тем, поддерживается возможность генерации параллельных программ для любой операционной системы, для которой имеется реализация MPI Например, для создания программы, ориентированной на Linux-кластер, необходимо лишь наличие библиотеки MPI и компилятора для соответствующей версии Linux

Информационный фонд программного комплекса хранится в базе данных, поддерживаемой СУБД MySQL

Объем программного комплекса составляет 18 7Мб, он требует для работы не менее 32Мб оперативной памяти

Программный комплекс PGRAPH 1 0 зарегистрирован в Отраслевом фонде алгоритмов и программ (свидетельство о регистрации №6314 от 13 06 2006 г )

Пятая глава посвящена апробации предложенных концепций на примерах описания реальных алгоритмов параллельных вычислений

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

В первом эксперименте исследовался алгоритм решения линейного дифференциального уравнения в частных производных методом конечных разностей. Рассматривалась задача Дирихле для уравнения Лапласа вида:

с12и/ск2 + с12и/с1у2 = 0, (х,у) е и, и(х,у)=</>(х,у), (х,у) е Г,

где О е К2 - двумерная область, представляющая собой прямоугольник со сторонами, параллельными осям координат, Г - граница области В.

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

В главе приводится последовательный алгоритм решения данной задачи и способ его распараллеливания, основанный на геометрической декомпозиции задачи. На рис. 4 показан способ распараллеливания задачи и графическая модель параллельного алгоритма.

процесс 1 промесс 2 х

Рис. 4

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

^ max — Тпосп/ТЦ

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

Полученная оценка используется для определения эффективности программ, созданных в разработанном программном комплексе с использованием предлагаемой модели. Сравнение проводилось между результатами работы нескольких версий программы, реализующей решение уравнения Лапласа: последовательной программы, написанной на языке С++, параллельной программы на языке С++ с использованием библиотеки MPI, а также параллельной программы, сгенерированной программным комплексом на основе графической модели. На рис. 5 изображены графики зависимости времени работы каждой программы Т от размерности задачи N.

Рис. 5

Из рисунка видно, что производительность параллельной программы, автоматически сгенерированной программным комплексом РОЯАРН 1.0 на основе модели параллельного алгоритма, близка к производительности аналогичной программы, написанной на текстовом языке программирования без применения средств моделирования. Разница в производительности составляет 10-12% и обусловлена применяемым методом организации вычислений на основе модели. В перспективе возможна модернизация этого метода с целью повышения производительности генерируемых программ.

В рамках второго эксперимента была проведена проверка наглядности модели при описании вычислительных алгоритмов. Была рассмотрена задача численного решения системы дифференциальных уравнений Навье-Стокса, описывающих обтекание летательного аппарата потоком газа1:

^ = ^(/г ^ ^ Ё1И д'р)

дI дх ду дх2 ду: дхду

где ^ = (Г/^.х.у), РзО.х.у), ..., Рц(1,х,у))т- вектор искомых функций.

На рис. 6 изображено графическое представление модели параллельного алгоритма, использующего принципы распараллеливания, предложенные в работе Г.А. Тарнавского и др.

1 Вычислительная система "ПОТОК-3": опыт параллелщэцит* программного комплекса. Часть I Идеология распараллеливания /Г.А. Тарнавскии, В.Д. к!орнеев, Д. А. Вайнер и др. // Вычислительные методы и программирование -

2003 -Т4,№1. - С. 37-48.

К(Агг) = Ь 13,22 Л Ь«,22 РЧАгз) - Ь>5.23 А Ь16.2Э Л Ьи.я Р(Агл) = Ь 1д,24 Л Ь19,и Л Ь20,2*1 л Ь2,.24 = Ь 22.25 Л Ьгз,25 л Ьг4,25

Рис. 6

Распараллеливание проводилось по двум основным определяющим параметрам задачи - высоте Н и скорости V полета (т.н. глобальная параллелизация).

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

В третьем эксперименте проведена апробация модели при описании более сложных вычислительных алгоритмов. Рассмотрена модель многосеточного алгоритма, предназначенного для решения дифференциальных уравнений в частных производных эллиптического типа, получившего название «универсальная многосеточная технология» (УМТ)2. Граф-модель алгоритма, распараллеленного в соответствии с принципами, изложенными в работе С.И. Мартыненко3, приведена на рис. 7.

1 Мартыненко С.И. Универсальная многосеточная технология для численного решения дифференциальных уравнений в частных производных на структурированных сетках // Вычислительные методы и программирование - 2000 - Т.1, №1. - С 83-102

1 Мартыненко С.и Распараллеливание универсальной многосеточной технологии // Вычислительные методы и

программирование. - 2003 - Т 4, №1 - С. 49-55.

-о-

-о-

-а

Выч. ^ Ч1Ц погрет

Иниц. 4 -[дН перем

Первая® Вторая® Третья®

сетка сетка сетка

® Нулевая©

1=1-1 ■0- сетка 0 ^ 1 = 1.р

Вывода рез-тов

Список предикатов 1.1

2.1. > О З.Е > Етах

= Ь25 Л Ь35 Л Ь45

Рис.7.

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

Н(С|б) = 0 Д ( 1Д (2#3#4)Д5 Д 6 Д (9 V 7Д8Д9)) Д 10 (1)

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

В заключении обобщаются результаты проведенного исследования, приводится список опубликованных работ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1) Проведен анализ существующих подходов к моделированию параллельных алгоритмов и организации параллельных вычислений на ЭВМ. По результатам анализа сделан вывод об актуальности разработок в области создания графических моделей параллельных алгоритмов, использующих явный параллелизм при описании вычислений и ориентированных на разработку программ для широко распространенных вычислительных систем с массовым параллелизмом, таких как 8МР-системы на базе многопроцессорных персональных ЭВМ и кластеры.

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в изданиях, рекомендованных ВАК:

1 Жидченко В В Метод нахождения границ области определения алгоритмических функций в стохастическом тестировании программных продуктов // Обозрение прикладной и промышленной математики - 2001 - Т 8, Выпуск 2 -С 590

Публикации в сборниках научных трудов:

2 Жидченко В В , Коварцев А H Метод ограничения разрядной сетки ЭВМ для автоматизированного тестирования комплексов программ // Вестник СГАУ, серия «Актуальные проблемы радиоэлектроники» / Самарский государственный аэрокосмический университет - 2000 -Вып 4 - С 85-91

3 Жидченко В В Современные средства межпрограммного взаимодействия в сложных программных комплексах // Перспективные информационные технологии в научных исследованиях, проектировании и обучении Сб науч тр / Самарский государственный аэрокосмический университет-2001 -С 45-52

4 Коварцев А H, Жидченко В В Программный комплекс моделирования параллельных вычислительных процессов PGRAPH 1 0 // Инновации в науке и образовании -2006 -№6 -С 7

Публикации в трудах международных конференций.

5 Жидченко В В Повышение качества разработки параллельных программ // НАДЕЖНОСТЬ И КАЧЕСТВО Труды международного симпозиума / Под ред H К Юркова - Пенза Изд-во Пенз гос ун-та - 2002 - С 134-135

6 Жидченко В В Автоматизация разработки параллельных программ в технологии графо-символического программирования // Материалы второго Международного научно-практического семинара / Под ред проф РГ Стронгина Нижний Новгород Изд-во Нижегородского госуниверситета, 2002 - С 341-347

7 Жидченко В В , Коварцев А H Моделирование синхронных параллельных вычислений при построении математических моделей сложных систем // Первая

международная конференция «Системный анализ и информационные технологии» САИТ-2005 Труды конференции В 2т Т2 -М КомКнига, 2005 -С 154-160 Публикации в трудах всероссийских конференций.

8 Жидченко В В Метод нахождения границ области определения алгоритмически заданной функции // IV Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» / Тез докл - Таганрог, 1998 С 99-100

9. Жидченко В В Комплекс программ моделирования параллельных синхронных вычислительных процессов // Методы и средства обработки информации Труды второй Всероссийской научной конференции / Под ред Л Н Королева -М Издательский отдел факультета вычислительной математики и кибернетики МГУ им МВ Ломоносова - 2005 - С 465-471 Тезисы докладов:

10 Жидченко В В Разработка средств интеллектуальной поддержки технологии графосимволического программирования // XXV самарская областная студенческая научная конференция / Тез докл - Самара, 1999 С 113-114

11 Жидченко В В Подсистема автоматизированного тестирования функциональных модулей технологии графо-символического программирования // 50а студенческая научно-техническая конференция / Тез докл - Самара, 2000 С 53

Подписано в печать 08 10 2007 г Отпечатано с готовых оригинал-макетов в типографии ООО "Новая техника" 443010, г Самара, ул Фрунзе, 145 Бумага офсетная Печать оперативная Тираж 100 экз

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

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и краткое содержание диссертации:

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

Основные результаты диссертационной работы состоят в следующем:

1) Проведен анализ существующих подходов к моделированию параллельных алгоритмов и организации параллельных вычислений на ЭВМ. По результатам анализа сделан вывод об актуальности разработок в области создания графических моделей параллельных алгоритмов, использующих явный параллелизм при описании вычислений и ориентированных на разработку программ для широко распространенных вычислительных систем с массовым параллелизмом, таких как SMP-системы на базе многопроцессорных персональных ЭВМ и кластеры.

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

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

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

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

Содержание диссертации отражено в следующих публикациях:

1. Жидченко В.В. Метод нахождения границ области определения алгоритмических функций в стохастическом тестировании программных продуктов. // Обозрение прикладной и промышленной математики. - 2001. - Т. 8, Выпуск 2. - С. 590.

2. Жидченко В.В. Метод нахождения границ области определения алгоритмически заданной функции // IV Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» / Тез. докл. - Таганрог, 1998. С.99-100.

3. Жидченко В.В. Разработка средств интеллектуальной поддержки технологии графосимволического программирования // XXV самарская областная студенческая научная конференция / Тез. докл. - Самара, 1999. С.113-114.

4. Жидченко В.В., Коварцев А.Н. Метод ограничения разрядной сетки ЭВМ для автоматизированного тестирования комплексов программ // Вестник СГАУ, серия «Актуальные проблемы радиоэлектроники» / Самарский государственный аэрокосмический университет - 2000. - Вып. 4. - С. 85 - 91.

5. Жидченко В.В. Подсистема автоматизированного тестирования функциональных модулей технологии графо-символического программирования // 50я студенческая научно-техническая конференция / Тез. докл. - Самара, 2000. С.53.

6. Жидченко В.В. Современные средства межпрограммного взаимодействия в сложных программных комплексах // Перспективные информационные технологии в научных исследованиях, проектировании и обучении. Сб. науч. тр. / Самарский государственный аэрокосмический университет - 2001. - С. 45 ~ 52.

7. Жидченко В.В. Повышение качества разработки параллельных программ // НАДЕЖНОСТЬ И КАЧЕСТВО. Труды международного симпозиума / Под ред. Н.К. Юркова. - Пенза: Изд-во Пенз. гос. ун-та. - 2002. -С. 134-135.

8. Жидченко В.В. Автоматизация разработки параллельных программ в технологии графо-символического программирования // Материалы второго Международного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2002. -С. 341-347.

9. Жидченко В.В., Коварцев А.Н. Моделирование синхронных параллельных вычислений при построении математических моделей сложных систем // Первая международная конференция «Системный анализ и информационные технологии» САИТ-2005: Труды конференции. В 2т. Т.2. -М.: КомКнига, 2005. - С. 154-160.

10. Жидченко В.В, Комплекс программ моделирования параллельных синхронных вычислительных процессов // Методы и средства обработки информации, Труды второй Всероссийской научной конференции / Под ред. JI.H, Королева. - М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова. - 2005. - С. 465-471.

11. Коварцев А.Н., Жидченко В.В. Программный комплекс моделирования параллельных вычислительных процессов PGRAPH 1.0 // Инновации в науке и образовании. - 2006. - № 6. - С. 7.

ЗАКЛЮЧЕНИЕ

1. Абрамов С.М., Кузнецов А.А., Роганов В.А. Кроссплатформенная версия Т-системы с открытой архитектурой // Вычислительные методы и программирование. 2007. - Том 8, Раздел 2. - С. 18-23.

2. Аткинсон Л. MySQL. Библиотека профессионала. М.:Вильямс, 2002. - 624 с.

3. Б. Страуструп Язык программирования С++. Специальное издание. М.: Бином, 2001. - 1099 с.

4. Барский А.Б. Планирование параллельных вычислительных процессов М:Машиностроение, 1980. - 192 с.

5. Бахур А.Б. Системные идеи в современной инженерной практике. -М.: Пров-пресс, 2000.

6. Белоцерковский О.М. Численное моделирование в механике сплошных сред. М.: Физматлит, 1994. - 442 с.

7. Бенькович Е.С., Колесов Ю.Б., Сениченков Ю.Б. Практическое моделирование динамических систем СПб.: БХВ-Петербург, 2002. -464 с.

8. Богачев К.Ю. Основы параллельного программирования. М.: БИНОМ. Лаборатория знаний, 2003. 342 с.

9. Бусленко Н.П. Моделирование сложных систем М.: Наука, 1968.-356 с.

10. Буянов Б. Б., Легович Ю. С., Лубков Н. В., Поляк Г.Л. Построение систем подготовки управляющих решений с использованием имитационного моделирования. // Приборы и системы управления. 1996. - №12. - С. 36 - 40.

11. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход М.:Наука, 1989. - 176 с.

12. Вальковский В.А., Котов В.Е., Марчик А.Г., Миренков Н.Н. Элементы параллельного программирования. М.: Радио и связь, 1983.-240 с.

13. Вельбицкий И.В. Технология программирования. Киев: Техника, 1984.-279 с.

14. Виттих В.А. Эволюционное управление сложными системами. // Известия Самарского научного центра РАН. 2000. - №1. - С. 53-65.

15. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления СПб.: БХВ-Петербург, 2002. - 608 с.

16. Востокин С.В. Графическая объектная модель параллельных процессов и ее применение в задачах численного моделирования -Самара: Изд-во Самарского научного центра РАН, 2007. 286 с.

17. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие -Нижний Новгород: Изд-во ННГУ им. Н.И.Лобачевского, 2000. -176 с.

18. Головашкин Д.Л. Методы параллельных вычислений (Часть I): Учебное пособие. СГАУ, Самара, 2002. - 92 с.

19. Головашкин Д.Л., Головашкина С.П. Методы параллельных вычислений (Часть II): Учебное пособие. СГАУ, Самара, 2003. -103 с.

20. Головашкин Д.Л., Сойфер В.А., Шустов В.А. Реализация параллельных вычислений при разностном решении уравнений математической физики. // Известия Самарского научного центра РАН. 2000. - №1. - С. 108

21. ГомаХ. UML. Проектирование систем реального времени, параллельных и распределенных приложений М.:ДМК Пресс, 2002. - 704 с.

22. Горелик A.M., Ушкова B.JI. Фортран сегодня и завтра. М.: Наука, 1990.

23. Грегори Р. Эндрюс Основы многопоточного, параллельного и распределенного программирования- Вильяме, 2002. 512 с.

24. Дейкстра Э. Взаимодействующие последовательные процессы. В сб. "Языки программирования" под ред. Ф. Женюи. М.: Мир, 1972. -С. 9-86.

25. Дж. Макконнелл Анализ алгоритмов. Вводный курс.-М.Техносфера, 2002. 304 с.

26. ЖидченкоВ.В. Метод нахождения границ области определения алгоритмических функций в стохастическом тестировании программных продуктов // Обозрение прикладной и промышленной математики. 2001. - Т. 8, Выпуск 2. -С. 590.

27. ЖидченкоВ.В. Подсистема автоматизированного тестирования функциональных модулей технологии графо-символического программирования // 50я студенческая научно-техническая конференция / Тез. докл. Самара, 2000. С.53.

28. Замулин А.В. Системы программирования баз данных и знаний -Новосибирск: Наука, 1990. 352 с.

29. Змитрович А.И. Интеллектуальные информационные системы. -Мн.: НТООО "ТетраСистемс", 1997. 368 с.

30. Ильин В.П. Линейная алгебра: от Гаусса до суперкомпьютеров будущего. // Природа. 1999. - №6. - С. 11-18.

31. Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981. - 158 с.

32. Коварцев А.Н. Автоматизация разработки и тестирования программных средств. Самарский государственный аэрокосмический университет, Самара, 1999. - 150 с.

33. Корнеев В.В. Параллельные вычислительные системы -М.:Нолидж, 1999. 320 с.

34. Коробейников В. П. Математическое моделирование катастрофических явлений. М.: Знание, 1986.

35. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.

36. Кудрявцев Е.М. GPSS World. Основы имитационного моделирования различных систем. М.: ДМК Пресс, 2004. -320 с.

37. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера М.: Энергоатомиздат, 1988. - 480 с.

38. Левин И.И., Омаров О.М. "Расширение сетей Петри для моделирования распределенных вычислений" // Информационные технологии моделирования и управления. 2005. №4(22). С. 555-562.

39. Легалов А., Кузьмин Д., Казаков Ф., Привалихин Д. На пути к переносимым параллельным программам. И Открытые системы. -2003.- №5.

40. Лищук В.А. Математические модели сердечно-сосудистой системы. Итоги науки и техники. Бионика, биокибернетика, биоинженерия (т.7)-М.: ВИНИТИ, 1990.

41. ЛюбченкоВ.С. Искусство программирования. RS-триггера?http://www.so ftcraft,m/auto/ka/rsm/rsm01 .shtml

42. Ляпунов А.А. О кибернетических вопросах биологии. // Проблемы кибернетики. 1972. - Вып. 25. - С. 5-40.

43. Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНЕ. М.: Мир, 1977. - 584 с.

44. Мартыненко С.И. Распараллеливание универсальной многосеточной технологии // Вычислительные методы и программирование. 2003. - Т.4, №1. - С. 49-55.

45. Мартыненко С.И. Универсальная многосеточная технология для численного решения дифференциальных уравнений в частныхпроизводных на структурированных сетках // Вычислительные методы и программирование. 2000. - Т.1, №1. - С. 83-102.

46. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем СПб:БХВ-Петербург, 2002. - 400 с.

47. Одинцов И.О. Профессиональное программирование. Системный подход СПб: БХВ-Петербург, 2002. -512 с.

48. Пархоменко В. П., Стенчиков Г. JI. Математическое моделирование климата. М.: Знание, 1986.

49. Перельман И.И. Оперативная идентификация объектов управления. -М.: Энергоиздат, 1982.

50. Петров А. А. Экономика. Модели. Вычислительный эксперимент. -М.: Наука, 1996.-251 с.

51. Полетаев И.А. О математическом моделировании // Проблемы кибернетики. 1973. - Вып. 27. - С.143-151.

52. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учебное пособие для втузов. СПб.: Политехника, 1996. - 885 с.

53. Романовский Ю.М., Степанова Н.В., Чернавский Д.С. Математическое моделирование в биофизике. М.: Наука, 1975.

54. Самарский А.А., Михайлов А.П. Математическое моделирование. Идеи, методы, примеры М.:Физматлит, 2001. - 320 с.

55. Стивен Янг (Stephen J. Young) "Алгоритмические языки реального времени. Конструирование и разработка (Real Time Languages: Design and Development)". М.:Мир, 1985. - 400 с.

56. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. - 400 с.

57. Тыугу Э.Х. Концептуальное программирование. М.: Наука, 1984. -256 с.

58. Фаулер М., Скотт К. UML в кратком изложении. Применение стандартного языка моделирования. М.: Мир, 1999. - 191 с.

59. Хендерсон П. Функциональное программирование. Пер. с англ. -М.: Мир, 1983.

60. Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. М.:Мир, 1989. - 264 с.

61. ХьюзК., Хьюз Г. Параллельное и распределенное программирование с использованием С ++. М.: Вильяме, 2004.

62. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С.А.Модулярные параллельные вычислительные структуры нейропроцессорных систем М.:Физматлит, 2003. - 288 с.

63. Черняев А.П. Системы программирования для высокопроизводительных ЭВМ. Итоги науки и техники. Вычислительные науки, т.З. М.: ВИНИТИ, 1990.

64. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.-628 с.

65. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления. // Известия Академии наук. Теория и системы управления. 2000. -№6.-С. 63-81.

66. Шеннон Р. Имитационное моделирование искусство и наука. -М.: Мир, 1978.-418 с.

67. Шумаков В.И., Новосельцев В.Н., Сахаров М.П., Штенгольд Е.Ш. Моделирование физиологических систем организма. -М.: Медицина, 1971.

68. Юдицкий С.А., Магергут В.З. Логическое управление дискретными процессами. М.: Машиностроение, 1987. - 175 с.

69. IA-32 Intel Architecture Software Developer's Manual. Intel Corp., 2003.

70. Высокопроизводительные параллельные вычисления на кластерных системах. Материалы второго Международного научно-практического семинара / По ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2002. -351 с.

71. Вычислительная система "ПОТОК-3": опыт параллелизации программного комплекса. Часть 1. Идеология распараллеливания /Г.А. Тарнавский, В.Д. Корнеев, Д.А. Вайнер и др. // Вычислительные методы и программирование. 2003. - Т.4, №1. - С. 37-48.

72. Введение в программирование для параллельных ЭВМ и кластеров: Учебное пособие. / Авторы-составители: Кравчук В.В., Попов С.Б., Привалов А.Ю., Фурсов В.А., Шустов В.А.; под ред. В.А.Фурсова. // Самара: Самарский научный центр РАН, СГАУ, 2000. -87 с.

73. Т-система с открытой архитектурой /Абрамов С.М., Адамович А.И., Инюхин А.В. и др. // Труды Международной научной конференции "Суперкомпьютерные системы и их применение. SSA'2004", 26-28 октября 2004 г. Минск, ОИПИ НАН Беларуси, С. 18-22.

74. A. Beguelin, J. J. Dongarra, G. A. Geist, R. Manchek, and V. S. Sunderam. Graphical development tools for network-based concurrent supercomputing. // Proceedings of Supercomputing 91, pages 435-444, Albuquerque, 1991.

75. Andrews G. Concurrent Programming: Principles and Practice.- Menlo Park, CA: Benjamin/Cummings, 1991.

76. Ashton D., Gropp W., Lusk E. Installation and User's Guide to MPICH, a Portable Implementation of MPI. Version 1.2.5 University of Chicago, Argonne National Laboratory, 51 p.

77. BabaogluO. Paralex: An Environment for Parallel Programming in Distributed Systems. Proc. ACM Int. Conf. On Supercomputing, July, 1992.

78. Backus J. Can Programming Be Liberated from von Neuman Style? A Functional Stile and Its Algebra of Programs.- Communications of ACM. 1978, v. 21, No. 8.

79. Bacon J. Concurrent Systems: Operating Systems, Database and Distributed Systems: An Integrated Approach. 2nd ed. Reading, MA: Addison-Wesley, 1998.

80. Booch G. Object-Oriented Design. Redwood City, Calif.: Benjamin/Cammings, 1991.

81. Booch G., Jacobson I., Rumbaugh J. The Unified Modeling Language for Object-Oriented Development: Documentation Set Version 1.1. September 1997.

82. Brinch Hansen P. Operating System Principles. Englewood Cliffs, N.J.: Prentice Hall, 1973.

83. Browne J.C., Azam M., and Sobek S. CODE: A Unified Approach to Parallel Programming. IEEE Software, July, 1989, p. 11.

84. Dongarra J.J., Bunch J.R., Moler C.B., and Stewart G.W. LINPACK: Users Guide. Soc. Indust. Appl. Math., Philadelphia, 368 p.

85. Fet Ya., Pospelov D. Parallel Computing in Russia Lect. Notes in Сотр. Sci., Vol. 964, Springer-Verlag, Berlin, 1995. pp. 464-476

86. Foster I. Designing and Building Parallel Programs. Reading, MA: Addison-Wesley, 1995.

87. Foster I., Kesselman C., eds. The Grid: Blueprint for a New Computing Infrastructure. San Francisco, С A: Morgan Kaufmann, 1999.

88. G. Hutton Programming in Haskell. Cambridge University Press, 2007. -184 c.

89. Harel D. Statecharts: A Visual Formalism for Complex Systems. // Science of Computer Programming. 1987. №8. C.231-274.

90. Harel D. On Visual Formalisms. CACM 31, no. 5 (May 1988): 514-530.

91. HempelR. The Argonne/GMD Macros in FORTRAN for Portable Parallel Programming using the Message Passing Programming Model. -Feb. 1991.

92. Hennessy J., Patterson D. Computer Architecture: A Quantitative Approach. 2nd ed. San Francisco: Morgan Kaufmann, 1996.

93. Jacobsonl. Object-Oriented Software Engineering. Reading, Mass.: Addison-Wesley, 1992.

94. Jordan H. A special purpose architecture for finite element analysis. -Proc. 1978 Int. Conf. on Parallel Processing, pp. 263-266.

95. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing: Design and Analysis of Algorithms. Menlo Park, CA: Benjamin/Cummings, 1994.

96. Lamport L. Proving the correctness of multiprocess programs. IEEE Trans. On Software Engr. - 1977. - SE-3, 2 (March): 125-143.

97. Peterson G. Myths about the mutual exclusion problem. // Information Processing Letters. -1981. -12, 3 (June): pp. 115-116.

98. Raynal M. Algorithms for Mutual Exclusion. Cambridge. MA: MIT Press, 1986.

99. Rumbaugh J., J.M. Blaha, W. Premerlani, F. Eddy, and W. Lorenson Object-Oriented Modeling and Design.- Englewood Cliffs, N.J.: Prentice Hall, 1991.

100. Schneider F. On Concurrent Programming. New York: Springer, 1997.

101. Simon Peyton JonesHaskell 98 language and libraries: the Revised Report. Cambridge University Press, 2003. - 272 c.

102. Tyugu, E., Valt, R. Visual programming in NUT. // Journal of visual languages and programming. -1997. v. 8. - C. 523 - 544.

103. W. Gropp and E. Lusk and N. Doss and A. Skjellum A high-performance, portable implementation of the MPI message passing interface standard Parallel Computing, volume 22, number 6, 09.1996, c. 789-828

104. Wilson G. Practical Parallel Programming. MA: MIT Press, 1995.