Программные средства моделирования динамически изменяющейся структуры параллельных систем тема диссертации и автореферата по ВАК РФ 01.01.10, кандидат физико-математических наук Борейша, Юрий Евгеньевич

• Борейша, Юрий Евгеньевич
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Борейша, Юрий Евгеньевич

ВВЕДЕНИЕ

ГЛАВА I. МОДЕЛИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ СИСТЕМ ПОСРЕДСТВОМ АСИНХРОННЫХ ВЗАИМОДЕЙСТВУЩИХ ПРОЦЕССОВ

1.1. Параллельное программирование и задачи имитационного моделирования.

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

1.3. Средства взаимодействия параллельных процессов.

ГЛАВА 2. ДИНАМИЧЕСКИЕ ПАРАЛЛЕЛЬНЫЕ ВЗАИМОДЕЙСТВУЮЩИЕ ПРОЦЕССЫ

2.1. Динамические параллельные взаимодействующие процессы - модель параллельных вычислений • •

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

2.3. ДПВП модель-вычислитель

ГЛАВА 3. СИСТЕМА АВТОМАТИЗИРОВАННОГО МОДЕЛИРОВАНИЯ

ПАРАЛЛЕЛЬНЫХ СИСТЕМ С ДИНАМИЧЕСКИ ИЗМЕНЯЩЕЙСЯ СТРУКТУРОЙ

3.1. Моделирование в системе СМВ. $

3.2. Некоторые вопросы верификации ДПВП моделей.

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

ЗАКЛКЯЕНИЕ.

Введение диссертации (часть автореферата) на тему «Программные средства моделирования динамически изменяющейся структуры параллельных систем»

Создание сложных технических систем, включая вычислительные комплексы и программное обеспечение, становится в настоящее время практически невозможным без использования аппарата малинного моделирования / 1,56,57,99,105,106 /. Особую важность ввиду этого приобретает проблема построения адекватных имитационных моделей. Один из наиболее перспективных путей ее решения предполагает использование методов и результатов теории параллельных вычислений /1,14,19,26,32,44,56,57,85,92,99,105,106 /. Поэтому одной из центральных задач параллельного программирования является разработка адекватных и эффективных средств описания параллелизма в программах, моделирующих сложные дискретные системы и происходящие в них процессы /3,15,19,21,35-39,61,64, 77,82,103,106 /.

Современный период развития кибернетики характеризуется интенсивной разработкой систем параллельной обработки информации / 3 /. Значительно возрастает роль взаимодействий между подсистемами таких систем. Это обуславливает новые качественные отличия от процесса независимой последовательной стационарной обработки с неизменяемой управляющей структурой / 19 /. Анализ возникающих при этом задач приводит к необходимости исследования динамически изменяющейся структуры сложных систем с учетом параллельного функционирования и взаимодействия составляющих их элементов / 44,102,106 /.

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

Большинство современных систем программного обеспечения (в особенности операционных систем) с точки зрения логического анализа представляют собой совокупности параллельно функционирующих взаимодействующих асинхронных процессов /1,26,48,55,57,85, 99,106 /. Как правило, процессы могут динамически порождаться и уничтожаться. Информационные и управляющие связи между ниш могут динамически перестраиваться. Ьсе это определяет количественные и качественные изменения структуры и состава исследуемых систем.

Следует отметить, что такое представление служит адекватной моделью для многих сложных параллельных систем (таких, например, как вычислительные сети, мультипрограммные системы, системы управления базами данных и т.д.), которые можно в соответствии с этим критерием выделить в подкласс сложных систем - параллельные системы с динамически изменяющейся структурой, сокращенно-ДИС / 44,102,106 /.

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

Данному определению удовлетворяют и так называемые параллельные асинхронные рекурсивно управляемые системы (ПАРУС). Для ПАРУС характерно то, что динамические изменения их структуры носят рекурсивный характер. Это свойство присуще системам, предназначенным для рекурсивно-параллельной обработки данных. Например, в задачах умножения матриц большой размерности структура управляющего пространства задается посредством рекурсивно расширяемых и сворачиваемых деревьев / 7,19/.

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

Рассмотрим некоторые ситуации ,в которых возникает необходимость исследования проблем,характерных для ДИС.

