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

!ЙСКСОСКИЙ ордена ШЪШ и ордона штжрьской РКВМЩИИ

энергетический институт

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

11ЛЖ1Х® СЕРГЕЙ ДШРИЕШЧ

удк 681.324.047

РАЗРАБОТКА икптуышшыш срцдспв РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ ИЙОГИАЦИИ

в июгашшяк имоитешшх кагашслх

Сгюциальность 05.13.13. -05.13.11. -

Вичислигелыша машики, комплшен, систеыи и сети. М&тоиатнчвсксв и программное обоспочаниэ вычислительных машин и систем

АВТОРЕФЕРАТ

диссертации на соискание учоной стопоии кандидата тсшшчэских наук

МОСКВА

1989

Работа выполнена на кафедра Прикладной математики Московского ордена Ленина и ордена Октябрьской революции энергетического института.

Научный руководитель', кандидат технических наук, доцент К0РАШ1ИН D.H.

Официальные оппоненты: доктор технических наук, профессор Вайрадян A.C.

кандидат технических- наук, доцент Дзегеленок И.И.

Ведущая организация: Вычислительный центр СО АН СССР.

Защита диссертации состоится " $" 1990 г.

в аудитории Г'¿/О в /в час. ОО мин. на заседании Специализированного Совета К.053.IG.09 Московского ордена Ленина и ордена Октябрьской революции энергетического института.

Отзывы в двух экземплярах, заверенных пэчатыз, просим присылать по адресу: 105835, ГСП, Москва Е-250, Красноказарменная ул., 14, Ученый Совет МЭИ.

С диссертацией можно ознакомиться в библиотеке МЭИ.

Автореферат разослан " " 1990 г.

А.Ф.БОЧКОВ

f ОЩАЯ ХЛРЛКТИ'ИСШКЛ РАБОТ!)

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

Поиски путей увеличения быстродействия ЭВМ привели в 60-х годах к появлению идаи параллельной обработки информации на многопроцессорных и многомашинных вычислительных системах ( ВС ), выразившусюя в создании языков параллельного программирования, таких как Алгол-68, Модула, Параллельный Паскаль и др. В нашей стране также исследовались и разрабатывались такого рода языки. В частности, мохно отметить р-язик и однородные вычислительные системы (ОВС) Евреинова-Косарева, асинхронные операторные схемы (АОС) Котова-Нариньяни и др. На кафедре Прикладной математики МЭИ были разработаны и роализованы на многопроцессорных комплексах ЕС ЭВМ языки функциональных схем (ÍMC) Кутопова-Фалька, граф-схем параллельных алгоритмов (ГСПА) Кутопова-Кораблина и асинхронных вычислительных сотой ( ABC ) Фалька-Строевой.

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

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

Возникает проблема разработки языка распределенного программирования С РП ), базирующегося на принципах, отличных от используемых в параллельных языках. К настоящему времени предложен ряд языков распределенной о (¡раб стеки информации. (РОИ), например, модели взаимодействующих последовательных процессов (CSP) Хоора и распределенных процессов СЕР) Хансена, язык Оккам и др. Однако, все

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

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

Основными ааданаыи. решаемыми в диссертации, является:

- исследование принципов построения и разработка языка распределенной обработки информации;

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

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

- исследование проблемы доказательства эквивалентности схем распределенных программ и вопросов трансляции схем в языках РОИ;

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

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

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

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

Предложена система аксиом и правил вывода, формализующих на

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

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

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

лись в рамках ряда научно-исследовательских работ по изучению архитектуры и математического обеспечения перспективных параллельных и распределенных вычислительных систем, выполняемых на кафедре Прикладной математики МЭИ ( научный руководитель к.т.н. доц. Кораблин D.n. ). Разработанная система внедрена на предприятиях: НИИ "Автоматика" и ИМИ "Альтаир", где она приыэняотся для спецификации и моделирования выполнения распределенных программ; она также внедрена в учебный процесс МЭИ.

