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

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

ОМАРОВ Омар Магадович

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

НА ОСНОВЕ СК-СЕТЕЙ

Специальность: 05.13.11 - "Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей"

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Махачкала - 2006

Работа выполнена на кафедре "Вычислительная техника" Дагестанского государственного технического университета (ДГТУ)

НАУЧНЫЙ КОНСУЛЬТАНТ:

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук Левин Илья Израилевич

доктор технических наук, профессор Абдулаев Ших-Саид Омаржанович

доктор технических наук, профессор Долгов Александр Иванович

доктор физ.-мат. наук, профессор Пнлиди Владимир Ставрович

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: Институт программных систем РАН

(ИПС РАН), г. Переславль-Залесский

Защита состоится "27" октября 2006 г. в 1420 на заседании диссертационного совета Д 212.259.05 в зале заседаний Ученого совета Научно-исследовательского института многопроцессорных вычислительных систем им. академика A.B. Каляева Таганрогского государственного радиотехнического университета по адресу: 347928, г. Таганрог, ул. Чехова, 2, корп. И, комн. 347.

С диссертацией можно ознакомиться в библиотеке ТРТУ.

Просим Вас прислать отзыв, заверенный печатью учреждения по адресу: 347928, г. Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44, Таганрогский гл г]тргтгпчп 'njjBWiiПДОиичгггпй университет Ученому секретарю диссер«№Йонн<агО)^Ь^^Д 212.259.05 Кухаренко А.П.

хУч^- 7'' .г-. l'H V;*.',,,. ^ /tr- Vk.

Автореферат разослан

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

доцент '"Ж.Г1. Кухаренко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Цель диссертационного исследования — повышение гарантоспособности параллельных программ в многопроцессорных и распределенных системах.

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

. Средством достижения цели является более адекватное моделирование процессов и

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

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

Современные средства моделирования распределенных и многопроцессорных систем строятся на основе трех различных концепций. К одной из таких концепций относятся языки дискретного имитационного моделирования, как правило, транзактного типа, в котором система представлена в виде совокупности устройств и множества связей между ними. На основе подобной структуры производится обработка случайного или детерминированного потока входных заявок (трагоактов). Как правило, алгоритм обработки задается на специальном языке, например на ОРББ/Н, БЬХ или на стандартном языке высокого уровня с использованием специальных библиотек. Языки транзактного типа обладают большей гибкостью, так как близки к языкам программирован«! высокого уровня. Они позволяют получать более точные данные о процессах функционирования ВС, так как осуществляют обслуживание каждого транзакта, но требуют большого времени для реализации моделирования.

Другая концепция моделирования распределенных систем основана на построении семантической модели системы. Для проверки модели на соответствие неформализованному описанию системы важны простота и наглядность описания, для чего средства верификации интегрируются со средствами документации систем, например ВР\у1пЛЖ\ут. К средствам семантического моделирования относятся сети Петри высокого уровня. Известные методы аналитического моделирования сетей Петри позволяют находить тупиковые ситуации и доказывать способность системы возвращаться в исходное состояние. В настоящее время сети Петри и их расширения широко используются для кибернетического моделирования процессов в дискретных системах. Однако расширенные сети Петри обладают существенным недостатком: транзакты одного типа в сетях Петри неразличимы, что не позволяет получать времена их обслуживания и может привести к отказу реальных систем.

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

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

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

Среди отечественных исследований в области разработки формальных методов моделирования параллельных и распределенных систем можно отметить работы H.A. Анисимова, О.Л. Бандман, И.Б. Вирбицкайте, Ю.Г. Карпова, В.Е. Котова, А.Е. Костина, И.А. Ломазовой, В.А. Соколова, В.А. Непомнящего, Л.А. Черкасовой и др. Однако их исследования были ориентированы на описание только управляющих компонент вычислительного процесса и не отражают сами вычисления.

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

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

В соответствии с поставленной целью для решения сформулированной научной проблемы определены частные научные задачи диссертации:

1) провести анализ методов и средств моделирования параллельных вычислительных процессов в многопроцессорных и распределенных системах;

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

3) исследовать и разработать методы расширения (увеличения) выразительной мощности представления по сравнению с традиционными сетями Петри и их расширений комплекса последовательных и параллельных управляющих процессов, а также вычислительных процессов с помощью СБ-сетей;

4) разработать правила модификации СР-сетей для эквивалентных преобразований, алгебру операций над СБ-сетями;

5) провести сравнение СБ-сетей с другими сетевыми моделями распределенных и параллельных вычислений;

6) разработать базовые конструкции формализованного описания параллельных и конвейерных вычислений на основе СБ-сетей для ускорения процесса создания и анализа параллельных программ для распределенных и многопроцессорных систем;

7) разработать формализованные модели типовых элементов вычислительных структур на основе СР-сетей, для анализа процессов синхронизации множества взаимосвязанных и взаимодействующих параллельных процессов;

8) разработать базовую модель на основе СР-сетей обнаружения нештатных ситуаций в распределенных системах для моделирования множества взаимосвязанных процессов и динамически изменяемых ресурсов в системе на различных уровнях абстракции и детализации;

9) обосновать структуру и разработать экспериментальную версию программного обеспечения для моделирования параллельных программ многопроцессорных и распределенных систем, включающую среду разработки и моделирования СР-сетей, на различных уровнях абстракции: кибернетическом, функциональном и структурном;

10) разработать тестовые примеры реализации параллельных процессов в распределенных и многопроцессорных системах на основе СР-сетей, подтверждающих достоверность разработанных моделей.

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

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

Наиболее существенные новые научные положения, выдвигаемые для зашиты:

1) сети Петри и их расширения не позволяют описывать все многообразие вычислений, встречающихся в кибернетических системах, в связи с чем разработка новых расширений сетей Петри актуальна;

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

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

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

Другие наиболее существенные новые научные результаты, выдвигаемые для защиты:

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

2) алгебра операций над СИ-сетями, отличающаяся применением для эквивалентного преобразования сложных СР-сетей в более простые конструкции модифицированных операций наложения, присоединения, исключения и итерации;

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

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

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

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

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

МВС ЕС-2703 и при реализации компонентов программного обеспечения региональной информационной сети Дагестанского Отделения ПФР.

Научная и практическая ценность работы. Практическое использование научных результатов позволило:

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

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

3) провести анализ реализации параллельных взаимосвязанных процессов в распределенных вычислительных системах. Предложены модели на основе СР-сетей типовых протоколов, реализуемых в компьютерных сетях. Совокупность моделей элементов вычислительных структур и типовых протоколов позволяет в 2-3 раза сократить время анализа параллельных программ, реализуемых в распределенных вычислительных системах;

4) решить прикладную задачу создания гарантоспособных программ на примере построения распределенной вычислительной системы и комплекса параллельных программ, реализуемых в ней на примере Отделения ПФР по РД. Использование механизма СР-сетей и созданных методов и программных средств анализа СР-сетей и параллельных программ позволили повысить надежность функционирования параллельных программ в компьютерных сетях в 1,5+2,5 раза.

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

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в ДГТУ, в НИИ МВС ТРТУ, непосредственным участником которых являлся автор диссертации. Результаты диссертации внедрены в Дагестанском государственном техническом университете, г. Махачкала; НИИ многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета, г. Таганрог; Южном научном центре Российской академии наук; ФГУП "18 ЦНИИ" МОРФ, г. Москва; ФГНУ НИИ "Спецвузавтоматика", г. Ростов-на-Дону; ООО "НТЦ Диамонд", г. Москва; ЗАО "Орбита", г. Краснодар; Дагестанском научно-исследовательском и технологическом институте информатики, г. Махачкала; ГУ-Отделении пенсионного фонда Российской Федерации по республике Дагестан (ОПФР), г. Махачкала.

Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-тех1ических конференциях: Республиканской научно-практической конференции "Радиоэлектроника народному хозяйству", Махачкала, 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 монография, 25 статей в центральной печати, из них 13 - в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации" ВАК, получено 13 авторских свидетельств, 2 свидетельства на регистрацию программ для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, шести разделов, заключения и списка литературы из 182 наименований. Она содержит 376 страниц текста, 3 таблицы, 206 рисунков, 18 страниц приложений.

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

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

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

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

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

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

Еще одним способом описания прикладных программ для распределенных систем является формализация описаний поведения на основе графического языка спецификаций. Наибольшее распространение получили такие графические языки на основе автоматных моделей как SDL и UML. Особенностью SDL является то, что в нем не различаются спецификации и описания. В основу языка положена концепция взаимодействия конечных автоматов Мили и связей между ними (процессов), описываемых с помощью SDL-диаграмм, содержащих графические обозначения, похожие на традиционные алгоритмические схемы, что приводит к громоздкости описаний. В языке UML используется диаграмма состояний Statecharts, предложенная Д. Харелом. Язык состоит из множества модельных элементов, которые представляют различные компоненты разрабатываемой схемы. Из-за необходимости введения дополнительных ограничешй диаграммы становятся необычайно сложными кроме тощ их нельзя построить по коду программы.

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

в моделируемой системе как наличие данных для операции в программе, состояние некоторого регистра и т.п. Определенные сочетания условий разрешают реализоваться некоторому событию, а реализация события изменяет некоторые условия. В сетях Пеггри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно лшо.ж'ес/иваи переходов и множеством позиций. В графическом представлении сетей переходы изображаются "барьерами" или планками (7), а позиции — кружками (Я). Сеть Петри (СП) является интеграцией графа и дискретной динамической системы. При этом отсутствие строго фиксированного аналитического подхода при определении отношения вход-выход сети делает эту систему алгоритмически неопределенной, как и для имитационных моделей.

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

