Функциональный метод спецификации семантики параллельных языков и алгоритмов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

ЯЗЕВ АЛЕКСЕЙ МИХАЙЛОВИЧ

УДК 681.142. 2

ФУНКЦИОНАЛЬНЫЙ МЕТОД СПЕЦИФИКАЦИИ СЕМАНТИКИ ПАРАЛЛЕЛЬНЫХ ЯЗЫКОВ И АЛГОРИТМОВ

01. 01. 09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ленинград 1990

/

Работа выполнена на кафедре технологии программирования культета прикладной матеыатики-процес'сов управления Ленинграде го ордена Ленина и ордена Трудового Красного Знамени г< дарственного университета.

Научный руководитель :

Официальные оппоненты

Ведущая организация :

кандидат физико-математических наук, доцент

Тузов Виталий Алексеевич доктор технических наук, профессор

Нелепин Рональд Апполонович кандидат физико-математических наук, научный сотрудник Мшагский Станислав Владимирович Киевский государственный университет им. Т. Г. Шевченко

Защита состоится ______1990 г. в----

часов на заседании специализированного совета К 063. 57.16 по присуждению ученой степени кандидата физико-математических наук в Ленинградском государственном университете по адресу : 190004, Ленинград, К 0., 10-я линия, дом 33, ауд. 88.

С диссертацией можно ознакомиться в научной библиотеке университета ( г. Ленинград, Университетская набережная, дом 7/9).

Автореферат разослан Ученый секретарь специализированного Совета

______1990 г.

Е Ф. Горьково!

- 3 -

ОБЩАЯ ХАРАКТЕРНО ТИКА* РАБОТЫ

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

Целью работы является :

- развитие метода математического моделирования языков, предложенного В. А. Тузовым, применительно к целям спецификации языков параллельного программирования;

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

- изучение методов и средств спецификации параллельных алгоритмов различных классов;

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

ентированных на обработку сложно структурированных данных;

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

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

Методика выполнения исследования. В качестве общей концепции средств спецификации языков и алгоритмов был выбран аппара функциональных грамматик, предложенный В. А. Гузовым. На средств предложенной модели параллельных вычислений и методов ее реализа ции оказали большое влияние идеи, подходы и методы, изложенные работах Э. Дейкстры(01 jkstra E.W. ), Е Котова, Р.Мильнера( Mi 1 не R. ), акредько, Д Тернера (Turner D.A.), T. Xoapa(Hoare C.A.R.) других.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на VIII Всесоюзной научной конференции по проблем теоретической кибернетики ( Горький, 5-7 июля 1988 г.), Всесою ном научно-техническом совещании "Программное обеспечение нов информационной технологии" ( Калинин, 1989), на научных семинар и заседаниях кафедры управления медико-биологическими системами

кафедры технологии программирования факультета прикладной матема-тики-процессов управления ЛГУ.

Публикации. Результаты диссертации отражены в работах [1-4].

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В п. 1.1 дается определение функциональной спецификации как тройки объектов (с, о, Г), где й - спецификация синтаксического домена, о - спецификация семантического домена, Г - спецификация семантического отображения. Спецификация синтаксического домена -это (однозначная) КС-грамматика с=( Чт, Р, б). Спецификация

