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

ЛЖЧГРАЛСШ 1ШИШ АВ11*ЖОККОГО ПРКЕОРОСТРОИЩ

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

ГЛКОЗ Вячеслав Ивчяов'п

Ш 031.1-12:530.2

А!ШПа ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И СИГГЕЭ ПР0ГРА12! С ИСПОЛЬЗОВАШИ! СИМВОЛЬНЫХ ОТЕЛ.

Спэцпальность 03.13.11 "Математлческсэ и програишсэ обэспэчонкэ вычислительных !/лиин. комплексов, спотси и сетсД."

Автореферат диссертации па соискание учено! стопзта кандидата технических наук

Ленинград 1091

Работа выполнена на кафедре "Вичяслителышх Ленинградского института авиационного приборостроения.

систеи"

Кучный руководитель1 кандидат технических наук В. В. внльчаков

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

доктор технических наук В.Д. Ефремов

кандидат технических наук В.И. Шкиртиль

Вздуц.1Я организация: институт кибернетики

»ш. В.М. Глушхова АН УССР

Завита состоится "_"_ 199_ года в__

часов на заседании специализированного совета K0S3.21.03 при Ленинградском институте авиационного приборостроения по адресу: Ленинград, ул. Герцена 67.

С диссертацией ыохно ознакомиться в библиотеке ЛИАП.

Автореферат разослан "_"_199_года.

Ученый секретарь

специализированного совета К063.21.03

кандидат технических наук /'"А'/В. В. Фильчаков

| ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблеми. Кахдал большая программная система является уникальной разработкой, ока ииеет свор архитектуру, свои особенности реализации и своя стиль. . Доказательство правильности больших готовых программ на современном этапа невозмогно. Более того, часто невозможно выполнить даго исчерпывающее тестирование таких систем. Эти Факторы создали предпосылки для упорядочения процесса проектирования программ так, чтобы угэ во время разработки постепенно оценивалось качество создаваемого продукта. Появляется различные технологии проектирования. системы автоматизации программирования, рекомендации по научной организации труда прог-раьеягетов. Поено сказать, что основные успехи достигнута в создании таких систем автоматизации прогргшафозаняя, которкэ позволяет организовать труд большого количества разработчиков, следить за корректностью и согласованностьа процесса проектирования, выпускать технологаческуп документации. Но такие системы,как правило, автоматизирует лишь некоторые рутинш:э операции в стандартно!! топюлогнн программирования. Наибольшая часть контроля ошибок приходится на процесс кодирования програиш, тогда как наиболее серьезные ошибки возникают на ранних стадиях проектирования: системен анализе и алгоритмизации. Поэтов целесообразно начинать автоматизация п формальный анализ именно на этапе алгоритмического проектирования и поддергивать весь процесс создания програшного обеспечения от составления алгоритмов до получения объектного кода, обеспечивая при это»! заданные показатели качества. ,

Большинство известных систем авторатпэацнл ориентировано на разработку программ для однопроцессорных ксипьптороа. Однако осноз-нш направлением увеличения быстродействия ЭВМ является создание многопроцессорных систем, сетсЯ а комплексов, требусяих специфического программного обеспечения. Хотя з отой области и супесгвуот много разработок и реализация, тем нэ менее отсутствует стандартизация как на архитектуру, тгд и на программное обеспечение. Появляется большое количество языков програмт-гпровапия, ориентированных на конкретную архитектуру. Различия мегду языками иногда настолько большие, что практически невозможна автоматическая трансляция с одного на другой. В то га время возможна разработка параллельных алгоритмов, которые го гут бить транслирован;} в различные параллельные языки. Поэтому большое значение ткет автоматизация проектирования параллельных алгоритмов, автогатизацпя п:с анализа и модели -рования в зависимости от условна реализации п архгггектурн исполни г:ж ородстп.