СП состоит из: множества позиций Р, множества переходов Т, входной функции I и выходной функции О, а также функции разметки позиций М. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход Ц в множество позиций Щ), называемых входными позициями перехода. Выходная функция О отображает переход Ц в множество позиций 0(ф, называемых выходными позициями перехода

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

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

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

Известны ингибиторные сети, представляющие собой сеть Петри, дополненную специальной функцией инцидентности РхТ—*{0, 1}, которая вводит ингибиторные (запрещающие) дуги для тех пар (р, /), для которых /пч (/', Т)=1. Ингибиторные дуги связывают только позиции с переходами, на рисунках их изображают заканчивающимися не стрелками, а маленькими кружочками. Переход t в ингибиторных сетях может сработать, если каждая его входная позиция, соединенная с переходом обычной дугой с кратностью w(p, t), содержит не менее w(p, t) фишек, а каждая входная позиция, соединенная с переходом t ингибиторной дугой (ее кратность всегда равна 1), имеет нулевую разметку. Используя ингибиторную дугу, можно промоделировать оператор условного вычитания.

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

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

Расширенные сети Петри позволяют описывать достаточно сложные вычислительные конструкции, а также представлять взаимодействия ресурсов системы и происходящих в ней процессов. Однако переходы в сети соответствуют в разных моделях различным назначениям. Например, когда сеть Петри описывает работу последовательной программы, то полагается, что переход соответствует вычислительному процессу, а позиции - точкам соответствующих взаимосвязи процессов. С другой стороны, когда сеть Петри описывает машину потока операндов (потоковые сети Петри), то назначения переходов и состояний существенно отличаются: переход означает операцию, выполняемую над операндами, а позиции соответствуют операнду. В первом случае в сети присутствуют только управляющие компоненты программы и полностью проигнорированы информационные связи. Во втором случае — наоборот: информационные зависимости представлены дугами, соединяющими места и переходы, а управляющая зависимость отсутствует. Если оба типа вычислений — поток команд и поток операндов не пересекаются в моделируемой системе, то подобного разграничения вполне достаточно. Однако существует целый ряд организаций вычислений, в которых оба типа потоков успешно сочетаются: система с автоматическим распределением ресурсов, система со структурно-процедурными вычислениями, одновременное использование конвейерных и процедурных вычислений, мультитрсдовыс вычисления. Для подобных систем не формализовано описание взаимодействия информационных зависимостей и управляющих компонент.

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

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

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

Принцип топологической эквивалентности позволяет значительно расширить свойства СП. Прежде всего, это относится к переходам, содержащим как ингибиторные, так и обычные дуги. Если некоторый переход / связан с позицией / п обычными дугами, то данный переход активируется тогда и только тогда, когда в позиции I содержится не менее чем п фишек. Если некоторый переход 8 связан с позицией / п ингибиторными дугами, то, на первый взгляд, данный переход должен активироваться тогда и только тогда, когда в месте / нет ни одной фишки. Однако в этом случае переход 6 эквивалентен по своим свойствам переход Д что противоречит ранее сформулированному принципу, согласно которому топологически неизоморфные переходы должны выполнять различные действия. Поэтому переход 5 должен активироваться тогда, когда в позиции / находится фишек меньше п. Условие срабатывания переходов можно описать с помощью следующих формул:

«оо-/чм*»> _, (1)

где — условие срабатывания перехода //; || < [| - число вершин в позиции I.

Для упорядочения правил срабатывания переходов СР-сети предложено, чтобы каждая позиция, связанная с некоторым переходом ц п дугами, из которых к - обычных дуг и т — ингибиторных дуг, заменялась групповой позицией /2. • • •• 1П>, причем каждая позиция которой Л связана с переходом ц единственной дугой, места 4 (=1,2,..., к соединены с переходом ¡л обычными дугами, а места 4 ¡'=£+1, £+2,..., п соединены с переходомц ингибиторными дугами. Если позиция I содержит N фишек, то они должны быть разделены между позициями групповой позиции, начиная с первой. Переход ц может быть представлен с помощью групповой позиции и т-\ переходов, последователи которых совпадают с последователями перехода ц. Причем первый переход связан с позицией 1=1,2,..., к обычными дугами и с позициями ингибиторной дугой. Каждый из остальных т-2 переходов соединен единственной дугой с позициями и ¡=к+2, к+ 3,..., п. Переход /г, связанный с позицией Г к обычными и т ингибиторными дугами, активируется, если позиция / содер-

жит больше к фишек, но меньше т фишек, то есть5(/() = Р(т > |/|| ^ к) . Подобное преобразование приведено на рис. 1.

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

Ял)

к + т \

(2)

Данная формула обобщает условие срабатывания перехода ц для случая, когда т=0. При отсутствии ингибиторных дуг верхняя граница количества фишек позиции /

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

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

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

дуги. На рис. 2 представлены реализации различных отношений для активации переходов.

0 И-

п+1 I г

н^Г0

5(Р) = (^>л) Я(Р) = (х < я) 5(Р) = (х = л)

Рис. 2. Реализация отношений с помощью разметки дуг.

Следующим шагом модернизации СР-сетей является введение в сеть компонент, меняющих разметку дуг. Каждой дуге СР-сети может быть поставлена в соответствие позиция, количество фишек в которой определяет разметку дуги (число обычных или ингибиторных дуг). При срабатывании перехода количество фишек в позициях, размечающих дуги, активирующих переход, остается неизменным. Графически соответствие позиции и разметки некоторой дуги обозначается с помощью а-дуги, инцидентной вершине и обычной дуге. Если обычная дуга является отношением д = <1>, где .у - вершина-начало дуги, с1 - вершина-конец дуги, то а-дуга является отношением ж = <г,9>, где 5 — вершина графа, а <7 — дуга. Введение нового компонента позволяет расширить возможности сетей и сделать их более мощными, чем самомодернизцэующиеся сети. Каждой дуге СР-сети может быть поставлено в соответствие несколько а-дуг, в том числе, и а-дуге может быть поставлена в

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

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

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

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

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

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

В(Р) = (Х<>0 а)

В(Р) = (Х>Ы) б)

В(Р)=(Х = М) в)

Рис. 3. Реализация отношений с помощью а-дуг.

Х:=Х+У Х:=ХУУ Х:=У

а) б) в)

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

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

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

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

Х:=Х+А*В

Х:=Х+

ш

а) б)

Рис. 5. Примеры СР-сетей, использующих операции умножения и деления.

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

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

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

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

Первый процесс задается последовательностью управляющих позиций (С-позиции) и переходов А,—*Pi—*А2—+Р2~*>Л3—<►Рз, второй процесс задается последовательностью управляющих позиций и переходов Bi—*Ti—*B2—*T2-*B3—*T3. Остальные позиции сети, представленные на рис. 6, являются функциональными (F-позиции) и предназначены для описания вычислений.

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

Для идентификации того или иного места управляющей G-позиции используются переходы, связанные не с отдельной позицией исходной сети, а с групповой позицией, при этом дуги, активирующие переход, помечаются разметкой i+I, то есть i — обычными дугами и одной /- ингибиторной дугой. Здесь i - индекс С-позиции исходной сети. Подобная конструкция позволяет существенно сократить число позиций в сети Петри и сделать ее более читаемой и в большей степени соответствующей традиционным методам программирования параллельных и распределенных вычислений. На рис. 66) представлена CF-сеть с групповыми позициями, преобразованная из сети, приведенной на рис. 6а).

В качестве примера вычислений в CF-сетях рассмотрим реализацию следующего фрагмента программы. CF-сеть приведена на рис. 7. Переходы Pt и Р2 активируются, когда имеется фишка в управляющей позиции у. Переход срабатывает, если число фишек в позиции к будет больше или равно числу фишек в позиции Ь. Условие активации перехода Р2 противоположное. Переход Р, соответствует ветке then, а переход Р2 — ветке else услов-

а) пример описания параллельного процесса

б) CF-сеть с групповыми позициями

Рис. 6. Примеры описания CF-сети.

ного оператора. Срабатывание перехода Р2 создаст фишку в управляющей позиции S, что делает возможной активацию перехода Р2. Дополнительным условием срабатывания перехода Р} является наличие фишек в позиции т, равное квадрату числа фишек в позиции к (двойная о-дуга с общим источником). Срабатывание перехода Р3 приведет к увеличению числа фишек в позиции/на величину d*a-e. Для операции вычитания в CF-сетях используется ингибиторная а-дуга.

if k >= b then /bV ГЛ(Т) (Tl e:=e+a*b+c*d Jr-^ else )/—Ш-* I * >(g> v

if к2*™

then

f:=f+d*a-e

Рис. 7. СР-сеть с управляющими местами и местами данных.

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

Определение 1. СР-сеть состоит из семи элементов: множества функциональных позиций множества управляющих мест С, множества переходов Г, отношения инцидентности 5: 5'с(^иС)х7'иЗг'х(^иС), отношения инцидентности А: Р и С 5, функции кратности дуг IV: функции начальной разметки функциональных позиций Л/0р: Р—и функции начальной разметки управляющих позиций Мое: С—*М.

Здесь множество N — множество натуральных чисел, множество М — множество, состоящее из двух чисел - нуля и единицы, М={0,1}. Таким образом, управляющей позиции может ставиться в соответствие или ноль, или единица, в то время как функциональной позиции может ставиться в соответствие любое натуральное число.

Более строго функция Мое требует, чтобы множество С было разделено на т непере-

т

секающихся подмножестве = . Для каждого подмножества множества управляющих

/=1

позиций С, = {Сп,С12.....С1к } справедливо следующее условие ]ГМ0С(Су) = 1.

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

Для каждого перехода t e T существует единственный элемент (Q ,t,Q '^e F, задающий для него входное мультимножество функциональных и управляющих позиций Q c.C\JF и выходное мультимножество Q cCU^. Функциональная или управляющая позиция s e С U F инцидентна переходу /, если set или set.

Отношение инцидентности А ставит в соответствие некоторую функциональную вершину f дуге, принадлежащей отношению S или отношению А. Более строго отношение А представляет собой объединение конечного числа п непересекающихся подмножеств

п

А= А/. Начальное подмножество А0 определяет множество а-дуг, смежных с дугами

/=о

CF-сетиЛо cFx((FUC)x7'U7'x(-/:'UC)). Подмножество А1 определяет множество а-дуг, смежных с дугами подмножества^: А1 с F х Aq. В общем случае А„ с Fx Arl_i.

Определение 2. CF-сеть Q\ будет эквивалентна CF-сети Q2, если мощности множеств управляющих и функциональных позиций сетей Qt и Q2 равны и найдутся функции соответствия Фс: Ci—*C2 и Фр: Fi—*F2 и при этом для любых одинаковых начальных разметок функциональных и управляющих позиций сетей Q, и Q2 все последующие разметки сетей равны.

В CF-сети на рис. 8а) два перехода имеют равные множества входных мест (позиции а и Ь) и выходных мест (позиции d и с), данную сеть можно преобразовать в сеть, приведенную на рис. 86), исключив один из переходов.

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

а) б)