семантического домена - это пара о=(н, { I¿)), где н - некоторое множество, называемое множеством значений, { f - совокупность частично определенных на декартовой степени множества м функций ?± со значениями в м. Спецификация семантического отображения -это совокупность семантических равенств Г={ к| р£Р), связывающих синтаксический и семантический домены. Пусть каждому правилу р€Р сопоставлена некоторая функция из семантического домена 0. Тогда семантическим отображением зет(Г) назьвается такая функция еуа! о' I(С)->Н, что для любого правила из Р вида А->х;А;х^... хяалх,7,¡, которому сопоставлена функция ^МЛ~>М , и

произвольных у^еЦАх), где А) =( хечт* | А=»'х), следующее ра венство обращается в тождество:

еуа! а(*1У1*2-.. хпупх (еуа1 ..., еуа! с(уд))-

Рассматриваются стратегии вычисления значения еуа!с( х), определяемое указанной выше примитивно-рекурсивной схемой. Вводятся аннотации для явного управления порядком вычисления.

В п. I. 2. исследуются средства спецификации семантическогс домена о, множества н и совокупности функций ( f Вводится понятие отождествления шаблона в некоторой КС-грамматике с значением, на основе которого затем строится класс операций левого отождествления.

Определение 1.1. Отождествлением слова х£Уг' с шаблоном р=х1Л1х2... ХПАаХц-и> где х*еУг\ А^еУдт, называется множеств< решений ( (у¡0,...,уао) } относительно переменных у/,...>ул словарного уравнения

Х/У/Х^. ..хпупхл + ; = х (I)

при условии, что каждое выводится из нетерминала А то есть А.г»'у 10 для всех ¿п, у Слово х отождествимо с шаблон<

<р если множество решений уравнения (I) не пусто.

Расширение понятия шаблона связано с наложением дополнитель ных условий на множество х) решений словарного уравнения (I) Выберем некоторое множество переменных (имен) Уаг= {V/, V¡,.. ), которое может быть бесконечным. Сопоставим каждой такой пере менной у €Уаг некоторый нетерминал А= агеа(у) Значениями пе! менной V будут слова в множестве { хОг' | А=»'х}. Тогда шаблона грамматики с называются слова конечной длины в алфавите (чт Уаг).

Определение I. 4. Операцией левого отождествления (1= ((у/,..., ¥>л!

-> (Ф1.....называется такое частичное отображение И: М"

М*, ЧТО Ь( X ......х„)=(у;, . . . , ук), где (у,,. . . , у*) = .....

Фк)[о], <т - наименьшая подстановка из у( <р!№<р2Ж .. х;№хД»

. ..№хд), если таковая существует. В противном случае ь(х/, ..., х й) неопределено.

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

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

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

В п. 2.1. вводятся понятия комплекта суперпозиций и о-функции. Пусть м, П, о - множества значений, базисных функций и функциональных переменных соответственно. Суперпозициями будем называть элементы множества ( и и О и о)'. Пустуй суперпозицию обозначим через N11. Комплектом из элементов множества х назовем элемент, принадлежащий множеству ВАа(х)=[х->2], где [х->г] - множество всех функций из х в 1, 1 - множество неотрицательных целых чисел. Над комплектами Бя ^бвдс(х) определена бинарная операция объединения « Ухех: $(х)=Б /( х)+Б х) •

Определение 2. 3. о-функцией называется элемент ^евАС^о).

Семантика о-функций задается отношением ОеГ£ВА6*(о) хВАС(Е), которое сопоставляет каждой о-функции множество комплектов суперпозиций. Выполнение о-функции рассматривается как неделимый переход от одного комплекта суперпозиций к другому по правилам, задаваемыми функцией переходов ех: I) вычисление базисных функций:

если 5=50||$ Б^аа^/З, абИ*, аЛ=( а . . . , а „), а^ем, /ЗеЕ, з/€ВАс(Е), f: мл->м^бО и функция Г определена для вектора значений

а\ тогда ex(s)=s0' |s,, где s0'=abA|3, bA=f(aA), иначе правило не применимо;

2) вычисление D-функций:

если S=S0|S j, S0=a;aAJf .. |acaAflf Л|3Я, a¿eM*, aA¿= (ai/,..., z ik( i)) t J3SE, S/eBAG(D, ari ty( f i)=fc( i) И ( f, J... ¡f „ .. |(jff) €Def, ítí£E; тогда в зависимости от значений пит воз можны три случая:

а) n=m: ex(s)=s0' |s где S0' = a;aA<r//S;|... |алаАсгй/Зй;

б) п<ш: ex(s)=s0' js0" |s где $„' = cc1iAoi0i[... |аяаАсгл/Зл,

S0"=aAtrn + 7J... |аАош.

в) п>га: ex(s)=s0' Js ¡, где S 0' = а;аАсГ;0/1... \авйлаа0а,

если п>=1, и so'=0A, если т=0. Правило вычисления базисных функций указывает на то, что вычисление отдельной суперпозиции осуществляется в соответствии со стратегией "вызов по значению". Правило вычисления D-функции описывает все возможные варианты порождения, уничтожения и синхронизации процессов, если с ниш ассоциируются суперпозиции, входящие в комплект. Даются определения безусловных, локально-условных и глобально-условных d-функций с шаблонами и некоторые преобразования одних в совокупность других, имеющих более простой вид.

В п. 2. 2. модель D-функций сравнивается с некоторыми известными моделями параллельных вычислений, в частности, с сетями Петр! и их расширениями. Вводится понятие (под)класса функциональны; -моделейлараллельных вычислений fs=(f, Def, ex) как множества моделей, в которых на множества F и "оёгт!аклюдьваются_некоторые^ог-раничения.

Определение 2. 5. Подклассом регулярных fs моделей называется множество таких моделей (f, Def, ex), что для любой пары (f ^• |f п, ff/J... JtfJ 6Def каждая суперпозиция a i содержит не более ол ного функционального символа f6D.

ТЕОРЕМА 2.1. Класс сетей Петри Мр,7»->) эквивалентен подклассу регулярных РБ моделей с вырожденными множествами значений и базисных функций, то есть М=О=0.

ТЕОРЕМА 2. 2. Класс сетей Петри с запрещающими дугами вкладывается в подкласс регулярных РЭ моделей с локально условными о-функциями.

в п. 2. 3. предлагается распределенная схема реализации модели й-функций. в схеме имеются два сорта вычислительных агентов : процессы, с которыми ассоциированы суперпозиции сгеЕ и согласова-тели, с которыми ассоциированы о-функции ^евдсСо). Вычислительные агенты связаны между собой конечным набором входных и выходных портов, используемые для передачи и получения сообщений. Протокол обмена сообщениями представляется в виде таблиц изменения соостояний вычислительных агентов и основан на динамическом упорядочении процессов с помощью временных меток. ТЕОРЕМА 2. 3. Любой процесс, находящийся в состоянии с, в течение конечного времени перейдет в состояние в или р. ТЕОРЕМА 2. 4. Если в системе процессов Рг, находящихся в состоянии С, существует группа процессов Рг' £Рг таких, что каждый является потенциальным партнером всех остальных, то в течение конечного времени либо эти процессы синхронизируются друг с другом, переходя в состояние р, либо некоторый процесс р€Рг' синхронизируется с другой группой процессов Рг"*Рг'.

Первая теорема гарантирует отсутствие дедлока в любой системе процессов, вторая - что система процессов является живой.

Третья глава посвящена вопросам функциональной спецификации семантики языков параллельного программирования. Исследуется возможность получения точных и ясных формальных спецификаций средств управления параллельными процессами с помощью введенной модели Р5.

В п. 3.1. дается определение функциональной грамматики. Определение 3.1. Одноуровневая функциональная грамматика GF -это набор (g0,FS,ц), где g0=(VVr, Р, s) - КС-грамматика, описывающая синтаксис некоторого языка L, fs=(f, Def, ex) - функциональная модель вычислений: ц : Р ->• Туре'хг - функция, сопоставляющая правилам грамматики G0 вида A->xjA/.. .хлАяхл+;, A¿€Vn, xiSVr', заголовки вида (ttл), ti€Type=( знач, функ, текст} и функциональные символы f £D.

В зависимости от того, что подразумевается под множеством значений м модели FS, получаются различные типы семантик языка. Можно выделить по крайней мере следующие типы. Если m=l(g'), где G' - КС-грамматика, описывающая синтаксис некоторого другого языка L', тогда получаем трансляционную семантику языка L относительно L'. Если в качестве м использовать собственную структуру данных языка L, то получим интерпретационную семантику.

Для последних предлагаются следующие интерпретации значения суперпозиции ах:

I) о>: BAG(E)->p(mxbag(Е)), то есть суперпозиция ах начинает выполняться в окружении совокупности процессов s 6BAG( Е) и заканчивает свое выполнение в окружении совокупности процессов s' €BAG(E), возвращая результат тем;

2) ах: STATE xBAG( Е) -)p(STATE хВ ag( Е)), то есть суперпозиция ах начинает выполняться в окружении процессов SSBAG( Е), когда состояние общей, разделяемой всеми процессами памяти есть s16STATE и заканчивает свое выполнение в окружении параллельных npoueccoB_sl_£BAG(Е), когда состояние памяти есть st' ESTATE;

