Введение к работе
Актуальность проблеми. Использование фон-неймановской структуры вычислительной систем. (ВС) с единственным центральным процессором было характерно для начального периода развития вычислительной техники. Стремление к повышению быстродействия ВС привело к появлению в 60-е годы идеи параллельной обработки информации на многопроцессорных ВС.
Первый шаг в направлении распределенной обработки данных Зыл вызван необходимостью децентрализации управления ВС при выполнении операций с периферийными вычислительными устройствами. Для этой цели были введоны независимые процессоры ввода/вывода ( каналы ), которые могут работать параллельно с центральным процессором, выполняя операции ввода/вывода.
Следующий этап был связан с появлением в начале 70-х годов ткро-ЭВМ, что вызвало появление разнообразных конфигураций ВС на базе мини- и микро-ЭВМ. Достижения в области технологии изготовления микросхем с очень большой плотностью (СБИС) позволили осуществить разработку ВС, состоящих из большого количества микропроцессоров, имеющих собственную память. В частности, одним из перспективных направлений проектирования высокопараллельных ВС является использование транспьютеров.
Очевидно, эффективное использование распределенных ВС требует и создания соответствующих языков программирования, получивших название языков распределенного програллирования (РП), и поддерживающих их программных комплексов, предназначенных для разработки, отладки и выполнения распределенных программ на этих языках.
Большой вклад в решение различных аспектов проблемы распределенной обработки информации внесли ученые России и других стран СНГ Евреинов Э.В., Поспелов Д.А., Косарев Ю.Г., Самойденко СИ., Хорошевский В.Г., Кщенко Е.Л., Цейтлин Г.Е., Летичевский А.А., Котов В.Е., Нариньяни А.С, Млренков Н.Н., Бандман О.Л., Трахтенгерц Э.А., Кутепов В.П., Борщев В.Б. и др.
Вместе с тем, как показывает практика, успешное решение этой проблемы требует разработки формальных методов задания семантики языков РП. Отсутствие точного метода описания семантики влечет серьезные проблемы не только в понимании
- 4 -конструкций языков программирования, но и в реализации эти: языков.
Одной из задач формальной семантики является построение систем доказательств правильности программ. В настоящее время требование, чтобы каждая разрабатываемая программ! сопровождалась доказательством ее правильности, является нереальным. Однако, в ряде случаев усилия по доказательству правильности программы являются вполне опразданными.
Еще одной областью приложения формальной семантига является анализ свойств программ, в частности, проблемі эквивалентности, завершимости программ, возможности ш зацикливания и т.д.
Чрезвычайно остро сказывается отсутствие методої формальной семантики при разработке и реализации язнкої распределенного программирования, а также доказательств* свойств распределенных программ, поскольку к традиционнш проблемам последовательных языков программирования добавляются проблемы функциональности программ, анализа временны) характеристик распределенных программ, что является особенж важным для систем реального времени, а также проблемы, связанные с взаимодействием и синхронизацией параллельнс работающих процессов, в частности, возможность возникновения тупиков, взаимных блокировок и т.п..
Существенный разрыв между имеющимися языками РП и языкам! описания распределенных систем (языками спецификаций), для которых разработаны поддерживающие их семантические теории, приводит к потере части свойств языков РП при трансляции их і такие языки для анализа распределенных систем. Этот факт влечеі необходимость создания, с одной стороны, семантических теорий, поддерживающих имещиеся языки РП, а, с другой стороны, язнкої РП, обеспечивающих возможность применения имеющихся семантических теорий для анализа программ в этих языках бе; существенных преобразований анализируемых программ.
Объектами исследования в диссертации являются: языки і системы параллельного и распределенного программирования взаимодействие в которых базируется на механизме передачі сообщений, и модели и методы анализа процессной семантию
эспределенных систем.
Указанные выше сферы применения методов формальной шантики для разработки и реализации языков РП, создания на ззе этих языков распределенных систем и их анализа говорит о эсомненной актуальности тематики диссертации.
Цель и задачи исследований. Целью диссертации является звышение эффективности разработки и анализа распределенных ^числительных систем, взаимодействие в которых базируется на эредаче сообщений.
Для решения поставленной цели в диссертации исследуются и зарабатываются следующие вопросы:
разработка семантических моделей и методов, характеризующих эзличные свойства распределенных систем указанного вида (в зстности, корректность программ, эквивалентность вспределенных программ, наличие тупиков, блокировок, ацикливаний и т.п.):
разработка семантической теории анализа процессов выполнения аспределенных систем, взаимодействие в которых базируется на ередаче сообщений;
разработка языка распределенного программирования , хорошо оддержиаваемого семантической теорией, и разработка на базе того языка комплекса программных средств для создания, отладки реализации распределенных систем.
Методы исследований. В диссертации используются емантические методы теории языков программирования, аппарат еории формальных систем, функционального анализа, метрической опологии, теории множеств, алгебраические методы и метода оделирования на ЭВМ.
Научная новизна. В работе на основе анализа имеющихся зыков распределенного программирования сформулирована и іеализована новая концепция распределенного программирования, базирующаяся на синтезе функционального подхода к построению ;зыков программирования и механизма асинхронного взаимодействия юмпонентов распределенной программы посредством сообщений :ерез каналы связи специального вида. Разработана семантическая еория анализа распределенных программ. В диссертации:
. на основе предложенной концепции распределенного
программирования разработан язык асинхронных функциональш схем (АФС), являющийся языком практического программирована и, таким образом, имеющий программную поддержку для создвнш отладки и реализации распределенных программ;
разработан блочный метод построения семантических моделе распределенных программ, обеспечивающий гибкость предложенної аппарата для анализа распределенных систем в зависимости с языка разработки;
построены исчисления формальных систем, предназначенные да анализа различных свойств распределенных систем (доказательсті корректности, эквивалентности схем программ, наличі исключительных ситуаций при выполнении программ и т.п. ] Доказана непротиворечивость построенных систем, разрешимое проблемы эквивалентности в различных подклассах схем программ; -построена семантическая модель для анализа корректное алгоритмов в языке граф-схем параллельных алгоритмов (ПА) доказана разрешимость проблемы корректности граф-схем ПА;
разработан семантический метод анализа распределенш программ в языке АФС, сопоставляющий АФС-программе множество е реализаций, что позволяет осуществлять анализ поведаю АФС-программ. Доказана корректность этого метода;
- разработан композиционный семантический метод аналиг
широкого класса языков РП, взаимодействие в которь
осуществляется посредством передачи сообщений. Доказаь
корректность предложенного семантического метода. Показаі
применимость этого метода для анализа распределенных программ
различных языках (csp, АФС и др.).
Практическая ценность. В работе:
- разработаны семантические модели и методы, которые могут быт
использованы для решения задач анализа и kohtdoj
функционирования распределенных систем, а также щ
проектировании и модификации этих систем;
- создана системе распределенного программирования на баг
предложенного языка асинхронных функциональных схеь
позволящая осуществлять разработку, отладку и реализвш
распределенных комплексов, а также разработку и исследоваш
моделей распределенных систем;
предложенный комплекс методов, моделей и инструментальных редств обеспечивает фундамент для разработки (или выбора из дающихся) языка РП в зависимости от целей проектирования, эагматики решаемых задач, что позволяет существенно повысить зчество программного продукта.
Реализация результатов работы. Предложенные в работе змантические модели и методы разрабатывались в рамках НИР, люлняемых на кафедре Прикладной матзматики МЭИ, по разработке зыков распределенного программирования (язык граф-схем ПА, /нкциональный язык параллельного программирования. язык ;инхронных функциональных схем), созданию инструментальных редств отладки и анализа программ в этих языках, а также люлнительных средств выполнения распределенных программ на ^числительных системах. Использование семантического метода, ^поставляющего распределенной программа множество всех ее ^числительных последовательностей, позволила решить проблему <вивалентности для подкласса функциональных схем программ, эдержащих циклы. Кроме того, рззрвОогапная семантическая здель для анализа программ в языке граф-схем ПА позволила ззрешить проблему корректности граф-схем ПА, что являотся зпременным условием правильного функционирования программы в зыко граф-схем ПА на ВС.
Разработка языка АФС с самого начала сопрововдалась эзработкой семантической теории, поддерживающей анализ эограмм в этих языках и влияющих, в свою очередь, на ясность и ястоту конструкций языка АФС.
Система распределенного программирования, базирующихся на зыке граф-схем ПА была принята в 1976 г. в качестве гандартного математического обеспечения многомашинных жплексов СМ1 и СМ2 разработчиком ЭВМ этой серии (НИИ УВМ, г. зверодокецк).
Система распределенного программирования на базе языка АФС *ла разработана вначале для комплексов СМ4, а затем и для змплексов IBM PC. Эти системы внедрены но предприятиях НИИА, 10 Космического приборостроения, ВНИИ "Альтаир", АО {риогекмаш" и др..
Выполненные НИР:
- исследование эффективности применения функциональных языков :
качестве языков параллельного программирования высокого уровн
(НИР МЭИ, 1979 - 1980, гос.per. N У63007, отв. исполнитель);
исследование и создание математического обеспечения для параллельных вычислений на комплексах ЭВМ (НИР МЭИ, 1983 1985, гос.per. N01830053441, отв. исполнитель);
разработка системы параллельной и распределенной обработк информации в локальной микропроцессорной сети (НИР МЭИ, 1985 1988, гос.per. N У36793, научное руководство);
разработка системы распределенного программирования для создания специализированных вычислительных комплексов (НИР МЭИ 1986 - 1989, N 335/86, научное соруководство);
разработка инструментальных средств, предназначенных дл спецификации, отладки распределенной вычислительной программно системы реального времени по теме КОЛЧАН (НИР МЭИ, 1990 - 1991 N У69559, научное руководство).
Результаты работы нашли отражение в постановке нове учебной дисциплины в МЭИ: "Семантика языков программирования" читаемой для студентов специальности "Прикладная математика" Созданные системы распределенного программирования используютс в качестве инструментальных средств при выполнении лабораторій работ по курсу "Вычислительные машины, системы и сети".
Апробация работы. Результаты исследований, составляют основное содержание работы, докладывались: на всесоюзні школах-семинарах "Параллельное программирование высокопроизводительные структуры" (Мукачево, 1980 г., Киев, 1984 г., Алушта, 1988 г., Уфа, 1990 г.), на семинаре і Математическом центре (Г.Амстердам) во время прохождения 1981 г. стажировки у проф. де Баккера, на двухстороннеї семинаре СССР-ГДР "Схемные и программные решения для локальні сетей" (Дрезден, 1987 г.), на семинарах ВЦ СО АН СССР (1979 г и Научного совета по комплексной проблеме "Кибернетика" АН СС( (Москва, 1988 г.), на республиканской научно-технической конференции по вопросам разработки и внедрения средств ВТ и У] в народное хозяйство (Тбилиси, 1977 г.), на IX Всесоюз» симпозиуме "Логическое управление в промышленности" (Ташкен 1986 г.), на YI Всесоюзном симпозиуме по модульным И
(Вильнюс, 1987 г.), на семинарах Московского ДНТП, кафедр ИМ, системотехники МЭИ и других научных форумах.
Публикации. По теме диссертации опубликовано 27 работ, выпущено 12 отчетов по темам НИР.
Структура и объем диссертации. Диссертация состоит из введения,1 пяти глав, выводов, списка литературы и приложений. Общий объем основного текста включает 299 стр., в том числе 15 рис.. Список литературы состоит из III наименований. СОДЕРЖАНИЕ РАБОТЫ