С точки зрения операционных систем концепция процесса представляет собой естественное обобщение работы реентерабельных программ в среде с виртуальной памятью /55,57/.За счет рассмотрения только логики процессов и игнорирования числа доступных физических процессоров можно обеспечить процессорно-независимые решения для целого ряда системных проблем. Эти решения будут гарантировать, что рассматриваемая система процессов составлена и функционирует правильно вне зависимости от того,разделяют процессы физические процессоры или нет.Концепция процесса имеет также много других применений в операционных системах. Она допуо-тила выделение и определение многих базовых задач ОС,упростила изучение их организации и динамики,привела к развитию полезных методологий проектирования.

Аналогичные проблемы возникают и при анализе такого широко используемого метода исследования сложных систем как системный подход/14,42,45/.Его суть состоит в расчленении системы на отдельные обозримые части с учетом их взаимодействия и изучении каждой из частей в отдельности. Модель всего процесса функционирования при этом отражает общую структуру системы и взаимосвязь выделенных элементов. Это приводит к тому, что сложность реальных систем в значительной мере определяется взаимодействием их составных частей, которое и является предметом исследования в большинстве задач имитационного моделирования / 14,16,18,26, 44,56,85,99,105 /.

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

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

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

Эффективные алгоритмы, определяющие оптимальный план распределения процессов, разработаны только для частных случаев. Последние результаты показывают, что оптимальные алгоритмы распределения процессов между свободными процессорами весьма сложны по своей природе / 3 /. Поэтому при разработке программного обеспечения имеют важное значение эвристические алгоритмы, методы и системы имитационного моделирования, которые часто позволяют получать распределения, близкие к оптимальным / 3,32,56,57 /.

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

Для обеспечения решения перечисленных и т.п. задач служит предлагаемая в диссертационной работе система СМВ (Система Моделирования Взаимодействий).

Построение адекватных имитационных моделей на базе теории параллельных вычислений начинает в настоящее время интенсивно развиваться и выглядит достаточно перспективным / 26,27,42,45, 86,92,99,102,105,106 /. Исследования в данной области позволяют предоставить в распоряжение пользователя, строящего модели систем, концептуальную основу для ясного и четкого мышления. Реальной становится возможность использования аппарата параллельного программирования в задачах имитационного моделирования. Это способствует повышению степени надежности модельных программ, осуществлению их разработки с учетом основных требований модульного и структурного программирования, использованию методов верификации и отладки больших систем, результатов, полученных в теории параллельных вычислений.

Следует отметить, что проблемы исследования и моделирования ДИС стояли перед разработчиками многих языков и систем моделирования/1,14,15,16,18,21,26,27,40,44,85,99,102,106 /. Некоторые из поставленных задач в каждом конкретном случае получили свое конкретное решение. Однако, более целесообразным следует считать формулировку и решение указанных проблем на единой концептуальной основе / 3,21 /. В качестве такой основы может служить развиваемый в данной работе формализм параллельных взаимодействующих процессов / 3,15,21,35,37-40,48,55,61,77,82,103,106 /.

Для исследования и изучения динамических и композиционных свойств ДИС наилучшим образом подходят динамические структурно-алгоритмические модели / 42,45 /. Они представляют собой алгоритмы, схемы алгоритмов, программы, структуры данных, отображающие функционирование исследуемых систем и их измененйя во времени. При этом используются средства имитационного моделирования. Широкое распространение структурно-алгоритмических моделей при проектировании систем обусловлено следующим. Эти модели представляют любой уровень детализации системы; для них применимы теоретические результаты и практический опыт, накопленный при экспериментировании с физическими моделями.

В данном классе моделей для решения поставленных проблем наиболее подходят модели взаимодействующих последовательных процессов Дейкстры-Хоара (&SP ) / 29,82,102 /, распределенных процессов Хансена (ЪР ) / /» динамических моделей Биледена (IDYMOL* ) / Юб /, параллельных задач языкаА1>А /15,96 /, мультимодульные модели Ю.В.Капитоновой и А.А.Летичевского /21/. В качестве программных средств в этих моделях используются одноименные языки.