3) сх: вДсСбтате хЕ)->р(ва6(зтатГ><Е)У) то—же,—что-и-2),_ло память локальна для каждого процесса;

4) ах: ВАб( Е)->р(в Ав(Е)), то есть суперпозиция ах стартует в окружении некоторых процессов и продолжает бесконечно (хотя бы

потенциально) развиваться вместе с ними.

Здесь STATE - множество состояний памяти. Начальное окружение специфицируется как начальное состояние памяти. Вводятся понятия условного, безусловного и многостороннего рандеву.

В п. 3. 2. по предложенной схеме формализуется язык CSP ( Communicating Sequential Processes), введений Т. Хоаром В качестве концептуальной основы языков параллельного (распределенного) программирования. Спецификация семантики CSP включает основные "параллельные" конструкции языка: параллельную команду, команду вывода и альтернативную команду.

В п. 3.3 специфицируется модель рандеву языка АДА. Спецификация дана для случая отсутствия операторов delay.

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

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

Четвертая глава посвящена проблемам спецификации параллельных алгоритмов.

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

Определение 4.1. Тип Т - это алгебра термов Т[Е], где Е - множество символов операций ( сигнатура алгебры).

Значения типа Т представляются термами в этой алгебре. Символы операций из £ разделяются на два непересекающихся подмножества : с - множество конструкторов данных, F - множество функций (функциональных символов). Вводится понятие аннотации управления представлением типа, существенным образом влияющей на пространственные характеристики реализации рекурсивных типов данных.

