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

Р Г Б ОД

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

и ~ И Г '

ВЯТКИН Валерии Владцмпромич

Специальности:

п."| К' 14- <"|1СТСМЫ опрцпотки ИНфорчаИПП 1! V П | ¡а КЛОН 11Я

0о.1 3. К) - Применение вычислительной техники, математического моделирования и мал емаа нческих методой в научных исследованиях.

АВТОРЕФЕРАТ

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

Таганро! - 1У9й

Работа выполнена в Таганрогском государственном радиотехническом университете

Научный консультант:

Доктор технических наук, профессор Г.И. ИВАНОВ

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

Доктор технических наук, профессор, Заслуженный деятель науки и техники Российской Федерации Л.С.БЕРШТЕЙН

Доктор технических наук, профессор Н.Г.ТОПОЛЬСКИЙ

Доктор технических наук, профессор А.Н. ГУД А

Ведущая организация: Вычислительный центр Ростовского государственного университета

Защита состоится "_"_ 1998 г. в_часов на заседании специализированного совета Д 063.13.02 в Таганрогском государственном радиотехническом университете по адресу 347915, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

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

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

Ученый секретарь совета Д 063.13.02 к.т.н., доцент

А.Н.ЦЕЛЫХ

Введение

Актуальность темы. Скорость управляющих программ является наиболее критическим фактором при проектировании систем логического управления. Вре-■>я реакции, являющееся основной характеристикой управляющих машин (контроллеров) .-обратно пропорционально их быстродействию. Более того, быстро-, («•истине во многом определяет и их емкостные характеристики. Это объяснятся двумя причинами. Во первых, в большинстве кон троллеров вычпсл< и не >рганпзовано метолом полного периодического сканирования всей программы, юэт-ому рост размера программы при постоянном быстродействии автоматн-lecKii влечет па гобой и увеличение времени реакции контроллера. С другой тороны. в многозадачных контроллерах количество залач. которые могут вы-юлняться одновременно, также прямо зависит от быстродействия.

Растутпая пространственная распределенность объектов и размерность ал-■оритмов управления вступает в противоречие с существующими методами обработки программ. Так, в распределенных системах управления, состоящих из сонтроллеров и удаленных систем ввода/вывода, связанных с контроллерами сетью. время однократного сбора входных данных и рассылки выходных сигналов .гожет многократно превышать время их обработки и требуемое время реакции Длительность каждого такта вычислений пропорциональна общему коли-¡еству входных переменных и времени опроса одного датчика. Замена цикли-1еского принципа вычислений на событийный способна существенно повысить характеристики системы управления без модификации аппаратных средств. В го же время, сохранение традиционных методов циклических вычислений в со-ic-тднпн с асинхронным интерфейсом способно дать лишь промежуточный зф-}->ект. Предлагаемая в данной работе замена перевычисления алгоритма уира-5лення па перевычисление только его "части, зависящей от события, способна обеспечить время реакции пропорциональное количеству изменившихся нерешенных.

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

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

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

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

Указанная цель достигается путем решения следующих задач:

1) Исследование и разработка методов событийного вычисления управляк щих программ. В частности:

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

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

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

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

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

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

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

На защиту выносятся следующие результаты:

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

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

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

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

г) Метод сокращения размера событийных ГС за счет построения обобщенной событийной ГС на основе обобщенного индексирующего отображения, принципы построения таких индексирующих отображений, алгоритмы вычисления БФ и их оценки.

д) Алгоритм},i построения и событийного перестроения (инкрементальной аннотации) обобщенных событийных граф-схем, в т.ч. логарифмических ГС.

2) Метод обобщенного разложения булевой функции по произвольной системе переходных функций и метол получения обобщенной граф схемы представления многозначной булевой функции по заданному множеству наборов переходных функций, позволяющий строить компактные и при :>том быстродействующие программы событийного перевычисления 1>Ф. Данный метод впервые позволил рассматривать многие известные граф-схемные представления булевых функций в качестве частных случаев обобщенных граф-схем алгоритмов, применяя, соответственно, однотипные алгоритмы вычисления, основанные ии интерпретаций обобщенных граф-схем. При этом обеспечивается возможность нахождения наиболее компактного графического представления для заданной исходной функции и, соответственно, компактной "событийной" граф-схемы для реализации событийного принципа вычислений.

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

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

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

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

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

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

Реализация и внедрение результатов работы. Основные результаты работы получены автором при выполнении научно-исследовательских и хоздоговорных работ по разработке, внедрению и дальнейшей модернизации интегрированных сред наглядного программирования логических систем управления по договорам с АО АвтоВАЗ, Констукторским бюро общего машиностроения г.Москва, Проектно - конструкторским предприятием "ИРИС", Конструкторским бюро информационно-заправляющих систем.

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

Внедрены и использованы следующие результаты

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

2) Алгоритмы построения обобщенных граф-схем на основе применения обобщенных аналитических разложений булевых функций.

•") Алгоритмы событийного разделения вычислений па интерактивную част/, и иредвычпеления, позволяющие обеспечить равномерную загрузку контроллера в событийном окружении, минимизируя при этом время реак-------

НИИ.

4) Алгоритмы построения событийных граф-схем по заданным ортогональным граф-схемам.

•>) Алгоритм!J событийной пнтерпреташи нсортогональных граф схем.

Аипробация работы. Основные результаты диссертации представлены на второй Международной научно-технической конференции " Актуальные проблемы фундаментальных наук (Москва 1992г.). семинаре фирмы OMRON по программному обеспечению контроллеров (Yokohama, Japan. 1995), международном семинаре Workshop on discrete event systems WODES'96 (Edinburg, U.K., 1996), Международной конференции японского общества управления SICE'97 (Tottori, Japan, 1996), семинаре по асинхронной логике (Aizu, Japan, 1997), семинарах японского научного общества по проблемам обработки информации [PSJ section "Algorithms" (Gifu, Japan, 1996; Iwate, Japan, 1997), Международной конференции Algorithms and architectures in real-time control AARTC'97 (Vil-amoura, Portugal. 1997), Международной конференции International Conference эп Parallel and Distributed Systems (Washington, USA. 1997), международном семинаре IL'b Workshop он discrete e\ent systems WODES'98 (Oagliari. ltaiy 1998) International conference 1EE and UKACC "CONTROl/98" (Swansea, U.K., 1998).

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

Структура и объем диссертации. Текст диссертации изложен на 241 странице, состоит из введения, семи разделов, заключения и приложений, содержит 59 рисунков, 5 таблиц и список литературы (140 наименований).

Содержание работы

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

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

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

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

Пусть О, Д. - произвольные конечные множества, и исходная функция заданг как / : Оп —Д, вектор аргументов X £ Оп и / - произвольное множестве упорядоченных списков натуральных чисел от 1 до п. Подмножество векторов адресуемое элементами множества I обозначим В1 = {Х[а] : <г& I}. Функции 7 : £)' х Д1 -4 Д, существенно зависящая от всех своих аргументов, определяет обобщенное разложение булевой функции по области I, если для произвольное функции / : Б" —> Д и любого сг £ I может быть однозначно найден вектор остаточных функций г = г\, гг,... г3 : Бп —» Д, такой что

ДХ)=Г(ХМ,т(Х))(УХеПп). (1]

Если множество I имеет регулярную структуру, описываемую, например как "множество всех упорядоченных подмножеств длины сР, то обобщенно« разложение приобретет наиболеее традиционный вид разложения по набору с переменных, где с1 называется порядком разложения. В случае булевых функций, очевидно, множество В заменяется на 1В, а функция разложения принимает вид Т : —> Д (Д = ЗР1).