Однако, кавдая из них в отдельности (с точки зрения исследования ДИС) обладает целым рядом недостатков. Так, например, в CSJ? и не затрагиваются вопросы динамического изменения структуры исследуемых систем; B^TiTHOU недостаточно внимания уделено проблеме структурированного взаимодействия процессов, вопросам модульного программирования на основе предлагаемых средств. Наиболее полно и сбалансированно эти задачи решены в мультимодульных программах и в языке A3) А . Тем не менее, механизм "рандеву", используемый для взаимодействия параллельных процессов (задач) языка АДХА , несколько затемняет суть взаимодействия и может быть успешно заменен "циклом обмена информацией". Это средство, в частности, оказывается и более удобным для описания ДИС.

В заключение отметим, что существующие формальные модели параллельных вычислений, такие как сети Петри / 3,88 /, параллельные схемы программ / 33 / и т.п., существенно используют статическую структуру исследуемых систем и поэтому не могут быть удобным аппаратом для исследования ДИС. Б связи с этим затруднена и верификация подобных систем.

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

Предлагаемые в настоящей работе программные средства используют, объединяют и развивают в рамках единой концептуальной основы наиболее удачные средства языков взаимодействующих последовательных процессов ( С S Р ), распределенных процессов (3>£ ), языка динамического моделирования (3>YJttOL ) и параллельных задач языка А.Ъ& • На их основе разработана система автоматизированного моделирования СМВ, реализующая на достаточно представительном уровне новую мощную модель параллельных вычислений -динамические параллельные взаимодействующие процессы (ДПВП модель). Основное внимание при этом концентрируется на корректном решении комплекса проблем, связанных с взаимодействием асинхронных параллельных процессов и динамическим применением структуры исследуемых систем. Рассматривается только асинхронный параллелизм с децентрализованным и частично централизованным управлением над распределенной и общей памятью, который хорошо соответствует естественному параллелизму задач и асинхронной организации сложных технических систем. Исследованы свойства и оценены возможности ДШП моделей и системы СМВ.

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

- структурная организация программ посредством иерархической и упорядоченной отношением "использует" совокупности модулей;

- аппарат типов процессов;

- аппарат динамического порождения произвольного числа процессов указанного типа и динамического завершения процессов;

- аппарат, обеспечивающий рекурсию по типам;

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

- аппарат выборочного ожидания сообщений и недетермированно-го выбора одного из возможных путей в программе ;

- аппарат, обеспечивающий динамическую перестройку связей в системе;

- аппарат временных задержек и планирования;

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

Структурно ДПВП модели представимы в виде ориентированных циклических графов (допускаются петли). Ориентированные дуги соответствуют отношению использования между описаниями типов процессов. В каждой вершине параллельно и асинхронно функционирует некоторое (счетное) множество процессов, описание типа которых содержится в вершине. Кавдый процесс однозначно характеризуется своим именем и специ<|икацией типа. Ьсе процессы вершины разделяют реентерабельное тело типа и имеют каждый свою локальную область данных аналогичную по структуре области данных своего типа (может быть предусмотрен доступ к общей разделяемой памяти). Отношение инициализации процессов в системе строится с учетом отношения "использует" и имеет вид дерева (рекурсивно расширяемого и сворачиваемого). За счет того, что значения переменных типа имя процесса можно передавать в качестве параметров (при инициализации и в сообщениях), граф взаимодействия процессов представляет собой достаточно гибкую и мощную динамическую сеть.

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

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

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

Работа выполнена в рамках темы ГКНТ "Разработать и сдать в Государственный фонд пакет прикладных программ для автоматизированного моделирования многопроцессорных ЭВМ" (постановление ГКНТ 180 от 03.05.79, № гос. регистрации 79066294, задание 0.80.15.38) и темы ГКНТ "Разработать теорию и технологию создания высокопроизводительных систем обработки информации, включающих диалог с ЭВМ на естественном языке", выполняемой в XI пятилетке лабораторией высокопроизводительных вычислительных систем при кафедре математической информатики факультета кибернетики Киевского госуниверситета и включенной в Общесоюзную комплексную целевую программу 0.Ц.027 "САПР и АСШГ (постановление ГКНТ № 474/250/132 от 12.12.80, № госрегистрации 8I00500I, задание 03.022 "ВЦ КП САПР").

Система автоматизированного моделирования СМВ реализована в ОС ЕС на машинах серии ^С ЭВМ, сдана в Украинский республиканский фонд алгоритмов и программ, включена в Государственный фэнд алгоритмов и программ и зарегистрирована под № П006406 от 05.05. 1983 г. Первичный экономический эффект от внедрения системы составляет 57,06 тыс. рублей.

