автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Функциональное моделирование в системах обработки данных



ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР АН АРМ. ССР

На правах рукописи УДК 681.3.068

ХАЛАТЯН ИГОРЬ ГУРГЕНОВИЧ

ФУНКЦИОНАЛЬНОЕ МОДЕЛИРОВАНИЕ В СИСТЕМАХ ОБРАБОТКИ ДАННЫХ

(05.i3.i6 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях)

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

Ереван - х990

гУА'к

Работа выполнена в Вычислительном центре' Академий, Наук Армянской С(

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

кандидат физико-математических наук МАРАНДШ Г. Б.

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

доктор технических наук БУДАГЯН Э. А.

кандидат физико-математических наук ВАРГАНОВ С. Р.

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

Институт кибернетики им. В. М. Глушкова АН УССР.

Защита состоится 1990 г. в * ' _ часов

на заседании специализированного совета 2.1 Я/по защите

диссертаций на соискание ученой степени кандидата технических наук при Вычислительном центре АН Армянской ССР и ЕГУ по адресу: г. Ереван, ул. П. Севака, 1.

С диссертацией можно ознакомиться в библиотеке ВЦ АН Армянской ССР и ЕГУ.

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

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

специализированного совета л I I г ■ )

д.ф.-м.н.„ профессор С С. С. АГАЯН

I " 3 "

:2 I

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

I

Урций /

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

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

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

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

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

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

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

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

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

- апробация системы в области моделирования электроннш схем, моделирования блоков атомных ста!!:-.;;й, систем связи.

Научная новизна. Предлагается архитектура системы моделирования объектов, описываемых системой многопараметрических уравнений со сложной структурой обратных связей.

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

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

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

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

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

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

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

Реализация результатов. Данная работа проводилась в соответствии с планом основных научно-исследовательских работ ВЦ АН Арм. ССР и ЕГУ по целевой комплексной научно-технической программе СЭВ п. 1.1.6.1.4.2.1.

Для введения задания в ЭВМ семейства ЕС разработан специальный, простой в обращении язык, позволяющий удобно взаимодействовать с ЭВМ в диалоговом режиме.

Выполнена программно-алгоритмическая реализация системы.

Комплекс программ, обеспечивающих решение перечисленных выше задач и полную работу системы программ, написан на языке

ПЛ/1 и конкретно реализован на'ЭБМ ЕС-1045.

Результаты работы используются:

- в Северо-Кавказском филиале НИИ систем связи и управления;

- в. Ереванском НИИ математических машин.

Ожидаемый годовой экономический эффект составляет 75 тысяч рублей.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на:

- открытом научном семинаре•сектора теории алгоритмов и автоматизированного синтеза программ ВЦ АН Арм. ССР и ЕГУ (1985-1988 гг.);

- общем семинаре ВЦ АН Арм. ССР;

- общем семинаре в Северо-Кавказском филиале НИИ систем связи и управления;

- Третьей республиканской конференции аспирантов Армянской

ССР.

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

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

Основной текст диссертации содержит малшнописных страниц.

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

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

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

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

?<(*) С, СЬ. ь, ... , ГмЗ (к)

.........................и)

Рн (ж) <2= См С Ъ, . . ■ , Г* 7 (к)

.•до кг.:ядос С* - функционал, представленный с помощь;-, еупер-псз1ГЦ.!И известны* базиены* функций и предикатов, а таьке "¡ункппональны:* переменны* Г,, Р31 • • ■ > , которые

применяется к переменным х . •

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

Пусть дана система рекурсивны", функций над область« /-- (<) ^ т, С Г,, Ъ, РмЦ М

Г"! (*}

где каждое ~Сс - функционал, представленный с помощью суперпозиции известных базисных функций и предикатов, а также функциональных переменных Р* , которые

применяются к переменным х = х-,, л,, . ..,.<«>.

Для конкретного набора 2)'е[) последовательность термов То Тг, Тг > которая называется вычислительной последова-