Апшйадаз^. Отдельные результата диссертационной работы докладывались на VI Всесоюзном симпозиума "Микропроцессорные системы и локальные сети реального времени" (Вильнюс, 1987), на совместном семинаре СССР-ГДР "Схемные и программные решения для локальных сетей" (Дрезден, 1987), на VIII Всесошной школе-семинаре "Параллельное программирование и высокопроизводительные структуры" (Киев, 1988), на научно-технической конференции МЭЙ "Перспективные технологии применения средств вычислительной техники" (Москва, 1988), на научно-технической конференции ВНИИ "Альтаир" (Москва, 1988), на научных семинарах, проводимых на кафодрэ ПМ МЭИ.

них работ, результаты исследований отражены в 3-х отчетах rio НИР,

рех глав, заключения, списка литературы из 56 наименований и 11 приложений. Общий объем работы - 214 листов, основная часть изложена на 108 стр. и.п. текста, содержит 4 табл. и 34 рис.

Исследования проводи-

ло tqmq диссертации автор имеет 5 почат-

Работа состоит из введения, четы-

- 6 -содереание рабста

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

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

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

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

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

Наиболее простым механизмом взаимодействия является использование операторов передачи и приела данных ( СБР, Оккам ). Более структурированный метод, предложенный в использует для этой цели вызов удаленной процедуры, объявленной в том процессе, с которым необходимо произвести обмен. Недостатком такого способа

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

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

Использование только локального или глобального недетерминизма, как это сделано □ ВР, существенно усложняет семантику программ и реализации языка. Так в модели DP каждый процесс при попадании в защищенную область должен переключиться с выполнения одной операции на другу», если его внутреннее состояние нэ согласуется с состоянием остальных процессов. Поэтому более удобный является метод синхронизации, основанный на комбинации локального и глобального нодетерминизма ( CSP, Оккам и др. ).

В главе также рассмотрены языки параллельного программирования ГСПА и ABC, разработанные на кафодро Прикладной математики МЭИ. Показано, что они не обладают в полной мере средствами, необходимыми для разработки распределенных программ. Однако, функциональный характер компонентов программы в этих языках дает возможность строить более простые программы и э значительной степени облегчает их анализ.

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

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

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

Программа в языке АФС С см. рис. 1 ) конструируется из набора функциональных компонентов, называемых функциональными процессами (<Й1), и набора передаточных компонентов, называемых камалсиси свази С КС ).

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

Взаимодействие Ш может осуществляться только с помощью передачи данных через каналы связи. Один (или несколько процессов) записываеэт данные в канал, другой процесс ( или несколько процессов ) читает данные из канала. <Ш может осуществить запись данных в канал только в случае готовности КС к приему информации, а затем продолжить свое выполнение. Чтение данных возможно только в случае готовности канала к выдача. Если КС не готов к обману, то ФП переходит в состояние ожидания.

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

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

функциональные процессы

Функциональный процесс определяет свои' собственные переменные и команду, задаедуо преобразование данных, fproc ::= FJf! name {docloc} с

docloc I:= type var {, var } [ = axpr {, expr- } ]; type ::= INT I FLOAT | DOUBLE | CHAR | BOOL .