Перейдем к краткому изложению работы по главам. Диссертация состоит из 7 разделов: введение, трех глав (9 параграфов), заключения, списка литературы и приложения.

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

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

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

GMB. Рассмотрены наиболее перспективные пути разработки подобных средств.

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

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

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

В параграфе 2.1 формализуется понятие ДПВП моделей, исследуются их свойства и особенности.

Параграф 2.2 посвящен системе программирования ДПВП и входному языку СМВ. Приведено описание грамматики языка, которая принадлежит к классу LA(i) . При построении соответствующего компилятора и интерпретатора это обеспечивает корректную работу алгоритмов рекурсивного спуска без возвратов.

В параграфе 2.3 описана ДПВП модель - вычислитель, посредством которой задается операционная семантика ДПВП моделей и реализация системы СМВ.

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

В параграфе 3.1 описываются основные особенности функционирования СМВ и моделирования посредством данной системы. Приведены основные технические характеристики СМВ.

В параграфе 3.2 исследуются вопросы верификации ДПВП моделей и использования для этих целей существующих полных и непротиворечивых систем доказательства правильности параллельных программ (на основе модифицированной методики Хоара для распределенных систем и Овицки-Гриса для параллельных систем с общей памятью (ресурсами)). Приведен алгоритм автоматического поиска циклических взаимоблокировок в ДПВП моделях.

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

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

В приложении содержатся листинги результатов моделирования в системе СМВ и акты о ее апробации и внедрении.

По теме диссертации опубликовано 9 печатных работ / 4-12 /. Основные результаты докладывались на республиканской школе-семинаре "Структурное программирование в системах алгоритмических алгебр" (Киев, 1981), на Всесоюзной конференции "Программное обеспечение вычислительных сетей и систем реального времени" (Киев, 1981), на Всесоюзной конференции "Синтез, тестирование, верификация и отладка программ" (Рига, 1981), на Всесоюзной школе молодых ученых "Методы создания программного обеспечения и технической реализации высокопроизводительных ЭВМ" (Киев, 1982), на УП объединенном семинаре "Разработка теоретического аппарата основных инвариантов и обеспечений автоматизированных интегрированных систем программирования жизненных циклов больших технических систем" (Николаев, 1982), на Всесоюзной конференции "Методология системного проектирования и построения современных САПР на ее основе" (Киев, 1983), на научных семинарах в МГУ, МИРЭА, КГУ, ИК АН УССР, ВЦ СО АН СССР.

Заключение диссертации по теме «Математическое обеспечение вычислительных машин и систем», Борейша, Юрий Евгеньевич

ЗАКЛЮЧЕНИЕ

Основными результатами предлагаемой диссертационной работы являются следующие:

- На основе развиваемого формализма параллельных асинхронных взаимодействующих процессов разработаны программные средства адекватного описания и моделирования динамически изменяющейся структуры параллельных систем. При этом использованы, объединены и развиты в рамках единой концептуальной основы наиболее удачные средства языков взаимодействующих последовательных процессов С.&Р, распределенных процессов 3>Р , языка динамического моделирования 3>YM.OL и параллельных задач языка АЪА .

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

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

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

- СМВ реализует на достаточно представительном уровне одну из наиболее мощных и базовых моделей параллельных вычислений.

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

- Система автоматизированного моделирования СМВ сдана в Укр-РФАП. Первичный годовой эффект от ее внедрения составляет 57,06 тыс. рублей.

Список литературы диссертационного исследования кандидат физико-математических наук Борейша, Юрий Евгеньевич, 1984 год

1. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных. - М.: Мир, 1980. - 394 с.

2. Агафонов В.Н. Типы и абстракция данных в языках программирования. В сб.: Данные в языках программирования, М.: Мир, 1982, с. 265-327.

3. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.: Наука, 1982. - 336 с.

4. Ан/исимов А.В., Борейша Ю.Е. Проектирование сложных систем посредством параллельных взаимодействующих процессов в режиме имитационного моделирования. Киев: Институт кибернетики АН УССР, 1983, Препринт № 83-4. - 38 с.

