Введение к работе
В диссертации изложены основные научные результаты, полученные и опубликованные в течение 1970—1991 гг., образующие новое перспективное направление автоматизации проектирования систем логического управления (СЛУ), ориентированное на синтез параллельно взаимодействующих подсистем при реализации заданного закона управления сложным объектом. Проанализированы и теоретически обобщены итоги исследований и разработок, выполненных для решения важной научной и народнохозяйственной проблемы повышения эффективности управления техническими системами и процессами за счет достижения максимального быстродействия. Приведены итоги использования на практике полученных научных результатов.
Актуальность проблемы. Большой класс технических систем составляют системы с сосредоточенными параметрами. Параметры могут быть конструктивными: процессор, технологический участок ГАП, память и т. д.; функциональными: алгоритм, величина потока, объем изготовляемой продукции и др. Существенный подкласс этих систем с сосредоточенными параметрами образуют логико-вычислительные системы — программно-аппаратные комплексы, системы управления гибким производством, локальные системы управления технологическим процессом. Описание функционирования систем этого класса осуществляется средствами логического управления. Для автоматизации проектирования таких систем удобной формализацией являются модели СЛУ, которые могут быть представлены функциями на графах. При разработке- математического обеспечения САПР и с целью борьбы с информационным взрывом в ЭВМ решается большой класс оптимизационных задач, порождаемых проблемой уменьшения размерности задач с помощью их декомпозиции. С другой стороны, повышение качества сводится к ослаблению функциональной связности проектируемых систем, которое определяет увеличение их безотказности, уменьшение взаимного влияния компонент системы. Последнее требование определяет вид декомпозиции, а именно — параллельной.
Параллельная декомпозиция соответствует мультипликативной операции декартова произведения. С помощью этой операции решается задача синтеза оптимального распределения процессов по ЭВМ ЛВС при создании отказоустойчивого программного обеспечения. Элементами одного из множеств в этом случае являются ЭВМ сети, а другого — решаемые задачи. Элементы декартова произведения находятся с учетом ограничений, порождаемых функцией совместимости задач, заданной кратностью резервирования каждой задачи и требуемой эффективностью использования вычислительных
ресурсов. .- '.'':--'.'" "
Операция декартова произведения множеств служит эф
фективным средством, формализации и ряда других задач, та
ких! "как оптимальное'распределение изделий по обрабатыва
ющим центрам, Оптимальное распределение файлов по диско
вым устройствам, оптимальное распределение транспорта по
карьерам и т. :д. Решение этих задач сопровождает создание
различного рода автоматизированных систем обработки ^ин
формации и управления, среди которых выделим системы ло
гического управления СЛУ, обеспечивающие распараллели
вание- управления. -
'" Проблема построения'декомпозиции СЛУ исследовалась в работах ряда отечественных и зарубежных ученых, которые создали алгебраическую теорию разложения автомата на-несколько более простых автоматов. Задача декомпозиции автоматов впервые была поставлена Хартманисом (1964 .г.),: который Для её решения предложил специальный язык — язык разбиений со свойством -подстановки (СП-разбиений) ;и'определил некоторые алгебраические операции над разбиениями. В результате развития языка СП-разбиений Хартманисом совместно со Стирнзом была создана '(1964 г.) абстрактная математическая система — алгебра пар,'-которая определила единую математическую основу всех результатов, полученных на основе изучения пар разбиений. '
"Для расширения возможностей этого подхода Но'буеки,
Тадаши, Нориоши предложили (1974 г.) расширение этой ал
гебры до алгебры троек, четверок, ..., п-к, что, в свою оче
редь, "было основано на использовании свойств соответствую
щих разбиений. ! . ' -
В работах -Йоли и Гинзбурга (Т964 г.) построение деком
позиции основано на нахождении униформных допустимых
разбиений, являющихся частным случаем СП-разбиенвй.
Предложенный Кохави метод основан на нахождении 'авто
мата, эквивалентного заданному, на множестве состояний кб-
торого существует хотя бы одно разбиение со свойством под--
становки. :
Расширив понятие СП-разбиений введением ПС-связки, О. П. -Кузнецов исследовал (1969 г.) задачу параллельной де-
композиций с разделением входов. Предложенный-им,;метод применим к.сравнительно узкому классу^автоматов, являющемуся подклассом автоматов с, СП-разбиением.на-множеет-васостряний. Г;,,.. . ,-,.. , , : - '.-.;. '.\»v\ -,- - -.7-. г. .;:: -.---. .... Более,,полное исследование-проблемы,- связанной; є -декомпозицией, конечных автоматов, содержится в.-цикле работ,: выполненных..: под руководством; академика-. Л. Н.-; Мелихова.-В.основу,разработанных-методов и, алгоритмов-декомпозиции здесь, положено нахождение; подстановок множества состоя-.' иди,., автомата, приводящих -матрицу смежности^ соответствующего графа к диагональному виду. В свою очередь, иахожде-. ние таких-подстановок требует, перебора-пар разбиений, что практически не реализуемо при разложении автоматов реальной сложности и приводит к необходимости поиска различного рода, эвристических приемов сокращения .перебора.
Таким образом, в рамках алгебраического подхода разрабатывались те или иные синтаксические процедуры решения задачи декомпозиции, которые в реальных проектах не давали решения проблемы, так как практические системы являются мультипликативно-повторными, т. е. структурами, в которых хотя бы две компоненты описываются соответствующими автоматными операторами, имеющими общий аргумент. Синтаксические процедуры были предназначены для фактического построения параллельной декомпозиции,- а для мультипликативно-повторных структур, быть может на.,последнем шаге выяснилась их принципиальная неприемлемость,, другими словами, синтаксические процедуры в рамках алгебраического подхода были процедурами распознавания мультипликативной бесповоротности, а не средством проектирования систем и не позволяли разрабатывать математическое обеспечение САПР СЛУ для произвольного случая.
Принципиально иной подход к решению задачи декомпозиции был предложен в начале 70-х годов [2, 3].-. Он состоит в нахождении и учете запрещенных фигур графа переходов автомата, определяющих его разложимость. В качестве инструмента решения задачи разработан аппарат многокомпо: нентной; раскраски графа, который позволяет- находить па» раллельную декомпозицию автомата без. громоздкого анализа свойств разбиений на множестве его состояний и-независимо от существования разбиений с заданными свойствами. Связь темы диссертации с государственными научными программами. Работа выполнялась в рамках Программы исследований в области естественных - наук до 20QQ года АН СССР, тема 12.9.1.1.15 «Создание элементов автоматизированного проектирования и управления горнодобывающими предприятиями», Программы Гособразования СССР, Министерства науки, высшей школы и технической политики РФ, раздел 6-.«Разработка теоретических основ проектирования и
создания автоматизированных' и- роботизированных техноло"-" тий "добычи-и -переработки твердых полезных ископаемых», отраслевых Программ Минсудпрома «Парус» и «Компас»:
Целью работы является разработка теории и практики
автоматизированного проектирования параллельно функцио
нирующих СЛУ на основе графовых моделей и их характе-
ризацйи. -
" Идея работы основана на характеризационном анализе и'
состоит в выявлении критических структур ориентированных,
графовых моделей, ограничивающих их разложимость с по
следующей трансформацией в неориентированные структу
ры и замене содержательного анализа моделей на стандарт
ные преобразования дискретной математики "с учетом запре
щенных фигур этих преобразований. '. ' :
,Методы исследований. Для решения поставленной в работе проблемы использовались методы дискретной математики,-в том числе теории графов и математической логики, теории автоматов и характеризационного анализа.
Основные научные положения, выносимые на защиту, и их новизна:
1. Метод преобразования модели, описывающей функционирование СЛУ в модель, определяющую ее структуру и позволяющую установить объективные условия разложимости исходного закона управления на основе определения связно: сти нетерминальных символов по входным терминальным символам [23].
2.. Идентификация СЛУ и характеризация параллельной декомпозиции "систем различных классов по соответствующей этому классу формализации с целью выбора базовых алгоритмов и программных модулей для проектирования подсистем, параллельное функционирование которых эквивалентно функционированию исходной системы [1, 12, 32].
-
Метод сведения задачи построения параллельной декомпозиции СЛУ к специальной задаче раскраски графов — многокомпонентной раскраске графа зацепления, определяющего функциональную связность состояний исходной модели; процедура преобразования графа переходов заданной СЛУ и полученной раскраски в графы переходов компонент разложения, декартово произведение которых содержит исходный граф [2, 14, 16, 23, 31].
-
Нахождение запрещенных фигур преобразования модели исходной системы в модели компонент разложения при заданных ограничениях на размеры компонент и степень автономности их работыдля каждой из предложенных формализации в зависимости от класса системы [9, 11, 20, 22].
-
Методы преобразования моделей расширением носителя, сужением сигнатуры по отношению зацепленное и рас-
ширением сигнатуры по отношению идентификации к виду, позволяющему получить удовлетворительное решение [19, 26, 28].
-,-.-6. Математическое обеспечение в виде совокупности алгоритмов, реализующих предложенные модельные преобразования, и программное обеспечение в виде пакета прикладных программ, отдельные- модули которого реализуют разработанные в работе или известные ранее алгоритмы, и позволяющее получать в целом решение- задачи, параллельной декомпозиции автоматных операторов '[4, 8, 30].
Обоснованность и достоверность научных положений, выводов и рекомендаций подтверждаются результатами использования предложенного метода декомпозиции для разложения автоматов различных классов при изменении в широком диапазоне, таких параметров, как мощность носителя модели, мощность множества входных терминальных символов, коэффициент плотности графа переходов автомата, степень равномерности распределения входных символов по. элементам сигнатуры модели; работоспособностью и надежностью СЛУ, созданных на базе разработанных методов и алгоритмов.
Научная значимость работы состоит в разработке принципиально нового подхода к решению задачи параллельной декомпозиции СЛУ, основанного на учете характеризации разложимости автоматного оператора на ранних этапах нроек^ тирования с помощью. предложенной многокомпонентной раскраски графов.
Практическое значение работы заключается в разработке:
— методики идентификации СЛУ. и рекомендаций'по ис
пользованию той или иной формализации в зависимости от
класса проектируемого устройства управления; -
. — процедур модельного преобразования, позволяющего заменить содержательный анализ модели, описывающей функционирование СЛУ, на последовательность стандартных операций дискретной математики в .модели, определяющей структуру компонент разложения;
' '— методики расщепления запрещенных фигур раскраски оптимальным сужением сигнатуры модели по отношению за-цепленностн состояний автомата . по входным терминальным символам;
способа оптимального расширения сигнатуры модели по отношению идентификации на основе учета частотных свойств модели с помощью предложенного функционала;
методики определения степени зацепленности состояний и нахождения пар состояний, соцветность которых обеспечивает разложимость автомата при заданных ограничениях на размеры компонент и степень автономности их работы;
алгоритмов модельных преобразований и вычислений,
позволяющих осуществлять автоматизированное проектирование параллельно функционирующих СЛУ по заданному в виде функций на графах закону управления;
— пакета прикладных программ, содержащего совокупность программных модулей, последовательность включения которых зависит от класса проектируемого устройства и бсу-ществляется с помощью программы «Диспетчер».
Реализация результатов работы. На основе полученных результатов разработана система управления погрузочно-транспортными операциями у капитальных рудоспусков и спуско-подъемными операциями на шахтных стволах А'рхон-ского и Згидского рудников Садонского свинцово-цинкового комбината..
Спроектировано устройство управления процессом спекания на агломерационной машине для завода «Электроцинк».
Разработанный декомпозиционный подход был применен при проектировании системы управления внутришах'тным электровозным транспортом и погрузочно-разгрузочными работами на руднике «Молибден» Тырныаузского вольфрамо-молибденового комбината.
В рамках отраслевых программ Минсудпрома «Парус» и «Компас» результаты работы использованы при создании САПР бортовой автоматики . систем жизнеобеспечения корабля.
Результаты исследований используются в учебном процессе Северо-Кавказского горно-металлургического института, научно-исследовательской работе студентов и аспирантов, при курсовом и дипломном проектировании, а также в цикле лекций по САПР.
Апробация работы. Основные положения работы докладывались и получили одобрение на семинарах «Оптимизация дискретных систем управления» (Москва, 1972, 1979), «Прикладные вопросы теории систем и системотехники» (Москва, 1973), «Вопросы автоматизированного логического проектирования устройств управления процессами и объектами в промышленности» (Челябинск, 1973), зональной научно-технической конференции «Разработка и внедрение систем автоматизированного проектирования в машиностроении» (Ижевск, 1983), на Всесоюзных симпозиумах «Логическое управление» и координационных совещаниях «Математическое обеспечение интеллектуальных систем САПР — ГАП (Москва, 1977; Баку, 1979; Курск, 1980; Каунас, 1980; Орджоникидзе, 1981; Алушта, 1982; Тбилиси, 1983; Куйбышев, 1985; Ташкент, 1986; Устинов, 1987; Орджоникидзе, 1988; Феодосия, 1989;' Симеиз, 1990; Новый Свет, 1991); на Всемирном конгрессе ITS-92 «Информационные коммуникации, сети, системы и технологии» (Москва, 1992).
Публикации. Основное содержание диссертации отражено в 32 научных работах, в том числе в 1 авторском свидетельстве.
. Автор выражает искреннюю признательность академику В. А. Горбатову за научные консультации и методическую помощь при подготовке диссертации.