Команды подразделяется на простые и составные, с SKIP; | BREAK; | EXIT; ! VAIT ехрг; | var := expr; I raad; I write; | SEQ ( с {. с } ) | PAR(c{c>) ! ALT ( g -> с { g -> с } ) 1 LCOP ( с )

К простым командам относятся: пустая команда SKIP, команда выхода из цикла BREAK, завершения <МЛ EXIT, ожидания WAIT, присваивания, ввода и вывода. Имеются четыре составные команды! последовательной и параллельной композиции, альтернативная команда ALT и команда цикла LOOP.

В качестве защиты в альтернативной команде может использоваться булевское выражение (Ь), команды ввода-вывода и ожидания, а также комбинация этих команд с булевским выражением:

5 ::= Ь | [Ь &] road | [Ъ &] write | [Ъ &] WAIT expr . При выполнении команды ALT определяется набор готовых к выполнении защищенных команд и осуществляется выполнение любой команды из этого набора. Защищенная команда является готовой, если булевское выражение имеет истинное значение, или канал, указанный в команде ввода-вывода, готов к взаимодействию, или истекло время, указанное в команде ожидания. Команда, комбинирующая локальный и глобальный недетерминизм, является готовой, если выполняются оба условия.

Если в альтернативной команда указаны только команды локального или смешанного недетерминизма и при этом все булевские выражения имеют значение ложь, то происходит ноуспешное завершение ФП. Если такая команда используется в команде цикла LOOP(ALT(b ... )), то происходит завершение цикла.

Канал связи может иметь множество точек входов и множество точек выходов:

doccan : .= CHAN etype : tlist f tlist }

etypo ::= ALL | ANY . В зависимости от объединения входов и выходов каналы могут быть разбиты на 4 группы. Канал типа ALL-ALL принимает данные по всем своим входам и выдает данные по всем своиы выходам, после чего становится готовым к приему очередной порции данных. Канал типа ANY-ANY принимает данные по любому из входов и выдает их на любой выход. КС типа ALL-ANY и ANY-ALL комбинируют вышеописанные случаи.

Каждый вход ( выход ) КС задается с помощью списка типа данных, принимаемых на этот вход ( выдаваемых с этого выхода ); tlist ::= type [ "["expr"]" ] {. type [ "["expr"]" ] }; | SYN; . Для задания множества однотипных входов ( выходов ) перед списком типов может быть указан диапазон С ехрг, ахрг ), задающий началь-

etypo : tlist С tlist } END can {, сап );

ный и конечный номера входов ( выходов ). Тип SYN указывается при описании КС, которые используется только для синхронизации ФП. Если часть прочитанных данных на нужно передавать на выход канала, то перед именем типа этих данных указывается символ "*". Для определения множества однотипных данных используотся массивы.

В командах ввода ( вывода ), входящих в тело <й~1, указывается имя канала, комар входа (выхода) и список переменных (выражений): road ::= READ (can[(expr)]) var C.var } | READ (can) SIGNAL . write ::= VRITE(can[(expr)]) expr C.expr } | WRITE(can) SIGNAL . Параметр SIGNAL используется для взаимодействия с каналами синхронизирующего типа.

АФС-прпграммя

АФС-программа в общем случае представляется с помощью набора вычислительных сетей ( net ):

prog '.: = not not '.: = NET name ( [ formpar ] )

{ net } { deccan | defcon }

BEGIN node С node } END dafcon :1= CONST name = expr; Каждая вычислительная сеть может иметь формальные параметры, в качестве которых используотся имена констант, каналов и других сетей. В сети определяются локальные константы и каналы связи.

Тело вычислительной сети состоит из набора ФП и из набора операций подстановки других вычислительных сетей, в которых указываются имена сетей и фактические параметры ( нет рекурсии ): node :1= fproc | name ( [factpar] ) . Выполнение АФС-программи предполагает одновременный запуск всех ФП. В начало выполнения все КС не содержат данных и готовы к приему информации. АФС-программа завершается, когда часть ФП ухе закончилась, а все остальные заблокированы, то есть ожидают готовности канала для выдачи или приема данных.

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

Производитель-потребитель.

producer

<z>

согшитог

РИС. 1

- 11 -

АФС-программа рошсния этой задачи имеет вид: NET example

CHAN ALL : INT; ALL : INT; END c; BEGIN

FUN producer INT x = o; LOOP ( ALT С

X < 3 -> £03 ( x x i;

VRITE ( с ) x; )

) )

FUH consumer INT x, у - I; LOOP ( SEQ ( READ ( с ) x; у : = у * x;

) )

END