5. Анисимов А.В., Борейша Ю.Е. Некоторые вопросы проектирования и верификации параллельных систем с динамически изменяющейся структурой. Киев, 1982, Рукопись представлена Киевским госуниверситетом, Депонирована в ВИНИТИ 8 июня 1982, № 2913-82 деп., - 28 с.

6. Анисимов А.В., Борейша Ю.Е., Николаев М.В. Система автоматизированного моделирования параллельных динамических систем. -Киев: УкрРФАП, 1983, инв. № 6047, зарегистрировано в ГФАП под № П006406 от 05.05.83, 160 с.

7. Анисимов А.В., Глибовец Н.Н., Борейша Ю.Е. Абстрактные типы данных и верификация асинхронных параллельных вычислений в управляющих пространствах. В сб.: Модели и системы обработки информации, Киев: Вища школа, 1983, вып. 2, с. 3-15.

8. Анисимов А.Б,, Николаев М.В., Борейша Ю.Е. Взаимодействие па-ра/ллельных процессов посредством обмена сообщениями. В сб.: Модели и системы обработки информации, Киев: Вшца школа, 1982, вып. I, с. 3-17.

9. Борейша Ю.Е. Моделирование сложных систем посредством параллельных взаимодействующих процессов. В сб.: Модели и системы обработки информации, Киев: Вища школа, 1982, вып. 3, с. 19-25.

10. Борейша Ю.Е. Моде ль-вычислитель для системы динамических параллельных взаимодействующих процессов. Программирование, 1984, № 3, с. 52-59.

11. Борейша Ю.Е. Моделирование посредством динамических параллельных взаимодействующих процессов. Кибернетика, 1985,в печати ).

12. Бусленко Б.Н. Автоматизация имитационного моделирования сложных систем. М.: Наука, 1977, - 239 с.

13. Вегнер П. Программирование на языке АДА. М.: Мир, 1983. -240 с.

14. Воронцов И.Н., Грешилов М.М. Система математических методов машинного моделирования "Взаимодействия". М.: Институт проб134лем управления, 1979т 228 с.

15. Вульф В., Лондон Р., Шоу М. Введение в построение и верификацию программ на языке Альфард. В сб.: Данные в языках программирования, М.: Мир, 1982, с. 123-153.

16. Глушков В.М. Программные средства моделирования непрерывно-дискретных систем. Киев: Наукова думка, 1975, - 152 с.

17. Глушков В.М., Анисимов А.В. Управляющие пространства в асинхронных параллельных вычислениях.: Кибернетика, 1980, № 5, с. 1-9.

18. Глушков В.М., Капитонова Ю.В., Летичевский А.А. Теория структур данных и синхронные параллельные вычисления. Кибернетика, 1976, & 6, с. 2-15.

19. Глушков В.М., Капитонова Ю.В., Летичевский А.А. 0 построении семейства алгоритмических языков для программирования и проектирования многопроцессорных систем. Кибернетика, 1981,1. I, с. 1-7.

20. Глушков В.М., Капитонова Ю.В., Летичевский А.А. Автоматизация проектирования вычислительных машин. Киев: Наукова думка, 1975, - 232 с.

21. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей. В кн.: Избранные вопросы алгебры и логики, Новосибирск, 1973, с. 3-26.

22. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975, - 544 с.

23. Дал У".И. Языки для моделирования систем с дискретными событиями. В сб.: Языки программированияt М.: %р, 1972, с. 344-403.

24. Дал У., Мюрхауг Б., Нюгорд К. Симула-67 универсальный язык программирования. - М.: Мир, 1969. - 100 с.

25. Дейкстра Э. Взаимодействие последовательных процессов. -В сб.: Языки программирования, М.: Мир, 1972, с. 9-84.

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

27. Деннис Дж.Б., Фоссин Дж.Б., Линдерман Дж.Б. Схемы потока данных. В кн.: Теория программирования, 4.2, Новосибирск!

28. ВЦ СО АН СССР, 1972, с. 7-32.

29. Донаху Д. Взаимодополняющие определения семантики языка программирования. В кн.: Семантика языков программирования, М.: Мир, 1980, с. 222-394.

30. Жук К.Д. Новые задачи моделирования больших технических систем. Электронное моделирование, 1980, № I, с. 5-12.