В 4. 2. дается опеделение понятия функциональной специфш ции параллельного алгоритма. Последняя представляет собой п; (D,s), где о - множество рекурсивных уравнений, определяю! совокупность функций, s - некоторое выражение (суперпозиция), рое должно быть вычислено. В качестве базисной операции пред гается использовать операцию сопоставления с шаблоном (patt roatchi ng).

Определение 4. 3. Шаблоном р типа t назьюается терм вида:

1) _ , где "_" - метасимвол, означающий, что с данным ш лоном отождествляется любое значение типа t;

2) х, где х - свободная переменная, получающая значени при отождествлении шаблона р с значением е;

3) с р /. . . р где с ее - к-арный конструктор типа t, i шаблон типа tj.

Синтаксическое отождествление значения х с шаблоном со я: ется сильным ограничением общей формы операции синтаксическ отождествления, описанной в главе I, так как проверка вьво мости =>'х трансформируется здесь в индуктивную проверку структуре шаблона равенства (идентичности) конструкторов та лона и значения.

В языке спецификаций используются только линейные шаблс для котоых операция отождествления реализуется намного эффект нее. Шаблоны используются в левых частях равенств из D, а таи В выражениях вида case einp;:e/|... |рп:еп end, KOTOJ является синтаксическим эквивалентом операции отождествления щего вида, описанной в главе I. Здесь е, е ..., ел - некото! выражения, рр„ - шаблоны Рассматриваются различные эь валентные преобразования, с помощью которых можно упрощать мантические равенства из D.

В п.4.3. рассматриваются метауровневые средства специф]

ции. Если сопоставить конструкторам некоторые функции, то структурное значение можно понимать как суперпозицию, которую можно также редуцировать к значению с помощью операцию редукции eval. Контекст связываний для конструкторов указывается в конструкции letcanstr 0 in е.

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

В п. 4. 5. рассматриваются недетерминированные параллельные процессы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

2. Всесторонне исследована операция отождествления с шабло-

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

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

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

1. Язев А. М. Описание семантики параллельных процессов с помощью обощенных функциональных грамматик. / ЛГУ-JL : 1987. - 19 С. -Деп. в ВИНИТИ 17. II. 87. - N8097-B87.

2. Язев А. М. О методе функциональной спецификации семантики параллельных программ и процессов. // Вычислительная техника в автоматизированных системах контроля и управления: Межвуз. сб. науч. тр. - Пенза: Пенз. политехи, ин-т. - 1989. - Вып. 19. - С. 53-57.

3. Язев А. М. О классе языков, порождаемых обобщенными функциональными грамматиками. // Проблемы теоретической кибернетики: VIII Всесоюз. науч. конф.: Тез. докл.: В 2ч.- Горький. - 1988ч. 2. - С. I7I-I72

4. Язев А. М. Представление и реализация сложноструктурированных данных, ориентированных: на параллельные процессы. // Тезисы докл. Всесоюз. научно-техн. совет. "Программное обеспечение ново! информационной технологии". - Калинин. - 1989.- С. 104-105.

ПУБЛИКАЦИИ