тельностью для Л' или вычислением Рк(2>') , строится следующим образом;

1. Первый терм То есть Рк. (2)')

2. Терм Тс+ц получается из Тс для каждого ¿>=0 за два шага:

а) подстановка: некоторые вхождения р1,Рг, Р*

в терме Тг .одновременно заменяются на т, С Р-,, , -Р"1 ,

Ъг. Г />, Р-г. , "V Р

ТСп С , • ••) Р* .7

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

Последовательность конечна, и Тк - последний терм в этой последовательности тогда и только тогда, когда Тк. не содержит вхождений символов Pi.Fi, —, Рм , т. е. если Тк. - элемент множества 2>

По правилу вычисления " ~С " можно судить о том, какие вхождения Р, (Е<) , Гг. С Е^)^...) Рп ( необходимо заме-

нять на

С Ъ, Р., - ( £■)

т«. Г Г.,, - --, О«-)

-г- Г Г р, Рл, 3 (£»0

I, г» (. ' ( | / • - - »

На каждом шаге подстановки мы заинтересованы только в "разумных" правилах вычисления, которые для каждого терма Vг , возникал-щего во время вычисления и содержащего вхождения символов р) 1 рг рм , будут определять непустую производимую

подстановку.

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

1. Первое правило. Правило самой левой - самой внутренней замены.

Среди всех вхождений функциональных символов Р<, . заменить то Р с (/ < I «; м) , аргументы которого

свободны от вхождения символов Р1/ /г ( . .. / рм , й которое расположено левее всех функций, имеющих аргументы, свободные от вхождения символов Р,, Рг, ... , Рн

Обозначим данное правило через

2. Второе правило. Правило самой правой - самой внутренней замены.

Среди всех вхождений функциональных символов Pi.Fi., заменить то р ^ (1 < I ё м) 1 аргументы которого

свободны от вхождения символов Ри рг 1 . . . ( р^ , и которое расположено правее всех функций, тлеющих аргументы, свободные от вхожденич символов Р1 ^ Гг , ... , Рн

Обозначим данное правило через

Во многих существуищих языках программирования используется правило самой левой - самой внутренней замены ¿х , в частности компилятор языка ПЛЛ применяет именно это правило при вычислении рекурсивны' прегради.:.

В системе АПС применяется правило саг.^ой правой - самой внутренне!": закснь . Ст; вится задача доказать, что значение функции Рк ( 1 ^ к. & м) из системы ( / ) на нао'оре

Ъ' б. О , вычисленное с помощью правила ¿х , всегда совпадает со значением этой функции, вычисленным с помощью правила Ях .

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

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

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

а) либо выдает результат;

б) либо вызывает себя на входных значениях X' , где X' = Р ( к) • Можно сказать, что работа рекурсивной

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

Обычно рекурсивная функция задается в виде

где COND (1), CONÙ (2), • - - , CONDin) - условия, a LINE (О, l//V£(z), ... ) L)nE(N), инструкции

для выполнения.

Рассмотрим работу рекурсивной программы по вычислению рекурсивно заданной функции, изображенной выше. Сначала выполняется проверка CONÙ (1) . Если проверка coNù(i) дает ответ "истина", то значение функции есть значение утверждения L/NE(l) . Если проверка COND(i) - ответ "ложь", то выполняется проверка COND (г.) . Процесс ид.-т тякпл образом до тех пор, пока не будет обнаружена первая из превье "л COND (t-) , дающая значение "истина". Значение » о,v.r.

случае есть значение утверждения ¿/NE f-z) . Если к:: с;..::г из проверок не окажется положительной, то значение 'унк*ц:;: -.сть значение утверждения и!NE. ( A/'tf) . Рекурсии вводится

F (к) =

t. INE (N) ¿-/NE ( N1-1)

LINE if) LI NE (Z)

CONÙ СN)

CO/V 0(1)