31. Карп P.M., Миллер Р.Е. Параллельные схемы программ. В кн.: Кибернетический сборник новая серия, М.: Мир, 1975, вып. 13, с. 5-61.

32. Котов В.Е. Теория параллельного программирования. Прикладные аспекты. Кибернетика, 1974, № I, с. I-I6, $ 2, с. I-I8.

33. Котов В.Е. Проблемы развития параллельного программирования. -В кн.: Перспективц системного и теоретического программирования. Новосибирск, 1979, с. 58-72.

34. Котов В.Е. О языках параллельного программирования. Кибернетика, 1980, ife 3, с. I-X2, № 4, с. 1-10.

35. Котов В.Е. Элементы параллельного программирования. М.: Радио и связь, 1983, - 239 с.

36. Криницкий В.Н., Криницкий Н.А. Исследование коллективов программ. Программирование, 1983, № 3, с. 3-9.

37. Криницкий Н.А. О параллельных алгоритмах. Программирование, 1983, № 4, с. 9-15.

38. Лельчук Т.И., Марчук А.Г. Поляр-язык параллельного асинхронного программирования. Программирование, 1983, № 4, с. 5968.

39. Лингер Р., Миллс X., Уитт Б. Теория и практика структурного программирования. М.: Мир, 1982, - 406 с.

40. Литвинов В.В. Математическое обеспечение проектирования вычислительных систем и сетей. Киев: Техника, 1982, - 176 с.

41. Майерс Г. Надежность программного обеспечения. М.: Мир,1980, 360 с.

42. Мановицкий В.И., Сурков Е.М. Система имитационного моделирования дискретных процессов ДИСМ, Киев - Одесса: Вшца школа,1981, 116 с.

43. Месарович М., Такахара Я. Общая теория систем. М.: Мир, 1978, - 342 с.

44. Миренков Н.Н. Системное параллельное программирование. 4.1, Новосибирск: Институт математики СО АН СССР, 1978, Препринт ОВС - 0 5, - 36 с.

45. Нариньяни А.С. Теория параллельного программирования. Формальные модели. Кибернетика, 1974, № 3, с. I-I6; № 5, с. I-I4.

46. Николаев М.В. О взаимодействии асинхронных процессов. Программирование, 1984, № I, с. 37-43.

47. Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977, - 288 с.

48. Программное обеспечение системы МИНИМАКС/В. Новосибирск: Институт математики СО АН СССР, 1979, Препринт ОБС-9, - 57 с.

49. СКИФ пакет программ для имитационного моделирования систем с дискретными событиями. - М.: ИН ЭУМ, 1977т - 100 с.

50. Средства отладки больших систем. М.: Статистика, 1977, -135 с.

51. Турский Б. Методология программирования на ЭВМ. М.: Мир, 1978, - 266 с.

52. Хоор Ч.Э.Р. Непротиворечивые взаимодополняющие семантики языков программирования. В кн.: Семантика языков программирования, М.: %р, 1980, с. 196-221.

53. Шкритзис Д., Бернстайн Ф. Операционные системы. М.: Мир, 1977, - 336 с.

54. Шеннон Р. Имитационное моделирование систем искусство и наука. - М.: Мир, 1978, - 418 с.

55. Шоу А. Логическое проектирование операционных систем. М.: Мир, 1981, - 360 с.

56. Шрайбер Т.Дж. Моделирование на gpss . М.: Машиностроение, 1980, - 592 с.

57. Якубайтис Э.А. Архитектура вычислительных сетей. М.: Статистика, 1980, - 280 с.

58. Bjorner D.,Jones С. The Vienna Developmeht Method. -Lecture Notes in Computer Science,1978,V 61,p.1-328.

59. Bryvant R.E.,Dennis J.B. Concurrent programming. -Lecture Notes in Computer Science,1982,V 143,p.426-451.

60. Campbell R.H.,Habeimann A.N. The specification of process synchronization, by path expressions. -Lecture Notes in Computer Science,1974,V 16,p.89-102.

61. Coleman D.,Gallimore R. Partial correctness of distributed programs. -Lecture Notes in Computer Science,1982,V 134, p.138-180.

62. Davis A.L. The architecture of DDM1: a recursively structureddata-driven machine. -Salt Lake City,University of Utah,1977, -187p.