Разложение называется аналитическим, если содержит в себе формальное правило получения остаточных функций для произвольно выбранной исходной булевой функции заданной в виде аналитического выражения. Важным способом задания внешней функции разложения (1) для случая регулярных разложений порядка ||А|| (А 6 Мп) (где N„ = {1,2,..., п}, а Мп— множество упорядоченных кортежей с неповторяющимися элементами из К1„) является задание внешней функции 5-местной операцией ор : Д* —»• Д на области значений функций / Пусть Ь = {^1,... ,/г,} : £)л —> В(2 < я < 2НлИ)-система функций, называемы* переходными. Тогда Т может задаваться как

Г{Х[\],т{Х)) = орМХ[\))г1{Х),... ,М*[А])М*)]. (21

Говорится, что разложение нормально, если система Ь удовлетворяет условик

л

У Л,- = 1. Если /г,- • = 0(\/г ф }) то разложение ортогонально. Разложение « = 1

называется ортпонормалъньш, если оно является и нормальным и ортогональ ным. Выбор операции ор : (В"1)* —Вт не влияет на вид остаточных функции г,- : В" ©т -

При выборе дизъюнктивной ор выражение (2) записывается как ^ = Л]П V /12Г2 V ... V 1г,г,

Определение (3) включает в себя как частные случаи ранее рассмотренные изложения-Шеннона и Лупанова и другие типы разложений:

• Разложение Шсшкша. Дизъюнктивное разложение Шеннона по к переменным получается выбором системы из 2к переходных функций

• Разложения Дэйвио являются примером, подтверждающим, что класс разложений Шеннона слабее (3): / = 0) фх[/|(:г.о)©/|(гл)], / = /1(^,1) Ф

п^т/^.г,! >]• Они получаются из (0) выбором неортогопальных систем переходных функций = 1, /г2 = х и /ц = 1, Ь,2 = х соответственно.

• Разложение Иванова с частичными подстановками, обобщающее разложение Лупанова, имеет следующие свойства:

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

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

•'•!) При заданной внешней дизъюнктивной функции р;ьз южеипя выбор сопряженных функций осуществляется однозначно в виде (.'-¿(х, :) —

Таким образом данное разложение также является частным случаем (о).

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

функций. На пего дает ответ следующая теорема.

Георема. Для ортонормалъной системы переходных функций /11,/12,... , остаточные функции могут быть найдены по правилу:

.4)

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

Теорема. Любая остаточная функция Л^^)' полУчаемая из / произвольно частичной подстановкой ((х, Ь), ^3), может быть найдена по правилам системе ортогональных переходных функций, где hj — хь.

Если область определения остаточных функций меньше области определе ния исходной функции, то многократное выполнение аналитических разлож* ний исходной и остаточных функций приводит к тому, что на каком-то шаг все остаточные функции становятся константами. Если исходную и кажду] остаточную функцию, полученную в процессе многократных аналитически разложений выполняемых до тех пор пока все остаточные функции не стану константами, изобразить в виде вершины графа с в исходящими дугами, т получим дерево, корню которого соответствует исходная функция, а листьям константы из множества значений Я. Процесс построения такого дерева назь: вается полным разложением функции в ее графическую схему (ГС). Известнс что для некоторых булевых функций не существует ортогональных предстг влений полиномиального размера, но существуют такие неортогональные гра(| схемные представления. Таким образом, для таких функций полное вычислени функции с использованием ортогональных граф-схем не имеет практическог смысла из-за показательного объема требуемой памяти. До тех пор, пока реч идет о полном вычислении, неортогональные представления также не имею особой привлекательности, поскольку в них время вычисления пропорциональ но размеру граф-схемы. Однако, как показано в последующих главах, в случа событийных вычислений даже неортогональные представления могут обеспе чивать весьма привлекательные характеристики.

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

Топологически ОГС является ациклическим связным графом

С = (V, Ь, ио 6 V, пед),

где: V = Уу + Уд-конечное множество вершин, состоящее из множества обо£ щенных условных вершин Уу с количеством исходящих дуг большим либо ра! ным 2 и множества обобщенных операторных вершин (вершин присваивания Уд из каждой из которых может выходить не более одной дуги. Те операторны вершины, из которых не выходит не одной дуги называются терминальным! Дуги графа задаются отображением Ь С V х V. Корень граф-схемы обозначе ется как и о 6 V. Прямых потомков вершины V будем обозначать г).с[1..й], гд

цля условных вершин s > 2, для операторных s = 1. В терминальных вершинах фимем y.ci = nil.

Семантические свойства ОГС определяются присвоением вершинам и дугам определенных аттрпбутов и заданием в их терминах функции ставящей ОГС 5 соответствие функцию /,. : 3'' ~> ¡¡Р. Операторная вершина имеет следую-

нпе аттрибуттл:"область"определепия-(домен)-®)1 -заданный списком индексов- ____

\ G Гт,„ выходных переменных и константный вектор их значений ral £ в котором значимым является только подмассив г>а/[А]. Аттрибутами обобщенной ссловной вершины (ОУВ) являются: описатель домена А £ Ып и набор переходных функций /¿1,. . ./¿.,(2 < i < 2''л'1'), задающий тип вершины. Домен Зл задаёт "воего рода идентификатор конкретной вершины.

Вершина в которой система переходных функций ортогональна также на-¡ывается ортогональной. Соответственно, схема, все условные вершины которой ортогональны, называется ортогональной ГС (ОрГС). При вычттелттии :i : 1ВЛ —> {0, 1} в ортогональной ОУВ система аз 5 ортогональных переходных функций может быть разложена в обобщенный бинарный граф, где количество условных вершин не превосходит 0(2"*"), количество операторных вершин не древосходит s и результат вычисляется за время 0(||Aj|). Это объясняет возмож-гость нахождения компактных обобщенных ГС, размер которых будет меньше 1ем у соответствующего бинарного графа той же функции. Действительно об-цее количество элементарных условных вершин будет равно 0( что

v^evu

ipii некоторых разложениях может быть существенно меньше оценки 0(2") би-¡арпого графа.

Полностью определенными называются 1С. в которых в каждом цуги иа-«шаюшемся ь корне каждая выходная переменная получает определенное значение 0 или 1. т.е. в каждом таком пути объединение доменок всех операторных вершин составляет вектор И,,,. Частным случаем полностью определенных ГС являются терминально-ограниченные, в которых все операторные вершины двляются терминальными и в каждой из которых А = Мт.

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

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

для заданной функции неограниченные диаграммы могут быть компактнее соответствующих ограниченных. Покажем это на примере. Разложим функцик / = х.](.г3 V • ?! V Щх]) V {х^ЩЧ ) (х4Щ V ам (;г.ч V ,т5)) в ограниченнук

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

Упорядоченными называются ГС, индексы вершины каждого пути из корня в одну из терминальных вершин удовлетворяют некоторому, одному и тому-ж€ отношению порядка. В зависимости от того, строгий или не строгий порядок выбран, получаются соответственно строго и нестрого упорядоченные ГС. Неупорядоченные ГС называют свободными. Очевидно, что строго упорядоченная ГС является ограниченной.