Программа завершается в результате завершения процесса-производителя С х < 3 г FALSE ). что приведет к блокировке процесса-потребителя.

В языке АФС также имеется средства для задания множества однотипных ФП или команд с помощш операции размножения, а также сродства планирования: приоритеты выполнения ФП, задержка ФП, распределение ФП и КС по виртуальтд» процессорам. Такие сродства позволят увеличить эффективность выполнения программы на ограниченных ресурсах.

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

Приы2й_2-. Проблема обедающих философов в языке ASC роиается сле-дуидим образом: NET dinphil Q

CHAN ALL : SYN; ALL : SYN; END fork [5]; BEGIN

(* i = 0. 4 ) phil ( fork [i], fork [(i + 1)15] )

END /* "Z" - операция деления по модулю */

NET phil С CHAN forkl, fork2 )

CHAN ALL : SYN; ALL : SYN; END onbr. oxit;

BEGIN

FUN init

PAR ( WRITE (forkl) SIOIAL; WRITE (exit) SIGNAL;' )

FUN think

LOOP ( Sffi) ( READ (exit) SIQJAL;

. . . дцхаетА . . .

WRITE (eater) SIfflAL; ) )

FUN eat

LOCP ( SEQ ( READ (enter) SIGNAL."

READ (forkl) SIGNAL". READ (fork2) SIGNAL; eea

WRITE (forkl)SIGHAL; WRITE (fork2)SI(3WL;

WRITE(exit)SIGNAL," ) )

END

В этом решении вилки представляется с помощью массива КС fork, философ может взять вилку ( прочитать из канала ) только Б том случае, если этого но сделал до него другой философ. Каждый философ представляется при помощи вычислительной сети pbil. <И1 think и eat моделируют поведение философа во время жизни, процесс init записывает начальные' данные в каналы forkl и exit.

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

Цепь функциональных процессов.

fpl Схп) fP2 (xn-l) -{cn-l)—' К

рис.. 2.

Каждое исходное данное обрабатывается в этой цепи последовательно. Однако, через некоторый промежуток времени, необходимый для загрузки всей цепи, АФС-программа сможет одновременно обрабатывать множество исходных данных.

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

В хшхьой-хлаш определяется денотационная семантика языка АФС. В ней не рассматривается доказательство корректности предло-

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

На основа метода определения семантики схем CSP-программ, предложенного в соавторство с научным руководителем доцентом [Сораблиным D.IL, разработан метод определения семантики подмножества схем. ЛФС-прогршш. Синтаксис схем АФС-программ задается следующим образом:

рг : := NET сап^ ; ... ; can,,, BB3IN fprocj^ fproc2 .. . fprocn END , con ::= CHAN j :: etypo(k) : atypo(l) , otypo ::= ALL | ANY , fproc : := FUN i : : с ,

с: •'= skip I break | exit | wait | a | read(i,k) | writQ(i,k) | SEQ ( ci;c2 ) I ALT (gc) I LOOP (ALT (ge)) | PAR (c1;...;cn) , : : = g -> с I gcj ; gc2 , g ::= tt I Ь I g & road(i.k) I g & write(i.k) | g & wait , где pr e Prog (схемы программ), can e Can (КС), otypo e ETypo (типы рходов-выходов), fproc e FProc (ФП), с e Com (команды), gc 6 GCom (защищенные команды), g e Guardo (защиты), a e АСот (элементарные команды), b е ВЕхр (булевские выражения), read 6 RCom (команды чтения), write 6 WCom (команды записи), i,j e CPLab (мотки <Ш и КС), k,1 e CNum (номера входов-выходов).

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

1. Априорно заданы множества семантических значений элементарных команд ( VACom ), булевских выражений ( VBExp ) и команд взаимодействия ( VRCom, WCom, Vîn, VOut ):

A e VACom. В e VBExp, IN s VRCom (J Vin, OUT e WCom IJ VOut.

2. Множество вычислительных последовательностей cp e CPath: cp ::= pO } et I cpwcp2 I cp I cpw I i I fail I deadlock ,

где pO - пустой процесс ( нормальное заолршение ); о. : : = А I В I (IN, CUT); - опорация конкатенации; ср* -

коночные последовательности вида ср^ср„..,wcp; ср" - бесконечные последовательности вида ср„ср_...; 1 - зацикливание ФП; fail -неуспешное завершение; deadlock - взаимная блокировка.

3. Семантика схем программ определяется на множостпо всех подмножеств CPath : Р, R б Р (CPfth), Л : Prog ? (CPath).

Основной особенностью разработанного метода является опреде-

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

Суть этого связывания заключается в том, что несинхронизиро-ванныы участкам однопрег/онно выполняющихся ФП сопоставляется множество ЕЛ, полученных путем произвольного перемешивания семантических значений зломентарных команд и булевских выражений. Если процессу требуется выполнить операцию ввода или вывода, то в случав готовности соответствующего КС в вычислительную последовательность записывается пара (IN, CUT). В случае команд локального недетерминизма выписываются все пути его разрешения, в случае глобального - только те, для которых взаимодействие с каналом имеет место. Такой подход позволяет точно'определять все возможные пути выполнения программы, в том числе пути, ведущие к исключительным ситуациям (заканчивающиеся символами l,fail и deadlock). Пример 3. Семантика схемы программы производитель-потребитель pr = NET CHAN l:: ALL(l) : ALL(l)

BEGIN FUN l:: LOOP ( ALT ( b -> SEQ ( aL; write (1,1) ))) FUN 2:: LOOP ( SEQ ( read (1,1); a2 )) END определяется сладующим образом'.

p = Л iprj = ( а-ах„ [ ( bj\1wa2 u )*-

( BJ^J^-Ai UA2 ) U ] w A2 ) „ deadlock = = £ deadlock U •B_A1_A2-doadlock U • • •

(J BJ^J^Jä^J^____.deadlock (J . . .

U BJ^^J^J^-BJ^J^... J^Jt2wA2„daadlock L) . . . } . Определение семантики с помощью множеств вычислительных последовательностей позволяет решать' ряд проблем, связанных с анализом распределенных программ, в частности, проблему сравнения схем. Опроделпнио 4. Если множество вычислительных последовательностей Р^, сопоставляемое схеме программы prj_, является подмножеством множества Р2 ( PL с Р2 ), сопоставляемого схеме рг2, то схема ргх слабее чем схема программы рг2 ( рг2 более недетерминированная ). Если множества вычислительных последовательностей равны, то схемы программ эквшзалеадшы ( = Р2 ).

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

Аксиа mí'.

АО. Р с PUP'

Al. PUP = Р

А2. Pi U Р2 = Р2 U Pi

A3. (Pi и Р2) и р3 = Pi и (Р2 и р3)

М. pOJ> = Р

А5. (PiJ>2)~P3 = РаЛРг-Рз)

Аб. (P!UP2)~P3 = = PL-Рз и Р2~Р3

А7. Pi-(P2UP3) : = РiJ>2 U Pi-Ps

A3. P„PW = pv

A3. Р* = PJP' U рО .

111 ( правша замет ). Пусть Р2 с Pi и Р2 с Р3. Тогда, если Р4 -множество, полученное из заменой Р2 на Р3, то Pj_ с Р(.

112 ( решение уравнений ).

а) Пусть Р = PjiJ3 U Р2 и Pj но содержит рО, тогда Р = Рх „Р2.

б) Пусть Р = PiJ5 и Рг не содержит рО, тогда Р = PLW.

Для введенной формальной системы были доказаны следуйте утверждения:

Доыма_5_ Пусть Р2 с Pj и Р2 = Р3. Тогда, если Р4 - множество,

полученное из PL заменой Р2 на Р3, то = Р4.

Топрпня R Система аксиом и правил вывода непротиворечива.

Следует отметить, что при сравнении сложных схем программ выбор необходимой аксиомы или правила вывода не всегда очевиден. Поэтому в работе был предложен метод сравнения, основанный на эквивалентном представлении множеств ВП конечными системами равенств. ОшедедсшйЛ^ Множество вычислительных последовательностей Peí1 (CPath) лродставимо с псмощьс конечной системы рекурсивных равенств, если имеется конечное множество P1,P2,...,Pn е J>(CPath) таких, что Р в Р^ и для любого i (1 < i < n)

pi = . U a13 w ри U 5 ( P¡ ) ( * )

где N = С 1, 2, .J.e n }, e { А, В, (IN, OUT) },