63. Dijkstra E.W. Hierarchical ordering syatem structuring concept. -Communications of the ASM,1974,V 17,N 10,p.549-557.

64. Hansen P.B. The programming language Concurrent Pascal. -IEEE Transactions on Software Engineering,1975,V 1,N 10,p.549-557.

65. Hansen P.B. The nucleus of a multiprogramming system. -Communications of the ACM,1970,V 13,N 4,p.238-241.

66. Hansen P.В. Distributed processes: a concurrent programming concept. -Communications of the ACM,1978,V 21,N 11,p.934-941.

67. Hartmann A. A Concurrent Pascal compiler for minicomputers. -Lecture Notes in Computer Science,1977,V 58,p.3-148.

68. Hewitt C.,Atkinson R. Parallelism and synchronization in Actor Systems. -Principles of Programming Languages,ACM,New York, 1977,p.267-280.

69. Hoare C.A.R. Towards a theory of parallel programming. -In: Operating systems techniques,New York,Academic Press,1972, p.220-230.

70. Hoare C.A.R. Monitors: an operating system structuring concept. -Communications of the ACM,1974,V 17,N 10,p.549-557.

71. Hoare C.A.R. Communicating sequential processes. -Communications, of the ACM,1978,V 21,N 8,p.666-677.

72. Horning J.J.,Randell B. Process structuring. -ACM Computers Serveys,1973,V 5,N 1,p.5-30.

73. Jorrand P. Specification of communicating processes and process implementation correctness. -Lecture Notes in Computer Science, 1982,V 137,p.242-256.

74. Kaubisch W.H.,Hoare C.A.R. Discrete event simulation based on communicating sequential processes. -Theoretical Foundations of Programming Methodology,Dordrecht,1982,p.625-642.

75. Kaubisch W.H.,Perrott R.H.,Hoare C.A.R.Quasiparallel programming. -Software Practice and Experience,1976,N 6,p.341-356.

76. Keller R.M. Sentinels: a language construct for multiprocess coordination. -Department of Computer Science,Salt Lake City, University of Utah,1978,-57p.

77. Kotov V.E. An algebra for parallelism based on Petri nets. -Lecture Notes in Computer Science,1978,V 64,p.39-55.

78. Levin G.M.,Gries D. A proof technique for communicating sequential processes. -Acta Informatica,1981,V 15,N 3,p.281-302 .

79. Manna Z. Verification of concurrent programs: the temporal framework. -Correctness Problems of Computer Science,London, 1981,p.215-273.

80. Rational for design of the ADA programming language. -SIGPLAN Notices,1979,V 14,N 6,part B,-218p.

81. Rosen B.K. Correctness of parallel programs: the Church-Rosser approach. -Theory of Computer Science,1976,V 2,p.183-207.

82. Rounds W.C.,Brookes S.D. Possible futures,acceptances,refusals and communicating processes. -22-nd annual symposium on the foundations of computer sciences,1981,p.140-149.

83. Ryan K.T. Software engineering and simulation. -IN: Winter simulation conference,New York,1979,Proceedings,V 1,p.476-482.lOO.Saito N. Synchronization mechanisms for parallel processing. -Lecture Notes in Computer Science,1982,V 143,p.2-22.

84. Shields M.W.,Lauer P.E. On the abstract specification and formal analysis of synchronization properties of concurrent systems. -Lecture Notes in Computer Science,197q

85. Silberschots A. Extending CSP to allow dynamic resource management. -Proceedings of symposium on reliability of distributed software and database systems,Pittsburgh,1981,p.78-82.

86. Stotts P.D. A comparative survey of concurrent programming languages. -SIGPLAN Notices,1982,V 17,N 10,p.50-61.

87. Stoy J. Foundations of denotational semantics. -Lecture Notes in Computer Science,1980,V 86,p.43-99.

88. Unger B.W. programming languages for computer system simulation. -Simulation,1978,V 30,N 4,p.101-110.

89. Wileden J. Techniques for modelling parallel systems with dynamic structure. -Journal of Digital Systems,1980,V 4,N 2,p.177-197.

90. Wirth N. The use of Modula.Design and implementation of Modula. Modular a language for modular multiprogramming. -Software practice and experience,1977,V 7,p.3-84.

91. Wirth N. algorithms*Data Structures = Programs. -Prentice Hall, Inc.,1976,-366p.