Так же как в случае ограниченных/неограниченных ГС, упорядоченные ГС менее компактны чем свободные. Например, для / = х1X2X3 УЩХ2Х4 V х{хзх^ V на рисунке 2 показано, что "свободный" бинарный граф имеет меньшее количество вершин, чем минимальный для этой функции ограниченный и упорядоченный бинарный граф.

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

Неортогональные ГС (НОрГС) с успехом используются для представления БФ и выполнения их преобразований. Известно, что некоторые неортогональные бинарные ГС имеют полиномиальный размер для некоторых из функций, ортогональные БГС которых имеют показательный размер. Таким образом неортогональные БГС имеют двойственную природу по отношению к ортогональным. Примером однородных неортогональных БГС являются т.н функциональные логические диаграммы имеющие набор переходных функций {х: 1}. Неоднородные ГС получаются в результате варьирования наборами переходных функций в процессе разложения исходной функции. Общей формой неоднородных БГС являются т.н. кронеккеровы диаграммы, вершины которых могут иметь один из следующих трех наборов переходных функций: {х, а:} , {ж, 1} , {х-, 1}. Логические цепи (ЛЦ) являются удобной графической формой изображения скобочных аналитических выражений БФ. С другой стороны, оказывается, что логические цепи тоже являются частным случаем ГС, получаемых с применением следующих ограничений: часть нетерминальных вершин, называемых функциональными (логические элементы) имеют набор переходных функций {1,1} при котором выбор остаточных функций разложения неоднозначен. Другая часть нетерминальных вершин - соответствующая входным каналам (входные вершины)- имеет ортогональный набор переходных функций {х,х}. ГС-логическая цепь строится по данному аналитическому выражению БФ как показано на рисунке 3.

Рис. 1. Пример неограниченной ГС (а),, ограниченной ГС (б) и упорядоченной ГС (в)

Рис. 2. Упорлдоченнал и свободная бинарная I С

В четвертой главе рассматриваются общие свойства и параметры событийных алгоритмов вычисления логических функций. Событийные вычисления представляют собой сочетание инкрементальных и частичных вычислений. Инкрементальные (происходит от английского термина incremental) вычисления находят изменение результата А/(х + Ах) основываясь на изменении входных переменных Ах. В частности, для булевой функции f : В" —> Вт инкрементальный принцип может быть в общем сформулирован так: на основе известного f (X) и данного Дх найти Af = f (X ф Ах) ф f (X). Под известным f (X) могут подразумеваться также и аттрибуты модели представления функции f.

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

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

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

Суть алгоритма состоит в предвычислении значений функции для всех возможных событий длина которых ограничена как |ij < к. Непосредственная комбинаторная оценка количества таких событий составляет O(jy). Если результат предвычислений сохранить в к— мерной таблице, то по данному событию S : |i| < к результат может быть извлечен из таблицы за время 0(|й|). Оказывается, что оценка количества событий является чересчур избыточной. В четвертой главе приводится более точная оценка количества событий, равная размеру (количеству терминальных вершин) минимального бинарного дерева задающего функцию. Данная оценка, в отличие от вышеприведенной комбинаторной, позволяет использовать свойства функций для минимизации объема

в I (1)

ф $ £>

©^ У Ь 1 ш ш 3 «>С1:

►О

О ТЗ

Й (о) Й

' о5 й ® 6

........А...! г1 ! Л

(х,Х, V х,){х, V Х,Х,) V х,(х, V Я) V (г, V (*, V X,) Х,)( X, V ;,(х,чх,))

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

Сибытие Лп

(х=х)

{у "1(1)1 (1=Т®Лх1

(г=*(хв!Лх)>

Д и К-ля чески обработка

Ъ*од млссилл Асс&ких \перыияишх ж Вычисление Вывод массиве > «ыетдных яеремеммых у \ВФздмоссим Вычисление В^оа'жсшл, яходкыт 1 * / |; «игодкмх ! |т1врем«ммыхх|{ ||| «ерсдемиху |

1 к 1 Г

* о(Н) <--------! - -1- скЫ!) Один г|икл о(М1) ----------->

Реакция на событие

Со бы пшнм обработка

|| Форыгорожим* ¡1 лекзпьре >1 -индоссо« событии*

|фсф4скротекис||~~ гавиеллшх

Л/=0.(5)

¡1 ссяитмл I , II для всех /е£,

¡1 5—ЗДАх) II ифчжроюж&у

'Ш

о(й)"> < о«"'

Рис. 4. Сравни тельная временная диаграмма циклической и событийной обработки

Y

Обозначения: Q 5f-0 3 м"1 [j Sf a> определено

Рис. 5. Структура данных для хранения всех событий глубины (/ = 3

State Х=<0,0,0,0,0> State Х=<0,1,0,1,0>

Рис. В. Бинарный граф дли функции в состоянии X = (0,0.0.0) (а) и пос/к- собышн 6 — {2,4) т.е. при А' + Дх = (0. 1.0, 1) (П).

__ Ж А

•-■:(£•) ¡1лк:!1.2 3 4.5_6_7 8 9

лШг.(у) |65*32| (А ,, ,@Ьз45б1

ГбПЕсЖ.

а) □ 6) "Щ

Рис. 7. Структура исходящих дуг вершины СГС (а) и СГС ллл ГС с рисунка 0-а в состоянии

X = (и, и.и,и) (б)

X

Рис. Организация мультиялыкоиого программирования ь срелс » рафНшчЛ

предвычислений.

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

Общая структура алгоритмов событийной интерпретации ортогональных ГС имеет следующий вид:

Предвычисление: Строит т.н. событийную ГС £■ — £{G, X) на основе задающей функцию ГС G и текущего состояния X.

Интерактивная -часть: Находит результат события путем интерпретации событийной ГС S на основе известного события S.

Понятие событийной ГС вводится на основе анализа зависимости результата интерпретации ГС обычным алгоритмом обхода с содержимым вектора 6. Таким образом алгоритм интерпретации ОрГС модифицируется так, чтобы его входом являлся вектор - описатель события S. Затем в алгоритме выделяются фрагменты, которые могут быть оптимизированы при помещении в событийную схему за счет применения предвычислений. Основным средством оптимизации является ускорение поиска в активных путях за счет использования ключей-индексов. В каждой вершине v активного пути v.P задается т.н. индексирующее отображение M : Indv —> v.~P. которое указывает местоположение индексов из области определения Indv в пути и.Р. Различные виды событийных ГС получаются применением к исходной ГС различных типов индексирующих отображений, имеющих соответственно различное соотношение скорости поиска и требуемой памяти.

Вначале в качестве примера рассматривается простейший вариант т.н. полного отображения с областью определения, состоящей из всего массива чисел 1..п. Получена оценка скорости интерпретации событийной ГС общего вида, построенной на основе такого отображения. Затем более детально исследуются упорядоченные ГС. Для ускорения поиска в активных путях таких схем предложены и исследованы несколько индексирующих отображений, являющихся более компактными чем полное отображение. Например, бинарный граф с активными путями в состояниях "до события" и "после события" для функции / = x4(x3Vxs)(xJ-xJVx^xi) V (x2'xïvx3xi)(x4x^vxj(x3vx5)) показан на рисунках 6 а) и б) соответственно. Событийная ГС для этой функции иллюстрируется на рисунке 7.

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

ется неизменным, так что направление активного пути не изменяется пока не встречается зависимая вершина.

Один шаг рекурсивного алгоритма СобытийныйОбтод описывается следующим образом* алгоритм применяете« к (ОУ) вершине г, и находит в v, .Р ближайшую к вершину w зависимую от события Ес.ш такая вершина существует и в результате события переходная функция в ней меняет своё значение, то алгоритм находит нового активно] о потомка r,+i — ac1jre(ir'' '). В этом случае алгоритм рекурсивно применяется к Интерпретация прекращается, если в активном ц\ ги г, Р больше н* остаётся зависимых от события вершин.

Алгоритм СобытийныйОбход (G : граф-схема, v £ \7(С): вершина: &: собьгп

Шаг 1. Если с номинальная. то / :=; г,.ml и алгорш м .¡авершаеч оя. Иначе:

Шаг 2. Найти подмножество = Vax Пч.Р вершин текущего пути зависимых от события S: Если гаких вершил не i, iu алгоритм завершаете».

Шаг 3. Среди вершин v,.P<s найти ги ближайшую к и в текущем пути и.Р;

Шаг 4. Найти подсобытие &и, относящееся к вершине iv : Sw = S П ш.Л (¡¡¿ш|| < Шаг требует времени 0()|d|] + w. ||Л||).

Шаг 5. Если система ортогональных переходных функций внутри событийной вершины задана в виде обобщенного бинарного графа g(tj), то вычисление активной функции интерпретацией этого графа требует времени, линейного к размеру домена этой вершины, т.е. ограничено сверху оценкой O(d). Результатом вычисления яшяется вершина г'. которая принадлежит ?>.Р если нкчивния переходная функция но irniemi i.'in, п роу плал с события, или являе гея илтт и: других потомков /г it iiponiBHo.M очучао.

Шаг С. Прпмсшпь алгори гм рекурсигаю к »' как: Событийпый()бхой{0. »•',

Собьггшшьш обход, таким образом, состоит в посещении всех вершин списка, имеющих индексы, входящие в событийный вектор 6. Задача рошае гея по еледователышм применением функции " Понск(J)" , находящей потомка текущей вершины г, имеющего индекс <)[jj. Поиск заканчивается в одном из .двух случаев: если вершина найдена или если такой вершины нет в списке. В последнем случае поиск останавливается в первой вершине с индексом большим искомого. Каждый последу юшни поиск начинается п вершине в ко горой закончился предыдущий. Очевидно, что это повторяется не более чем ||d|| раз, т.е. пока не проверены все элементы вектора-запроса. Ускорение поиска ближайшей зависимой вершины производится за счет использования в каждой вершине ГС индексирующего отоГ>])11жстп1. Обшпн пришит построения индексирующего отображения в вершине с сое I опт в следующем:

Каждой вершине с npnnuuusae тся пттрттбут Irtd, являющийся упорчдочен-ным маенвим индексов в интервале 1..п С rpoj ое индексирующее отображение Mv(i)(Vi 6 lndv) указывает на вершину с индексом г в активном пути ¿.Р, если такая вершина существует, или имеет значение нулевой вершины NIL в противном случае. Нестрогое индексирующее отображение указывает на вершину

с индексом, минимальным среди присутствующих в пути индексов больших или равных г.

Если массив Indv является непрерывным интервалом чисел от минимального индекса, встречающегося в пути и.Р, до максимального индекса в этом пути, то соответствующее отображение называется полным. Полное отображение может быть задано в виде линейного массива с постоянным времененм доступа к каждому элементу по индексу. Полное отображение может быть мажорировано отображением с fndv ~ 1. .. п -f 1.

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

на множестве вершин V с ребрами заданными отображением Mv. Количество

ребер в событийной ГС оценивается как Y1 U?t<^u|- В случае строгого индексные v

рующего отображения количество ребер событийной ГС, очевидно, не превосходит |V|n. Скорость построения событийной ГС в лучшем случае линейна её размеру. Нахождение ближайшей зависимой вершины может быть выполнено за время 0(||i||) следующим образом:

1) Построить множество Ve = {A/v(î[î])|î = 1, |<Щ ближайших к v зависимых вершин текущего пути.

2) Найти в этом множестве самую близкую к v вершину.