Рис. 8. Преобразованиеэквивалентных переходов.

а) б)

Рис. 9. Поглощение перехода

Особым случаем является такой, когда различается разметка входных дуг на единицу, но при этом значение А=1, то есть один переход соединен с входной псвицией обычной дугой, а второй переход соединен с входной позицией ингибиторной дугой. Данный пример показан на рис. 10. Переход^ (рис. 10) сработает, если в позиции а находится, по крайней мере, одна фишка, а переход Рг сработает, если в позиции а нет фишки, данная позиция связана с переходом Р2 ингибиторной дугой.

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

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

б) в)

Рис. 10. Замена переходов обобщенным переходом.

И, тем не менее, есть достаточно четкое отличие: переход P¡ сработает при любом количестве фишек, в то время как переход Р>2 сработает только в диапазоне [0,1]. Для того чтобы ликвидировать эту неточность, можно изменить разметку дуги <а, í>)2> с 21 на col, где со - символ бесконечности, тогда переходР12 будет срабатывать при любом количестве фишек. Данная CF-сеть приведена на рис. 10в). Для компенсации фишки по-прежнему необходима обратная ингибиторная дуга второго рода.

Сформулировано общее условие эквивалентности: если два перехода топологически изоморфны, а разметка дуг перехода является дополнением друг друга, то такую пару переходов можно заменить единственным переходом с разметкой col, которая срабатывает всегда и посылает фишки с входных позиций в выходные позиции ^[1,=°] V Р2[0] = р[0,оо].

Разработана алгебра CF-сетей, включающая операции наложения, присоединения, исключения, итерации. На рис. 11 представлен результат операции присоединения CF-сетей.

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

Рис. 11. Результат операции присоединенияСР-сетей.

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

ся

о:

!У1 ЧУп

<у

сЯЪУ1

сЫчЬУл

а) Т-сеть 6) У-сеть

Рис. 12. Реализация с помощью СИ-сетей основных переходовЕ-сетей.

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

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

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

Д) е)

Рис. 13. СР-сети типовых взаимосвязанных процессов

На рис. 13а представлен последовательный процесс, процесс детерминированного выбора — на рис. 136, процесс недетерминированного выбора по данным — на рис. 13 в, процесс недетерминированного выбора по управлению — на рис. 13г, параллельный процесс — на рис. 1 Зд, чередование процессов — на рис. 1 Зе.

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

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

Укрупненная структура программного комплекса средств моделирования приведена на рис. 14.

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

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

На рис. 15 приведены экраны среды разработки СР-сетей. Библиотеки компонентов предоставляют пользователю набор базовых графических объектов, из которых могут строиться СР-сети или их компоненты.

Результаты моделирования СР-сети могут быть выражены численным выражением для дальнейшего скоростного анализа с помощью подсистемы имитационного моделирования. Для формирования параметров компонентов системы или сети используется соответствующая утилита Для получения подобных оценок разработана специальная утилита среды разработки и моделирования СР-сетей - МитЬегТгапг. Данная программа произво-

Рис. 14. Струетура программного комплекса средств моделирования

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

■■■¡^^■■■■НШ

ЕШ

1Г и. * «I # И А

ГЕййлиошеуцкомпрн

меню и панель инструментов

1ентов)

/

\ Т( /.

I у"-

/С*2

Е^З —• ; '

Г ■ Д-

Цтраницы

. Т

^трока состояния

Ъ в I * 4 0

•в?

еЗ-

а) среда разработки СИ сетей б) пример окна дерева объектов

Рис. 15. Экраны среды разработки СР-сетей.

На рис. 16 показаны экраны программы, позволяющей задать список событий и е-событий сети, определяющих дисперсию транзактов. При анализе СР-сетей производится построен® гистограмм групповых событий, а также определение частоты группового события. На основании полученных данных утилита ЫитЬегТгапг производит расчет параметров компонентов сети или многопроцессорной системы по ранее введенным формулам в прикрепленном файле ш.Ьп1. На основе моделирования с помощью СР-сетей фрагментов параллельных программ и распределенных вычислительных систем определяются численные параметры исследуемых аппаратно-программных комплексов.

Рис. 16. Экраны программы ЫитЬегТгапг.

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

Модель сети состоит из подмоделей, каждая из которых описывает либо узел сети, либо канал связи. В подсистеме имитационного моделирования предусмотрены четыре вида подмоделей: "клиент", "сервер", "коммутатор", "связь". Подмодель "клиент" предназначена для формирования нагрузки в сети и создания информационных потоков. "Сервер" — узел сети, в котором происходит обработка запросов от "клиентов". Подмодель "коммутатор" моделирует работу сетевого оборудования (коммутатор, маршрутизаторХ обеспечивающих передачу информации от "клиентов" к "серверам". Подмодель "связь" моделирует работу каналов связи. Представленное в системе моделирования множество подмоделей позволяет составить модель для сетей достаточно высокой сложности. Экраны подсистемы имитационного моделирования показаны на рис. 17.

Эксперимент позволяет получить такие графики, как, например, зависимость среднего времени ответа серверов от коэффициента нагрузки.

В пятой главе представлены примеры реализации с помощью СР-сетей различных типов взаимодействия процессов в многопроцессорных системах. Приведены варианты реализации с помощью СР-сетей взаимосвязанных процессов, обращающихся к общему ресурсу, а также реализация вычислений для БШТО-систем, М1МО-систем и конвейерных вычислителей.

Рассмотрим в качестве примера различные варианты параллельной реализации в широком смысле этого слова следующего фрагмента программы:

5-4

Рис. 17. Экраны подсистемы имитационного моделирования

й>г ¡:=1 Ю п ¿о х[(]:= ((а[1]+Ьр])*сН^Н)* ((а[|"1+Ьр])*срН[1]);

Параллельная реализация данного выражения подразумевает независимое вычисление оператора присваивания процессорами системы. На рис. 18а) представлены вычисления в СР-сети, соответствующие функционированию 31МО-системы (каждый переход активизирует изоморфные фрагменты СР-сети, то есть выполняет одинаковые операции); на рис.186) представлены вычисления в СЕ-сети, соответствующие мультипроцедурной реализации вычислений в М1МЕ)-системе, когда каждый процессор реализует вычисления по своей собственной процедуре.

Управляющие позиции образуют независимые процедуры. Наличие фишки в определенном месте управляющей позиции соответствует счетчику команд процессора, который инициирует выполнение определенной команды. Команде процессора соответствует переход СР-сети. Множество процедур активизируется стартовым переходом при наличии фишки в позиции

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

а) пример функционированияЗМО-системы б) пример функционированияМ1МО-системы Рис. 18. Пример СР-сети, реализующей параллельные вычисления.

Структурная реализация вычислений является предельным вариантом построения конвейерных вычислений, когда темп обработки информации совпадает с темпом передачи данных. СР-сеть, моделирующая структурную реализацию циклического выражения, приведена на рис. 19. В данной сети активизация переходов производится не по наличию фишки в определенной управляющей позиции, а при наличии фишек в местах Мх, где д: — операнд. Подобные места можно определить как маркеры операндов. Для активизации переходов необходимо наличие фишек на всех местах, соответствующих маркеру входных операндов. После срабатывания перехода полученный результат может быть использован на следующей ступени конвейера.

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

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

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

Рис. 19. СБ-сеть, моделирующая структурную реализацию циклического выражения.

Предложены и проанализированы с помощью СР-сетей аппаратно-программные средства, обеспечивающие повышение гарантоспособности параллельных программ.

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

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

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

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

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

Рис. 21. СР-сеть, реализующая децентрализованное решение задачи об обедающих философах.

Рис. 20. Фрагмент СР-сети, реализующей распределенное решение задачи.

\

Проведены исследования данной СБ-сети, доказывающие, что в сети не возникнет дедлок, поскольку официанты обязательно отдадут использованные ресурсы ("грязные" палочки).

Предложены модели на основе СБ-сетей типовых протоколов, реализуемых в компьютерных сетях. Совокупность моделей элементов вычислительных структур и типовых протоколов позволяет в 2-3 раза сократить время анализа параллельных программ, реализуемых в распределенных вычислительных системах.

Разработаны и исследованы модели на основе СР-сетей для анализа региональной распределенной информационно-вычислительной сети (РИВС) и при создании комплекса

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

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

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

1ВМ ¡Бенаа Л П

1Р и У нл* -ЦШ1

www.opfrd.ru с И а У ■Р**Р РТР Пота

РвгЦемтр'^ "»■»И»* Омм

* ?

ЛИ ВС

Рот. Центра пиве цвп

Сетевая среда -

районы

П

цаЯвнм

4Р~

урны

Рис. 22. РИВС Дагестшского ОПФР.

Основой информационной системы Дагестанского ОПФР, как и других региональных ОПФР, являются сервера IBM ¡Serias, которые работают в локальной сети, содержащей пользовательские терминалы и системы управления. Значительная доля информации и первичных данных поступает из районных пунктов персонифицированного учета. Эту информацию должны своевременно получать МРП и передавать их в Отделение ПФР (региональный центр — Per. Центр), информацию по вновь застрахованным лицам передают в ПФР (г. Москва) для получения страховых номеров. В этой цепи передачи информации существуют узкие места: процесс передачи информации из РП в МРП и далее в Per. Центр, ввиду отсутствия развитой телекоммуникационной системы и надежных коммутируемых линий связи (связано с территориальной удаленностью большинства РП в условиях горной республики).

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

