Введение к работе
Актуальность темы. Скорость управляющих программ является наиболее кри-чпескпм фактором при проектировании систем логического управления. Вре->я реакции, являющееся основной характеристикой управляющих машин (контроллеров) .-обратно пропорционально их быстродействию. Более того, быстро-. (ейстшіе во многом определяет и их емкостные характеристики. Это объяснятся двумя причинами. Во первых, в большинстве контроллеров вычне.-к л це ірганпзовано метолом полного периодического сканирования всей программы, юзтому рост размера программы при постоянном быстродействии автоматп-іескп влечет за гобой и увеличение времени реакции контроллера. С другой тороны. в многозадачных контроллерах количество залач. которые могут вы-юлняться одновременно, также прямо зависит от быстродействия.
Растутпая пространственная распределенность объектов и размерность ал-оритмов управления вступает в противоречие с существующими методами обработки программ. Так, в распределенных системах управления, состоящих из сонтроллеров и удаленных систем ввода/вывода, связанных с контроллерами сетью, время однократного сбора входных данных и рассылки выходных сигналов .гожет многократно превышать время их обработки и требуемое время реакцій. Длительность каждого такта вычислений пропорциональна общему коли-іеству входных переменных и времени опроса одного датчика. Замена циклн-іеского принципа вычислений на событийный способна существенно повысить характеристики системы управления без модификации аппаратных средств. В го же время, сохранение традиционных методов циклических вычислении в ео-іетлнші с асинхронным интерфейсом способно дать лишь промежуточный зф-рект. Предлагаемая в данной работе замена перевычисления алгоритма упра-ілешія на перевычисление только его "части, зависящей от события, способна обеспечить время реакции пропорциональное количеству изменившихся нерешенных .
Указанный алгоритмический подход оптимизации управляющего устрой-;тва является более универсальным по сравнению с аппаратными методами оптимизации, поскольку известно, что рост размерности прикладных задач опережает темп роста производительности как компьютеров вообще, так и контроллеров в частности. Алгоритмические усовершенствования же работает всегда, независимо от используемой аппаратной платформы.
Массивы булевых функций формально задающие алгоритмы логического управления являются ядром большинства прикладных задач логического упра-злення. Соответственно, эффективность контроллера во многом определяется зыбором формы представления и алгоритмов вычисления булевых функции. Таким образом, событийная оптимизация вычисления систем булевых функции является ключевой проблемой в повышении производительности систем логического управления.
Цель работы. Разработка и исследование событийных алгоритмов вычисле-
ішя логических функций, задающих автоматные алгоритмы управления, про, назначенных для применения в дискретно-событийном окружении и обеспечі вающих оптимальное соотношение времени реакции контроллера и требуемс памяти. Нахождение алгоритма обеспечивающего минимальное время реакцш Указанная цель достигается путем решения следующих задач:
1) Исследование и разработка методов событийного вычисления управляй
щих программ. В частности:
а) Исследование обобщенных графических форм задания булевых фуні
ний (БФ) построенных с использованием обобщенного разложени
БФ для получения оптимального соотношения скорости обработки
размера памяти, требуемого для хранения БФ.
б) Разработка и исследование алгоритмов событийного вычисления лс
гических управляющих программ в классе общих неортогональны
граф-схем алгоритмов.
в) Разработка и исследование алгоритмов событийного вычисления лс
гических управляющих программ в классе ортогональных граф-схе)
алгоритмов.
г) Разработка методов и алгоритмов интеграции событийно- ориенти
рованной техники вычисления в интегрированное программное обес
печение распределенных и многопроцессорных контроллеров.
2) Разработка инструментальных и системных средств программирован!!
контроллеров, реализующих вышеупомянутые алгоритмы событийног
вычисления управляющих программ.
Методы исследования базируются на применении теории вычислительны систем, теории дискретного управления, теории дискретных и булевых функ ций, теории автоматов, теории графов, теории вероятностей, математическог анализа, асимптотических оценках алгоритмов.
Научная новизна Научная новизна диссертации состоит в разработке исследовании эффективных алгоритмов вычисления управляющих програмі в программируемых логических контроллерах, основанных на использовани обобщенных графических схем алгоритмов и событийно-ориентированных методов вычислений.
На защиту выносятся следующие результаты:
1) Теория событийно-ориентированных вычислений алгоритмов логическог управления, состоящая из модели разделения инкрементальных вычисле ний на две части - интерактивные вычисления реакции устройства упра вления и межсобытийные предвычисления промежуточных данных, моде лей и алгоитмов вычисления и перевычисления булевых функций на гра фовых формах представления, а также оценки этих алгоритмов. В част ности:
а) Нижняя оценка интерактивного алгоритма количеством переменных
изменивших свои значения и верхняя оценка объема предвычисленпй
произведением размера минимального бинарного дерева, задающего
функцию, на общее количество аргументов ф\нкппи.
б) Алгоритмы событийных вычислений на неортогональных граф-схема;
имеющий сложность интерактивной части пропорциональную коли
честву затронутых событием вершин граф-схемы при сложности
предвычислений пропорциональной произведению размера сокращен
ной граф-схемы на общее количество аргументов.
в) Алгоритмы событийных интерактивных вычислений, основанные на
построении ''событийной'' граф-схемы по заданной ортогональной граф-схеме представления СБФ, имеющий сложность интерактивной части, линейно зависящую от количества переменных, изменивших свои значения в результате события, и сложность предвычпелепия, пропорциональную произведению размера сокращенной граф-схемы на общее количество переменных.
г) Метод сокращения размера событийных ГС за счет построения обоб
щенной событийной ГС на основе обобщенного индексирующего ото
бражения, принципы построения таких индексирующих отображе
ний, алгоритмы вычисления БФ и их оценки.
д) Алгоритмы построения и событийного перестроения (инкременталь
ной аннотации) обобщенных событийных граф-схем, в т.ч. логариф
мических ГС.
-
Метод обобщенного разложения булевой функции по произвольной системе переходных функции и метод получения обобщенной граф схемы представления многозначной булевой функции по заданному множеству наборов переходных функции, позволяющий строить компактные п при ;>том быстродействующие программы событийного перевычисления 1>Ф. Данный метод впервые позволил рассматривать многие известные граф-схемные представления булевых функций в качестве частных случаев обобщенных граф-схем алгоритмов, применяя, соответственно, однотипные алгоритмы вычисления, основанные на интерпретации обобщенных граф-схем. При этом обеспечивается возможность нахождения наиболее компактного графического представления для заданной исходной функции и, соответственно, компактной "событийной" граф-схемы для реализации событийного принципа вычислений.
-
Системные, инструментальные и языковые средства программной поддержки организации эффективных вычислений в логических контроллерах, основанные на использовании наглядных представлений графических схем алгоритмов управления.
Достоверность полученных в диссертации результатов подтверждается математическими доказательствами и аналитическими оценками, а также разработкой действующего серийно тиражируемого программного продукта.
Теоретическая ценность полученных в диссертации результатов состоит в том, что они представляют собой основу теории высокоэффективных алгоритмов вычисления управляющих программ, предназначенных для применения в событийно-ориентированных системах управления с критическими требованиями к времени реакции.
Практическая ценность полученных в диссертации результатов в том, что они они дают возможность построения средств программирования контроллеров обеспечивающих высокую эффективность как проектирования программ за счет использования наглядных графических представлений, так и получаемого исполняемого кода, особенно при применении в распределенных и многопроцессорных системах.
Предлагаемый в диссертации метод построения обобщенных граф-схем впервые обеспечивает возможность вычисления функции с использованием наиболее компактного граф-схемного представления, существующего для этой функции. Для большинства функций это означает возможность нахождения граф-схемы размера полиномиально зависящего от количества аргументов функции, что обеспечивает и полиномиальное время предвычислений в событийных методах. При этом время интерактивной части вычислений, прямо влияющее на время реакции контроллера, линейно зависит от количества вершин граф-схемы, ассоциированных с изменившими значение переменными, в случае произвольной неортогональной схемы, либо линейно зависит от количества изменившихся переменных в случае если схема ортогональна.
Кроме того, предлагаемые в диссертации методы и алгоритмы обеспечивают эффективное использование событийного принципа вычислений не только при вычислении булевых функций, но и на макро уровнях процессов и задач, что делает событийный подход сквозным и поэтому эффективным.
Реализация и внедрение результатов работы. Основные результаты работы получены автором при выполнении научно-исследовательских и хоздоговорных работ по разработке, внедрению и дальнейшей модернизации интегрированных сред наглядного программирования логических систем управления по договорам с АО АвтоВАЗ, Констукторским бюро общего машиностроения г.Москва, Проектно - конструкторским предприятием "ИРИС", Конструкторским бюро информационно-заправляющих систем.
Результаты диссертации внедрены в составе серийно тиражируемых пакетов программного обеспечения "Интервью-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 on Parallel and Distributed Systems (Washington, USA. 1997), международном семинаре I L К Workshop on discrete e\ent systems WODKS'98 (Cagliari. Italy 1998) Internatiotial conference 1EE and UKACC "CONTROLW (Swansea, U.K., 1998).
Публикации. По результатам диссертационной {заботы опубликовано - 35 печатных работ, в том числе 2 монографии.
Структура и объем диссертации. Текст диссертации изложен на 241 странице, состоит из введения, семи разделов, заключения и приложений, содержит 59 рисунков, 5 таблиц и список литературы (140 наименований).