Очевидно, что время нахождения такой вершины линейно к |J|: Тпоиск < 0(||d"||). Тогда, общее время интерпретации событийной ГС ограничено оценкой

Т^ = 0(\5\х k) + 0(T*xk)+0(1). (б)

В упорядоченной ГС время поиска ближайшей зависимой вершины является постоянным - вершина Mv(min(6)) и является искомой. Следовательно, в УОБГ Т* - 0(|5|). Поскольку однажды встреченные в событийной вершине индексы больше не встречаются в пути, следовательно второе слагаемое оценивается как 0(e) и оценка (6) упорядоченных ГС превращается в

4 = 0(|i|) + 0(|i|) + 0(l) = 0(|i|). (7)

Обобщенное индексирующее отображение в вершине и имеет область определения Indv, состоящую из произвольного числа индексов меньшего либо равного |г.Р|. Без ограничения общности можно доопределить Indv тремя значениями: Ind[0] = v.index, Ind[ 1] = active(v).index, Indv[last] = n + 1. В этом случае интервал между максимальным и минимальным индексами равен исходному интервалу в который может попасть индекс а промежуточные индексы разбивают его на под-интервалы:

[/n<4[0] = v.index, Indv[1]], [IndJ[<S\, Indv[\),

[Indv[i], Indv[i -f l],

[Indv[last — 1], n + 1 = Indv [Zasi]]

Обход пути реализован следующим образом. Пусть t> обозначает текущий элемент пути с обобщенным индексирующим отображением, а индекс j - текущее положение в массиве J. Предусловием алгоритма обхода является v — го J = 1. В вершине г и при текущем значении j алгоритм пшет вершину с индексом <5[jj являющуюся потомком г следующим образом: если такал вершина существует, то должётГсУптествор.атк интервал-/n<i¡r[г —1] - <• S[j] <C-Ind„[i). — Определение интервала в который попадает q — требует времени, пропорционального log|ind|. Таким образом, даже если в массиве lnd нет искомого то за время logj/nrf| неопределенность в его .местоположении сокращается со всего интервала v.indix..n до интервала [Irid[i - I],/л</[/]] имеющего меньшую длину. Hfi-кчльк" последова'1 ельных приближений обязательно приведут в искомую вершину ''ejn она существует, или к тон вершине, в которой возможно будет установить, что искомой вершины нет. Количество приближений зависит иг количества, л расположения индексов р массиве Ind.

Скорость обхода списка зависит от того, сколько шагов требует последовательное приближение к искомой вершине. Это прямо зависит от того, как распределены индексы в массиве ¡ndv. Например, при |/nGÍ„| = 1 и Ind[ 1] = active[v) индексирующее отображение превращается в исходный однонаправленный список, поиск в котором требует времени, пропорционального его длине. Если же вершина содержит указатели на всех потомков, как в полном индексирующем отображеии, то последовательное приближение к искомой вершине занимает всего один шаг. При этом поиск нужного указателя занимает постоянное время. Оптимальный баланс между количеством необходимой для реализации дополнительной информации и скоростью поиска имеет бинарный попек реализация которш о различными индексирующими отображениями и рассмотрена в главе 5.

Индексное отображение задано аналитически если описано правило но котором} может быть определен размер его области определения \Indv \ п конкретные значения индексов в Irnlv. Может была, описано либо правило распределения индексов u fvd„. по которым однозначно находятся значении А/,.(/?к/г). либо наоборот задано правило нахождения разбиения пути на иодиптервалы вершинами к.';, по которым Irid,. восстанавливается как Indv(i) = M~l(w{). Первый пршшпп задания отображения будем называть индексным, а второй позиционным.

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

будет явля'1 вся:

• В индексном прппшшс: п - i .index 4 1 задающий максимальное количество индексов которое может встретиться в пути г.Р:

• В иозициошюм иршшдше: длина пути |е.Р|.

Сам принцип будем соответственно называть дистанционным. В случае двух аргументов это будут:

• В индексном принципе: v.index и п.

• В позиционном принципе: общая длина максимального активного пути |*>4.Р|, которому принадлежит вершина v Е t/'s.P и длина пути [ь'.Р|. По отношению к пути ys.P участок v.P будем называть "хвостом".

Такой принцип называется координатным.

Варианты сочетаний принципов задания индексирующего отображения иллюстрируются в следующей таблице:

Индексный Позиционный

Дистанционный Indv = F(n — v.index + 1) Mv =Ф(|и.Р|)

Координатный Indu = G(n,v.index) Mv = Ф(|г;,.Р|, |u.P|)

Если индексное отображение реализует бинарный поиск, то в случае индексного задания длина интервала неопределенности составляет N — п — v.index + 1, и- индексам присваиваются Indv — v.index + 2°, v.index + 21,... , v.index + 2["logAT|-i_ з качестве Mv(Ind(i)) принимается вершина to,-, ближайшая к началу пути Vj среди всех вершин Wi = {w : w.index > г} , т.е. Wi.index = min(w.index) для любого w G Wi-

В случае позиционного задания, длина интервала неопределенности равна L = |и.Р|, и индексирующее отображение задается списком из flog L] вершин ги0, w\,.. .Wfi0gi]_i, находящихся от v на расстоянии 2°,21,.. .2fIo8i,"l-1 соответственно.

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

Индексный Позиционный

Дистанционный log log I x log L x |i|

Координатный 2|rf|logn 2|i|logL

В шестой главе диссертации предлагаются алгоритмы событийной интерпретации неортогональных ГС общего вида и неортогональных деревьев. В обобщенной вершине, сформированной неортогональным разложением, несколько (от 0 до в) переходных функций могут быть истинны одновременно. Следовательно, количество вершин, посещаемых во время обхода неортогональной ГС может быть равно общему количеству вершин |У|, что делает их применение для полного вычисления БФ непривлекательным по сравнению с ортогональными ГС. Однако, использование неортогональных ГС для событийных вычислений может быть более выигрышным.

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

Общий принцип событийной интерпретации неортогоналъных ГС состоит в том, чтобы определить попадает ли корень схемы в число вершин, изменяющих значение своей функции, т.е. в множество Уд/. Это является следствием решения бол*-е обшей задачи пнкременд алыюп аппотапнп ГС. которая со< то-ит в нахождении всего множества Уд/ на основе известного Удх или Удц. ПопятноГчто"оптпмгйьиып'пнкременталйпый'а'лгорптм'псгможе'т выполняться быстрее чем 0(|Уд/|).

Функция разложения Т в вершине V может рассматриваться как функция домена х = Л'[А] ц осгаточных функций в верни шах-потомках {г. = /с,, ¡с,г, . ■ ■ . /с,. При фиксированных входных переменных, переменные домена х и остаточные функции Г сохраняют постоиниые значения. Следовательно, в фиксированном состоянии Т является булевой функпиен переменных: .Тхг((')х. (Н'с). которая называется переключательной:

~ дТ(х. ax.fr. сН'с) — дЗ-~кг(д-х. о\'с). (8)

Изменение значения функции /„ (т.е. д/г, = 1) в вершине и (переключение) может произойти, если произошло изменение или в переменных домена пли в некоторой остаточной функции, или и там, и там.

Например, однородные (с1 = = 2) функциональные бинарные ДПР (ПЗ-ББ) строятся с использованием (неортогонального) разложения Дейвио при Ь = (ж, 1). Функция 7"хг в такой вершине может быть выражена следующим образодг:

Що!',., V ^Дл)/,-,(н./;, - ./;,) V х) V д!,., (■>■/" у ¿о; V (9)

Пх\д[С1д[с_ д дд) уд^'о/А V

шэи. (ПТ, ^дд Vr(^vy;,^)) \fdTMJcJcA

Существует восемь возможных комбивадпи значений дг, <?/0. При фиксированных значениях г. Д,, Д-.2 значение Т может быт), предвычнелено и со-храненно для каждой из этих восьми комбинаций. Как только фактическая ком-бппаппт значений дт, д/,, д/, 2 становится известной, дифференциал вершины может быть найден за постоянное время наряду с указателем на вершину где распространение переключения заканчивается.

Другим примером неортогональных ГС являются обычные логические цепи, которые могут рассматриваться как неоднородные НОрГС с Т — (1, 1) ,х = 0 в функциональных элементах \\ Т = = л, в лттстьях. Например, в

бинарном элементе ИДИ:

Лег = V д^дГгМп =/о). (Ю)

В частности, если известно, что только в одном из потомков (например в с 1) дифференциал равен 1, то получим, что дифференциал функции равен значению обратному к значению в другом потомке д/ = Д2 и наоборот. Значение

второго операнда при котором меняется значение результата операции называется разрешающим, и блокирующим в противном случае. Если же дифференциал равен 1 в обоих потомках (с?/с, = 3/С2 = 1), то дифференциал функции равен

Л, — и

В логической цепи множество Удь, размер которого, определяет сложность интерактивной части событийного алгоритма, эквивалентно множеству вхождений изменившихся переменных в формулу. Размер схемы |У|, который определяет объем предвычислений, является линейным к размеру формулы. Исходное множество Удь задает своего рода начальную маркировку вершин ГС. Предлагаемый алгоритм модифицирует эту маркировку по определенным правилам, сокращая на каждой итерации общее количество маркированных вершин. Благодаря найденной связи между множествами Уд^ и Уд/ по известной финальной маркировке может быть сделан вывод о принадлежности корня ГС к множеству Уд/.

Если внешняя функция разложения имеет вид Т = ЬГС, то переключательная функция может быть представлена в виде ^Хг(5х, д/с) = Ф(д{с> <9Ь(х, <9х)). Если добавить каждой обобщенной вершине дополнительного фиктивного потомка (для определенности всегда крайнего правого), соответствующего ЗЬ, то все вершины из множества модифицированных вершин всегда будут листьями дерева и соответственно, будут взаимно независимы. В полученной таким образом ГС вершина имевшая 5 потомков будет иметь в + 1 потомка - по одному на каждый операнд переключательной функции.

Будем говорить, что минимальный общий предок (МОП) подмножества 5 С 5 является наименьшим если:

1) не содержит ни одной вершины из

2) УР С 5 : |Р| > 2 1{Р) = £(5).

Обозначим множество МОП всех подмножеств ¿> символом ЗЛ(^), а множество наименьших МОП обозначим как тш(5Л(5)). Дерево с корнем в наименьшем МОП будем называть минимальным модифицированным деревом или, сокращенно, ММД. Пусть Б - произвольное подмножество <5, имеющее наименьший МОП V = £(Б) 6 тж(Ш), и с обозначает его произвольно выбранного прямого потомка с = г>.с,-(Уг = 1, в). Тогда:

Лемма. |К(Сс) П 5| < 1 - т.е. поддерево с корнем в любом прямом потомке V содержит не более одной вершины из Б.

Общий алгоритм находит переключение 5/гСУдЬ)- Если функция переключается в ¿(Удь), то имея предвычисленные значения потенциала переключение в корне ГС может быть вычислено за постоянное время. Если же /¿суль) не переключается, то не переключается и функция в корне ГС.

Обозначим рабочее множество независимых вершин символом 5. Вначале 5 = Удь. Алгоритм выделяет в Б минимальные модифицированные деревья,

находит их дифференциал и удаляет по очереди из S. Если найденный дифференциал ММД равен 1, то корень ММД добавляется ко множеству S на следующей итерации. Общее количество итераций алгоритма не превосходит |Удь| и на последней итерации алгоритм находит дифференциал в вершине £(Уди)-Как ото было упомянуто выше, как тол1>ко дифференциал в ¿(Удь) становится

известенг дифференциал-в корне ГО может быть вычислен за постоянное время----

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

Оценка времени выполнения ал[ орптма ограничена

Тпоргс = 0(|УЛЬ|- -1- [Удь! \Tjmmj |) (11)

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

Пусть множество нелатшегтмт.тх пррптпгг S упорядочено по возрастанию. Подмножество д = |a¿, «¿+1,.. . ,aj-i.aj} следующих друг за другом по порядку элементов S, такое, что t(q) = ¿(a;, a,-+i) = Ü(o¿+i, п.+г) = • • • = t(a.j-\, cij) назовем последовательностью, имеющей общего минимального общего предка, или, короче, инвариантной последовательностью. Такая последовательность является полной, если к ней нельзя добавить ни одной вершины справа или слева без нарушения общего МОП.

Лемма. П полной инвариантной последовательности nuda

Ч = {a,. n¡ + -.....a, i.a,}

МОП té h'jiainaix <лршин ¡таен общему МОП последовательности: t(a.¡.aj) ~

Тоорома. Для минимальности МОП побмножгстеш q С 5 необходимо, чтобы q было инвариантной полной пое идоватслъностъю.

Упорядоченное множество независимых вершин S — a^aj,... может быть

представлено п как множество полных инвариантных последовательностей Q = 41 ■ Ч2- ■ ■ • 1 минимальная ллина последовательности q, равна 2. а две coi ед-ние последовательности g¿_i,<7; всегда имеют различных МОП ф t(qi))