Основная информационная составляющая регионального Отделения ПФР заключается в ведении двух основных баз: базы застрахованных лиц и базы получателей выплат. База застрахованных лиц представляет собой трехуровневую распределенную систему (Центр-Регион-Район), база получателей выплат при централизованном назначении и выплате - двухуровневую систему (Регион-Район). Информация в этих двух базах тесно взаимосвязана, имеется ряд прямых и косвенных зависимостей, в связи с чем согласованность информации в этих обеих базах является основным критерием качества исполнения основных функций Отделения ПФР.

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

Далее анализировалась загрузка серверов с учетом распределения задач и количества клиентов. Моделировалась работа с одной из основных БД - базой получателей выплат, используемой в настоящее время в ОПФР. Были промоделированы три модели организации работы с двумя типами клиентов, просмотр (R-читающий процесс) и работа (W-пишущий процесс) с БД, при этом в первом и во втором случаях сервера работают со все-

ми клиентами, в третьем варианте сервера разделены по типам клиентов. Результаты моделирования приведены на рис. 23. Схема взаимодействия представлена на рис. 24.

Графики для всех трех вариантов построены для скоростей серверов 200 и 400 заявок/с. Средний размер заявки, поступающей от клиента, составляет 2-=-2,5 кбайт, средний размер ответа сервера — 10-11 кбайт. Как видно из графиков, распределение серверов по задачам дает значительное преимущество по сравнению с остальными вариантами.

Также были исследованы работа серверов по передаче файлов (РТР-сервер, почтовый сервер) и сетевое оборудование при работе в сети локальных и удаленных пользователей при нормальной и пиковой нагрузке возникающей в начале и в конце месяца. Анализ результатов моделирования показал, что узким местом для данной структуры сети является канал связи и сетевое оборудование, загрузка которого составляет в среднем 70%^80%. Произведена модернизация коммутационного оборудования, что позволило при незначительных финансовых затратах существенно повысить производительность КС и обеспечить повышение гарантоспособности функционирования распределенной информационной системы Дагестанского ОПФР.

Рис. 23. Зависимость времениответа (Т.т) от количе- Рис. 24. Варианты организацииработы ства клиентов (К*). Серверов.

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

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

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

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

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

Разработаны методы представления с помощью СР-сетей параллельных вычислений, реализуемых в БИ^ГО- и М1ШЭ-системах, конвейерных вычислителях и компьютерных сетях, а также их сочетаниях. Предложенные базовые конструкции параллельных и конвейерных вычислений на основе СР-сетей позволяют ускорить процесс создания и анализа параллельных программ для распределенных и многопроцессорных систем.

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

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

Для эффективной разработки гарантоспособных параллельных программ на базе СР-сетей создана интегрированная среда разработки программных компонентов.

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

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

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

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

Основные публикации по теме диссертации

1. Левин И.И., Омаров О.М. Анализ вычислительных процессов и структур на основе CF-сетей. - Махачкала: Изд-во Дагестанского научного центра РАН (ДНЦ РАН), 2006. - 253 с.

2. Николаев И.А., Бабенко Л.К., Матвеева Л.Н., Омаров О.М. Организация вычислительного комплекса на базе многопроцессорной вычислительной системы для автоматизации физического эксперимента// Известия Северо-Кавказского научного центра высшей школы. Технические науки, 1986. - № 2. - С.25-30.

3. Дордопуло А.И., Омаров О.М. Представление операторов параллельного программирот-ния в у нифицированнойпараллельной форме // Известия ТРТУ. Тематический выпуск "Интеллектуальные и многопроцессорные системьГ. - Таганрог: Изд-во ТРТУ, 2004. - Т. 9. - С. 70-74.

4. Левин И.И., Омаров О.М. Управляющие функциональные сети Петри для моделирования распределшных вычислительных сетей // Вестник Дагестанского научного центра РАН. - Махачкала: Изд-во ДНЦ РАН, 2005. -Т.21.-С. 44-49.

5. Левин И.И., Омаров О.М. CF-сети - инструмент для оперативного анализа распределшных вычислений // Известия ТРТУ. Тематический выпуск "Интеллектуальные и многопроцессорные системы".-Таганрог:Изд-во ТРТУ,2005.-Т. 10.-С. 124-130.

6. Омаров О.М. Моделирование с помощью CF-сетей взаимосвязных процессов // Вестник Дагестанского научного центра РАН. - Махачкала: Изд-во ДНЦ РАН, 2005. - Т.22. - С. 25-30.

7. Омаров О.М., Гаджиев М.А., Ахмедов Р.К., Тагиров А.Т. Корпоративная сеть передачи данных Отделения Пенсионного фонда России по Республике Дагестан // Информационные технологии, 2005. - № 3. - С. 64-67.

8. Омаров О.М. Инструментальные средства моделирования распределенных вычислительных систем на основе CF-сетей // Информационныетехнологии, 2006. - №4. - С.58-63.

9. Омаров О.М. Возможности CF-сетей для адекватного моделирования распределенных вычислений//Научная мысль Кавказа. Приложение,2006. - № 3. - С. 166-173.

10. Омаров О.М. Формальная модель для описания и моделирования параллельных вычислительных процессов на основе CF-сетей // Изв. вузов. Сев.-Кавк. регион. Техн. науки, 2006. Приложение к № 1. - С. 3-14.

11. Омаров О.М. Моделирование и анализ функционированиякомпьютернойсети Отделения пенсионного фонда России по республике Дагестан// Изв. вузов. Сев.-Кавк. регион. Техн. науки, 2006. Приложение к№ 2. - С. 5-17.

12. Омаров О.М., Абдулгамидов A.A. Репликационные приложения распределенных баз данных в информационных системах с низкоскоростными каналами связи // Изв. вузов. Сев.-Кавк. регион. Есгесгв. науки. Приложение, 2006. - № 3. - С. 22-31.

13. Омаров О.М. CF-сети для моделирования распределенных информациенно-вычислительныхсистем// Телекоммуникации,2006. - № 7. - С. 21-25.

14. Омаров О.М. Использование CF-сетей для описания и моделирования параллельных вычислительных процессов// Приборы и системы. Управление, контроль, диагностика, 2006. ■ № 7, ■ С.22-26.

15. Левин И.И., Дордопуло А.И., Омаров О.М. Унифицированное представление алгоритма задачи для произвольного варианта распараллеливания // Искусственный Интеллект. - Донецк: Наука i освгга, 2004. - Т 3. - С. 133-139.

16. Омаров О.М. Моделирование параллельных алгоритмов с использованием сетей Петри // Искусственный интеллект. - Донецк: Наука i oceiTa, 2005. - Т 4. - С. 240-244.

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

18.0маров О.М., Абдулгамидов A.A. Распределенные базы данных на основе гибридных топологий репликационных приложений // Информационные технологии моделирования и управления. - Воронеж: Научная книга, 2005. - № 6(24). - С.877-884.

19. Омаров О.М. Устройство для сопряжения источника и приемника информации. АС №1226473, БИ № 15, 1986.

20. Омаров О.М. Устройство для централизованного управления вычислительной системой. АС №1259261, БИ № 35, 1986.

21.Бабенко Л.К., Макаревич О.Б., Омаров О.М., Карпов Е.В., Катаев О.В. Устройство для централизованногоуправления вычислительной системой.АС № 1674146, БИ№ 32,1991.

22. Омаров О.М. Устройство для управления обменом информацией. АС №1783525, БИ №47,

1992.

23. Омаров О.М. Устройство для сопряжения многопроцессорной вычислительной системы. АС № 1160423, БИ № 21, 1985.

24. Айдемиров И.А., Омаров О.М. Микропрограммное устройство управления. АС №1117637, БИ №37, 1984.

25. Омаров О.М. Многоканальное устройство приоритета. АС №1251081, БИ №30,1986.

26. Омаров О.М. Многоканальное устройство для обслуживания запросов. АС № 1149258, БИ№13,1985.

27. Омаров О.М. Устройство присритетного управления. АС № 1070552, БИ № 4, 1984.

28. Омаров О.М., Османов Р.Ш. Система имитационного моделирования и анализа сетей // Свидетельство об официальнойрегистрации программы для ЭВМ. № 2005611605/РОСПАТЕНТ. -М„ 29.08.2005.

29. Омаров О.М. Интегрированная среда для анализа и моделирования информационных сетей на базе фу нкциональноуправляющих сетей Петри // Свидетельство об официальнойрегистрации программы для ЗМ № 2005612206 / РОСПАТЕНТ? М„ 29.08.2005.

30. Омаров О.М. Теория вычислительных процессов и структур. Учебное пособие. - Махачкала: РИО ДГТУ, 2006. - 268 с.

ЛР № 020565 от 23 июня 1997 г. Подписано к печати. В .^2006 г. Формат 60x841/16. Бумага офсетная. Печать офсетная. Усл. п.л. - 2,0. Уч. - изд.л. - 1,8. Заказ №271. Тираж 150 экз.

ГСП 17А, Таганрог, 28, Некрасовский, 44. Типография Таганрогского государственного радиотехнического университета.

ВВЕДЕНИЕ.

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

1.1. Математическая модель взаимодействия процессов.

1.2. Параллельные граф-схемы алгоритмов.

1.3. Сети Петри.

1.4. Расширенные сети Петри.

1.5. Принципы построения CF-сетей.

1.6. Выводы.

2. ОСНОВНЫЕ СВОЙСТВА CF-СЕТЕЙ.

2.1. События в CF-сетях.

2.2. Представление последовательных и параллельных процессов с помощью CF-сетей.

2.3. Реализация вычислений с помощью CF-сетей.

2.4. Эквивалентные преобразования CF-сетей.

2.5. Алгебра CF-сетей.

2.6. Решение с помощью CF-сетей противоречий в параллельных алгоритмах.

2.6.1. Противоречие детерминированного и случайного.

2.6.2. Противоречия синхронных и асинхронных процессов.