ceND (г.)

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

Пример I. Рассмотрим знакомую нам рекурсивную программу, вычисляющую факториал числа X .записанную в упрощенном виде

F : PR.ОС (X) ;

IF Х=| THEM RETURN (О;

ELSE RETURN [К' F(X-I));

END;

Чтобы проследить, как работает такая программа, выполним ее для некоторого конкретного значения аргумента X , например для X = Ч

F (Н) = '4 • F(Ъ) Так как условие 4=1 ложно, то

F (4) = * • F IS) Теперь нужно вычислить F (з) т. е. рекурсивно обратиться к F .

_ F (2.) так как ПРИ вычислении F (з)

условие 3=1 ложно, то "

4-3-2- F(1)

Р (3) = 3- Р (2.)

так как условие 2=1 ложно, то = 2 • Р(1) .

_ ^ 3, • 2 • 1 так как У^0®116 истинно» т

1

= .24 = 4/

' Пример-2. Рассмотрим следующую рекурсивную функцию (функцию Дккермана), применимую для любой пары неотрицательных целых чисел X, , Х2 • Программа, реализующая, эту функцию, имеет вид

А : PR.DC ( X,, Хг);

Х, = 0 тнаы иетигг.ы (

ei.se /я хг=.0 ти£Ы аети/г-м (А

ei.SE Ретины (л ! А (х,, хг - {))).

Еыо-

Проследим, как выполняется такая программа для некоторой пары X» и *г - Например, для X, ~ 1 , Хг = 2.

4 = А (0-,А(р,А(1,1)))

= /? {9, А (0, А (1,0)))

= А (0, А (0, А (ф,Щ = А(0, А (0,г)) = А (0,3,)

= ч

так как условия Х< = 0и Хг = 0 ложны, необходимо вычислять А (1,1) ~ рекурсивное обращение

так как условия Х1=0 и Хг = 0 ложны, нужно вычислять А (1,0)

так как условие У.1-0 ложно, а Хг = 0 истинно

так как Х> = 0 истинно, следовательно, А (0,г}= 1+1 -2

так как X» =0 истинно, следовательно, А (0,2}-=2+Л±з

так как X * = 0 истинно, следовательно, А (С,Л)= 3+1 = 4

Из этого примера следует, что при выполнении вычислений для рекурсивной программы мы можем сталкиваться с неоднозначностями, которые требуют уточнений. Например, в приведенных вычислениях при обращении А (0, А (1,1)) . мы предполагаем, что

А (1,1) должно быть вычислено прежде, чем мы продолжим вычисления, относящиеся к внешнему обращению к . Если отдать предпочтение вычислениям, связанньм с внешним обращением, то вычисления должны были бы идти в следующем порядке:

А (1,2)' А (0, А (1,1))= А(1.!)+1- А(0, А(1,0)) + 1ш - (& (1,0) + 1) + 1= (А + + 1 = 4

Значение A(i,Z) остается тем же, хотя последовательность вычислений отлична от предыдущей. Можно доказать, что если к одним и тем же аргументам некоторой рекурсивной функции применять две различные последовательности ее вычисления, то результат будет один и тот же при условии конечности этих последовательностей. Однако вполне возможно, что одна последовательность не будет заканчиваться, хотя другая последовательност закончится. Рассмотрим следующий пример.

Пример 3. Возьмем рекурсивную программу, применимую к любой паре неотрицательных целых Л) , Хг.

F: PROC ( X., /.г):

IF х,= 0 THEN R£ruaN (0);

Et-SB RETU/iN ( F (0, F( X,, Xi ));

ENP;

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

По правилу внешнего обращения F(hi) = F(0г F( 1,1)) так как условие л<=0 ложно

- 0 так как условие Л/ - 0 истинно

для внешнего обращения к F

По правилу внутреннего обращения

F( 1> 1) - F (0, F (1,1)) так как условие Xi - ф ложно

= F(0, F(0, F (1, I))) = F (ф, F(Q, F (Ф, F(1,1)))) и.т-А.

т. д.

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

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

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

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

Результат одного цикла работы рекурсивной программы ависит только от входного набора X . Таким образом, говоря вычислении рекурсивных функций рекурсивными программами языков лсокого уровня, такими, как ПЛД, нужно -отметить, что запомина-ие в стеке всех регистров и автоматических переменных является збыточным. Для организации рекурсивных вычислений существенным данном случае является лишь запоминание входных наборов, также адресов, содержащихся в регистрах ±4 и 15, которые 5еспечиваэт вызов программы и возврат к нужному состоянию или, эчнее, выдачу нужного входного набора.

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

Пусть дана функция Фиббоначи

ий Г (1,1)

конечна и 1) =0 .Во втором

Значение функции в точке 4 зависит от значения функции в точках 3 и 2. Дерево значений для функции Фиббоначи в точке А имеет вид:

к

У данного дерева 9 вершин и именно столько раз будет вызвана рекурсивная процедура в языке типа ПЛ/1. Очевидно, что система многократно вызывает программу на тех значениях, которые были уже вычислены ранее. Например, таблица вызовов для точки «4 выглядит следующим образом:

Р01ЫТ

0

1 2

. 3 4

с/)ы,!ые

2 з 2 I 1

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

При разработке системы программного моделирования АПС был£ поставлена задача избавиться от перечисленных недостатков

~ -L.J —

в организации рспурсивьых вычислений.

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

Однако проблема облегчается тем, что система АПС ориентирована на решение специфического класса задач - вычисление рекур-сивны1-: функций. Понятие функции в данном случае исключает использование STATIC ' переменных, т. е. использование процедур, содержащих переменные с "памятью", исключается также использование EX TER.NAL. переменных, файлов и т. д.

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

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

Данный метод весьма эффективен в большинстве случаев, особенно полезно его применение- при целочисленных вычислениях, )дкако имеется п ряд :«1нусов. Наиболзе существенны» недостатком является то, что при глубокой рекурсии таблица вычисленных тачетЯ может вырасти настолько,, '-то ее проаютр на'кавдса шгг вычисления с некоторого момента будет обходиться -дордае,' чем повторное вычисление функции. Известны разл.и.^ш подходы к решени-i данней пробдалы. Предлагается, например, создавать

упорядоченную таблицу с целью минимизировать время ее просмотра Однако при разработке системы АШ было решено отказаться от данного решения, поскольку это повлекло бы за собой дополнитель ные затраты быстродействия при записи в таблицу, которые не окупались имеющимися плюсами. Было решено просматривать таблищг вычисленных значений "снизу - вверх", что в большинстве случаев на порядок эффективнее просмотра "сверху - вниз", так как при рекурсивных вычислениях функция обычно вызывает функции на аргументах, значения которых находятся в конце таблицы.

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

Целью данной главы является доказательство того, что результатом работы программы Р , созданной системой моделирования на основе полученного описания функции F на входном наборе Z> , является неподвижная точка функции F эквивалентно доказательству того, что программа Р организуе1 вычисление функции F по правилу самой правой - самой внутренней замены.

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

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

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

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

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

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

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

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

. Халатян И. Г. Пакет прикладных программ - автоматический • программный синтез. Тезисы докладов Третьей Республиканской конференции аспирантов Армянской ССР. Часть 2, Ереван, 15-17 марта 1989 г.

. Халатян И. Г. Автоматический программный синтез - АПС. БУкопись депонирована в Арм. НИИНГИ, per. номер 65АР-89.

. Халатян И. Г. Доказательство правильности системы АПС. Рукопись депонирована в Арм. НИИНТИ, per номер Z4AP-30-

. Халатян И. Г. ФЛ - язык описания рекурсивных функций. Препринт. Ереван: Издательство АН Армянской ССР, 1990 г.

Публикации