и одну общую вершину v = ^¿„i П </¿.

Уточненный с учетом всего вышесказанного алгоритм Снизу-вверх состоит из двух частей. Вначале алгоритм формирует стек последовательностей, так. чтобы их .МОП были упорядочены по возрастанию - на вершине стека находится минимальный элемент. Множество последовательностей Q просматривается но порядку. На нервом шаге в стек помешается первая последовательность q-¡. На шаге i текущий кандидат на добавление в стек - последовательность q¡. Если ¿([u.top])>i(qi) то qi добавляется в стек, иначе из стека удаляется столько элементов, что последнее условие становится истинным. Ясно, что сокращенные

пары удовлетворяют критерию минимальности поскольку они минимальны 1 стеке и меньше чем После того, как весь массив обработан н стек постро ен - производится последовательное сокращение элементов начиная с вершинь стека. Сложность алгоритма может быть оценена по количеству операций со кращения, которое ограничено 0(|Удь|). Таким образом, вместо алгоритма имеющего сложность квадратично зависящую от |Удк| получен алгоритм, име ющий время выполнения линейно зависящее от |Удь|:

ТнорГС < 0(|Удь ¡(¿+8)) (12;

Седьмая глава диссертации содержит описание методов применения разработанных алгоритмов в системах наглядного программирования распределенных систем логического управления "Граф-Цикл" и "Интервью". Факторы, влияющие на вычислительную эффективность программ логического управление можно условно разделить на две группы. К первой относятся те, что определяют структуру и характеристики алгоритма управления, ко второй - параметры реализации этого алгоритма. Таким образом, поддержка процесса проектирования алгоритмов и программ логического управления соответствующим!' методологическими и программно- инструментальными средствами может влиять как на скорость разработки соответствующих прикладных систем, так и не их качественные характеристики - корректность, надежность, вычислительнук эффективность.

Инструментальные интегрированные системы наглядного технологического программирования " Интервью" и " Граф-Цикл" реализуют ряд технических решений, позволяющих оптимизировать как получаемый исполняемый код, так и время проектирования и отладки.

Система "Интервью" предназначена для разработки АЛУ для ПЛК среднего и малого класса. Система содержит полный набор средств проектирования и тестирования программ на трех языках - систем булевых формул, релейно-контактных схем и функциональных схем. Система генерирует оптимизированный исполняемый код с учетом событийных алгоритмов, предложенных е диссертации.

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

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

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

1рограммированпя не должны влиять на временные характеристики контрол-юра. Более того, внесение изменении в программу в процессе динамической шдикашш также не должно приводить к некорректно» работе контроллера и (екорректпым данным индикации ни в одном цикле работы контроллера. Ис-•ледованные в диссертации граф-схемные представления и событийные и инкрементальные алгоритмы при применении в системе ''Граф-Никл*' позволяют:

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

2) Минимизировать обмен данными между контроллером и удаленными модулями ввода/вывода, а также между контроллером и устройством программирования и отладки (УПО), и сохранить тем самым исходное время реакции контроллера даже при одновременной динамической индикации до 20 программных .моду-лен.

.'!) Обеспечить возможность модификации программы "на лету"' (on the fly) с сохранением корректности как самого исполняемого кода, так и дан-пых динамической индикации. Достигается применением алгоритма инкрементальной модификации и аннотации граф-схем.

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

Заключение

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

Основные теоретические и практические результаты, полученные в диссертации, заключаются в следующем:

1) Предложен метод обобщенного разложения булевой функции по произ вольной системе переходных функций и метод получения обобщенно! граф-схемы представления многозначной булевой функции по заданному множеству наборов переходных функций, позволяющий строить компакт ные и при этом быстродействующие программы вычисления БФ. Дан ный метод впервые позволил рассматривать все известные граф-схемньк представления булевых функций в качестве частных случаев обобщенны} граф-схем алгоритмов, применяя соответственно однотипные алгоритмь вычисления основанные на интерпретации обобщенных граф-схем. Пр1 этом обеспечивается возможность нахождения наиболее компактного графического представления для заданной исходной функции.

'2) Разработана теория событийно-ориентированных вычислений состоящю в разделении инкрементального алгоритма вычисления на две части ■ интерактивные вычисления реакции и межсобытийные предвычисленш промежуточных данных. Получены нижняя оценка объема интерактивны? вычислений 0(\д |) и верхняя оценка объема предвычислений 0(п \Умувд\) инвариантные к форме представления функции.

3) Предложен и исследован алгоритм событийных вычислений на неортого нальных граф-схемах имеющий сложность интерактивной части пропорциональную количеству затронутых событием вершин граф-схемы 0(Ув] при сложности предвычислений пропорциональной размеру граф-схемь

от).

4) На основе введенного понятия "событийной" граф-схемы разработан метод событийных вычислений, имеющий сложность интерактивной частр линейно зависящую от количества переменных измениивших свои значения в результате события и сложность предвычисления пропорциональную произведению размера сокращенной граф-схемы 0(|У|) на общее количество переменных п. Предложен способ обмена память/время путе!У построения обобщенной событийной граф-схемы на основе обобщенногс индексирующего отображения. В частном случае логарифмического индексирующего отображения получены оценки О(1о§ п |<5|) и тг |У|) дл* интерактивной части и предвычислений соответственно.

5) Разработаны и исследованы алгоритмы построения и событийного перестроения обобщенных событийных граф-схем в т.ч. основанных на логарифмическом индексном отображении, позволяющие синтезировать собы тийные ГС с заранее заданными характеристиками размера и быстродействия.

6) Разработаны системные, инструментальные и языковые средства программной поддержки организации эффективных вычислений в логических контроллерах серий "ВАЗ С60-С400", основанные на использова нии наглядных представлений графических схем алгоритмов управления

Система программирования ^ Интервью" реализует предложенные событийные алгоритмы путем генерации оптимизированного исполняемого кода по исходному алгоритму, заданному в одной из форм представления систем булевых функции. Система "ГрафЦиюГ обеспечивает преобразование алгоритма заданного в виде параллельно-последовательной ГС в эффективный соьытийный год.----------------- - - --------------— -

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

[1] Вяткин В.В., Перельман A.M. Технология разработки алгоритмов логического управления. В кн.: Организационно-экономические проблемы разработки вычуг.лительнои тегники.^еп. в ВИНИТИ. 19й8,с. 11-17.

[2] Вяткин В.В. Система программирования микропроцессорных логических контроллеров дискретной промышленной автоматики ЦИКЛ-2.0 в кн. Тезисы докладов участников семинара "Применение однокристальных ЭВМ в народном хозяйстве",Киев, РДНТЭП, 1990,с.32.

[3] Вяткин В.В., Иванов Г.И. Перспективная система программирования ПЛК в форме графических схем алгоритмов Граф-Цикл в кн.Программируемые

контроллеры МикроДАТ, Харьков 1991. тезисы докладов.с.23

Г'1] Вяткин В.В., Иванов Г.И. Сравнительный анализ современных языков программирования систем автоматизации производства на базе графических схем алгоритмов и различных форм представления систем булевых функций. X Всесоюзная научная сессия, посвященная Дню радио. Тезисы докладов, с.147, М., Радио п связь, 1991.

[5] Вяткин В.В..Иванов Г.И.,Ошетер В.II. Повышение эффективности программирования ПЛК на языках комбинированных релейно-контактных и

функциональных схем В кн. Программируемые контроллеры МикроДАТ. Харьков 1991. тезисы докладов.,с.25

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

управляющие системы, Таганрог, ТРТИ, 1992, деп.в ВИНИТИ N116-B92, - 31с.

[7] Вяткин В.В., Ошетер В.В, Метод эмуляции двумерных грамматик и его применение при проектировании редактора релейно-контактных схем В кн. Информационно-управляющие системы, Таганрог, ТРТИ, 1992, деп.в ВИНИТИ N117-B92, - 16с.