V i 5 (Pi) с { рО, 1, fail, deadlock } и Vi V j 3 k e N : Pjj = Pk. ЛшшаЛк. Каждое множество вычислительных последовательностей Ре? (CPath), сопоставляемое оператором S схема АФС-программы рг, может быть эквивалентно представлено с помощью коночной системы равенств вида ( * ).

Теорема Я. Пусть Р и Р' - множества вычислительных последовательностей, сопоставляемые схомам программ рг и рг'. Тогда 1) Р с Р' тогда и только тогда, когда для этих множеств можно построить системы рекурсивных равенств такие, что для любого

слагаемого каждого рекурсивного равенства множества Р найдется слагаемое соответствующего равенства Р', начинавшееся с того же самого символа.

2) Р = Р' тогда и только тогда, когда найдутся две системы рекурсивных равенств, представляющие Р и Р', эквивалентные с точностью до обозначений.

3) Проблема сравнения схем АФС-программ разрешима.

На базе этих результатов был разработан метод сравнения схем программ, основанный на преобразовании соответствующих множеств последовательностей к требуемым системам рекурсивных равенств. Метод заключается в последовательном выписывании рекурсивных равенств для обоих схем программ. На каждом шаге сравниваются множества слагаемых Ht и MJ рекурсивных равенств для схем рг и рг'. Если Mj = Щ, то продолжаем процесс для всех пар слагаемых; если Mi с М[, то продолжаем процесс только для слагаемых из множества Mt. Так как исходные множества рекурсивных равенств конечны, то и предложенный процесс также будет конечным. В итоге мы получим один из результатов", а) если VI: М^ с М(, то схема рг слабее рг'; б) если Vi: = М[, то схемы рг и рг' эквивалентны; в) если 3i: Mi#H[ или 3j,k: M-j с Щ и с то схемы рг и рг' несравнимы. Пример 10. Сравним схему прозводитель-потребитель рг со схемой рг', в которой изменен порядок записи простых команд в первом ФП. рг' = NET CHAN l:: ALL(l) : ALL(l)

BEGIN FUN l:: LOOP ( ALT ( b ~> SEQ ( write (1,1); ))) FUN 2::- LOOP ( SET) ( read (1,1); a2 )) END Выпишем системы рекурсивных равенств:

