Введение к работе
Актуальность работы. Одними из самых сложных и актуальных проблем технологии программирования являются проблемы обоснования надежности программного обеспечения (ПО), приобретающие особое значение в связи с массовым внедрением в практику параллельных и распределенных вычислительных систем (ПРВС). Поэтому при проектировании параллельного и распределенного ПО (ПРПО) к традиционным задачам разработки ПО добавляется ряд более сложных задач, связанных с необходимостью правильной организации параллельных и распределенных вычислений (ПРВ).
Чаще всего актуальные проблемы обоснования надежности ПРПО сводятся к проблемам обоснования его корректности. Решение последних основывается на использовании формальных моделей параллелизма (ФМП), позволяющих анализировать поведенческие свойства ПРПО.
В настоящее время предложено и исследовано большое количество ФМП, ориентированных на решение различных задач, связанных с ПРВ и отличающихся, главным образом, степенью детализации моделируемых процессов и явлений. Наиболее развитыми ФМП являются сети Петри (СП) и их расширения. Важные результаты по этим ФМП обобщены в работах Питерсона Дж., Кото-ваВ.Е. и ряда других исследователей. Однако анализ показывает, что среди предложенных ФМП нет таких, которые бы в комплексе предоставляли следующие возможности:
учет таких особенностей функционирования ПРВС, как наличие временных характеристик, конфликтов, разделяемых ресурсов и одновременного развития событий;
наличие описательных средств, максимально удобных для практического применения при проектировании ПРПО;
наличие в достаточной степени развитых методов формального анализа ПРПО, позволяющих исследовать его корректность.
В качестве наиболее приемлемого в этом смысле ФМП в [8, 11] предлагается и развивается аппарат PS-сетей.
Актуальность данной темы определяется необходимостью создания новых и совершенствования предложенных ранее методов анализа ПРПО, описываемых на основе PS-сетей.
Исследования и разработки по теме проводились в соответствии с утвержденными планами НИР института «Кибернетический центр» ТПУ, и были включены в 1995-1998 гг. в Государственную НТП «Трансферные технологии, комплексы и оборудование» (подраздел «Программные системы»).
Фундаментальные исследования по теме «Разработка моделей и методов проектирования программного обеспечешія мультипроцессорных вычислительных систем» выполнялись в 1992-1994 гг. по Гранту Миннауки России.
Прикладные исследования проводились в рамках ряда хоздоговорных и госбюджетных НИР, в том числе по НИР, включенной в Межвузовскую НТП "Геоинформационные системы" Минобразования России (Проект 04.0003.99).
Цель работы и задачи исследования. Целью диссертационной работы является создание математического и программного обеспечения для анализа
корректности ПРПО на основе аппарата PS-сетей. Для достижения этой цели работе решаются следующие задачи:
-
Развитие теории PS-сетей в направлении совершенствования описатель ных и аналитических возможностей данного аппарата, в том числе введени формальных понятий и определений, характеризующих поведенческие свойст ва PS-сетей при исследовании корректности описываемого на их основе ПРПО
-
Разработка методов и алгоритмов, позволяющих посредством выявлени поведенческих свойств PS-сетей осуществлять анализ корректности описывае мого на их основе ПРПО.
-
Создание программных средств, реализующих предложенные методы і алгоритмы.
-
Исследование эффективности предложенных методов, алгоритмов і созданных программных средств, для чего следует решить ряд задач анализ корректности проектируемого ПРПО.
Методы исследований. В работе использованы методы теории множєсте теории линейной алгебры, теории алгоритмов, теории графов и комбинаторию и теории моделирования.
Научную новизну полученных в работе результатов определяют:
-
Формальные определения поведенческих свойств PS-сетей и методы об наружения этих свойств, предназначенные для обоснования корректности про ектируемого ПРПО;
-
Матричное представление аппарата PS-сетей, а также теоретике множественное и матричное представления базового подкласса аппарата PS сетей — BPS-сетей, предназначенных для формального анализа поведенчески: свойств описываемого на их основе ПРПО;
-
Алгоритмы эквивалентных преобразований над PS-сетями, позволяю щие осуществлять приведение PS-сети к BPS-сети с сохранением ее поведеігче ских свойств;
-
Теория асинхронной интерпретации BPS-сетей, опирающаяся на ря, теорем, доказанных автором, и позволяющая на основе решения уравнения СА перехода расширить возможности анализа BPS-сети в части применения метод; инвариантов;
-
Иерархический подход к спецификации ПРПО и к обоснованию ег< корректности, основанный на понятии метадуги и позволяющий в значитель ной степени компактифицировать описание ПРПО и осуществлять в отдельно ста анализ каждого уровня иерархии;
-
Способ масштабирования модельного времени, позволяющий осуществ лять интеграцию разверток метадуг при использовании иерархического подхо да к спецификации ПРПО и обоснованию его корректности.
Практическая ценность и реализация результатов работы. Практичс ски значимыми являются созданные модели, методы, алгоритмы и программ ные средства для анализа проектируемого ПРПО на предмет его корректности Программные средства функционируют на ПЭВМ типа ГОМ PC в операцион ной среде Windows 95/NT. Объем разработанного на языке C++ ПО составляс более 6500 строк программного кода.
Предложенные модели, методы и алгоритмы, а также разработанные программные средства анализа ПРПО были внедрены в Государствеїшом научно-исследовательском институте информационных технологий и телекоммуникаций «Информика» г. Москва при проектировании и исследовании корректности способов организации распределенной обработки информации в проекте «ГИС-сервер социально-экономической сферы субъекта федерации», разработанного для использования в сети Internet. Эти же методы, алгоритмы и программные средства внедрены при исследовании верхних границ времени выполнения операций над данными пользователями «Регионального банка геологической информации по геологии нефти и газа и недропользованию», разработанного в Западно-Сибирском геологическом научно-аналитическом центре г. Тюмень. Созданные программные средства анализа ПРПО также были внедрены в учебный процесс в Томском политехническом университете. Результаты внедрений подтверждаются соответствующими актами о внедрении.
Основные положення, выносимые на защиту:
-
Предложенные методы и алгоритмы анализа ПРПО позволяют исследовать его корректность еще на этапе проектирования.
-
Теория асинхронной интерпретации BPS-сети существенно расширяет возможности анализа поведенческих свойств описываемого на их основе ПРПО.
-
Иерархический подход к спецификации ПРПО и обоснованию его корректности на основе аппарата PS-сетей позволяет более наглядно, чем другие существующие ФМП, описывать ПРПО, при этом можно осуществлять анализ его поведенческих свойств как для каждого уровня иерархии в отдельности, так и для всей модели ПРПО в целом.
-
Разработанные теоретические положения, методы, алгоритмы и программные средства позволяют проектировать надежное и эффективное ПРПО.
Апробация работы. Основные результаты работы докладывались и обсуждались на Международной конференции «Фундаментальные и прикладные проблемы охраны окружающей среды» (г. Томск, 1995 г.), на Международной конференции «Всесибирские чтения по математике и механике» (г. Томск, 1997 г.), на I Международном симпозиуме по науке и технологии KoRus'97 (г. Ульсан, Южная Корея, 1997 г.), на П Международном симпозиуме по науке и технологии KoRus'98 (г. Томск, 1998 г.), на VI Международном семинаре «Распределенная обработка информации» РОИ'98 (г. Новосибирск, 1998 г.), на III сибирском конгрессе по прикладной и индустриальной математике ИНПРИМ'98 (г. Новосибирск, 1998 г.), на IV Международном симпозиуме по науке и технологии KoRus'2000 (г. Ульсан, Южная Корея, 2000 г.).
Публикации. По результатам исследоваїшй опубликовано 14 работ, в том числе 9 статей.
Личный вклад:
-
Постановки ряда рассмотренных в диссертации задач выполнены совместно с Н.Г. Марковым и Е.А. Мирошниченко, при этом математические формулировки задач исследований осуществлены автором.
-
Разработка и формулировка определений PS-сетей, их маркировки и
правил функционирования в матричном виде, разработка методов, способов v алгоритмов анализа ПРПО на основе PS-сетей, а также программные средства, реализующие предложенные методы и алгоритмы, осуществлены автором. Основные научные результаты, полученные с применением предложенных методов, моделей и подходов, также принадлежат автору.
-
Постановка задачи исследования корректности способов организации распределенной обработки информации в ГИС-сервере социально-экономической сферы субъекта федерации осуществлена совместно с Н.Г. Марковым и П.М. Острасть, разработка моделей ГИС-сервера проведена совместно с Е.А. Мирошниченко. Результаты исследования получены автором.
-
Постановка задачи определения верхних границ времени выполнения операций над данными пользователями «Регионального банка геологической информации по геологии нефти и газа и недропользованию» осуществлена В.В. Уваровым. Разработка моделей, описывающих функционирование регионального банка, а также их исследования проведены автором.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 101 наименования и приложений. Объем основного текста диссертации составляет 123 страницы машинописного текста, иллюстрированного 35 рисунками и 9 таблицами.