Основаниец для выполнения работы послужили комплексная целевая программа развития САПР бортового оборудования в XIII пятилетке, утвержденная заместителей министра авиационной промышленности и научно-техническая программа 0.08.01, утвержденная постановлением ГКНТ СССР. Госпланом СССР. Академией наук СССР. Работы проводились в рамках НИР по темам: "Разработка и исследование инструментальных средств автоматизации проектирования программного обеспечения Б1ШС". "Исследование эффективности параллельных алгоритмов и их реализаций".

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

Основные задачи, решаемые в работе, состоят в следунаем:

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

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

разработка средств анализа логической корректности алгоритмов,

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

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

Методы исслод звания. В исследованиях были использованы : теория алгоритмов, теория Формальных языков, теория сетей Петри, математическая логика.

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

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

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

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

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

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

- интерактивный графический ввод алгоритмов и сетей Петри,

- трансляция алгоритмов в Формальные модели и тексты программ,

- анализ свойств алгоритмов на базе сетей Петри и их расширений.

Данная система применена в создании технологии разработки программного обеспечения бортовых вычислительных систем, для анализа сетевого программного обеспечения персональных ЭВМ.

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

Основные положения, выносимые на защиту:

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

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

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

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

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

- Институт информатики и математического моделирования технологических процессов Кольского научного центра АН СССР,

- Ленинградское научно-производственное объединение "Электро-

автоматика".

- Научно - исследовательский институт ПКИ "Терминал". Апробация работы. Основные результаты работы докладывались и обсуждались на следующих семинарах и конференциях: 1-ая Всесоюзная научно-техническая конференция "Практическое применение современных технологий программ, пакетов прикладных программ в вычислительных системах и сетях ЭВМ", Днепропетровск, 1983;

Всесоюзная школа-семинар по внедрению в народное хозяйство ПЭВМ. Минск, 1988;

Всесоюзное научно-практическое совещание "Электронно - вычислительная техника в общеобразовательной школе", Новосибирск, 1988; Всесоюзная научно-техническая конференция "Диалог человек-ЭВМ". Свердловск, 1989;

Всесоюзная научно-техническая конференция "Перспективы развития вычислительных систем", Рига, 1989;

Научно-практический семинар "Технология проектирования программных и аппаратных средств вычислительных систем". ЛШПП, Ланинград, 1989. 1990;

10-й Всесоюзный симпозиум по избыточности, Ленинград, 1989; Научно-техническая конференция "Математические и программные методы проектирования управляющих и информационных систем", Пенза, 1990; Международная конференция "An Intellegent System for Disributed System Software Design". Москва, 1990.

Публикации. По теме диссертационной работы опубликовано 20 работ.

Структура и обьем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы. Основной текст содержит 118 страниц. Список литературы содергат 111 наименований.

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

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

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

-Э-

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

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

