Содержание к диссертации
Введение
1. Анализ методов представления распределенных и параллельных вычислений 24
1.1. Математическая модель взаимодействия процессов 24
1.2. Параллельные граф-схемы алгоритмов 34
1.3. Сети Петри 44
1.4. Расширенные сети Петри 57
1.5. Принципы построения CF-сетей 62
1.6. Выводы 80
2. Основные свойства CF-сетей 84
2.1. События в CF-сетях 84
2.2. Представление последовательных и параллельных процессов с помощью CF-сетей 89
2.3. Реализация вычислений с помощью CF-сетей 93
2.4. Эквивалентные преобразования CF-сетей 99
2.5. Алгебра CF-сетей 111
2.6. Решение с помощью CF-сетей противоречий в параллельных алгоритмах 117
2.6.1. Противоречие детерминированного и случайного 117
2.6.2. Противоречия синхронных и асинхронных процессов 124
2.7. Выводы 139
3. Сравнение CF-сетей с другими формальными моделями распределенных и многопроцессорных систем 142
3.1. Сравнение CF- сетей 142
3.1.1. CF- сети и оценивающие сети (Е-сети) 142
3.1.2. CF-сети HF-СЄТИ 153
3.1.3. CF-сети и цветные сети Петри 162
3.1.4. CF- сети и объектные сети Фалька 166
3.2. Представление с помощью CF-сетей типовых взаимосвязанных процессов 169
3.2.1. Последовательный процесс 169
3.2.2. Процессы выбора 171
3.2.3. Параллельные взаимосвязанные процессы 174
3.2.4. Подчиненные процессы 176
3.3. Применение CF-сетей для моделирования взаимосвязанных процессов 182
3.4. Выводы 189
4. Программное обеспечение для моделирования параллельных программ многопроцессорных и распределенных систем 191
4.1. Основные принципы создания комплекса программ для моделирования распределенных и параллельных вычислений на основе CF-сетей 191
4.2. Общая структура программного обеспечения для моделирования параллельных программ многопроцессорных и распределенных систем 194
4.3. Среда разработки CF-сетей 199
4.3.1. Особенности пользовательского интерфейса среды синтеза и анализа CF-сетей 204
4.3.2. Средства отладки CF-сетей 208
4.3.3. Библиотеки стандартных мастеров 217
4.4. Программа взаимосвязи кибернетических моделей на основе CF-сетей и аналитических моделей дискретных систем 221
4.5. Подсистема имитационного моделирования вычислительных систем и сетей 223
4.5.1. Редактор сети 225
4.5.2. Моделирование процессов в сети 227
4.6. Выводы 233
5. Применение CF-сетей для моделирования параллельных программ многопроцессорных и распределенных систем 235
5.1. Требования к механизмам взаимодействия ресурсов и процессов в многопроцессорных и распределенных системах 235
5.2. Моделирование параллельных программ для многопроцессорных систем 240
5.3. Средства и методы эффективного взаимодействия процессов и ресурсов в многопроцессорных и распределенных системах 248
5.3.1. Механизм критической секции 249
5.3.2. Буферизация запросов 253
5.3.3. Механизмы синхронизации множества процессов обмена 259
5.3.4. Механизмы синхронизации групповых процессов обмена 263
5.3.5. Механизмы повышения надежности процессов обмена 267
5.4. Выводы 280
6. Моделирование с помощью cf-сетей распределенных систем 282
6.1. Методы организации распределенных вычислений 282
6.2. Моделирование протоколов с помощью CF-сетей 290
6.3. Моделирование и анализ региональной информационно-вычислительной сети 298
6.3.1. Структура региональной информационно-вычислительной сети 300
6.3.2. Синхронизация распределенных баз данных 304
6.3.3. Моделирование процесса синхронизация распределенных баз
с помощью CF-сетей 318
6.3.4. Моделирование и анализ функционирования ИВС
Дагестанского отделения ПФР 324
6.4. Выводы 336
Заключение 338
Список использованных источников
- Расширенные сети Петри
- Представление с помощью CF-сетей типовых взаимосвязанных процессов
- Общая структура программного обеспечения для моделирования параллельных программ многопроцессорных и распределенных систем
- Средства и методы эффективного взаимодействия процессов и ресурсов в многопроцессорных и распределенных системах
Введение к работе
Ведущие специалисты в области вычислительной техники указывают в качестве конечной цели развития информационных технологий создание системы "вездесущих" вычислений, которая должна обеспечить доступ к информации и к средствам ее обработки практически в любом месте Земного шара. Для создания подобной системы необходимо решение целого комплекса взаимосвязанных научно-технических проблем и, прежде всего, в области программного обеспечения распределенных вычислительных ресурсов [1]. При создании программ для распределенных и многопроцессорных систем программист неизбежно сталкивается с рядом технических сложностей, к которым относятся: ненадежность коммутационной структуры, сложность согласования скорости работы множества функциональных устройств, но главной проблемой программирования распределенных, а, в общем случае, параллельных вычислительных систем является адекватная замыслу разработчика реализация в системе множества вычислительных процессов. Обеспечить согласованное функционирование в дискретных системах сотен, а иногда даже тысяч взаимосвязанных процессов невозможно без принципиально новых подходов к построению программных комплексов.
Под программой, как правило, понимают текст на определенном языке программирования, соответствующий спецификации и формально выведенный из фиксированного набора предпосылок и данных. Правильной программой принято считать алгоритм, реализованный для определенной вычислительной системы, не содержащий ошибок. Неоднозначное понятие "ошибка программы" обычно трактуется как невыполнение программой действий в некотором аппаратно-программном окружении, которые ожидаются от нее на основании эксплутационной документации. Более точно следовало бы говорить о несогласованности между программой и документацией по ее применению [2,3]. В большинстве случаев задание на разработку программы формулируется неформально, что не позволяет доказать формальными математическими методами корректность текста программы. Как указывал Э. Дейкстра [3], невозможно также доказать правильность программы с помощью ее тестирования, которое может только продемонстрировать наличие в программе ошибки. Для программ распределенных вычислительных систем, число состояний которых может достигать нескольких миллионов, ситуация еще более усугубляется. Недетерминизм выполнения параллельных программ не позволяет тестированием оценить все многообразие сочетаний состояний процессов в системе.
В этой связи по аналогии с вычислительными устройствами целесообразно говорить не о корректных, т.е. безотказных программах, а о гарантоспособных программных комплексах (dependability - это свойство вычислительной системы, позволяющее обосновано полагаться на выполнение услуг, для которых она предназначена [4]), которые с высокой вероятностью обеспечивают выполнение функций при заданных условиях в течение определенного временного интервала. В отличие от правильных программ гарантоспособные программы не исключают наличие ошибок, важно лишь, чтобы эти ошибки при практическом применении этих программ в заданных условиях проявлялись достаточно редко.
Методы прогнозирования и устранения ошибок могут считаться способами подтверждения гарантоспособности, так как они указывают, каким образом можно достичь уверенности в способности системы к выполнению предопределенных услуг [4].
Для оценки гарантоспособности программ следует анализировать последствия каждого отказа. В некоторых нештатных ситуациях ошибки в программах могут вызывать лишь неудобства при их эксплуатации, тогда как другие ошибки могут иметь катастрофические последствия. Поэтому для оценки надежности параллельных программ необходимы средства моделирования, с одной стороны, достаточно простые, чтобы разработчик мог оперативно обрабатывать представленные данные, а, с другой стороны, точно отражающие события, происходящие в системе при реализации распределен 8 ных вычислений. Современные средства моделирования распределенных и многопроцессорных систем строятся на основе трех различных концепций. К одной из таких концепций относятся языки дискретного имитационного моделирования, как правило, транзактного типа, в котором система представлена в виде совокупности устройств и множества связей между ними. На основе подобной структуры производится обработка случайного или детерминированного потока входных заявок (транзактов). Как правило, алгоритм обработки задается на специальном языке, например на GPSS или на стандартном языке высокого уровня с использованием специальных библиотек [5,6].
Другая концепция моделирования распределенных вычислительных систем основана на построении семантической модели системы. Доказательство, что система способна выдавать требуемый результат при заданных временных и ресурсных ограничениях, состоит из двух стадий. Сначала модель проверяется на соответствие неформализованному описанию системы, для чего необходимы простота и наглядность описания, например, часто средства верификации интегрируются со средствами документации систем (BPwin/Erwin) [7]. Далее в соответствии с методиками [8] проводится тестирование модели на примерах. К средствам семантического моделирования относятся язык UML [9] и сети Петри высокого уровня [10, 11]. Элементы средств верификации присутствуют также в языках VHDL, VeriLog [12], широко используемых для синтеза и анализа вычислительных устройств, получивших в последнее время широкое распространение, благодаря развитию ПЛИС-технологии [13].
С концепцией верификации тесно связана задача анализа корректности параллельных асинхронных алгоритмов. Эта задача в отличие от общей проблемы верификации имеет точную формальную постановку и методы решения, которые связаны, в частности, с использованием сетей Петри [14-19]. Как известно, сети Петри представляют собой бихроматический ориентированный граф, на котором в явном виде заданы пред- и постусловия каждого события системы. Известные методы аналитического моделирования сетей Петри позволяют находить тупиковые ситуации и доказывать способность системы возвращаться в исходное состояние. В настоящее время сети Петри и их расширения широко используются для кибернетического моделирования распределенных систем. Такие расширения сетей Петри как временные сети [16,20], стохастические (GSPN) сети [21] и Е-сети [16,22,23] ориентированы на моделирование процессов в дискретных системах. Однако расширенные сети Петри обладают существенным недостатком, состоящим в том, что транзакты одного типа в сетях Петри неразличимы, что не позволяет получать времена их обслуживания и может привести к отказу реальных систем.
Известен формальный аппарат описания параллельных систем в терминах взаимодействующих последовательных процессов Ч. Хоара [24], обладающий преимуществами при представлении взаимного влияния процессов, структурированности, отсутствия расходимостей, тупиков и возможности формального доказательства правильности при проектировании вычислительных систем, представляемых в виде параллельной композиции взаимодействующих подсистем. Однако подобный аппарат не обладает достаточной наглядностью представления модели, что затрудняет в ряде случаев его использование для анализа распределенных нерегулярных вычислительных систем, состоящих из разнородных объектов. Кроме того, аппарат взаимосвязанных последовательных процессов, достаточно точно описывающий реализацию вычислений в традиционных многопроцессорных системах (наиболее известным представителем которых являются кластерные системы), неадекватно представляет вычисления в конвейерных системах.
Таким образом, существуют три основные концепции моделирования распределенных вычислений и представления параллельных процессов: на основе языков транзактного типа, на основе описания взаимосвязанных последовательных процессов и на основе расширенных сетей Петри. Языки транзактного типа обладают большей гибкостью, так как близки к языкам программирования высокого уровня. Они позволяют получать более точные данные о процессах функционирования ВС, так как осуществляют моделирование обслуживания каждого транзакта. В свою очередь, расширенные сети Петри представляют более наглядные модели, поскольку в их основе лежит графовое представление состояний и событий системы. Более того, сети Петри позволяют проводить аналитическое моделирование параллельных асинхронных алгоритмов системы и выявлять тупиковые ситуации, что является общей задачей проектирования современных распределенных вычислительных систем. Взаимосвязанные последовательные процессы являются одним из основных процессов описания параллельных (в узком смысле этого слова) процессов, на основе которых синтезированы широко применяемые в настоящее время протоколы параллельных вычислений.
Следует отметить, что при использовании некоторого математического описания модели (например, на основе системы массового обслуживания) имеется выигрыш в простоте и стоимости пакета моделирования, но присутствует проигрыш в гибкости и общности модели. При использовании некоторого стандартного подхода к описанию модели (например, транзактно-ориентированного в GPSS [5], процессно-ориентированного в Симула [25] или событийно-ориентированного в Simskript [26]) ситуация обратная - мы выигрываем в гибкости и общности и теряем в простоте и стоимости модели.
В настоящее время намечается тенденция объединения в едином вычислительном контуре вычислительных компонент, которые ориентированы на различные типы высокоскоростных вычислений: параллельные вычисления, конвейерные вычисления, а также их различные комбинации [27]: макроконвейерные вычисления, взаимосвязанные параллельные конвейеры, конвейеры конвейеров, системы автоматического распараллеливания по данным [28]. Для анализа подобных систем нужны принципиально новые средства моделирования распределенных вычислений, которые обладали бы достоинствами существующих средств моделирования и имели бы дополнительные возможности, обеспечивающие реализацию анализа параллельных процессов на качественно новом уровне. Целью работы является повышение гарантоспособности параллельных программ в многопроцессорных и распределенных системах.
Средством достижения цели является более адекватное моделирование процессов и ресурсов на различных уровнях детализации.
Невозможно обеспечить разработку и создание гарантоспособных параллельных программ для многопроцессорных и распределенных систем без адекватного моделирования взаимодействия множества взаимосвязанных процессов и ресурсов системы. С другой стороны, моделирование параллельной программы на самом низком уровне абстракции - структурном -требует чрезвычайно больших временных затрат, а, учитывая недетерминизм выполнения временных конструкций, перебор различных комбинаций реализации параллельных программ достигает немыслимых величин. В этой связи целесообразно разработать единый механизм: методы и программные средства, которые позволили бы осуществлять моделирование взаимодействия вычислительных процессов и ресурсов сети на различных уровнях детализации и абстракции. Это позволит, с одной стороны, достаточно точно представить процессы, происходящие в системе при реализации параллельной программы, а, с другой стороны, сократить время моделирования и обнаружения нештатных ситуаций параллельных алгоритмов до приемлемой величины.
Научная проблема, решаемая в диссертации: разработка научных основ моделирования распределенных и многопроцессорных систем, обеспечивающих повышение (максимизацию) гарантоспособности параллельных программ в многопроцессорных и распределенных системах при заданных структурах многопроцессорной системы и топологии компьютерной сети, и требований к ним.
Среди отечественных исследований в области разработки формальных методов моделирования параллельных и распределенных систем можно отметить работы Н.А. Анисимова, О.Л. Бандман, И.Б. Вирбицкайте, Ю.Г. Карпова, В.Е. Котова, А.Е. Костина, И.А. Ломазовой, В.А. Соколова, В.А. Непомнящего, Л.А. Черкасовой и др. Однако их исследования были ориентированы на описание только управляющих компонент вычислительного процесса и не отражали сами вычисления.
Предлагается в качестве средства анализа процессов в распределенных и многопроцессорных вычислительных системах использовать разработанное автором расширение сетей Петри, свободное от указанных выше недостатков. Многочисленные расширения сетей Петри, как правило, ориентированы на представление структурных составляющих вычислительных устройств или программ и не позволяют адекватно описать типовые программные конструкции. Это вызвано, прежде всего, тем, что сети Петри и их расширения направлены на описание только управляющих компонент вычислительного процесса и не отражают сами вычисления [14-23]. Современные парадигмы программирования, требующие инкапсуляции управляющих конструкций и данных, противоречат этой установке. В предлагаемых управляющих функциональных сетях (Control Function Net) имеются возможности адекватно представить все многообразие взаимосвязи программных конструкций и обрабатываемых данных, а также отразить разную длительность выполнения различных процессов на событийном уровне моделирования.
CF-сети позволяют более точно представлять различные взаимосвязи между параллельно-последовательными процессами, происходящими в распределенных системах, обеспечивают описание срабатывания переходов при различных условиях, как привычно для программистов. На основе CF-сетей может быть представлена практически любая параллельная программа, причем уровень абстрагирования процессов в системе будет определять пользователь.
В отличие от кибернетических моделей, использующих традиционные сети Петри, модели на основе CF-сетей позволяют осуществлять моделирование вычислительных процессов в многопроцессорных и распределенных системах как на кибернетическом, так и на функциональном уровнях абстракции, в последнем случае учитываются не только взаимодействие процессов и ресурсов, но и непосредственно вычисления, реализуемые в моделируемой системе. При необходимости более детального моделирования вычислительных процессов в распределенных и многопроцессорных системах следует опуститься на уровень структурного программирования, учитывающего разбиение системы на элементы и реализацию связей между ними. CF-сети могут адекватно представить взаимодействие вычислительных процессов и ресурсов системы на структурном уровне. На данном уровне абстракции с помощью CF-сетей должны быть описаны системы коммутации многопроцессорных систем, топология компьютерных сетей для распределенных систем, а также протоколы взаимодействия ресурсов системы и параллельных процессов. При необходимости детали взаимодействия элементов системы при выполнении параллельных программ могут быть скрыты. Кроме того, возможности CF-сетей позволяют получить численные оценки, характеризующие скорость прохождения информационных потоков, а также скорости реализации запросов процессов к ресурсам системы.
В соответствии с поставленной целью для решения сформулированной научной проблемы определены частные научные задачи диссертации:
1) провести анализ методов и средств моделирования параллельных вычислительных процессов в многопроцессорных и распределенных системах;
2) разработать принципы построения единого формального аппарата для описания вычислительных процессов в многопроцессорных и распределенных системах на различных уровнях абстракции;
3) исследовать и разработать методы расширения (увеличения) выразительной мощности представления по сравнению с традиционными сетями Петри и их расширений комплекса последовательных и параллельных управляющих процессов, а также вычислительных процессов с помощью CF-сетей;
4) разработать правила модификации CF-сетей для эквивалентных преобразований, алгебру операций над CF-сетями;
5) провести сравнение CF-сетей с другими сетевыми моделями распределенных и параллельных вычислений; 6) разработать базовые конструкции формализованного описания параллельных и конвейерных вычислений на основе CF-сетей для ускорения процесса создания и анализа параллельных программ для распределенных и многопроцессорных систем;
7) разработать формализованные модели типовых элементов вычислительных структур на основе CF-сетей, для анализа процессов синхронизации множества взаимосвязанных и взаимодействующих параллельных процессов;
8) разработать базовую модель на основе CF-сетей обнаружения нештатных ситуаций в распределенных системах для моделирования множества взаимосвязанных процессов и динамически изменяемых ресурсов в системе на различных уровнях абстракции и детализации;
9) обосновать структуру и разработать экспериментальную версию программного обеспечения для моделирования параллельных программ многопроцессорных и распределенных систем, включающую среду разработки и моделирования CF-сетей, на различных уровнях абстракции: кибернетическом, функциональном и структурном;
10) разработать тестовые примеры реализации параллельных процессов в
распределенных и многопроцессорных системах на основе CF-сетей,
подтверждающих достоверность разработанных моделей.
Методы исследований основаны на использовании: теории вычислительных систем, элементов теории графов, теории множеств, теории параллельных взаимодействующих процессов, теории сетей Петри, теории массового обслуживания; в экспериментальных исследованиях применялись методы имитационного моделирования распределенных и многопроцессорных систем.
Теоретические исследования подтверждены вычислительными экспериментами на имитационных моделях MB С и региональных компьютерных сетей, а также реализацией параллельных программных средств на многопроцессорных системах и региональных компьютерных сетях в инте 15 ресах ряда предприятий и организаций.
Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в ДГТУ, НИИ МВС ТРТУ, непосредственным участником которых являлся автор диссертации.
Наиболее важными из них являются:
"Исследование и разработка параллельного интерфейса связи объекта с МВС", № ГР 01.83.0052005, руководитель НИР - Б.В. Захаркин;
"Исследование и разработка аппаратно-программных средств подсистемы связи с объектом и внешними устройствами для многопроцессорной вычислительной системы", №ГР 01.85.00188980, в рамках комплексной программы 0.80.14, тема 01.10 по Постановлению ГКНТ СССР и комиссии Президиума СМ СССР № 442/377, руководитель НИР - Б.В. Захаркин;
"Исследование и разработка принципов построения и организации системы реального времени и средств связи с внешними устройствами МВС", № ГР 01.86.0122416, руководитель НИР - к.т.н. О.М. Омаров;
"Разработка системы ввода-вывода вычислительного комплекса", № ГР 01.89.0007077, руководитель НИР - к.т.н. О.М. Омаров;
"Разработка и создание информационно-телекоммуникационной системы для общеобразовательных учреждений в горных районах Республики Дагестан (2003-2004)" в рамках программы "Федерально-региональная политика в науке и образовании", руководитель НИР - д.т.н., профессор Ш.-М.А. Исмаилов;
"Исследование возможности путей создания вычислителя с программируемой архитектурой", руководитель НИР - член-корреспондент РАН, д.т.н., профессор И.А. Каляев, заказчик в.ч. 25714;
"Исследование и разработка математических и программных средств для
эффективного распараллеливания прикладных задач на
высокопроизводительных вычислительных комплексах", руководитель НИР -член-корреспондент РАН, д.т.н., профессор И.А. Каляев;
"Разработка и исследование интеллектуальных аппаратно-программных средств многопроцессорных вычислительных и управляющих систем с динамически программируемой архитектурой", № ГРО 120.0510629, руководитель НИР - член-корреспондент РАН, д.т.н., профессор И.А. Каляев;
"Создание модульно-наращиваемых многопроцессорных систем (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса", выполняемой в рамках мероприятия 1.12-САЗ по программе Союзного государства "Развитие и внедрение в государствах-участниках Союзного государства наукоёмких компьютерных технологий на базе мультипроцессорных вычислительных систем" (шифр "ТРИАДА")", руководитель - д.т.н. И.И. Левин;
"Исследование принципов построения сверхвысокопроизводительных вычислительных систем со структурной организацией вычислений", научный руководитель НИР - д.т.н., И.И. Левин;
"Исследование возможности эффективной реализации вычислительно трудоемких фрагментов задач на реконфигурируемых вычислителях на основе ПЛИС", научный руководитель НИР - член-корреспондент РАН, д.т.н., профессор И.А. Каляев.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях: Республиканской научно-практической конференции "Радиоэлектроника народному хозяйству", Махачкала, 1983; научной сессии Дагестанского филиала АН СССР, Махачкала, 1985; V Всесоюзной школе-семинаре "Распараллеливание обработки информации", Львов, 1985; на X всесоюзном совещании по проблемам управления, Алма-Ата, 1986; на VII международной научной конференции "Актуальные проблемы информатики: математическое, программное и информационное обеспечение", Минск, 1998; второй международной научно-технической конференции "Моделирование интеллектуальных процессов проектирования и производства (САД/САМ/ 98)", Минск, 1998; республиканских научно-практических конференциях "Дагинформ", Махачкала, 2001, 2003, 2005; всероссийской научно-технической конференции "Современные информационные технологии в управлении", Махачкала, 2003; всероссийской научно-методической конференции "Телематика", С-Петербург, 2004, 2005; международной научно-технической конференции "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций", Рязань, 2004, 2005; Международной научной конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы", Кацивели, 2004, Дивноморское, 2005; Международных научно-технических конференциях "Интеллектуальные системы (IEEE AIS 04)" и "Интеллектуальные САПР" (CAD-2004), Таганрог, 2004; Научно-технических конференциях преподавателей, сотрудников и студентов Дагестанского политехнического института, Махачкала, 1981-2005.
По теме диссертации опубликовано 70 печатных работ, из них: 1 монография, в соавторстве с научным консультантом, объемом 253 с. (авторских 50%), 13 статей в периодических научных изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации" ВАК для публикации научных работ, отражающих основное научное содержание докторских диссертаций ("Информационные технологии", "Вестник Дагестанского научного центра РАН", "Известия ТРТУ", "Известия ВУЗов. Северокавказский регион. Технические науки", "Известия ВУЗов. Северокавказский регион. Естественные науки", "Научная мысль Кавказа", "Телекоммуникации", "Приборы и системы. Управление, контроль, диагностика"), общим объемом 102 с. (авторских 81%), 9 статей в научно-технических журналах ("Управляющие системы и машины", "Многопроцессорные вычислительные структуры", "Электронная техника. Серия. Экономика и системы управления", "Информационные технологии моделирования и управления", "Вестник Дагестанского государственного технического университета", "Искусственный интеллект") общим объемом 47с. (авторских 54% ), 3 статьи в научно-технических сборниках общим объемом 23с. (авторских 51%), 1 депонированная рукопись ВИНИТИ общим объемом 16 с, 13 авторских свидетельств на изобретение (доля участия 72%), 2 свидетельства об официальной регистрации программ для ЭВМ (доля участия 75%), тезисы 29 докладов, 1 учебное пособие объемом 268с, кроме того, материалы диссертации использовались при написании 14 отчетов по НИР.
Все научные результаты, полученные при решении крупной научной проблемы разработки научных основ моделирования распределенных и многопроцессорных систем, обеспечивающих повышение гарантоспособности параллельных программ в многопроцессорных и распределенных системах при заданных структурах многопроцессорной системы и топологии компьютерной сети, и требований к ним получены автором лично.
Расширенные сети Петри
Сети Петри могут быть использованы для моделирования самых различных систем, в том числе аппаратного и программного обеспечения ЭВМ. Очевидно, что сети Петри могут адекватно моделировать разные системы, однако могут существовать такие системы, которые нельзя должным образом моделировать сетями Петри, т. е. мощность моделирования сетей Петри имеет пределы. Применение классических подходов и добавление дополнительных атрибутов позволили разработать сети различной целевой направленности, получившие название расширенные. Классификация расширенных сетей Петри приведена на рис. 1.9. [14-17,48]
Рассмотрим подробнее некоторые типы сетей Петри.
Ингибиторная сеть представляет собой сеть Петри, дополненную специальной функцией инцидентности /jN: PxT-f{0, 1}, которая вводит ингибиторные (запрещающие) дуги для тех пар (р, t), для которых /IN (Р, 7)=1 [49,15]. Ингибиторные дуги связывают только позиции с переходами, на рисунках их изображают заканчивающимися не стрелками, а маленькими кружочками.
Переход t в ингибиторных сетях может сработать, если каждая его входная позиция, соединенная с переходом обычной дугой с кратностью w(p, t) содержит не менее w(p, і) фишек, а каждая входная позиция, соединенная с переходом t ингибиторной дугой (ее кратность всегда равна 1), имеет нулевую разметку. Например, используя ингибиторную дугу, можно промоделировать оператор условного вычитания (если хх Ф 0, то хх = xt -1) и получить фрагмент ингибиторной сети (рис. 1.10).
Ингибиторные сети равномощны машине Тьюринга [49,15] используются для разработки диагностических моделей средств вычислительной техники.
Приоритетные сети [15]. В реальных дискретных системах имеет место ситуации, когда из двух готовых работать устройств требуется запустить сначала одно, например первое, а затем второе. Другими словами, одно из устройств имеет приоритет на запуск перед другим в том случае, если оба готовы работать, причем совсем не обязательно, чтобы эти переходы были конфликтующими. Эти ситуации не моделируется в сетях Петри в силу принятого правила срабатывания нескольких готовых к срабатыванию переходов. В приоритетных сетях Петри вводится дополнительное отображение приоритетности PR. Для этого вводится множество приоритетов Z, элементы которого частично упорядочены некоторым отношением (меньше или равно). С каждым переходом t сети Петри связан его приоритет pr(J)GZ. Если несколько переходов являются разрешенными, то срабатывает тот из них, который имеет наивысший приоритет. В сетях с приоритетами срабатывания переходов уже не соблюдается принцип чисто локального управления функционированием сети. Для определения перехода, который станет активным, здесь привлекается более глобальная информация о состоянии сети. Этот подход приближает сети Петри к реально функционирующим системам, и выразительная мощность (мощность моделирования) возрастает. Такие сети используются для моделирования систем на уровне задач.
Цветные (раскрашенные) сети Петри [50, 51,15] . Выразительность сетей Петри заметно уменьшается, если необходимо моделировать материальные или информационные потоки. В этом случае объекты, циркулирующие в сети, имеют отличительные признаки, в то время как маркеры в сетях Петри обезличены. При моделировании сетями Петри дискретных систем маркеры часто соответствуют объектам, передаваемым от компонента к компоненту системы (данным в информационных системах, управляющим сигналах, ресурсам и т.п.). Зачастую эти объекты имеют дополнительные атрибуты, позволяющие различать их и использовать эти различия для управления функционированием системы. Однако в классической модели сетей Петри маркеры "безлики" и не отражают такие различия.
Предикатные (Predicate Transition Nets) сети имеют следующие особенности. К множеству переходов Т вводится множество предикатов S, причем множество дуг сети помечено в соответствии с предикатами. Предикаты определяют, сколько и каких маркеров удаляется из входной позиции и сколько и каких маркеров появится в каждой выходной позиции. Переход возбужден и может сработать, если в его входных позициях имеются необходимые маркеры в соответствии с предикатами, приписанными к входным дугам [52].
Представление с помощью CF-сетей типовых взаимосвязанных процессов
Фишки в стандартных сетях Петри являются безликими объектами и не отражают данные в информационных системах, что затрудняет применение сетей для функционального моделирования реальных дискретных систем.
Развитие теории сетей Петри привело к появлению, так называемых, «цветных» сетей Петри [15,50,51,88,89]. Понятие цветности в них тесно связано
с понятиями переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Несмотря на некоторые сходства между цветными сетями Петри и программами, они не применяются в качестве языка программирования.
Для адекватного описания обменов данных между различными компонентами системы с помощью сетей Петри было предложено предписывать фишкам группу признаков, в частности, различные цвета. Это привело к тому, что условия срабатывания переходов и правила изменения разметки сети задаются с помощью специальных таблиц, учитывающих цвета фишек [15]. Для каждого перехода сети необходимо сформировать индивидуальную таблицу условий срабатывания. В такой таблице столбцы, соответствующие входным местам переходов, содержат сочетание конкретных признаков фишек, при которых переход может сработать, столбцы, соответствующие выходным местам переходов, указывают признаки, в соответствии с которыми при активации перехода добавляются фишки в выходные места для каждого входного сочетания признаков. Пример раскрашенной сети приведен на рис. 3.21.
Данная сеть моделирует фрагмент операционной системы, управляющей обменами между тремя накопителями на магнитных дисках D\,D2,Di и центральным процессором через два независимых канала А и В, причем дисковод D\ использует канал А, а дисковод Di - канал В, а дисковод DT, - оба канала [15]. В этой сети использованы следующие фишки с признаками: - d\4i4i - фишки, отмечающие возможность связи с дисководами DUD2,D3; -a,b- фишки, отмечающие доступность каналов А и В; - а,р,у,5,є - вспомогательные фишки для запоминания предыстории функционирования системы.
Подобную сеть можно представить с помощью CF-сетей, при этом определенному типу сообщений будет соответствовать разное количество фишек. В отличие от традиционных сетей Петри и их расширений CF-сети позволяют осуществлять переходы для строго определенного количества фишек в конкретной позиции, а не для числа фишек в позиции, превышающей наперед заданный барьер. Это свойство позволяет синтезировать CF-сеть, моделирующую обмен информацией между дисководами и центральным процессором. Пример такой сети показан на рис. 3.22.
На рис. 3.23 представлена раскрашенная сеть модели передачи сообщения от процессора Р0 к п процессорам Р\,Р2,...,Рп- При этом N={x\rx2,...,Xn} -множество красок фишек и краска xt соответствует данным для процессора Pv Каждый процессор Рх выполняет один и тот же алгоритм над собственными данными и либо подтверждает получение Q+, либо не подтверждает Q.
На рис. 3.24 представлена CF-сеть, реализующая вышеприведенные функции. Здесь в качестве отличительного параметра для срабатывания перехода Т\ используется общее число фишек в позиции Q+. Для того, чтобы переход сработал, необходимо чтобы число фишек в позиции Q+ было равно R, которое рассчитывается по формуле R =. Если хоть один процессор выдаст вместо Q+ фишку в позицию Q , то общее число фишек в позиции Q+ не будет равно R и переход Рі не сработает. Это условие эквивалентно условию срабатывания перехода Р\ на рис. 3.23, который срабатывает, если все фишки в позиции Q+ принадлежат множеству N.
Переход Тг срабатывает, если число фишек в позиции Q больше единицы. То есть, по крайней мере, один процессор выдал сообщение в позицию Q , что свидетельствует о том, что, по крайней мере, одно сообщение не было принято. В CF-сетях это реализуется с помощью обыкновенной дуги, в раскрашенных сетях - с помощью признака xeN.
Аналогичным образом можно построить с помощью CF-сетей и более сложные зависимости, реализуемые с помощью раскрашенных сетей Петри.
Основная задача объектных сетей Р.Фалька [90,91] (Object Petri net) -разделение заданий на подзадачи для распределения между несколькими агентами с целью параллельного выполнения. В сетях этого класса каждой дуге, соединяющей место и переход или переход и место, поставлен в соответствие параметр модифицируемой кратности. В частном случае в качестве параметра модифицируемой кратности может быть число, которое имеет тот же смысл, что и кратность дуг для обычных сетей Петри. В общем случае в качестве кратности может выступать некоторый символ места. В этом случае кратность равна текущей разметке указанного места. Так как разметка места может динамически меняться, то и кратность дуг, которым сопоставлено место, динамически меняется [15,90].
Несложно заметить, что самомодифицируемые сети Фалька являются частным случаем CF-сетей, в которых можно не только изменять кратность дуг сетей, но и изменять степень влияния размечающего места на кратность дуг в сети. В CF-сетях это делается с помощью а-дуг, размечающих а-дуги
Общая структура программного обеспечения для моделирования параллельных программ многопроцессорных и распределенных систем
На основе вышеизложенных принципов построения системы моделирования параллельных и распределенных вычислений на основе CF-сетей была разработана структура программного комплекса. Укрупненная структура программного комплекса средств моделирования приведена на рис. 4.1.
Модели компонентов многопроцессорной или распределенной системы и параллельных программ представляются в виде иерархической CF-сети, которая формируется с помощью редактора CF-сети на основе библиотеки типовых компонентов. Созданная модель может быть проанализирована с помощью эмулятора CF-сетей. При обнаружении нештатных ситуаций в параллельных программах в CF-сеть, описывающую параллельный алгоритм, вносится соответствующее исправление. Пользователю предоставляется специальная опция Explorer CF-сетей, обеспечивающая интерактивный просмотр CF-сети в удобном графическом интерфейсе.
Результаты моделирования CF-сети могут быть выражены численным выражением для дальнейшего скоростного анализа с помощью подсистемы имитационного моделирования. Для формирования параметров компонентов системы или сети используется соответствующая утилита.
Диалоговый программный комплекс должен состоять из двух подсистем: подсистемы анализа и моделирования для получения качественных характеристик исследуемой вычислительной системы на основе CF-сетей и подсистемы имитационного моделирования для оценки временных характеристик [104,105,71].
Подсистема имитационного моделирования многопроцессорных и распределенных систем содержит редактор топологии межкомпонентных связей, блок подготовки моделирования, а также графический интерфейс для представления результатов моделирования.
CF-сети являются средством моделирования как параллельной программы, так и структуры исследуемой распределенной или многопроцессорной системы, учитывающих ее основные структурные связи, причем в динамике функционирования и с учетом заданных протоколов взаимодействия компонентов системы. Поэтому на этапе построения CF-сети, моделирующей параллельную вычислительную систему, определяются основные компоненты и подсистемы, а также потоки информации, циркулирующие в ней.
Многочисленные расширения сетей Петри, как правило, ориентированы на представление структурных составляющих вычислительных устройств или программ и не позволяют адекватно описать типовые программные конструкции. Это вызвано, прежде всего, тем, что сети Петри и их расширения направлены на описание только управляющих компонент вычислительного процесса и не отражают сами вычисления. Современные парадигмы программирования требуют инкапсуляции управляющих конструкций и данных. На основе управляющих функциональных сетей появляется возможность адекватно представить все многообразие взаимосвязи программных конструкций и обрабатываемых данных, а также отразить разную длительность выполнения различных процессов на событийном уровне моделирования.
CF-сети позволяют более точно представлять различные взаимосвязи между параллельно-последовательными процессами, происходящими в распределенных системах, обеспечивают описание срабатывания переходов при различных условиях, как привычно для программистов. На основе CF-сетей может быть представлена практически любая параллельная программа, причем уровень абстрагирования процессов в системе будет определять пользователь.
В отличие от кибернетических моделей, использующих традиционные сети Петри, модели на основе CF-сетей позволяют осуществлять моделирование вычислительных процессов в многопроцессорных и распределенных системах как на кибернетическом, так и на функциональном и структурном уровнях абстракции.
При моделировании на кибернетическом уровне учитываются только функции управления процессом решения, а также взаимодействие процессов и
ресурсов моделируемой системы. На данном уровне абстрагирования можно использовать только управляющие компоненты CF-сетей. В то же время современные технологии программирования и, прежде всего, основанные на объектно-ориентированной парадигме, диктуют необходимость не разделять процесс вычисления (обработку информации) от процессов управления вычислениями. Таким образом, необходимо создавать модели, адекватно представляющие управляющие и функциональные компоненты оригинала.
При моделировании на функциональном уровне учитывается не только взаимодействие процессов и ресурсов, но и непосредственно вычисления, реализуемые в моделируемой системе. На данном уровне абстрагирования необходимо использовать как управляющие, так и функциональные компоненты CF-сетей. Вычислительные функции будут реализованы с помощью новых конструкций - размечающих а-дуг, а значения вычислений будут представлены числом фишек в определенных позициях CF-сетей.
При необходимости более детального моделирования вычислительных процессов в распределенных и многопроцессорных системах следует опуститься на уровень структурного программирования, учитывающего разбиение системы на элементы и реализацию связей между ними. CF-сети могут адекватно представить взаимодействие вычислительных процессов и ресурсов системы на структурном уровне. На данном уровне абстракции с помощью CF-сетей должны быть описаны системы коммутации многопроцессорных систем, топология компьютерных сетей для распределенных систем, а также протоколы взаимодействия ресурсов системы и параллельных процессов. При необходимости детали взаимодействия элементов системы при выполнении параллельных программ могут быть скрыты.
Средства и методы эффективного взаимодействия процессов и ресурсов в многопроцессорных и распределенных системах
В настоящее время существует большое количество различных комплексов программ для моделирования сетей Петри: Design/CPN [109], Artifex [110], INCOME Process Designer [111], Petri Net Kernel [112], INA [112], PROD [113], Maria [113], пакет DSPNexpress [114], симулятор для моделирования F-сетей [115], симулятор вложенных сетей Петри [116], программный комплекс для моделирования вычислительных систем иерархическими сетями Петри [117] и другие, каждый из которых предлагает богатые возможности по моделированию разновидностей сетей Петри. Однако не существует инструментальных средств, позволяющих работать с CF-сетями.
Для иерархического проектирования и моделирования CF-сетей с учетом вышеизложенных принципов и современных достижений в области графических средств программирования разработана и создана интегрированная среда [108,118] на платформе Microsoft.NET Framework, в качестве графического редактора используется офисное приложение MS Office Visio SDK 2003 [119].
Среда позволяет создавать CF-сети в иерархической форме, а также имеет возможность пошагового моделирования построенной CF-сети, что позволяет наглядно увидеть работу как всей сети, так и отдельных её компонентов, а также обнаружить нештатные ситуации в моделируемом объекте: дедлоки, отказы и расхождения. Среда разработки обеспечивает возможность создания CF-сетей и их компонентов любой сложности в виде граф-схем. Редактор CF-сетей сочетает в себе возможности как универсального графического редактора, так и специализированного.
В общем случае граф-схема CF-сети строится из четырех типов объектов: F-Место, С-Место (Управление), Переход и Дуга (Связь). Такое минимальное число элементов достаточно для построения CF-сетей любой сложности. Графическое представление элементов CF-сети показано на рис. 4.2.
Разрешается соединять объектами Связь остальные объекты. Согласно правилам построения CF-сетей объекты F-Место и С-Место (Управление) могут быть соединены дугами только с объектами Переход. Объект Переход, в свою очередь, может быть соединён дугами только с объектами F-Место и С-Место (Управление). Это является обязательным условием для построения граф-схем CF-сетей и последующего их моделирования. Если пользователь создаст граф-схему, нарушающую указанные правила, то будет выдана синтаксическая ошибка, и моделирование такой CF-сети не осуществится.
Следует отметить, что элемент Связь может быть соединён с другим элементом Связь. Данный факт не реализуем в топологических терминах: дуга не может быть инцидентна дуге в графах. Однако при реализации CF-сетей с изменяемой разметкой формируются определенные отношения, которые получили название а-дуга. Обычная дуга является отношением, которая ставит в соответствие одну вершину графа другой вершине. Отношение а-дуга ставит в соответствие вершину графа и дугу графа. При этом дуга, которой ставится в соответствие некоторая вершина с помощью я-дуги, в свою очередь, может быть я-дугой. Примеры соединения объектов показаны на рис. 4.3.
Пользователь может при анализе процессов в сети оперировать только предварительно созданными элементами, которые помещены в библиотеку. Каждому созданному объекту сети - граф-схеме автоматически ставится в соответствие уникальное условное графическое обозначение (УГО).
Каждая граф-схема в общем случае состоит из множества фигур, которые можно определить как совокупность некоторых графических объектов, состоящих из сегментов кривых Безье и обладающих рядом графических атрибутов, таких как перо, кисть, текст и шрифт. Фигуры могут быть сгруппированы по иерархическому принципу, как показано на рис. 4.4. Здесь Фигура 1 и Фигура 2 сгруппированы в Фигуру 5, аналогично Фигура 3 и Фигура 4 сгруппированы в Фигуру 6, а Фигура 5 и Фигура 6 сгруппированы в Фигуру 7. Фигуры нижнего уровня с номерами 1-4, отличаются от фигур с номерами 5-7 тем, что они обладают графическим представлением, в то время как фигуры 5-7 обладают только текстовым атрибутом.