2.7. Выводы.

3. СРАВНЕНИЕ CF-СЕТЕЙ С ДРУГИМИ ФОРМАЛЬНЫМИ МОДЕЛЯМИ РАСПРЕДЕЛЕННЫХ И МНОГОПРОЦЕССОРНЫХ СИСТЕМ.

3.1. Сравнение CF- сетей.

3.1.1. CF-сети и оценивающие сети (Е-сети).

3.1.2. CF- сети и F-сети.

3.1.3. CF-сети и цветные сети Петри.

3.1.4. CF- сети и объектные сети Фалька.

3.2. Представление с помощью CF-сетей типовых взаимосвязанных процессов.

3.2.1. Последовательный процесс.

3.2.2. Процессы выбора.

3.2.3. Параллельные взаимосвязанные процессы.

3.2.4. Подчиненные процессы.

3.3. Применение CF-сетей для моделирования взаимосвязанных процессов.

3.4. Выводы.

4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ МОДЕЛИРОВАНИЯ

ПАРАЛЛЕЛЬНЫХ ПРОГРАММ МНОГОПРОЦЕССОРНЫХ И РАСПРЕДЕЛЕННЫХ СИСТЕМ.

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

4.2. Общая структура программного обеспечения для моделирования параллельных программ многопроцессорных и распределенных систем.

4.3. Среда разработки CF-сетей.

4.3.1. Особенности пользовательского интерфейса среды синтеза и анализа CF-сетей.

4.3.2. Средства отладки CF-сетей.

4.3.3. Библиотеки стандартных мастеров.

4.4. Программа взаимосвязи кибернетических моделей на основе

CF-сетей и аналитических моделей дискретных систем.

4.5. Подсистема имитационного моделирования вычислительных систем и сетей.

4.5.1. Редактор сети.

4.5.2. Моделирование процессов в сети.

4.6. Выводы.

5. ПРИМЕНЕНИЕ CF-СЕТЕЙ ДЛЯ МОДЕЛИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ МНОГОПРОЦЕССОРНЫХ И РАСПРЕДЕЛЕННЫХ СИСТЕМ.

5.1. Требования к механизмам взаимодействия ресурсов и процессов в многопроцессорных и распределенных системах.

5.2. Моделирование параллельных программ для многопроцессорных систем.

5.3. Средства и методы эффективного взаимодействия процессов и ресурсов в многопроцессорных и распределенных системах.

5.3.1. Механизм критической секции.

5.3.2. Буферизация запросов.

5.3.3. Механизмы синхронизации множества процессов обмена.

5.3.4. Механизмы синхронизации групповых процессов обмена.

5.3.5. Механизмы повышения надежности процессов обмена.

5.4. Выводы.

6. МОДЕЛИРОВАНИЕ С ПОМОЩЬЮ CF-СЕТЕЙ РАСПРЕДЕЛЕННЫХ СИСТЕМ.

6.1. Методы организации распределенных вычислений.

6.2. Моделирование протоколов с помощью CF-сетей.

6.3. Моделирование и анализ региональной информационно-вычислительной сети.

6.3.1. Структура региональной информационно-вычислительной сети.

6.3.2. Синхронизация распределенных баз данных.

6.3.3. Моделирование процесса синхронизация распределенных баз с помощью CF-сетей.

6.3.4. Моделирование и анализ функционирования ИВС

Дагестанского отделения ПФР.

6.4. Выводы.

Ведущие специалисты в области вычислительной техники указывают в качестве конечной цели развития информационных технологий создание системы "вездесущих" вычислений, которая должна обеспечить доступ к информации и к средствам ее обработки практически в любом месте Земного шара. Для создания подобной системы необходимо решение целого комплекса взаимосвязанных научно-технических проблем и, прежде всего, в области программного обеспечения распределенных вычислительных ресурсов [1]. При создании программ для распределенных и многопроцессорных систем программист неизбежно сталкивается с рядом технических сложностей, к которым относятся: ненадежность коммутационной структуры, сложность согласования скорости работы множества функциональных устройств, но главной проблемой программирования распределенных, а, в общем случае, параллельных вычислительных систем является адекватная замыслу разработчика реализация в системе множества вычислительных процессов. Обеспечить согласованное функционирование в дискретных системах сотен, а иногда даже тысяч взаимосвязанных процессов невозможно без принципиально новых подходов к построению программных комплексов.

Под программой, как правило, понимают текст на определенном языке программирования, соответствующий спецификации и формально выведенный из фиксированного набора предпосылок и данных. Правильной программой принято считать алгоритм, реализованный для определенной вычислительной системы, не содержащий ошибок. Неоднозначное понятие "ошибка программы" обычно трактуется как невыполнение программой действий в некотором аппаратно-программном окружении, которые ожидаются от нее на основании эксплутационной документации. Более точно следовало бы говорить о несогласованности между программой и документацией по ее применению [2,3]. В большинстве случаев задание на разработку программы формулируется неформально, что не позволяет доказать формальными математическими методами корректность текста программы. Как указывал Э. Дейкстра [3], невозможно также доказать правильность программы с помощью ее тестирования, которое может только продемонстрировать наличие в программе ошибки. Для программ распределенных вычислительных систем, число состояний которых может достигать нескольких миллионов, ситуация еще более усугубляется. Недетерминизм выполнения параллельных программ не позволяет тестированием оценить все многообразие сочетаний состояний процессов в системе.

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

Методы прогнозирования и устранения ошибок могут считаться способами подтверждения гарантоспособности, так как они указывают, каким образом можно достичь уверенности в способности системы к выполнению предопределенных услуг [4].

Для оценки гарантоспособности программ следует анализировать последствия каждого отказа. В некоторых нештатных ситуациях ошибки в программах могут вызывать лишь неудобства при их эксплуатации, тогда как другие ошибки могут иметь катастрофические последствия. Поэтому для оценки надежности параллельных программ необходимы средства моделирования, с одной стороны, достаточно простые, чтобы разработчик мог оперативно обрабатывать представленные данные, а, с другой стороны, точно отражающие события, происходящие в системе при реализации распределенных вычислений. Современные средства моделирования распределенных и многопроцессорных систем строятся на основе трех различных концепций. К одной из таких концепций относятся языки дискретного имитационного моделирования, как правило, транзактного типа, в котором система представлена в виде совокупности устройств и множества связей между ними. На основе подобной структуры производится обработка случайного или детерминированного потока входных заявок (транзактов). Как правило, алгоритм обработки задается на специальном языке, например на 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]. Для анализа подобных систем нужны принципиально новые средства моделирования распределенных вычислений, которые обладали бы достоинствами существующих средств моделирования и имели бы дополнительные возможности, обеспечивающие реализацию анализа параллельных процессов на качественно новом уровне.

Целью работы является повышение гарантоспособности параллельных программ в многопроцессорных и распределенных системах.

Средством достижения цели является более адекватное моделирование процессов и ресурсов на различных уровнях детализации.

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

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

Среди отечественных исследований в области разработки формальных методов моделирования параллельных и распределенных систем можно отметить работы Н.А. Анисимова, O.JI. Бандман, И.Б. Вирбицкайте, Ю.Г. Карпова, В.Е. Котова, А.Е. Костина, И.А. Ломазовой, В.А. Соколова, В.А. Непомнящего, JI.A. Черкасовой и др. Однако их исследования были ориентированы на описание только управляющих компонент вычислительного процесса и не отражали сами вычисления.

Предлагается в качестве средства анализа процессов в распределенных и многопроцессорных вычислительных системах использовать разработанное автором расширение сетей Петри, свободное от указанных выше недостатков. Многочисленные расширения сетей Петри, как правило, ориентированы на представление структурных составляющих вычислительных устройств или программ и не позволяют адекватно описать типовые программные конструкции. Это вызвано, прежде всего, тем, что сети Петри и их расширения направлены на описание только управляющих компонент вычислительного процесса и не отражают сами вычисления [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-сетей, подтверждающих достоверность разработанных моделей.

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

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

Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в ДГТУ, НИИ МВС ТРТУ, непосредственным участником которых являлся автор диссертации.

Наиболее важными из них являются:

Исследование и разработка параллельного интерфейса связи объекта с МВС", № ГР 01.83.0052005, руководитель НИР - Б.В. Захаркин;

Исследование и разработка аппаратно-программных средств подсистемы связи с объектом и внешними устройствами для многопроцессорной вычислительной системы", № ГР 01.85.00188980, в рамках комплексной программы 0.80.14, тема 01.10 по Постановлению ГКНТ СССР и комиссии Президиума СМ СССР № 442/377, руководитель НИР - Б.В. Захаркин;

Исследование и разработка принципов построения и организации системы реального времени и средств связи с внешними устройствами МВС", № ГР 01.86.0122416, руководитель НИР - к.т.н. О.М. Омаров;

Разработка системы ввода-вывода вычислительного комплекса", № ГР 01.89.0007077, руководитель НИР - к.т.н. О.М. Омаров;

Разработка и создание информационно-телекоммуникационной системы для общеобразовательных учреждений в горных районах Республики Дагестан (2003-2004)" в рамках программы "Федерально-региональная политика в науке и образовании", руководитель НИР - д.т.н., профессор Ш.-М.А. Исмаилов;

Исследование возможности путей создания вычислителя с программируемой архитектурой", руководитель НИР - член-корреспондент РАН, д.т.н., профессор И.А. Каляев, заказчик в.ч. 25714;

Исследование и разработка математических и программных средств для эффективного распараллеливания прикладных задач на высокопроизводительных вычислительных комплексах", руководитель НИР -член-корреспондент РАН, д.т.н., профессор И.А. Каляев;

Разработка и исследование интеллектуальных аппаратно-программных средств многопроцессорных вычислительных и управляющих систем с динамически программируемой архитектурой", № ГР 0120.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) Левин И.И., Омаров О.М. Анализ вычислительных процессов и структур на основе CF-сетей. - Махачкала: Изд-во Дагестанского научного центра РАН, 2006. - 253 с.

2) Левин И.И., Омаров О.М. Управляющие функциональные сети Петри для моделирования распределенных вычислительных сетей // Вестник Дагестанского научного центра РАН. - Махачкала: Изд-во ДНЦ РАН, 2005. -Т.21.-С. 44-49.