объекты: множество переменных М = { и, .....п„>, множество опера-

лз

цнй Г = ( ft.f.....fk). Функция входных переменных InM : Г —* к ,

Функция выходных переменных OutM : F —► К1. Функция выходного управления InC : F —► (Г3)0 .Функция зходного управления OutC : F —» (F03)3. Простой алгоритм определяется как набор ( M.F.InM,OutM,InC, OutC ).

Система алгоритмов вводится путец определения ?шсгества простых алгоритмов и отношения иерархии на этсч ¡гногзство. Пусть дано taicrecTDO А = \ , А,.....Аг >, где Ai - простой алгоритм ( А, = (

г

it . F. . Inf^ .OutR , IrC, .OutCj }). Введен два множества ¿? = и F ,

Г Г Г 1 =1

n F. =0 = и м , nil =0, которые вклпчавт в себя полный набор спера-1 и t =i t =i

цкй и переменных всех прости алгоритмов из ьшокестза А. Введем отношение иерархии следусаув Функцию Н с £ FA. Система алгоритмов это набор (А,Н). "

Вычислительным процессом над множеством операций 7 называется слово над алфавитом F(xeF'). Данное слово определяет порядок выполнения операция в вычислительнем процессе. Мноеэстео допустимых вычислительных процессов для алгоритма иоззга рассматривать как некоторый Формальный язык над алфавитом операций. Язык могло описать с помоцьв грамматика, козно такге установить класс языка, его свойства.

Утверждение 2.1. Для управлявшей структуры последовательно г.-алгоритма A=(F,C, f о. Г^) мпогество допустимых вычлелительчьг процессов является автоматным языком над алфавитом F.

Утверждение 2.2. Пусть A(=(F,, С,, f,s. fia). Аа= (Fa, С f S- f,п fa ява последовательных алгоритма. Тогда д'

алгоритма A =(F.C,CP,f0,fe). где F = F, и F„u {fa>u<fe>. С=С, и С

СР= <(Гг.Г13). (Г^Г^). (1\(Гав.Гв)>, множество допустимых вычислительных процессов является автоматным языком.

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

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

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

Для описания синтаксиса графосимволического языка и для описания правил генерации текстов программ и символьных сетей из системы алгоритмов используется аппарат так называемых графовых грамматик . Графовая грамматика - это набор (М.Т.З.Р), где К - множество нетерминальных символов, Т - множество терминальных символов, - стартовый символ, Р - множество продукций вида (а —► р, Vе, Vе), где а е N. Р = (У^, - некоторый граф с множеством вершин Уд и множеством дуг Ер, V3 с - множество начальных вершин, Vе с - множество конечных вершин. с ¡1 и Т. Граф Са = (Уа,Еа) называется непосредственно-выводимым из графа = (У( ), где Уа с К и Т. V, с N и Т, в соответствии с продукцией Рд = (а —► р, Vе). если граф может быть получен из графа С, по следующему правилу: в графе вершина а заменяется на граф Р, каждая дуга вида (х.а) заменяется на множество дуг (х.у), где уеУг, а каждая дуга вида (о.х) заменяется на множество дуг (у,х). где ус Vе. Количество дуг, заменяющих каждую (х.а), равно | V5!, а количество дуг. заменяющих каждую дугу (а.х), равно | Vе|. Непосредственная выводимость графа из графа в соответствии с продукцией Р обозначается С,

в.. Граф С, непосредственно выводим из С, (в й.), если суя Я г р! ж

одествует некоторая продукция Р такая, что -х—» ва. Транзитивное замыкание отношения => порождает отношение выводимости

Графовая грамматика (И.Т.Б.Р) порождает язык I. который является множеством всех графов ^ > таких, что 3 => , и для

любого множество вершин образуется из множества терминальных символов.

В качестве Формальной модели алгоритма, используемой для анализа его свойств, применяется символьная сеть. Символьная сеть отличается от простой сети Петри определением маркеров и правил срабатывания переходов. Структура символьной сети Б=(Р,Т,К), где Р"{р, tpa,...,РП> - конечное множество позиций, п^О,

Т={1 Ла,... ,t > - коночное множество переходов, n 2: о. РлТ= 3 . ЮРхТШхР—*Н - отношение инцедентности. Структура символьной сети является структурой ординарно;! сети Петри, т.е. каздый переход и позиция связакп не более, чем одной дугой. Кавдая позиция сикволь-ной сети маркируется некоторым количеством маркеров. Маркировка M сета представляет собо?I вектор маркировок наглой позиции. Маркерами в символьной сети являются слова, состаяленнкэ из сиголов алфавита А , а маркировка M определяется как отображение: р —» (Aif)a, (д")и-АихАкх ... .

Маркировка символьной сети ыогхет изменяться посредством выполнения переходов. Вид удаляемых и добавляе.'.йгх маркеров определяется с помоаью правил, которые подобны продукциям в системе Поста. Каздое Taicoe правило когно представить как несколько продукций з системе Поста, которые имеют несколько левых частей и несколько правых. Символьные сети такге, как и сети Петра, мояго подвергнуть Формальному анализу. Кэиу свойствами онкольной сети и аиало гичнкмн свойствами сетей Петри существует взаимосвязь. Кахдой сп-.золыюй сети молю поставить в соответствие соть Потри, в которой символьные маркеры заменены на простые маркеры сети Потри, а правила выполнения переходов стандартны. Пусть символьная соть С= (P.T.K,Л, Г,МЭ). ей соответствует сеть Петра С = (Р,Т,К,сг(Мо )), здесь сг: Рх(Ам)и —>N,cr(p1 ,Н) равна количеству слов в млрклровко M в позиции pt. Нигэ приведены основные утверждения, касзгапеся сзязп свойств символьных сетей и сетей Петри.

Утверждение 2.4. Если переход ttсимвольной сета (P.T.K,А,Г) возбужден в маркировке H , то переход Ц сэгл Потри (P.T.K) возбужден в маркировке сг(М).

Утверждение 2.5. Если в символьной сзти (Р,Т,К,А,Г) маркировка На непосредственно досгиит из маркировки М( после выполнения перехода t, то з сети Петри (Р,Т,К) маркировка ff(Ma) непосрэдствеп-но достигииа из маркировки cr(Ht ) после выполнения перехода t.

Утверждение 2.6. Все допустимые последовательности выполнена переходов символьноЯ сети (P,T.F,A,r,M0) допустимы в простоя сети Петри (P,T,F,o(!l0)).

Следствие 1. Если сеть Петри (Р,Т,К,сг(Мэ )Заканчивает работу, то любая символьная сеть (Р,Т,К,А,Г.Мо) заканчивает работу.

Следствие 2. Если сеть Петри (Р,Т,К.сг(М0)) ограничена, то любая символьная сеть (Р,Т,К, А,Г\М0 ) ограничена.

Символьная сеть позволяет определить два вида языков. С одкоз стороны, это языки, составленные из символов переходов, а г

другой, это языки, составленные из воэмозшых маркеров в позициях сети. Пусть R(C,H0) - множество достижимости символьной сета С. Пусть L(p) = < а е А+/ В М б R(C.M0) & а € М(р) >. L(p) называется языком позиции р символьной сети. Языком маркеров символьной сети

п

называется объединение языков всех позиций L = U L{P. ).

п 1=1 1

Утверждение 2.7. Для любой системы Поста (2, П, А) можно построить символьную сеть С такую, что ее язык маркеров будет совпадать с многеством теорем системы Поста.

Для простых сетей Петри вводились различные расширения, основанные на сопоставлении элементам сети некоторых дополнительных атрибутов, изменяющих правила возбуждения и срабатывания переходов. По аналогии с временными сетями каждому переходу символьной сети шею сопоставить целочисленную Фиксированную задержу срабатывания. Пусть С - символьная сеть, т:Т—> N-Функция, отобразашая множество переходов Т сети С в множество натуральных чисел. Тогда Св1=(Св.т)- временная символьная сеть. Семантика работ Св1 относительно С изменяется так же. как и семантика временной сети относительно сети Петри. Рассмотрим соотношение свойств временных Ct, символьных С,, символьных временных Св1 и простых сетей Петри С.

Утверждение 2.8. Пусть С=(Р,Т.1,0) - простая сеть Петри, Ct= (С.т) - временная сеть, Св=(С,А,Г.М0) - символьная сеть и Csl= (С,т) - временная символьная сеть. Тогда справедливы следующие соотношения: Llt< Ц, Let* LB, LBt< L, Ls<i Lst, L^, где L - префиксный язык с Функцией поыечения, уникальной для каждого перехода, и без X - переходов.

Следующее расширение, которое здесь рассматривается - строго иерархическая символьная сеть. В такой сети каждому переходу может соответствовать подсеть нижнего уровня. Формально символьную строго иерархическую сеть можно определить следуюаим образом. Пусть С = <С0,С,.....Сп> - конечное множество символьных сетей, где С4 =

(Р. ,Т. .0. Л. .А. .Г. ,Мо1). Пусть £ Т = U Т.. П Т. = 0. ЕР = и Р.. n 1 =i »=« 1 =»

П Р. = 0. функция иерархии моют быть определена как X : £ Т •» С. 1 =i

Можно ввести отношение Х°е Сх С и X1 е £ Т х £ Т. Для Ц 6 £ Т и t, с Т^. Имеет место C1X°CJ, если X(t, ) = Cjr Це Ct. Для отношений иерархии должны выполняться следующие условия: а) У С,е С У С,€ С (CjX'CJ ♦ ),б) 3 Сое С ">3 С,€С : С,ХвСв.в) У С,€ С, С,*

С03 Cj € С (CJX°C1) . Если X(tt) = 0 , то переход ts называется простым или несоставным. Если X(tj) = Cj, то Ц называется состав-

нку, а сеть С^ называется внутренней сстьа для перехода Ц. Рассмотрим свойства языков иерархической символьной соти. Пусть Lt терминальный язык с уникальной Функцией попечения без X - переходов для простой сети Ct. Если не накладывать никаких ограничения на структуру сетей, составляющих иерархическую сеть, то справедливо следуваее утверждение.

Утверждение 2.9. Произвольная символьная сеть не мозеот породить свободней язык L = {а.аа.аав,в,ва,ваа>.

Утверждение 2.10. Класс строго иерархических символьных сетей строго мощнее классов символьных сетей и простых сетей Петри.

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

Утверждение 3.1. Пусть даны сеть Петри С = ( Р.Т,К,М0 ), Р -{р>. Т = <t>. К : РхТ и ТхР —» U, И : Р Н, Мо с !í. п систем Поста PS = ( 2.А.П ). 2 = Р и {,>, А = aS.aS.....aS. n=|P|. at =

i=M0(Pl). п { b,s,.b2sa.....bnsn - b;s,.b;s,.....b;sn >.

¡n|=|TI.Vt1eT 3 nten :

П. = b S ,b S.....b S -» b'S ,b'S.....b'S

1 i 1' a a.....n n « » ' a a* ' n n

bj = pj . 1 = К((Pj )) bj = p¡ . 1 = К((Ц.рл)).

Определим отображения:

1. V : M —» Этакое, что V(M) = а, ,аа.....ап , где а, 3 pj.

l=M(pt).

2. V"1: 2* —► М такое, что V"' ( at ,аа.....an)=M • гго ai " Р» •

М(р, )=1.

Пусть R(C) - множество достижимых маркировок сети Петри С, T(PS) -

множество выводимых теорем в системе Поста PS.

Тогда

1. V М 6 R(C) 3 а б T(PS) а а = V(M).

2. V а e T(PS) 3 М е R(C) & М = V-1(a).

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

Далее в третьей главе описываются правила построения символьных сетей, описывающих информационную и управляющую структуры алго-

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

Рассмотрим структуру маркировки, описывающей поло памяти. Будем считать, что каадая переменная из И имеет имя, например. r.L. Пусть I - алфавит, та которого строятся значения переменных из М. Тогда алфавит, из которого могут быть построены маркеры для поля памяти, представляет собой объединение 1ими{,>и{=>. Здесь запятая и знак равенства является специальными символами, позволятоими отде лить значения переменных от их имен. Структура маркера, описываюае-го значения всех перэкенных, должна быть следующая-'

п,= г,. п2 = ха.....= хп

Здесь х, - слово над алфавитом I, описываюаее значение переменных «а,.

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

^ т1= -'Б, - ^

Здесь слово должно представлять собой некоторую комбинат® символов За и символов из алфавита I.

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

Четвертая глава содержит описание методов анализа свойств сетей Петри и символьных сетей. Все методы основаны на построении графа достижимости. В графе достижимости простой сети возможна потеря информации за счет появления символа ш. Однако в некоторых случаях можно избежать использования символа ш. Вместо него можно использовать выражение вида а+пЬ, где а и Ь - константы, п - переменная. Символ ь> появляется, если на дереве существует цикл от маркировки М1 до маркировки Маи Ма>М1. тогда из маркировки Ма можно запустить те же переходы, что я из М1. В результате вместо Ма можно получить маркировку Ма'= И, + п * (Ма-М,). Здесь п - количество запусков последовательности переходов, ведущей от М, к Ма. В первом параграфе предлагается алгоритм, получающий для некоторых - маркировок параметрическую зависимость от количества срабатываний переходов. Для дальнейшего определения достижимости требуется решить систему линейных алгебраических уравнений. Параметрический граф достижимости состоит из вершин, каждой вершине 1 соответствует расширенная маркировка МШ. В маркировке сети Петри каждый элемент является числом, различаются значения этих чисел. В расширенной марки-

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

а( п1 + аапа +. ..+ а|сп,с + Ь, где а( ,аа.....ап,Ь=сопБ1. Выражение

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

Следуюпшй метод анализа достижимости основан ка инвертировании направления дуг в сети. Пусть С = (Р.Т.1.0) - граф сети Петри, тогда С = (Р.Т.0,1) - граф инверсной сети Петри. Тогда справедливо следусаее:

Утверждение 4.1. В сети С достижима маркировка МП( ко маркировки М тогда и только тогда, когда в инверсной сети С из маркировки достижима маркировка М,.

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

Утверждение 4.2. Но возникает бесконечных цепочек обращений к доказательству предиката "принадлежит.дереву (М^ДМ^)" -

начальная маркировка) баз возникновения возврата.

Утверждение 4.3. Доказательство предложения "принадле-)" заканчивается.

• Утверждение 4.4. Для любой маркировки М^ принадлежащей графу доспшшэсти. доказательство предиката "принадлежит лереву (М-^Мд)" заканчивается успеижо. Для лххЗой маркировки не принадлежащей

графу достижимости, доказательство предиката "принадлежит_дереэу (М^Мф)" заканчивается неудачно.

Пятая глава посвяаена описанка инструментальной системы, авте-штизнруваей этап алгоритмического проектирования. Данная система поддерживает проектирование от создания структуры иерархии алгоритмического проекта до получения текстов програм-л. реалнзув\;г.;< г.что-

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

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

В заключении формулируются основные выводы работы:

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

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

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

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

5. Иерархическая структура системы алгоритмов обеспечивает-линейный рост сложности анализа при увеличении размера системы. Сложность анализа определяется как Ct «гг, где Ct - сложность анализа одного модуля, п - количество модулей.

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

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

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

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

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

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

11. Из символьной сети может быть получена простая сеть заменой символьных маркеров ка обычные. Любая последовательность срабатываний, допустимая в символьной сети, допустима в соответствующей сети Петри.

12. Символьная сеть позволяет описать управляющею и информационную структуру алгоритма, возможно символьное тестирование выполнения.

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

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

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

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

'. Жаков В.И.. Пыхалов И.В.. Фкльчаков B.D. Повышек:::. сфзок-

тивности вычислительного процесса в задачах статистического моделирования // Вычислительные машины, комплексы я сети: cd. научи. тр. / Ленингр. ин-т авиац. проборостр. 19SQ. Вып. 182. С.86-93.

2. Яаков В.И., Пыхалов И.В., Фильчаков В.В. Программное обеспечение для статистического моделирования на персональной ЭВМ// Диалоговые системы и персональные ЭВМ: Меавуз. сб. научн. тр./ ЛИАП. Д.. 1987, Вып.187. С.38-45.

3. Егоров А.Н., Жаков В.И., Пыхалов И.В. Асинхронный итерационный метод для распределенных вычислений // Распределенные вычисления я системы на СБИС: Нежвуэ. сб. научн. тр./ ДИАП, Д.. 1988. С.72-81.

4. Яакоз В.И., Щекин C.B. Методы и средства логического анализа моделей этапов полета//Мешзуз. сб. научн. тр./ОЛАГА.Л..1888. С.53-03.

5. Жаков В.И.. Пчелкина А.А., Пыхалов И.В., Фильчаков В.В. Моделирование параллельных процессов в задачах метода ! !снто-Карло // Нехвуз. сб. научн. тр./ ОЛАГА, Л., 1988, С.75-83.

6. Жаков В.И., Пчелкина A.A.. Фильчаков В.В. Инструиегггалъг.оэ средство разработки функционального проекта систэа для распрэ-деленных вычислений// Всесоюзная школа-семинар по внедрении п народное хозяйство ПЭВМ. Тез. докл. .ч.2. 1'j.hck, 1938, С.70-72.

7. Лаков В.И., Смекалов A.B., Фильчаков В.В. Использование алгоритмической избыточности для контроля систолических вычислений. 10-й Всесоюзный симпозиум по избыточности, Л., 1989.

3. Жаков В.И., Корсакова Н.В., Никитин A.B., Фильчаков В.В. Структуры данных. Уч. пособ. ЛИАП, Л., 1990. 75с.

9. Ясаков В.И.. Фильчаков В.В. Програшочя система для разработай параллельных алгоритмов. ОФАП МГУ, инв.Н Н378384 от 10.12.1Е90.

10. Жаков В,И., Фильчакоз В.В. Инструментальная система автоматизации проектирования параллельных алгоритмов./ Тез. докл. научн.-технич. коиф. "!'лтематические н программные методы проектирования управляющих и информационных систем". Пенза. 1S90.

11. ¡Гаков В. II., Фильчакоз В. В. Программная система для спецификации и анализа алгоритмов распределенной обработки дашнх./Сб. науч. тр. "Методы л средства вычислительного эксперимента. Апатиты: изд-во Кольского научного центра АН СССР, 1990. С. 20-27.

12. Жаков В.И., Фильчакоз В.В., Пекин C.B. Описание сетей Петрл с помощью систем Поста.// Материалы научн.-практич. семинара "Технология проектирования программных н аппаратных средств вычислительных систец". ЛДНТП, Л., 1990. С.24-29.

13. Игнатьев М.Б., Жаков В.И., Пчелкина A.A.. Фильчаков В.В.

Програимная система оценки временных характеристик параллельных процессов. ОФАП СССР, МГУ, инв.К М88188 от 8.12.83.

14. Сильчаков В.В., Жаков В.И., Пчелкина A.A. Концептуальное проектирование программных систем //Практическое применение современных технологий программ, пакетов прикладных программ в вычислительных системах и сетях ЭВМ/ Тезисы 1 Всесоюзной научно-технической конференции, ч.1. Днепропетровск. 1988.

15. Бргоэовский A.B., Каков В.И., Фильчаков В.В. Интерактивная система анализа и моделирования параллельных вычислительных систем // Технология проектирования программах и аппаратных средств вычислительных систем. Тез. докл., ч. 1.Л., 1989, с.34-33.

18. БргеэозскнЗ A.B., Каков., Фильчаков В.В. Диалоговые системы поддергки проектирования программных систем. Тезисы докладов всесовдн. науч.-технич, конферекщш "Диалог человек-ЭВМ", Свердловск: 1989, ч.2. с.79-81.

17. Бргзэовсккй A.B.. /Глков. В.И. , Фильчаков В.В. Программные средства для подвергни проектирования и анализа распределенных вычислительных скстеи. Тезисы докл. научн.-технич. конференции "Перспектива развития вычислительных систем". Рига, 1SS3.

18. Брезэовский A.B., Каков В.И., Фильчаков В.В. Интегрированная систем анализа и цодолирования параллельных вычислительных систем // "Технология проектирования программных и аппаратных средств аичислатодышх снстеа": Материалы научно-технической конференции / ШТП. Л.. 1929. с. 70-71.

19. Бргозовский A.B., Гаков В.И., Фильчаков В.В. Автоматизированная технология проектирования программного обеспечения распределенных шчнеявтельшве систем./ Материалы научн.- практнч. сешшарг "Технология прооктирования программных и аппаратных средств вычислительных систем". ЛДНТП, Л.. 1830. С. 14-17.

£0. Brzhozovsky Л.V., Filchakov V.V., Zhakov V.l. An Intellegant Systea for Dlsributed System Software Design //Advanced Infornation Processing/ H. Schv/artzel.I. Mizin (Eds. )-Springer -Verlag: Berlin Haidalborg. lS30.-p.60-63.