[8] Вяткин В.В., Иванов Г.П., Ошетер В.П., Федоренко В.И. Язык программирования логических контроллеров Граф-Цикл. В кн. Информационно-управляющие системы., Таганрог ТРТИ, 1992, деп. в ВИНИТИ N 120-В92,

- 16с.

[9] Вяткин В.В. Применение языков параллельных граф-схем алгоритмов в математическом обеспечении программируемых логических контроллеров. В кн. Информационно-управляющие системы, Таганрог ТРТИ, 1992, N 119-В92, -9с.

[10] В. Вяткин, Федоренко В.И., Ошетер В.П. Система программирования контроллеров серии СЮ0-С300 "Интервью" Руководство пользователя, АвтоВАЗ, 1992, 120с.

[11] В.Вяткпн Методика разработки и отладки управляющих программ в системе " Интервью" Пособие по прикладному программированию, АвтоВАЗ,

1993

[12] Вяткин В.В., Кондрашев И.А., Федоренко В.И., Ошетер В.П. Система программирования контроллеров серии С100-С300 "Интервью" Руководство системного программиста, АвтоВАЗ, 1993

[13] Вяткин В.В., Иванов Г.И., Кондрашев И.А., Макаров Р.В., Ошетер В.П., Федоренко В.И Концепция наглядного блок - схемного программирования и ее реализация в инструментальном комплексе подготовки и отладки технологического программного обеспечения "ГрафЦикл", В кн. Тезисы докладов международной конференции "Актуальные проблемы фундаментальных наук", М.:, 1993.

[14] Байдуганов М.Ю., Близнюков С.А., Вяткин В.В., Иванов Г.И., Кондрашев И.А., Макаров Р.В., Ошетер В.П. Система автоматизированного учета и контроля налогообложения правильности физических лиц, В кн. Тезисы докладов Международной конференции "Актуальные проблемы фундаментальных наук", М.:, 1993

[15] Безлепкин A.B., Вяткин В.В., Горбатюк В.Ф., Иванов Г.И., Ланкин А.В, Автоматизированный аппаратно-программный комплекс "АРМ - рентгене

- дефектоскописта", В кн. Тезисы докладов Международной конференциь "Актуальные проблемы фундаментальных наук", М.:, 1993

[16] Вяткин В.В., Чернецов А.М., Пройдаков Н.И., Шарашкин H.A., Кондрашев И.А. Серия программируемых контроллеров СЮО-СЗОО и устройст! программирования С400-415 Эксплуатационная документация, АвтоВАЗ

1994

[17] Вяткин В.В., Иванов Г.И. Граф-Цикл - наглядное блок - схемное программирование в промышленных системах управления, В книг< "Информационно-управляющие системы, вып.2, ТРТУ, 1994

18] Байдуганов М.Ю., Близнюков С.А.. Вяткин В.В., Иванов Г.И., Макаров Р.В.. Ошетер В.П., Решетняк СЛ.. Федоренко В.И., Фомин Н.П. Автоматизированная система управления, контроля и информационного обеспечения Совета и Администрации г. Таганрога В книге "Информационно-управляющие системы, вып.2, ТРТУ, 1994

19] Вяткин В.В., Иванов Г.И.. Кондрашев И.А.. Макаров Р.В., Ошетер В.П.. Федоренко В.И. Концепция наглядного блок - схемного программирования и её реализация в инструментальном комплексе подготовит и отладки технологическою программного обеспечения систем управления Граф-Цикл, В книге "Информационно-управляющие системы, вып.2, ТРТУ, 1994

20] Вяткин В.В., Иванов Г.И. Прикладное программирование в промышленных системах управления Таганрог, ТРТУ, 1996, 104 с.

21] Вяткин В.В., Иванов Г.П., Ошетер В.П., Федоренко В.П.. ГрафЦикл - система наглядного программирования промышленных логических контроллеров. Управляющие системы и машины, 1996, N3, с. 33-44.

22] Вяткин В.В., Иванов Г.И. Эффективная машинная реализация управляющих программ Таганрог, ТРТУ, 1998

23] V.Viatkin, N.Ishii, and T.Hayashi. Event oriented evaluations of binary decision diagrams, pages 374-379. International workshop on discrete event systems, IRE, Edinburgh, 1996.

24] V.Viatkin, K.Nakano, and T.Hayashi. Evaluation of logic expressions based on event-oriented interpretation of marked functional diagrams, pages 12431248. 35th international conference of Society for instrumentation and control engineering of Japan, 1996.

25] V.Viatkin, K.Nakano, and T.Hayashi. Logic evaluations as processing of queries using binary decision diagrams. IPS J SIG Notes, 96-89:31-38, 1996.

26] Valerv Viatkin, Tatsuya Hayashi, and Naohiro Ishii Event-driven improvement of response time for logic controllers Nago\'a Institute of Technology. Technical report T1196-06, 1996

27] Valery Viatkin, Koji Nakano, Tatsuya Hayashi Logic evaluations as processing of queries using binary decision diagrams Nagova Institute of Technology. Technical report TR96-07, 1996

28] Valery Viatkin, Koji Nakano, and Tatsuya Hayashi Evaluation of logic expressions based on event-oriented interpretation of marked functional diagrams, Nagoya Institute of Technology, Technical report TR96-08, 1996

[29] V.Viatkin, K.Nakano, arid T.Hayashi. Optimized Processing of Complex Even in Discrete Control Systems using Binary Decision Diagrams, pages 445-45 International workshop on algorithms and architectures in real-time contrc IFAC, 1997.

[30] V.Viatkin, K.Nakano, and T.Hayashi. Event-driven evaluation of combinatori logic circuits. IPS J SIG Notes., 58-6:41-48, 1997.

[31] V.Viatkin, K.Nakano, T.Hayashi, and G. Ivanov. Event-oriented parallel log computations for distributed real-time control systems, pages 553-558. Proc. < International Conference on Parallel and Distributed systems, IASTED, 1997

[32] V. Viatkin, K.Nakano, and T.Hayashi. Computation and on-line recomputatic of boolean functions using decision diagrams. Submitted to IEICE Transaction

[33] V.Viatkin, K.Nakano, and T.Hayashi. Event-driven evaluation of logic contr programs based on binary decision diagrams. Submitted to Automatica, 1998.

[34] V.Viatkin, K.Nakano, T.Hayashi, and G.Ivanov. Event-driven algorithms incremental logic computations using generalized decision diagrams. To appe; in proc. of UKACC International conference on CONTROL'98, Swansea, U.K 1998.

[35] V.Viatkin, K.Nakano, T.Hayashi, and G.Ivanov. Event-driven evaluation orthonormal and non-orthonormal generalized decision diagrams. To appear : proc. of International workshop on discrete event systems, IEE, Cagliarv, Ital

Личный вклад в публикациях выполненных в соавторстве состоит в след ющем: [1]- идея и алгоритм автоматического вывода управляющих програм по заданным спецификациям, [2,3,4,8,10,12,13,21] - общая архитектура систе наглядного программирования систем логического управления, общая конце: ция языка Граф-Цикл, классификация принципов и систем программирован! контроллеров, [25-35] принцип построения событийных ГС (включая логарис мические статические и динамические СГС) и их интерпретации, принцип н ортогональных разложений БФ и интерпретации неортогональных ГС, общг принцип преобразования алгоритмов инкрементальных вычислений к событи ному виду, алгоритмы событийной интер ных и неортог

нальных ГС и их аналитические оценки.

1998.

1998.

Типография МРЦПК Таганрогского государственного радиотехнического университета. Заказ 17/7. Тираж 100 экз. 1998 г.

Q // У/ ЯГ JW/a-S"

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

Специальности:

05.13.14 - Системы обработки информации и управления

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