pi = BJ>2 U deadlock Pi = вJP2 и deadlock

р2 = Aj.J>3 с р; AxJ'j и а2_р.

Рз = bj>< и Рз = bj>; и A2_Pi

Ра = axj>5 и А2~Р2 Pi = А1-Р5 и А2-Р2

Р5 = bj>6 и a2-p3 Р5 = rj>; и А2-Р3

ре = AiJ», и A2J>4 t р« = A2J>;

Следовательно, схемы рг и рг' несравнимы: Р=Л 1рг1 Ф Р'=М |рг'1.

Рассмотренный метод определения семантики был разработан для выбранного подмножества схем АФС-программ. Добавление в это подмножество параллельной команды и защищенных команд, комбинирующих локальный и глобальный недетерыинизм, потребует значительных изменений в операторе В. Поэтому был разработан другой метод, базирующийся на наборе универсальных операций над множествами Ш: кожпозиции ( сопоставляется с1,'с2 и 8 -> с ), объединения

( gcx.'gcj ), итерации ( LOOP (ALT( gc )) ) и связывания множеств ( PAR ( Ci," ...', cn ) ). В работе предложен конструктивный способ задания этих семантических операций с помощью систем рекурсивных равенств и даны примеры их использования для определения семантики схем CSP и АФС-программ.

