Методы и средства моделирования вычислительных процессов в многопроцессорных и распределенных системах на основе CF-сетей

Ведущие специалисты в области вычислительной техники указывают в качестве конечной цели развития информационных технологий создание системы «вездесущих» вычислений, которая должна обеспечить доступ к информации и к средствам ее обработки практически в любом месте Земного шара. Для создания подобной системы необходимо решение целого комплекса взаимосвязанных научно-технических проблем и, прежде всего, в области программного обеспечения распределенных вычислительных ресурсов [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.52 005, руководитель НИР — Б. В. Захаркин;

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

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

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

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

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

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

Разработка и исследование интеллектуальных аппаратно-программных средств многопроцессорных вычислительных и управляющих систем с динамически программируемой архитектурой", № ГР 0120.510 629, руководитель НИР — член-корреспондент РАН, д.т.н., профессор И. А. Каляев;

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

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