3) Омаров О.М. Моделирование с помощью CF-сетей взаимосвязанных процессов // Вестник Дагестанского научного центра РАН. - Махачкала: Изд-во ДНЦ РАН, 2005. - Т.22. - С. 25-30.

4) Омаров О.М. Инструментальные средства моделирования распределенных вычислительных систем на основе CF-сетей // Информационные технологии, 2006. - № 4. - С. 58-63.

Наиболее существенные новые научные положения, выдвигаемые для защиты:

1) сети Петри и их расширения не позволяют описывать все многообразие вычислений, встречающихся в кибернетических системах, в связи с чем разработка новых расширений сетей Петри актуальна;

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

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

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

Другие наиболее существенные новые научные результаты, выдвигаемые для защиты:

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

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

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

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

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

Достоверность и обоснованность полученных в работе результатов подтверждается полнотой и корректностью исходных посылок, теоретическим обоснованием, непротиворечивостью математических выкладок. Теоретические исследования подтверждены вычислительными экспериментами на имитационной модели многопроцессорных систем и региональных сетей, а также реализацией компонентов математического обеспечения на МВС ЕС-2703 и при реализации компонентов программного обеспечения региональной информационной сети Дагестанского Отделения ПФР.

Научная и практическая ценность работы. Практическое использование научных результатов позволило:

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

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

3) провести анализ реализации параллельных взаимосвязанных процессов в распределенных вычислительных системах. Предложены модели на основе CF-сетей типовых протоколов, реализуемых в компьютерных сетях. Совокупность моделей элементов вычислительных структур и типовых протоколов позволяет в 2-3 раза сократить время анализа параллельных программ, реализуемых в распределенных вычислительных системах;

4) решить прикладную задачу создания гарантоспособных программ на примере построения распределенной вычислительной системы и комплекса параллельных программ, реализуемых в ней на примере Отделения ПФР по РД. Использование механизма CF-сетей и созданных методов и программных средств анализа CF-сетей и параллельных программ позволили повысить надежность функционирования параллельных программ в компьютерных сетях в 1,5-2,5 раза.

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в ДГТУ, в НИИ МВС ТРТУ, непосредственным участником которых являлся автор диссертации. Результаты диссертации внедрены в Дагестанском государственном техническом университете, г. Махачкала; НИИ многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета, г. Таганрог; Южном научном центре Российской академии наук, г. Ростов-на-Дону; ФГУП "18 ЦНИИ" МО РФ, г. Москва; ФГНУ НИИ "Спецвузавтоматика", г. Ростов-на-Дону; ООО "НТЦ Диамонд", г. Москва; ЗАО "Орбита", г. Краснодар; Дагестанском научно-исследовательском и технологическом институте информатики, г. Махачкала; ГУ - Отделении пенсионного фонда Российской Федерации по республике Дагестан (ГУ-ОПФР по Республике Дагестан), г. Махачкала.

Структура диссертации. Диссертация содержит 376 страниц текста и состоит из введения, шести глав, заключения, списка литературы из 182 наименований и приложения на 18 страницах. В диссертацию включены 206

6.4. Выводы

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

2) Предложены модели на основе CF-сетей типовых протоколов, реализуемых в компьютерных сетях. Совокупность моделей элементов вычислительных структур и типовых протоколов позволяет в 2-3 раза сократить время анализа параллельных программ, реализуемых в распределенных вычислительных системах.

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

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

5) С помощью механизма CF-сетей промоделированы критические участки распределенной системы Дагестанского ОПФР. Определены численные параметры узлов распределенной системы. Предложены изменения в системе синхронизации распределенной БД Дагестанского ОПФР и механизмы репликации, позволяющие избежать дедлоков.

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

7) Решена прикладная задачи создания гарантоспособных программ на примере построения распределенной вычислительной системы и комплекса параллельных программ, реализуемых в ней на примере Дагестанского ОПФР. Использование механизма CF-сетей и созданных методов и программных средств анализа CF-сетей и параллельных программ позволило повысить надежность функционирования параллельных программ в компьютерных сетях в 1,5-2,5 раза.

ЗАКЛЮЧЕНИЕ

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

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

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

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

В диссертации получены следующие новые теоретические и прикладные результаты.

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

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

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

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

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

6) Разработаны базовые конструкции формализованного описания с помощью CF-сетей параллельных вычислений, реализуемых в SIMD- и MIMD-системах, конвейерных вычислениях и модели типовых элементов вычислительных структур, отличающиеся применением элементов, введенных в CF-сети в порядке расширения известных сетей Петри. Базовые конструкции параллельных и конвейерных вычислений позволяют ускорить процесс создания и анализа параллельных программ для распределенных и многопроцессорных систем.

7) Проведен анализ реализации параллельных взаимосвязанных процессов в распределенных вычислительных системах. Предложены модели на основе CF-сетей типовых протоколов, реализуемых в компьютерных сетях. Совокупность моделей элементов вычислительных структур и типовых протоколов позволяет в 2-3 раза сократить время анализа параллельных программ, реализуемых в распределенных вычислительных системах.

8) Разработаны и проанализированы модели на основе CF-сетей технических решений, предназначенных для повышения надежности реализации процессов обмена и, как следствие, увеличения гарантоспособности параллельных программ, реализуемых в системе. Предложенные аппаратно-программные средства апробированы и реализованы при построении многопроцессорной системы ЕС-2703 и математического обеспечения высокопроизводительного многопроцессорного комплекса «Фреон».

9) Решена прикладная задачи создания гарантоспособных программ на примере построения распределенной вычислительной системы и комплекса параллельных программ, реализуемых в ней на примере Дагестанского Отделения ПФР. Использование механизма CF-сетей и созданных методов и программных средств анализа CF-сетей и параллельных программ позволили повысить надежность функционирования распределенных программ в компьютерных сетях Дагестанского Отделения ПФР в 1,5-2,5 раза.

Основные научные результаты диссертации опубликованы [65-68, 70,71, 76,77,92-97,99,103-105,108,117,118,120-122,129,133-135,137,154,157,158,164, 167,168,173,174,178-180,182].

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

1. Гофф М.К. Сетевые распределенные вычисления: достижения и проблемы. М.: КУДИТС-ОБАР, 2005. - 320 с.

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

3. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978. - 278 с.

4. Авиженис А., Лари Ж.К. Гарантоспособные вычисления: от идей до реализации в проектах / Пер. с англ. // ТИИЭР, 1986. Т.74. - С.8-21.

5. Кельтон В., Лоу А. Имитационное моделирование. Классика CS. 3-е изд.- СПб.: Питер; Киев: Издательская группа BHV, 2004. 847 с.

6. Бенькович Е., Колесов Ю., Сениченков Ю. Практическое моделирование динамических систем. СПб.: BHV, 2002.

7. Маклаков С.В. BPwin и ERwin. CASE-средства разработки информационных систем. М.: ДИАЛОГ-МИФИ, 1999. - 256 с.

8. Канер С. и др. Тестирование программного обеспечения / Пер. с англ. -Киев: ДиаСофт, 2000. 544 с.

9. Буч Г., Рамбо Дж., Джекобсон А. Язык UML. Руководство пользователя / Пер. с англ. ДМК, 2000. - 432 с.

10. Smith Е. Principles of high-level net theory. Lectures on Petri nets // Lecture notes in Computer Science, 1998. Vol. 1491. - P. 174-210.

11. Genrich H.J., Lautenbach K. System modelling with high-level Petri nets // Theoretical Computer Science, 1981. Vol. 13. - P. 109-136.

12. Поляков A.K. Языки VHDL и VERILOG в проектировании цифровой аппаратуры. Солон-Пресс, 2003. - 320 с.

13. Зотов В.Ю. Проектирование цифровых устройств на основе ПЛИС фирмы XILINX в САПР WebPACK ISE. М.: Горячая Линия-Телеком, 2003. -624 с.

14. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.-264 с.

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

16. Никонов В.В., Подгурский Ю.Е. Сети Петри. Теория. Применение. // Зарубежная радиоэлектроника, 1984. № 4. -С. 28-59.

17. П.Никонов В.В., Подгурский Ю.С. Применение сетей Петри // Зарубежная радиоэлектроника, 1986. № 11. -С. 17-37.

18. Розенблюм Л.Я. Сети Петри // Техническая кибернетика, 1983. № 5. -С. 12-40.

19. Мурата Т. Сети Петри: свойства, анализ, приложения (обзор) // ТИИЭР, 1989.-№4.-С. 41-85.

20. Бестужева Н.Н., Руднев В.В. Временные сети Петри. Классификация и сравнительный анализ // Автоматика и телемеханика, 1990. № 10. - С. 3-21.

21. Bause Falko, Kritzingcr Pieter. Stochastic Petri Nets // An Introduction lo the Theory. Advanced Studies in Computer Science. Vieweg Verlagsgesellschaft, 1996.-P. 1-250.

22. Noe J.D. Lecture Notes in Computer Science, 1980. № 84.

23. Костин A.E., Илюшечкин B.M., Корнилов A.P. Представление параллельных процессов в распределенных микропроцессорных системах Е-сетями // Изв. вузов. Приборостроение. 1986. - № 3. - С. 28-33.

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

25. Андрианов А.Н., Бычков С.П., Хорошилов А.И. Программирование на языке Симула-67. М.: Наука. Гл. ред. физ.-мат. лит., 1985. - 288 с.

26. Морозов В.К., Долганов А.В. Основы теории информационных сетей. М.: Высшая школа, 1987. - 271 с.

27. Бурцев B.C. Новые методы организации вычислительных процессов для задач, обладающих высоким параллелизмом // Труды международного симпозиума ICSNET'. М., 2001. - С. 61-64.

28. Banneijee U. Dependence Analysis for Supercomputing. Kluver Academic Publishers, New York, 1988.

29. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1974.-216 с.

30. Анишев П.А. О детерминированности параллельных граф-схем / В кн. Вопросы теории и построения вычислительных систем. Вып. 73. Вычислительные системы. Новосибирск, 1978. - С. 40-52.

31. Бандман О.Л., Пискунов С.В., Сергеев С.Н. Задачи параллельного микропрограммирования / В кн. Вопросы теории и построения вычислительных систем. Вып. 73. Вычислительные системы. Новосибирск, 1978. - С. 3-24.

32. Методы параллельного микропрограммирования / Анишев П.А., Ачасова С.М., Бандман О.Л., Пискунов С.В., Сергеев С.И. Новосибирск: Наука, 1981.-181 с.

33. Plummer W.W. Asynchronous arbiters. IEEE Transactions of Computers, 1972. - V.C-21. - N 1. - p.37-42.

34. Corsmi P., Frosini G. A model for Asynchronous Control Networks. -Digital Processes, 1976. N 2. - p. 47-62.

35. Rumbaugh J. A Data Flow Multiprocessor. IEEE Transactions of Computers, 1977. - V.C-26. - N 2. - p.138-147.

36. Шейнин Ю.Е. Организация асинхронного вычислительного процесса над структурированными данными / В кн. Параллельное программирование и высокопроизводительные системы. Новосибирск: ВЦ СО АН СССР, 1980. -Ч. 2.-С. 107-116.

37. Шейнин Ю.Е., Татков Д.Е. Система визуально-графического параллельного программирования. Per № ГосФАП 50990000176,1999.

38. Баер Ж.Л. Методы исследования параллелизма // В кн. Системы параллельной обработки / Под ред. Ивенса Д. М.: Мир, 1985. - С. 80-105.

39. Гольдштейн Б. С. Сигнализация в сетях связи. Том 1. М.: Радио и связь, 2001.-439 с.

40. ITU Recommendation Z.100: Specification and Description Language. 1993.-204 p.

41. Harel D. Biting the silver bullet: Toward a brighter future for system development // Computer, 1992. Jan. P. 8-20.

42. AsmL // http://research.microsoft.com/fse/asml/

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

44. Гуров B.C., Мазин М.А., Нарвский А.С., Шалыто A.A. UML. SWITCH-технология. Eclipse // Информационно-управляющие системы, 2004. -№ 6, С.12-17.

45. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990. - 196 с.

46. Patil S.S. An Asynchronous Logic-Array. MAC Technical Memorandum 62. Project MAC, M. I. Т., May 1975. - 30 p.

47. Bernardinello L., De Cindio F. A survey of Basic Net Models and Modular Net Classes, LNCS vol.609, Springer Verlag, 1992.

48. Agerwala, T. and M. Flynn, Comments on capabilities, limitations and "correctness" of'Petri nets', in Proc. 1st Symp. On Сотр. Arch., 1973. Pp. 81-86.

49. Jensen K. Coloured Petri nets and the invariant method // Theoretical Computer Science.-l981.- Vol. 14. P. 317 - 336.

50. Jensen K. Coloured Petri Nets. Vol. 1.- EATCS Monographs on TCS, Springer Verlag.-1994.

51. Genrich H.J., Lautenbach K. System modeling with high-level Petri nets // Theoretical Computer Science, 1981. V. 13. - N 1. - P. 109 - 136.

52. Котов B.E. Алгебра регулярных сетей Петри // Кибернетика, 1980. -№5. С. 10-18.

53. Котов В.Е., Черкасова JI.A. Структурированные сети // Кибернетика, 1981. №4. - С.33-41.

54. Cherkasova L.A., Kotov V.E. Struktured nets // Proc. 6th MFCS. Lecture Notes in Computer Science, 1981. Vol.118. - P. 242-251.

55. Valk R. On the computational power of extended Petri nets. In: Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1978. - V. 64. - Pp. 526-535.

56. Valk R. Self-modifying nets, a natural extension of Petri nets. -In: Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1978. V.62. - Pp. 464-476.

57. Nutt G.J. Evalution Nets for Computer System Perfomance Analysis. -AFIPS FJCC, 1972. Vol. 41. - Pp. 279-286.

58. Костин A.E. Программный комплекс для сетевого имитационного моделирования дискретных систем с параллельными процессами // Управляющие системы и машины, 1987. № 4. - С. 98-102.

59. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах: Учеб. пособие для вузов. М.: Высш. Шк, 1987.- 248 с.

60. Baer J.-L. and С. Ellis, 'Model, design, and evaluation of a compiler for a parallel processing environment', IEEE TSE, SE-3, 6, Nov, 1977. Pp. 394-405.

61. Каляев A.B., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003. - 380 с.

62. Beveridge & Wiener. Multithreading Applications in Win32 / Addison-Wesley, 1997.-368 p.

63. Костин A.E., Савченко Л.В. Модифицированные Е-сети для исследования систем распределенной обработки информации // Автоматика и вычислительная техника. М., 1988. - № 6. - С. 27-35.

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

65. Левин И.И., Омаров О.М. Управляющие функциональные сети Петри для моделирования распределенных вычислительных сетей // Вестник Дагестанского научного центра РАН. Махачкала: Изд-во ДНЦ РАН, 2005. -Т.21.-С. 44-49.

66. Dufourd С, Finkel A., Schnoebel Ph. Reset nets between decidability and undecidability // Proc. 25th Int. Coll. Automata, Languages, and Programming (ICALP'98), Lecture Notes in Computer Science, 1998. Vol. 1443. - P. 103-115.

67. Омаров О.М. Формальная модель для описания и моделирования параллельных вычислительных процессов на основе CF сетей // Изв. вузов. Сев.-Кавк. регион. Техн. науки, 2006. Приложение к № 1. - С. 3-14.

68. Левин И.И., Омаров О.М. Анализ вычислительных процессов и структур на основе CF-сетей. Махачкала: Изд-во ДНЦ РАН, 2006. - 253 с.

69. Левин И.И., Пономарев И.М. Структурно-процедурная реализация задачи трассировки // Искусственный интеллект. Донецк: ДонДПШ, 2003. -№3. - С.121-129.

70. Альянах И.Н. Моделирование вычислительных систем. Л.: Машиностроение, 1988.-223 с.

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

72. Эндрюс Г.Р. Основы многопоточного параллельного и распределенного программирования. М.: Вильяме, 2003. - 505 с.

73. Омаров О.М. Использование сетей Петри для моделирования параллельных алгоритмов // Материалы научной международной школы

74. Высокопроизводительные вычислительные системы (ВПВС-2005)». -Таганрог: Изд-во ТРТУ, 2005. С. 108-112.

75. Омаров О.М. Моделирование параллельных алгоритмов с использованием сетей Петри // Искусственный интеллект. Донецк: Наука i осв1та, 2005. - Т 4. - С. 240-244.

76. Криницкий Н.А., Миронов Г.А., Фролов Г.Д. Программирование и алгоритмические языки / Под ред. А.А. Дородницына 2-е изд., испр. и доп. -М.: Наука. Гл. ред. физ.-мат. лит., 1979. - 512 с.

77. Хигман Б. Сравнительное изучение языков программирования / Пер. с англ. / Под ред. В.В. Мартынюка. М.: Мир, 1974. - 524 с.

78. Baer J.-L. and J. Jensen, 'Simulation of large parallel systems: Modeling of tasks', in Proc. 3rd Int. Symp. On Modeling and Perfomance Evaluation, Oct. 1977. -Pp. 53-73.

79. Gardner M. The Unexpected Hanging and Other Mathematical Diversions. University of Chicago Press, 1991.

80. Raymond Smullyan, Forever Undecided: A Puzzle Guide to Godel, 1987.

81. R. Kirkham. The Two Paradoxes of the Unexpected Hanging // Phil Stud, 1986.-№49.-Pp. 19-26.

82. Рузавин Г.И. Философские проблемы оснований математики. М.,1983.

83. Костин А.Е., Илюшечкин В.М., Корнилов А.Р. Представление параллельных процессов в распределенных микропроцессорных системах Е-сетями // Изв. вузов. Приборостроение, 1986. № 3. - С. 28-33.

84. Гордеев А.В. Расширение модели Е-сетей для представления процессов обработки прерываний // Сб. науч. тр. «Распределенные вычисления и системы на СБИС». Л.: ЛИАП, 1988. - С. 51-56.

85. Гордеев А.В., Молчанов А.Ю. Применение сетей Петри для анализа вычислительных процессов и проектирования вычислительных систем: Учеб. пособие. СПб: ГААП, 1993.- 80 с.

86. Peterson J. A note on colored Petri nets. Information Processing Letters, 1980. - Т.П. -№1. - Pp. 40-43.

87. Zerros C.R., Irani K.B. Colored Petri nets: their properties and applications. Systems Engineering Laboratory TR 107, University of Michigan, 1977.

88. Valk R. Petri nets as Token Objects: An Introduction to Elementary Object Nets // Proc. Int. Conf. on Application and Theory Petri nets. Lecture Notes in Computer Science, 1998. Vol.1420. - P. 1-25.

89. Левин И.И., Дордопуло А.И., Омаров О.М. Унифицированное представление алгоритма задачи для произвольного варианта распараллеливания // Искусственный интеллект. Донецк: Наука i ocBiTa, 2004. -ТЗ.-С. 133-139.

90. Дордопуло А.И., Омаров О.М. Представление операторов выбора в унифицированной параллельной форме для произвольного варианта распараллеливания // Материалы Международной научной конференции

91. Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004». Таганрог: Изд-во ТРТУ, 2004. - Т. 1. - С. 219-223.

92. Baer, J.-L., 'Modeling for parallel computations: A case study', in Proc. 1973 Sagamore Сотр. Conf. Parallel Processing, 1973. Pp. 13-22.

93. Омаров О.М. Моделирование с помощью CF-сетей взаимосвязных процессов // Вестник Дагестанского научного центра РАН. Махачкала: Изд-во ДНЦ РАН, 2005. - Т.22. - С. 25 - 30.