Такхо в главе рассмотрены вопросы трансляции схем программ. Определены функции преобразования подмножества схом АЗС-программ ( в котором отсутствуют команды break и oxit ) в схемы CSP-npor-рамм еозфд_с : Prog* -> Progc и наоборот схом CSP в схемы АФС-программ Сопрс_А : Ргойс -» Ргойд, где ProgA - подмножество схем АФС-программ, Progc - подмножество схем CSP-программ. При трансляции схемы АФС-программн каналы связи прообразуются в последовательные процессы CSP, осуществляющие в цикле прием и выдачу данных. При трансляции схемы CSP-программы для каждой пары взаимодействующих команд вводится КС. Для предложенных правил преобразования были получены следующие результаты: 1£ЮЕШа_Ц_ ЛА [prAl = J<c 5eompA.c (prA)] .

1£шша_12-. Лс iprc]/{ (in,OUT) ) c -*a ieompc.A (prc)l/UIN;0UT)) ■

где P/{(in,out)> ~ множество HI, полученное из множества P после удаления всех пар (IN, 0(JT).

Отметим, что схема АФС-программы (теорема 12) является более недетерминированной по сравнение с исходной CSP-схвмой потому, что выполнение команд чтения и записи через КС но синхронизировано.

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

I I Э> (CPath) X ЕУ У ( и С 1, fail, efcadlock } ) , где 2Г" - множество состояний памяти программы с типичным элементом сГ" = < 0]^, о2.....оп а о - типичный элемент множества Е

( множество состояний ФП и КС ). Например, для программы производитель-потребитель мы получим:

1 С Рх. ) = [ о~ = <0l, с2[х\0], а3[у\1]> ] = I ( Р2, <Г ) = . • ■ = { б? } = ( < <Ji[l\3], ff2[x\3], а3[х\3,у\6] > } , где o[x\v] обозначает состояние, полученное из о путем замены старого значения перомонной х значенном v.

В чотпортой глпт рассматриваются основные принципы реализации языка АФС на многомашинной ЕС, описана реализация отладочных средств языка и одномашинная версия АФС-системы программирования,

разработана технология отладки и выполнения программ и приводен пример использования средств АФС-систеыы.

Для реализации языка АФС в работа предложена следующая структура внутреннего представления АФС-программы ( рис. 3 ).

Внутриыашишюо представление ЛФС-програшш.

Файл сети ]

| Заголовок вычислительной сети |

L _

_ J

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

Выполнение АФС-программы осуществляется под управлением набора локальных диспетчеров ( ЛД ), функционирующих на всех машинах ВС. По команде запуска на машине пользователя начинает выполняться главный ЛД, который осуществляет распределение КС и <Н1 по ресурсам ВС и инициирует выполнение остальных ЛД. Все диспетчеры загружают КС и запускают <1П, которые распределены на данный компьютер. Во время выполнения ЛД обслухиваяг запросы ФП на чтение и запись данных. Также ЛД определяют момент завершения программы и выгружают из памяти все заблокированные ФП. Общая схема функционирования диспетчера для одномашинной версии может быть представлена с помощью следующего псевдокода на языке Си: Загрузиа_$айла_сети; Запуек_эадач_ФП;

nreq = О; /* Число необработанных запросов (задержанных ФП) */ nfin = о; /* Число нормально завершившихся ФП */

