Содержание к диссертации
Введение
1 Параллельные вычисления на ЭВМ 13
1.1 Классификация параллельных вычислительных систем 13
1.2 Явный параллелизм и автоматическое распараллеливание 17
1.3 Графические модели параллельных процессов 20
1.4 Взаимодействие параллельных процессов 27
1.4.1 Механизмы синхронизации параллельных процессов 28
1.4.2 Проблема тупиков в параллельных алгоритмах 36
Выводы и основные результаты 38
2 Графическая модель алгоритмов параллельных вычислений 39
2.1 Концептуальное описание граф-модели 39
2.2 Синхронизация между параллельными ветвями граф-модели 43
2.3 Создание граф-моделей параллельных вычислений ...46
2.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
3.6.1 Параллельная модель RS-триггера 102
3.6.2 Модель RS-триггера без синхронизации 109
Выводы и основные результаты 112
4 Программный комплекс моделирования и анализа алгоритмов параллельных вычислений 113
4.1 Архитектура программного комплекса моделирования и анализа алгоритмов параллельных вычислений 113
4.2 Программный комплекс моделирования и анализа алгоритмов параллельных вычислений PGRAPH 1.0 116
4.2.1 Создание моделей параллельных алгоритмов в программном комплексе PGRAPH 1.0 119
4.2.2 Генерация исходных текстов параллельных программ на языке C++ 123
4.2.3 Межмодульный информационный интерфейс 124
4.2.4 Обмен данными между параллельными процессами 126
4.2.5 Модуль передачи сообщений 128
Выводы и основные результаты 129
5 Экспериментальные исследования практической значимости модели 130
5.1 Решение уравнения Лапласа 130
5.1.1 Постановка задачи и последовательный алгоритм решения уравнения Лапласа 130
5.1.2 Параллельный алгоритм решения уравнения Лапласа 132
5.1.3 Экспериментальная проверка эффективности параллельного алгоритма 138
5.2 Распараллеливание алгоритма решения системы дифференциальных уравнений Навье-Стокса 143
5.3 Распараллеливание многосеточных методов 149
Выводы и основные результаты 161
Заключение 163
Список использованных источников 167
Приложение 1. Тексты программ и примеры моделей 177
- Явный параллелизм и автоматическое распараллеливание
- Синхронизация между параллельными ветвями граф-модели
- Метод поиска критических данных на основе алгебры над способами использования данных
- Программный комплекс моделирования и анализа алгоритмов параллельных вычислений PGRAPH 1.0
Введение к работе
Развитие моделей описания параллельных вычислений происходит с середины XX века одновременно со становлением теории последовательных вычислений.
Основными проблемами параллельных вычислений являются согласованное использование данных (синхронизация) и связанная с ней проблема тупиковых ситуаций. Для синхронизации вычислений разработано множество механизмов, таких как семафоры, критические секции, событийное управление, мониторы. Однако универсального решения, приемлемого для любых задач, до сих пор не найдено. Одни методы синхронизации не разрешают проблему возникновения тупиковых ситуаций, другие сложны для практического применения.
Параллельный вычислительный процесс приобретает особую сложность при распараллеливании на уровне подзадач и подпрограмм. В этом случае параллельные процессы могут иметь сложную внутреннюю структуру, длительность их выполнения не фиксирована; процессы взаимодействуют, обмениваются данными и обращаются к общим ресурсам. Корректная синхронизация таких процессов особенно важна для обеспечения правильности работы параллельной программы. Сложность взаимодействия параллельных процессов на уровне подзадач и подпрограмм практически исключает безошибочную работу с ними без применения средств автоматизации и делает актуальным применение методов математического моделирования для изучения взаимодействия параллельных процессов, оценки их характеристик и проверки корректности синхронизации с целью создания надежных параллельных программ.
Одной из проблем как последовательных, так и параллельных вычислений, является наглядное представление вычислительного процесса с целью создания такой нотации (желательно графической), которая позволила
бы разрабатывать модели описания параллельных вычислительных процессов конечным пользователям - специалистам в различных предметных областях.
В области теории и практики моделирования параллельных вычислений существенный вклад внесли такие ученые как Г. Буч, В.В. Воеводин, Вл.В. Воеводин, В.П, Гергель, Э. Дейкстра, В.Е. Котов, К. Петри, Р.Г. Стронгин, Ч. Хоар, И.Якобсон и др.
Вопросам разработки графических моделей вычислительных процессов посвящены работы И.В. Вельбицкого, А.Н. Коварцева, Д.Харела и др.
Использование графических моделей позволяет ускорить разработку параллельных вычислительных процессов и повысить их надежность, поскольку допускает более компактное, чем текст, интуитивно понятное и легко формализуемое представление вычислительного процесса, исключающее множество ошибок при проектировании и удобное для разработки методов автоматического анализа модели.
Существует множество графических моделей описания параллельных процессов, а также систем, позволяющих генерировать программы на основе этих моделей. Каждая модель имеет специфическую область применения, в которой она обладает максимальным удобством использования и наглядностью. В области описания вычислительных процессов наиболее удобной представляется форма, близкая к традиционным блок-схемам. Проектирование вычислительных процессов в модели, близкой к блок-схемам, реализовано в технологии графо-символического программирования (ГСП-технологии), разработанной на кафедре информационных систем и технологий Самарского государственного аэрокосмического университета. Модель ГСП-технологии ориентирована на последовательные вычисления, но заложенные в нее принципы позволяют перейти к описанию параллелизма. Настоящая диссертационная работа посвящена разработке графической модели параллельных вычислительных процессов, базирующейся на модели ГСП-технологии, а также методов и средств автоматического анализа предложенной модели, способствующих повышению надежности параллельных
вычислительных процессов. В результате работы создан программный комплекс, реализующий указанные методы и средства, предназначенный для построения моделей параллельных вычислительных процессов и автоматической генерации параллельных программ на их основе.
Результаты работы представляют большую практическую значимость, поскольку позволяют упростить и ускорить разработку параллельных вычислительных процессов специалистами в различных предметных областях, предоставляя интуитивно понятную модель описания вычислений, средства автоматического анализа модели и возможность повторного использования обширного фонда алгоритмов и программ, созданных в технологии ГСП, при переходе к параллелизму вычислений.
Целью диссертационной работы является сокращение сроков разработки параллельных алгоритмов и повышение их качества за счет создания программного комплекса, предназначенного для моделирования и анализа алгоритмов параллельных вычислений с использованием наглядной графической модели и средств автоматического поиска ошибок совместного использования данных и синхронизации.
. В соответствии с поставленной целью, в диссертационной работе решаются следующие задачи исследования:
Анализ существующих подходов к моделированию параллельных алгоритмов и организации параллельных вычислений на ЭВМ;
Разработка графической модели алгоритмов параллельных вычислений, ориентированной на использование конечными пользователями в различных предметных областях;
Разработка методов автоматического поиска критических данных и анализа корректности синхронизации в алгоритмах параллельных вычислений, описываемых предлагаемой моделью;
Создание программного комплекса, предназначенного для построения моделей алгоритмов параллельных вычислений и их реализации на ЭВМ с параллельной архитектурой;
5) Апробация модели при решении практических вычислительных задач, а также экспериментальная проверка эффективности параллельных программ, созданных с использованием модели.
Методы исследования. В диссертационной работе используются методы математического анализа, теория графов, теория формальных грамматик, логика предикатов, численные методы.
Научная новизна. В результате проведенных исследований был получен ряд новых научных результатов:
Разработана новая модель описания алгоритмов параллельных вычислений, ориентированная на их наглядное графическое представление;
Разработаны и реализованы метод и алгоритм автоматического поиска критических данных в предложенной модели;
Предложен метод анализа корректности синхронизации в модели параллельного алгоритма;
Разработаны и реализованы метод и алгоритм поиска тупиков в алгоритмах параллельных вычислений, описываемых предложенной моделью;
Создан программный комплекс, содержащий визуальную среду для построения графических моделей алгоритмов параллельных вычислений, средства автоматизированного поиска критических данных и проверки корректности синхронизации параллельных вычислений, а также средства автоматического синтеза параллельных программ на основе созданных моделей.
На защиту выносятся:
графическая модель алгоритмов параллельных вычислений;
метод и алгоритм автоматического поиска критических данных в предложенной модели;
метод анализа корректности синхронизации в параллельном алгоритме;
метод и алгоритм поиска тупиков в алгоритмах параллельных вычислений, описываемых предложенной моделью.
Практическая ценность работы заключается в разработке программного комплекса моделирования алгоритмов параллельных вычислений и их реализации на ЭВМ с параллельной архитектурой. Использование программного комплекса не требует от пользователя глубоких познаний в теории параллельного программирования, что позволяет применять его для создания эффективных параллельных программ конечными пользователями, специалистами в различных предметных областях. Программный комплекс обеспечивает возможность автоматического синтеза параллельных программ на основе построенных моделей.
Результаты диссертационной работы нашли применение при выполнении работ по тематическому плану научно-исследовательских работ в Самарском государственном аэрокосмическом университете, финансируемых из федерального бюджета по единому заказ-наряду в 1998 г., утвержденному министерством общего и профессионального образования РФ. Результаты диссертационной работы внедрены в учебный процесс специальности 230102 -Автоматизированные системы обработки информации и управления Самарского государственного аэрокосмического университета, что подтверждено актом внедрения.
Апробация работы. Основные положения диссертационной работы, научные и практические результаты докладывались на двух всероссийских и трех международных конференциях: IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 1998); Второй Всероссийской научной конференции «Методы и средства обработки информации» МСО-2005 (Москва, 2005); Международном симпозиуме «Надежность и качество» (Пенза, 2002); Международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2002); Первой международной конференции «Системный анализ и информационные технологии» САИТ-2005 (Переславль-Залесский, 2005).
Публикации. Всего по теме диссертации опубликовано 11 печатных работ. Список опубликованных работ приведен в заключении. Структура и краткое содержание диссертации:
Диссертация состоит из основной части и приложения. Основная часть содержит введение, пять глав, заключение, список использованных источников. Приложение содержит тексты программ и примеры моделей.
В первой главе проводится анализ существующих моделей описания алгоритмов параллельных вычислений, а также средств и методов реализации параллельных вычислений, рассматриваются различные архитектуры параллельных вычислительных систем.
Вторая глава посвящена описанию предлагаемой графической агрегатной модели (граф-модели) параллельных алгоритмов. Приводится формальное описание модели, описываются принципы ее построения и организации взаимодействия (синхронизации) между параллельными участками алгоритма.
В третьей главе описываются методы проверки корректности модели алгоритма параллельных вычислений. Разработанные в рамках работы методы позволяют находить в параллельном алгоритме данные, совместно используемые несколькими вершинами (критические данные), а также проверять корректность введенных разработчиком модели дуг синхронизации и семафорных предикатов. Корректная синхронизация подразумевает последовательное исполнение вершин, использующих критические данные, и отсутствие тупиков в вычислительном алгоритме, описываемом моделью.
В четвертой главе приводится описание программного комплекса PRGAPH 1.0, предназначенного для моделирования алгоритмов параллельных вычислений с использованием предлагаемой модели.
Пятая глава посвящена апробации предложенных концепций на примерах описания реальных алгоритмов параллельных вычислений.
Рассмотрены графические модели нескольких алгоритмов решения вычислительных задач, опробованы методы поиска критических данных и
проверки корректности синхронизации, экспериментально исследована эффективность параллельных программ, синтезируемых разработанным программным комплексом на основе графической модели алгоритма.
В заключении обобщаются результаты проведенного исследования, приводится список опубликованных работ.
Явный параллелизм и автоматическое распараллеливание
Работы в области моделирования и построения параллельных алгоритмов можно разделить на два больших направления: 1) Неявный параллелизм. Это направление изучает методы автоматической генерации параллельных алгоритмов на основе их последовательных прототипов (автоматического распараллеливания последовательных алгоритмов). 2) Явный параллелизм. Разработка методов организации вычислений, изначально ориентированных на реализацию на ЭВМ с параллельной архитектурой. Исследования в области автоматического распараллеливания вычислительных алгоритмов необходимы в связи с наличием большого объема ранее разработанных методов, алгоритмов и программ для решения различных задач на последовательных ЭВМ. Их реализация на параллельных ЭВМ требует модификации, связанной с распределением данных и вычислений по узлам параллельной ЭВМ, а также с адаптацией под особенности архитектуры конкретной ЭВМ. Этот процесс важно автоматизировать, чтобы максимально сократить его длительность и избавить исследователей - специалистов в различных областях, которые часто являются авторами и пользователями вычислительных программ, от знакомства со спецификой конкретной ЭВМ, на которой программа будет исполняться.
Автоматическое распараллеливание имеет большое значение и при создании новых вычислительных программ. Последовательные алгоритмы удобны и естественны для человека в силу того, что люди привыкли думать и действовать последовательно. Вместе с тем, любая современная ЭВМ обладает определенной степенью параллелизма. Появление многоядерных процессоров в персональных ЭВМ позволяет с уверенностью говорить о том, что в ближайшем будущем все ЭВМ будут параллельными. В подобных условиях массовое использование ЭВМ для выполнения пользовательских программ, большинство из которых являются последовательными, становится невозможным без применения методов автоматического распараллеливания.
Различают распараллеливание на уровне выражений и распараллеливание на уровне команд. В первом случае используются свойства математических и логических операций (ассоциативность, коммутативность, дистрибутивность) для изменения порядка вычислений в выражениях. Если в результате такого изменения удается выделить независимые друг от друга фрагменты выражения, то их вычисляют одновременно (параллельно).
При распараллеливании на уровне команд исследуются зависимости между различными участками алгоритма с точки зрения используемых данных и очередности выполнения. Независимые друг от друга участки выполняют параллельно.
Работы в области автоматического распараллеливания вычислительных алгоритмов принадлежат таким ученым, как Абрамов С.М./1, 73/, Воеводин В.В., Воеводин Вл.В./15/, Легалов А.И./39/, Тыугу Э.Х./57, 102/ и др.
Объектом для анализа с целью автоматического распараллеливания, как правило, является программа на одном из языков программирования, реализующая вычислительный алгоритм. Отдельной областью исследований является так называемое функциональное программирование, в котором «единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции и задание для этого имени выражения, вычисляющего значение функции, а единственным правилом композиции — оператор суперпозиции функции». /59/ Функциональное программирование позволяет описать процесс вычислений в декларативном стиле, который, в отличие от «традиционного» императивного стиля написания программ, предоставляет большую свободу для модификации программы на этапе ее трансляции в исполнимый код, с целью распараллеливания. Первыми средствами создания параллельных программ на основе функциональных программ, были FP /78/, Haskell /88, 101/, ПРИЗ /31/. Среди современных систем следует отметить Т-систему /1, 73/, ПИФАГОР /39/, NUT/102/.
Наряду с несомненными достоинствами, такими как .возможность использования ранее разработанных и хорошо отлаженных последовательных программ, сохранение привычного для человека последовательного стиля разработки вычислительных алгоритмов, обеспечение переносимости программ, автоматическое распараллеливание обладает недостатками. Основным недостатком является ограниченная область применения. К сожалению, не все последовательные алгоритмы допускают эффективное распараллеливание. Иногда сам численный метод, на основе которого построен алгоритм, не допускает распараллеливания.
Для достижения максимальной производительности необходимо уже на этапе разработки алгоритма учитывать параллелизм и явно выделять участки, которые должны выполняться одновременно. Более того, необходимо учитывать архитектуру и особенности конкретной параллельной ЭВМ, на которой будет исполняться программа.
Основные сложности, с которыми сталкиваются исследователи в области построения параллельных алгоритмов с явным параллелизмом, в первую очередь связаны с наглядным представлением алгоритма. Текстовая нотация, традиционно используемая в математике и программировании, удобна для представления последовательных процессов. Однако последовательная природа самого текста значительно затрудняет восприятие текстового описания параллельных вычислений. На первый план выдвигаются графические способы описания параллелизма.
Основой подавляющего большинства графических способов представления параллельных процессов является форма представления в виде графа, то есть совокупности вершин (узлов), соединенных между собой дугами (ребрами). В отличие от текстовой формы записи, в которой объекты (символы и слова) образуют последовательность, а каждый объект связан только с левым и правым «соседом», графовая форма позволяет наглядно изображать более сложные взаимосвязи, поскольку в ней каждый объект может соединяться с несколькими другими объектами. В этом смысле текстовая форма одномерна, в то время как графовая форма - многомерна. Возможность варьировать геометрические размеры, форму и цвет вершин, внешний вид и толщину дуг, изменять взаимное расположение вершин без изменения топологии графа значительно увеличивают выразительные возможности графовой формы представления.
Графические модели обычно являются ориентированными графами, в которых дуги определяют направление передачи данных или зависимость между вершинами. Вершины и дуги обычно снабжаются текстовыми аннотациями, которые именуют их, перечисляют их содержимое или свойства.
Синхронизация между параллельными ветвями граф-модели
При создании математических моделей параллельных вычислений ключевой проблемой является синхронизация вычислений, т.е. организация их согласованного выполнения. Существуют различные способы синхронизации, такие как критические интервалы, семафоры, обмен сообщениями и почтовые ящики, мониторы /33/. В предлагаемой модели применяется комбинированный способ, использующий одновременно механизмы передачи сообщений и принципы мониторной синхронизации.
Определим почтовый ящик Lpost как список, формируемый из сообщений, с помощью которых вершины модели информируют друг друга о своем состоянии: Lpost = [fijojo WmjnL гДе И-ij - сообщение, посылаемое от вершины Aj вершине Aj. Возможность передачи сообщения от одной вершины граф-модели другой вершине изображается графически дугой синхронизации Фу, проведенной из вершины-источника сообщения в вершину-получатель сообщения. Дуги синхронизации изображаются пунктирными стрелками (рисунок 2.1, б).
Если вершины не являются взаимоисключающими, то использование операции "V" над их сообщениями не разрешает конфликта совместного использования данных, так как приход сообщения от одной из таких вершин не исключает запуска другой на исполнение. Примеры подобных ситуаций приведены на рисунке 2.2, б), в).
На рисунке 2.2, б) граф-модель дополнена дугой Ч . Если управление передается по этой дуге от вершины А4 к вершине А5, то оператор последней может исполняться одновременно с оператором вершины Аг, что приведет к конфликту совместного использования данных.
На рисунке 2.2, в) вершины А4 и А5 принадлежат различным параллельным ветвям. В этом случае использование операции "Vм в семафорном предикате вершины А2 также не исключает конфликта, поскольку операторы вершин А4 и As могут исполняться одновременно, и приход сообщения от одной из них не гарантирует, что оператор другой вершины также завершил исполнение.
Приведенные рассуждения и примеры показывают, что операцию "V" в семафорных предикатах следует применять с осторожностью, и только в тех случаях, когда легко видеть, что вершины, от которых исходят дуги синхронизации, являются взаимоисключающими. 2.3 Создание граф-моделей параллельных вычислений
Создание модели начинается с изучения предметной области (ПО), в которой будут производиться вычисления. Под предметной областью в дальнейшем понимается совокупность набора данных и набора операторов (вычислительных модулей), производящих вычисления над этими данными (словарь данных и библиотека вычислительных модулей) (см. рисунок 2.3).
Словарь данных Библиотека вычислительных модулей Имя Тип Нач. знач. Комментарий Модуль 1 D1 TD1 D1_0 Данное Dl Модуль 2 D2 TD2 D2_0 Данное D2 і! Модуль К DN TDN DN_0 Данное DN Рисунок 2.3 - Предметная область
Словарь данных представляет собой таблицу, в которой для каждого данного определено уникальное имя, тип, начальное значение и краткий комментарий к его назначению в ПО.
Вычислительные модули делятся на базовые модули и объекты. Под базовым модулем понимается исходный текст вычислительного модуля, представленный в виде функции на одном из языков программирования (например, С или C++), с соблюдением определенного формата.
Характерная форма модуля — это текстовый файл, являющийся объектом для текстового редактора. Удобство редактирования и наглядность диктуют ограничения сверху на размер модуля, который обычно колеблется в диапазоне 30-300 строк исходного текста.
Базовый модуль на уровне интерфейса оперирует формальными параметрами и описывает алгоритм преобразования формальных параметров. В предлагаемой модели понятие формального параметра заменено понятием типа данного, поскольку на самом деле другие атрибуты параметров в базовых модулях не несут никакой смысловой нагрузки, важен лишь тип параметра и порядок его использования, а "осмысление" назначения параметров возникает только после их аппликации к фактическим параметрам. Например, процедура, реализующая формулу А = В С, в одной интерпретации типов данных вычисляет силу F по заданным ускорению а и массе т материальной точки (F = а т), в другой - путь S, по заданной скорости V и времени t (S = V t).
Привязка объектов к данным ПО производится путем формирования так называемого паспорта объекта. Процедура привязки называется паспортизацией объекта. Под паспортом объекта понимается таблица, содержащая перечень имен формальных параметров и соответствующих им имен данных ПО с указанием способа получения ими своих значений. По способу получения своих значений данные в паспорте делятся на три группы: 1) инициируемые (импортируемые) данные, которые должны принять значения до их использования объектом; 2) вычисляемые (экспортируемые) данные, которые впервые получают свои значения в процессе выполнения объекта (в процессе вычислений); 3) множества инициируемых и вычисляемых данных могут пересекаться, образуя множество модифицируемых (изменяемых) данных. Таким образом, создание объекта на основе базового модуля сводится к формированию паспорта объекта. Процесс паспортизации заключается в установлении соответствий между именами формальных параметров базового модуля и именами данных ПО. При этом необходимо следить за совпадением типов формальных параметров базового модуля и соответствующих данных ПО.
Это свойство полиморфизма объектов позволяет избежать избыточности при порождении новых акторов, которые различаются между собой только привязкой по данным. Другими словами, на основе одного отлаженного и оттестированного базового модуля за счет механизма автоматизированной привязки по данным можно построить несколько корректных акторов, что позволяет значительно ускорить создание модели.
Кроме акторов используются еще два вида объектов: предикаты и агрегаты. Отличие между объектами заключается в способе использования данных. Акторы и агрегаты могут изменять значения данных, с которыми они работают, а предикаты не изменяют значений данных. При этом акторы и агрегаты вырабатывают признак аварийного или нормального завершения вычислений, а предикаты — признак истинности или ложности проверки некоторого условия над значением данных.
Формально предикат представляет собой отображение из множества данных предметной области на множество логических значений "истина" и "ложь": 4 (di, d2, ... , dm) - {0, 1}. Невозможность изменения предикатом данных, с которыми он работает, делает все его данные входными: ( 1Ь d2,..., dm) є Din.
Объекты являются исходным материалом для построения графической модели - агрегата. Агрегат создается в форме графа, в котором объекты ПО играют роль вершин и дуг. Дуги — предикаты, а вершины — акторы или агрегаты. Дуги графа определяют передачу управления от одной вершины к другой.
Предикат — это логическая функция, которая в зависимости от значений данных ПО равна 0 или 1. Если значение 0, то переход по дуге запрещен. Иначе — переход разрешен. Переход выполняется после завершения вычислений в текущей вершине, по самой приоритетной из всех разрешенных дуг, исходящих из нее.
Формально агрегат представляет собой помеченный ориентированный граф с входной (корневой) и выходной (концевой) вершинами: G = {А, , Ф, R}, где А = {Аь А2, ..., Ап} - множество вершин графа, каждая вершина А, помечена некоторым актором, Р = { ш, Ч ш, ..., 4%} - множество дуг управления, Ф = {Фщ, Фуа, ..., Ф } - множество дуг синхронизации, R — отношение над множествами вершин и дуг графа, определяющее способ их связи.
Метод поиска критических данных на основе алгебры над способами использования данных
Оперируя понятием способа использования, задачу поиска критических данных можно сформулировать следующим образом: зная способ использования данных в каждой вершине, найти такие данные, для которых способ использования графом модели в целом равен 3.
Предлагаемый алгоритм поиска критических данных решает задачу именно в такой формулировке. Он основан на построении формального описания граф-модели, которое позволяет обнаруживать в ней критические данные на основе информации о способе использования данных каждой вершиной и взаимном расположении этих вершин.
Переход из вершины Aj в вершину А2 возможен только при истинности одного или сразу нескольких предикатов рь р2,..., рп. Приоритеты дуг значения не имеют. Очевидно, что п дуг в этом случае могут быть заменены одной дугой, предикат которой будет равен дизъюнкции предикатов Рь р2 Рп- С учетом приведенных рассуждений, далее предполагается, что из одной вершины в другую может следовать не более одной дуги.
Второе замечание связано с исследованием иерархических моделей, агрегат которых в качестве вершин содержит другие агрегаты. Для поиска критических данных такие модели могут быть приведены к форме без иерархии. При этом вершины, содержащие агрегаты, заменяются подграфами, соответствующими этим агрегатам.
Замена производится по следующему алгоритму: 1) Входящие в заменяемую вершину А; дуги направляются в корневую вершину агрегата Gk1, содержащегося в вершине А;; 2) Если в агрегате G имеется более одной конечной вершины, то в него добавляется фиктивная конечная вершина, не выполняющая ни каких действий (с нулевым временем выполнения), в которую направляются дуги из других конечных вершин; 3) Дуга, исходящая из вершины Aj, заменяется на дугу из конечной вершины агрегата Gk1.
Предложенный способ исключения иерархии соответствует принципам управления процессом вычислений в рассматриваемой модели, поэтому не приводит к потере или появлению новых критических данных. Поскольку фиктивные конечные вершины не обращаются к данным, их введение также не влияет на способ использования данных в модели.
Рассмотрим возможные варианты взаимного расположения вершин в графе модели. Простейший случай - передача управления из одной вершины модели в другую. Введем двуместную операцию следования над способами использования данных в вершинах, соединенных дугой управления. Обозначим эту операцию символом "А". Результатом операции будет способ использования данных для подграфа, состоящего их двух вершин и соединяющей их дуги. Пример подграфа приведен на рисунке 3.4, а).
Критические данные в таком подграфе могут быть только в том случае, когда они уже присутствуют в одной из его вершин, то есть способ использования некоторого данного в одной из вершин подграфа равен 3. Для определения результата операции следования при других значениях способа использования данных учтем то обстоятельство, что критические данные возникают только при использовании данных для записи. Если рассматриваемый нами подграф будет исполняться одновременно с другой параллельной ветвью, имеющей с ним общие данные, то при использовании этих данных для записи в любой из вершин А\ или Аг, может возникнуть конфликтная ситуация. Следовательно, результат операции следования должен быть равен 2, если хотя бы одна из вершин подграфа использует некоторое данное для записи. Результаты операции следования для любых значений способов использования данных приведены в таблице истинности на рисунке 3.4, б).
Рассмотрим подграф Gi, изображенный на рисунке 3.4, в). Этот подграф обозначает ветвление, то есть развитие алгоритма по одному из нескольких путей. Он состоит из вершин, в которые входят последовательные дуги, исходящие из одной и той же вершины (на рисунке 3.4, в) эта вершина изображена пунктиром). Введем для таких подграфов операцию ветвления над способами использования данных в вершинах, принадлежащих различным направлениям развития вычислений. Обозначим ее символом "V". Формула вычисления способа использования данных в подграфе G2 приведена на рисунке 3.4, в). Таблица истинности для операции ветвления приведена на рисунке 3.4, б).
Отметим, что предложенная алгебра над способами использования данных содержит формулы, которым нельзя поставить в соответствие корректный в предлагаемой модели агрегат. Так, формуле 3) соответствует агрегат, состоящий из двух отдельных вершин, одна из которых может получить управление. Условие, при котором это происходит, не определено. Поскольку в предлагаемой модели выполнение алгоритма начинается с единственного оператора, лежащего в корневой вершине агрегата, рассмотренный случай является некорректным.
Аналогично, формула 4) описывает две отдельные вершины, исполняющиеся параллельно и не связанные никакими дугами. Так как параллельные ветви в граф-модели должны начинаться и заканчиваться дугами определенного типа, такой агрегат также будет некорректным. При описании реальных агрегатов формулы 3) и 4) всегда используются совместно с операцией следования.
Доказательство: Так как граф-модель не содержит параллельных ветвей, в ее формуле не может присутствовать операция параллельного исполнения. При построении формулы такой граф-модели, на основании свойства эквивалентности операций следования и ветвления, все операции ветвления можно заменить на операции следования. Таким образом, какой бы сложной ни была структура граф-модели, ее формула будет содержать полный перечень вершин модели, символы операции следования, и возможно, скобки. Используя свойство ассоциативности операции следования, скобки из такой формулы можно исключить. Свойство поглощения операции следования позволяет исключить из формулы также все повторные вхождения вершин. После указанных преобразований формула над способами использования данных будет состоять из перечня вершин граф-модели без повторений, разделенных операцией следования. Утверждение доказано.
Программный комплекс моделирования и анализа алгоритмов параллельных вычислений PGRAPH 1.0
В рамках настоящей работы разработан и реализован программный комплекс PGRAPH 1.0, предназначенный для визуального построения граф-моделей параллельных алгоритмов и автоматической генерации программ на основе этих моделей.
Программный комплекс ориентирован на работу в модели передачи сообщений. Генерируемые программы могут исполняться как на вычислительных системах с общей памятью, так и в распределенных системах. Механизм передачи сообщений между параллельными процессами базируется на технологии MPI (Message Passing Interface) /103, 15/, которая представляет стандартизованные средства передачи сообщений в различных операционных системах на различных аппаратных платформах.
Программный комплекс работает под управлением операционной системы семейства Microsoft Windows (98, 2000). Тем не менее, генерируемые параллельные программы могут работать в любой операционной системе, для которой имеется реализация MPI. Например, для создания программы, ориентированной на Linux-кластер, необходимо лишь наличие библиотеки MPI и компилятора для соответствующей версии Linux. Выбор языка программирования для описания базовых модулей также ограничен лишь наличием реализации MPI для этого языка. В настоящее время реализована версия программного комплекса PGRAPH 1.0, использующая для написания базовых модулей язык C++. Архитектура программного комплекса соответствует архитектуре, представленной на рис. 4.1. Для взаимодействия с пользователем используется графический оконный интерфейс Windows. Подсистема управления параллельными вычислениями интегрирована с графическим редактором граф-моделей. Благодаря этому, при выполнении различных действий в системе, пользователь всегда видит текущий агрегат, над которым эти действия выполняются (рисунок 4.2).
В систему интегрирован редактор текстов, предназначенный для написания исходных текстов базовых модулей и выполняющий простейшие операции по проверке их синтаксической корректности, а также редактор объектов технологии ГСП. Компилятор объектов выполнен в виде отдельного модуля. Он позволяет на основании описания объектов, хранящегося в информационном фонде системы, генерировать исходные тексты на языке C++, предназначенные для компиляции в среде программирования Microsoft Visual C++ 6.0. В качестве компилятора исходных текстов используется программный продукт Microsoft Compiler, входящий в состав указанной среды программирования. При создании программ для операционной системы, отличной от Windows (например, Unix), достаточно подключить к системе соответствующий компилятор объектов и компилятор исходных текстов.
Система использует реализацию MPI, созданную в Аргоннской научной лаборатории (Argonne National Laboratory) (США) - MPICH1161.
Это одна из наиболее распространенных реализаций МРІ, имеющая версии для операционных систем WindowsNT/2000 и Unix.
В состав MPICH входит простейшее средство программирования и измерения производительности программ - библиотека MPED. При построении проекта с использованием этой библиотеки все вызовы МРІ-функций обрамляются короткими участками кода, сохраняющими временные метки в журнальном файле. Визуальное средство анализа этого файла - программа Jumpshot, входящая в состав MPICH - позволяет наглядно изображать временные диаграммы процесса выполнения параллельной программы. Используя это средство, можно измерять соотношения между длительностью выполнения основного кода программы и временем, затрачиваемым на передачу сообщений, и в результате такого анализа выявлять в программе точки потери производительности.
Подсистема управления параллельными вычислениями осуществляет запуск параллельной программы на выполнение. По желанию пользователя может генерироваться версия программы, построенная с использованием профилировочной библиотеки MPED. В этом случае подсистема управления параллельными вычислениями выполняет предварительную обработку журнального файла и запуск программы Jumpshot для его анализа.
В соответствии с концепциями технологии ГСП, моделирование начинается с определения типов и данных предметной области. Поддерживается словарь типов, содержащий описание базовых типов данных языка C++, а также определенных на его основе пользовательских типов (рисунок 4.3).
На основе зарегистрированного в системе базового модуля, а также inline-модулей, созданных в интегрированном текстовом редакторе, пользователь конструирует объекты технологии ГСП - акторы и предикаты. Этот этап выполняется в редакторе объектов, который служит для проведения операции паспортизации. Каждому параметру базового модуля ставится в соответствие некоторое данное предметной области, для которого определяется способ его использования базовым модулем: чтение, запись или модификация. Результатом данного этапа является порождение паспорта объекта и его сохранение в информационном фонде системы.
Функция вычисления семафорного предиката вводится на следующем этапе. Если дуга синхронизации ведет в вершину Aj, имеющую другие входящие дуги синхронизации, то пользователю предлагается отредактировать логическое выражение семафорного предиката RAj. Как и для функции отправки сообщений, возможно описание произвольной подпрограммы, которая будет выполнена перед запуском вершины в случае истинности семафорного предиката. В этой подпрограмме, например, может быть описан прием данных от некоторого процесса распределенной вычислительной системы.
Представление словаря данных в виде класса преследует две цели:
1) Унифицируется межмодульный интерфейс параллельной программы; 2) Для доступа к данным предметной области каждому модулю необходимо передать лишь указатель на объект, описанный указанным классом. Объект объявляется глобальным и становится доступным любому модулю программы.
Функции чтения и записи членов-данных класса могут выполнять дополнительные функции, например проверку корректности присваиваемых значений, ведение статистики по частоте использования данного, дамп значения данного в журнальный файл или на экран, передача данного между различными параллельными процессами.
Рассмотрим последнюю возможность более подробно. В распределенной вычислительной системе любой процессор работает с локальной областью памяти, следовательно, необходимо обеспечить пересылку данных между процессами, выполняющимися на различных процессорах. Ниже описывается один из способов организации подобной пересылки, реализованный в программном комплексе PGRAPH 1.0.