94. Олифер Н.А., Олифер В.Г. Средства анализа и оптимизации локальных сетей, www.sitforum.ru

95. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. - 512 с.

96. Веников В.А., Веников Г.В. Теория подобия и моделирования. М.: Высшая школа, 1984. - 439 с.

97. Омаров О.М. Модели и методы анализа распределенных информационно-телекоммуникационных сетей // Тезисы докладов Всероссийской научно-технической конференции «Современные информационные технологии в управлении». Махачкала. ИПЦ ДГТУ. 2003. -С. 35-36.

98. Омаров О.М. Имитационная модель для проектирования и анализа инфокоммуникационных сетей // Труды Всероссийской научно-методической конференции «Телематика-2004». СПб.: СПбГУ ИТМО, 2004. - С.41-42. http://tm.ifmo.ru/tm2004/index.php

99. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высш. школа, 1983.-272 с.

100. Аврамчук Е.Ф., Вавилов А.А., Емельянов С.В. Технология системного моделирования / Под ред. С.В. Емельянова. М.: Машиностроение, Берлин: Техник, 1988. - 520 с.

101. Соколов В.А., Солопов А.Г. Разработка инструментальных средств моделирования систем одного класса сетей Петри высокого уровня // Вестник компьютерных и информационных технологий, 2005. № 6. - С.48-53.

102. Антонюк Д.А., Омаров О.М. Программный комплекс для моделирования вычислительных систем сетями Петри // Вестник Дагестанского

103. Государственного Технического Университета. Вып.2 (технические науки). -Махачкала, 1998. - С. 48-52.

104. Омаров О.М. Интегрированная среда для анализа и моделирования информационных сетей на базе функционально управляющих сетей Петри // Свидетельство об официальной регистрации программы для ЭВМ № 2005612206/ РОСПАТЕНТ. М., 29.08.2005.

105. Пауэлл К. Visio 2002. М.: Лори, 2005. - 512 с.

106. Омаров О.М., Османов Р.Ш. Система имитационного моделирования и анализа сетей // Свидетельство об официальной регистрации программы для ЭВМ № 2005611605/ РОСПАТЕНТ. М., 29.08.2005.

107. Богуславский Л.Б., Ляхов А.И. Методы оценки производительности многопроцессорных систем. М.: Наука, 1992. - 213 с.

108. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. М.: Энергоатомиздат, 1984. - 168 с.

109. Авен О.И., Турин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

110. Таненбаум Э. Компьютерные сети. 4-е изд. СПб.: Питер, 2003.517с.

111. Flynn M.J. Some computer organizations and their effectivenss. IEEE Trans., 1972. V. 6-21. - Pp. 948-960.

112. Dijkstra, Е. W. 1965. Solution of a problem in concurrent programming control. Comm. ACM 8,9 (September). P.569.

113. Бурцев B.C. Принципы построения многопроцессорных вычислительных комплексов «Эльбрус». М., 1977. - (Препр. /ИТМ и ВТ; №21).

114. Peterson, G. L. 1981. Myths about the mutual exclusion problem. Information Processing Letters 12,3 (June). Pp. 115-116

115. A.c. 1182533.Устройство для сопряжения источника и приемника информации./ Омаров О.М. БИ № 36,1985. - 4с.

116. А.с. 1413637. Устройство для управления обменом информацией / Бабенко Л.К., Макаревич О.Б., Омаров О.М. и др. БИ № 28, 1988. - 6 с.

117. А.с. 1536383. Устройство для обслуживания запросов / Омаров О.М. и др. БИ №2, 1990.-7с.

118. А.с. 1783525. Устройство для управления обменом информацией/ Омаров О.М. БИ № 47,1992. - 11 с.

119. А.с. 1070552. Многоканальное устройство приоритета. / Омаров О.М., БИ № 4 ,1984. 4с.

120. А.с.1149258. Многоканальное устройство для обслуживания запросов. / Омаров О.М., БИ № 13, 1985. 5с.

121. А.с. 1251081. Многоканальное устройство приоритета. / Омаров О.М., БИ №30, 1986.-4с.

122. А.с. 1259261. Устройство для централизованного управления вычислительной системой. / Омаров О.М., БИ № 35, 1986. 9с.

123. А.с. 1674146. Устройство для централизованного управления вычислительной системой. / Бабенко JI.K., Макаревич О.Б., Омаров О.М., и др., БИ № 32,1991.-6с.

124. А.с.1117637. Микропрограммное устройство управления. / Айдемиров И.А., Омаров О.М. БИ № 37,1984. - Зс.

125. Айдемиров И.А., Омаров О.М. Синтез микропрограммного устройства управления с комбинированной адресацией // Управляющие системы и машины, 1986. № 3. - С. 35-40.

126. А.с. 1160423. Устройство для сопряжения многопроцессорной вычислительной системы. / Омаров О.М.- БИ № 21, 1985. 9с.

127. Омаров О.М. Периферийный параллельный интерфейс матричного процессора вычислительной системы // В кн.: Вычислительные системы и алгоритмы. Ростов н/Д: РГУ, 1985. - С. 125-129.

128. А.с.1241245. Устройство для сопряжения многопроцессорной вычислительной системы с внешними устройствами / Омаров О.М. и др.- БИ №24 ,1986.-9с.

129. Николаев И.А., Омаров О.М., Петрыкин Ю.С., Тищенко А.Г. Разработка системы автоматизации научных исследований на базе многопроцессорного вычислительного комплекса // Препринт ИАЭ им. И.В.Курчатова 4196/15. - М.: ИАЭ им. И.В.Курчатова, 1985. - 15 с.

130. Бабенко JI.K., Макаревич О.Б., Николаев И.А., Омаров О.М. Высокопроизводительный вычислительный комплекс для автоматизациинаучных исследований // X Всесоюзное совещание по проблемам управления. Алма-Ата, 1986. Кн. II. М., 1986. - С.421-422.

131. Кондаков О.А., Матвеева JI.H., Омаров О.М. и др. К вопросу построения процессора связи моделирующего комплекса // Управляющие системы и машины, 1980. № 5. - С. 25-28.

132. Омаров О.М. Анализ организации ввода-вывода в высокопроизводительных вычислительных системах. Махачкала, 1984. - 16 с. - Рукопись представлена Дагестанским политехническим институтом. Деп. В ВИНИТИ 1984, №7596. - С. 84.

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

134. Кузьминский М. Эволюция подсистемы ввода-вывода мэйнфреймов IBM // Открытые системы. М.: «Открытые системы», 1999. - № 1.

135. Омаров О.М. О повышении производительности многопроцессорных вычислительных систем при построении управляющих вычислительных комплексов // Многопроцессорные вычислительные структуры. Таганрог: Изд-во ТРТИ, 1984. - Вып. 6(XY). - С. 17-18.

136. Bic, L., and А.С. Scaw. 1988. The Logical Design of Operating Systems, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall.

137. Жиро К. Доказательство корректности протокола в случае ошибок в сети передачи данных / Система параллельной обработки: пер.с англ. / Под ред. Д. Ивенса. М.: Мир, 1985. - С.126-145.

138. Бандман О.Л. Проверка корректности сетевых протоколов с помощью сетей Петри // АВТ, 1986. № 6. - С.82-91.

139. Анисимов Н.А. Формальная модель для разработки и описания протоколов на основе теории сетей Петри // АВТ, 1988. № 6. - С.3-10.

140. Омаров О.М. Применение иерархических сетей Петри для формализованного описания и моделирования интерфейсов // Проектирование электронной аппаратуры с применением САПР. Межвузовский научно-тематический сборник. Махачкала: РИО ДГУ, 1988. - С.72 - 74.

141. Крылов В.В., Самохвалова С.С. Теория телетрафика и ее приложения. СПб.: БХВ-Петербург, 2005. - 288 с.

142. Шварц М. Сети связи: протоколы, моделирование и анализ. В 2-х ч. / Пер. с англ. М.: Наука, 1992.

143. Омаров О.М. CF-сети для моделирования распределенных информационно-вычислительных систем // Телекоммуникации, 2006. № 7. - С. 21-25.

144. Иванов А.А. Корпоративные сети как составляющая информационной инфраструктуры России // В кн. Связь России в XXI веке / Под. ред. проф. Л.Е. Варакина. М.: МАК, 1999. -С. 41-65.

145. Салов В., Плотникова И., Горохов С., Брусенцев Г. Сеть областного масштаба. PC WEEK/RE N8, 11 марта 2003.

146. Омаров О.М., Гаджиев М.А., Ахмедов Р.К., Тагиров А.Т. Корпоративная сеть передачи данных Отделения Пенсионного фонда России по Республике Дагестан // Информационные технологии, 2005. № 3. - С. 64-67.

147. Иртегов Д.В. Введение в сетевые технологии. Спб.: БХВ-Петербург, 2004. - 560 с.

148. Танненбаум Э., Ван Стеен М. Распределенные системы, принципы и парадигмы. Спб.: Питер, 2003. - 507 с.

149. Кренке Д. Теория и практика построения баз данных. Спб.: Питер,2003.

150. Омаров О.М., Абдулгамидов А.А. Распределенные базы данных на основе гибридных топологий репликационных приложений // Информационные технологии моделирования и управления. Воронеж: Научная книга, 2005. - № 6(24). - С.877-884.

151. Омаров О.М., Абдулгамидов А.А. Репликационные приложения распределенных баз данных в информационных системах с низкоскоростными каналами связи // Изв. вузов. Сев.-Кавк. регион. Естеств. науки. Приложение. 2006.-№3.-С. 22-31.

152. Богуславский Л.Б., Ляхов А.И. Оценка производительности распределенных информационно-вычислительных систем архитектуры «КЛИЕНТ-СЕРВЕР» // Автоматика и телемеханика, 1995. №9. - С. 160-175.

153. Омаров О.М. Моделирование и анализ функционирования компьютерной сети Отделения пенсионного фонда России по республике Дагестан // Изв. вузов. Сев.-Кавк. регион. Техн. науки, 2006. Приложение к № 2.-С. 5-17.