while ( nfin + nreq < nimfp ) { /* Обработка запросов */ Получшм>_запрос_от_ФЛ;

if ( Запрос_виполнгш ) С /* Выполнить запрос */

if ( Код_запроса == STOP ) nfin++; else { Выполнит* запрос;

while ( Есяь_выполншые_запросы ) {

Файл сети

Заголовок вычислительной сети

Каналу Канал2 КанаЛщ

ФПЛ

ФП,

Щ,

Файлы образов задач функциональных процессов рис 3

- 19 -

Внбратъ_маибодее_приоритет71ны'11_эапрос;

Выполнить_эапрое; nreq—; }

}

}

е1зе nroq>+; /ж Запрос не выполним */

}

Завершгиие_вътолчечш;

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

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

Разработанные система отладки и одномашинная версия АФС-системы реализованы на мини-ЭВМ типа СМ-4 в операционной системе 0C-FB. Программное обеспечение написано на языке Си, за исключенном машинозависимых подпрограмм межзадачного взаимодействия ФП и ДЦ, реализованных на макроассемблере СМ-4. Общий объем разработанных программ - 175 Кбайт ( система отладки ) плюс 150 Кбайт ( целевая система ), из них 28 Кбайт - локальный диспетчер.

0С1ЮНИЕ РЕЗУЛЬТАТА PATOTIJ

1. Приводен обзор и дан сравнительный анализ моделей и языков параллельной и распределенной обработки информации.

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

3. На основе предложенной модели разработан язык асинхронных функциональных схем ( АФС ),' дан ряд примеров, демонстрирующих полезность используемых в ном концепций ГП.

4. Определена денотационная семантика схем АФС-программ и на оо основе разработан формальный метод сравнения схем программ, предназначенный для доказательства эквивалентности схем. Определены правила взаимной трансляции схем CSP и АФС-программ и показана

их корректность. Предложен формальный метод инторпротации схем программ ( определение денотационной семантики программ ).

5. Сформулированы общие принципы выполнения АФС-программы на многомашинной вычислительной системе и определены основные функции исполнительных средств системы распределенного программирования на базе языка АФС.

6. Разработаны правила преобразования ( операционная семантика ) АФС-программ во внутриыашинное представление.

7. Разработаны инструментальные и исполнительные средства системы отладки АФС-программ и одномашинной версии системы РП.

8. Разработанная система внедрена на ряде предприятий радиопромышленности и в учебный процесс в МЭИ.

Основные положения диссертации достаточно полно отражены в следующих опубликованных работах:

1. Кораблин О.П., Налитов С.Д.. Волочков Н.Ф. Язык асинхронных функциональньк схем -' концепция распределенного программирования // Материалы VI Всесоюзного симпозиума по модульным ИВС.-1987.- Вильнюс,- С. 82-84.

2. Кораблин D.I1.. Налитов С.Д. Распределенное программирование для локальных сетей // Тезисы докладов VIII Всесоюзного семинара "Параллельное программирование и высокопроизводительные структуры",- 1988.- Киев.- С. 73.

3. Кораблин D.-П., Налитов С. Д. Применение языка асинхронных функциональных схем для моделирования распределенных систем // Тезисы докладов VIII Всесоюзного семинара " Параллельное программирование и высокопроизводительные структуры".- 1988.-Киев.- С. 74.

4. Кораблин D.П., Налитов С.Д. Язык асинхронных функциональных схем - концепция распределенного программирования // Программирование,- 1989.- К 6,- С. 35-45.

5. Кораблин D,n., Кроввиди Р., Налитов С.Д. Реализация параллельных вычислений на многомашинных вычислительных комплексах мини- и ыикро-ЭВМ // Сб. науч. тр. МЭИ "Математическое обеспечение ЭВМ, комплексов и сетей".- 1986.- ff 86.- С. 21-29.

подписано к печати 22.H89 Л.-30265 Уч.-vija. Í0 печ..\.',25

Закал '*•••?' Н.чл . н^мгр А Г' Тираж <Р0 Бесплатно Типография vi3iaTC.\bcTu;v МЭИ. Красноказарменная, 13.