ДИССЕРТАЦИЯ на соискание ученой степени доктора технических наук

Таганрог - 1998

Оглавление

1. Современные задачи вычислительной теории цифро-

вых управляющих автоматов 16

1. Исторический обзор..............................................16

2. Модели вычислительной реализации различных типов автоматных алгоритмов............................................26

3. Событийные системы и событийный принцип вычислений . 31

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

2. Аналитические разложения БФ 42

1. Обобщенное разложение дискретной функции................42

2. Получение остаточных функций при помощи подстановок . 44

2.1. Операция подстановки в аналитическое выражение 44

2.2. Свойства полных подстановок в аналитическое выражение ....................................................53

2.3. Операция подстановки в СДНФ........................54

3. Обобщенное нормальное разложение..........................56

3.1. Разложения Шеннона и Лупанова......................57

3.2. Разложение Дэйвио......................................59

3.3. Обобщенное разложение Иванова с частичными подстановками ................................................59

4. Выводы............................................................65

3. Графовые модели вычисления БФ 67

1. Обобщенные граф-схемы булевых функций..................67

1.1. Бинарные графы и деревья..............................67

1.2. Свойства ориентированных ациклических связных графов (ОАГ)............................................76

1.3. Определение обобщенной ГС............................80

2. Синтез граф-схем и их сокращение............................84

3. Классы граф-схем................................................88

3.1. Определенные и неопределенные ГС ..................88

3.2. Ограниченные ГС........................................88

3.3. Упорядоченные ГС ......................................90

3.4. Неортогональные ГС....................................91

3.5. Однородные и неоднородные ГС ......................93

3.6. Логические цепи как неоднородные ГС ..............93

3.7. Общий вид бинарных ГС................................94

4. Численные характеристики граф-схем........................96

5. Ортогональные обобщенные граф-схемы......................99

6. Канонизация обобщенных бинарных графов.........101

6.1. Сокращение бинарных графов.............105

7. Выводы..............................107

4. Событийные вычисления в реальном времени 110

1. Принцип событийных вычислений...............110

2. Общая схема событийных вычислений............112

3. Применение предвычислений..................120

4. Переключательные свойства булевых функций.......126

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

5.1. Сложность пред вычисления для произвольного Е . . 133

6. Выводы..............................137

5. Событийная интерпретация ортогональных схем 143

1. Событийная интерпретация граф-схем............143

2. Интерактивный алгоритм интерпретации ОрГС......150

3. Ускорение поиска ближайшей зависимой вершины.....155

4. Обобщенные событийные граф-схемы ............160

4.1. Обобщенное индексирующее отображение......160

4.2. Стратегии назначения указателей...........161

5. Дистанционное индексное и позиционное задание логарифмического индексирующего отображения ..........164

6. Координатно-индексное задание индексирующего отображения ...............................167

7. Оценка длительности предвычисления............179

7.1. Состав предвычисляемых данных...........179

7.2. Оценка времени построения событийной граф-схемы 180

7.3. Инкрементальная аннотация ГС............182

7.4. Инкрементальный алгоритм изменения реверсивных деревьев.......................185

7.5. Системы указателей в реверсивных деревьях .... 187

8. Выводы..............................188

6. Событийная интерпретация неортогональных ГС 191

1. Событийный и инкрементальный алгоритмы........191

2. Свойства неортогональных переходных функций......193

3. Формулировка задачи вычисления БФ в терминах НОрГС 195

4. Потенциал вершины.......................196

5. Минимальная модифицированная, часть ГС.........197

6. Интерактивная часть вычислений...............201

6.1. Общий алгоритм интерпретации...........201

6.2. Детализация алгоритма и получение более точной оценки...........................203

7. Событийная интерпретация логических цепей........212

8. Интерпретация сверху - вниз..................218

8.1. Рекурсивное вычисление переключателя.......218

8.2. Вероятностная оценка дистанции свободного распространения в ЛЦ...................219

8.3. Вероятностная оценка количества вершин при ин-

терпретации не использующей предвычислений ... 221

9. Инкрементальная аннотация неортогональной ГС.....223

10. Выводы..............................224

7. Граф-схемное построение управляющих программ 231

1. Наглядное технологическое программирование.......231

2. Система технологического программирования ПЛК С100-С300 "Интервью" ........................236

2.1. Структура управляющей программы.........236

2.2. Сервисные средства и отладочные режимы.....242

2.3. Редактор РКС......................245

2.4. Отладка технологических программ.........247

3. Организация среды интегрированной наглядного программирования ПЛК ГрафЦикл...................249

4. Конструкции языка ГрафЦикл и их использование.....251

5. Организация средств программирования и отладки .... 260

5.1. Интегрированная среда.................260

5.2. Система компиляции и связи..............262

6. Примеры разработки и реализации систем управления в системе ГрафЦикл........................263

6.1. Участок кирпичного завода..............263

6.2. Процедурно-алгоритмическая модель.........274

7. Событийные принципы обеспечения эффективности исполняемого кода.........................276

7.1. Источники параллельности в управляющих программах ............................276

8. Методы реализации параллельных алгоритмов управления 280 8.1. Событийная интерпретация бинарных графов для

простых событий....................283

9. Реализация вычисления логических цепей..........286

10. Выводы..............................287

Введение

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

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

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

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

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

Указанная цель достигается путем решения следующих задач:

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

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

а) Разработка и исследование алгоритмов событийного вычисле-

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

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

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

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

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

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

На защиту выносятся следующие результаты:

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

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

3) Метод событийных вычислений, основанный на построении "событийной" граф-схемы по заданной ортогональной граф-схеме представления СБФ, имеющий сложность интерактивной части линейно зависящую от количества переменных измениивших свои значения в результате события и сложность предвычисления пропорциональ-

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

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

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

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

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

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

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

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

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

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

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

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

Внедрены и использованы следующие результаты

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

2) Алгоритмы построения обобщенных граф-схем на основе применения обобщенных аналитических разложений булевых функций.

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

4) Алгоритмы построения событийных граф-схем по заданным ортогональным граф-схемам.

5) Алгоритмы событийной интерпретации неортогональных граф-схем.

Аппробация работы. Основные результаты диссертации представлены на второй Международной научно-технической конференции "Актуальные проблемы фундаментальных наук (Москва 1992г.), семинаре фирмы OMRON по программному обеспечению контроллеров (Yokohama, Japan, 1995), международном семинаре Workshop on discrete event systems WODES'96 (Edinburg, U.K., 1996), Международной конференции японского общества управления SICE'97 (Tottori, Japan, 1996), семинаре по асинхронной логике университета компьютерных наук (Aizu, Japan, 1997), семинарах японского научного общества по проблемам обработки информации IPS J section "Algorithms" (Gifu, Japan, 1996; Iwate, Japan, 1997), Международной конференции Algorithms and architectures in real-time control AARTC'97 (Vilamoura, Portugal, 1997), Международной конференции International Conference on Parallel and Distributed Systems (Washington, USA, 1997), международном семинаре IEE Workshop on discrete event systems WODES'98 (Cagliari, Italy, 1998), International conference IEE and UKACC "CONTROL'98" (Swansea, U.K., 1998).

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

Структура и объем диссертации.

Текст диссертации изложен на 332 страницах, состоит из введения, семи разделов, заключения и приложений, содержит 85 рисунка, 5 таблиц и список литературы (184 наименования).

Глава 1

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

1. Исторический обзор

Наиболее распространенным подходрм к проектированию алгоритмов управления дискретными объектами в системах автоматизированного управления технологическими процессами (АСУ ТП) является автоматный. В качестве устройства управления (УУ) синтезируется управляющий автомат [18], т.е. устройство имеющее конечный набор логических (дискретных) входов, выходов и внутренних состояний, а также алгоритм задающий взаимосвязь между их значениями в дискретном времени.

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

[1, 2], А.Гилла [5], А.Н.Мелихова [11]