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

< . . Государственный комитет Российской Федерации по высшему образованию

Московский государственный горный университет

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

МОСКАТОВ Александр Генрихович

УДК 621.3

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

Специальность 05.13.12 — «Системы автоматизации проектирования (промышленность)»

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

Москва 1994

Работа выполнена в Московском государственном горном университете.

Научный руководитель акад., проф., докт. техн. наук ГОРБАТОВ В. А.

Официальные оппоненты: акад., проф., докт. фнз.-олат. наук РЕШЕТНИКОВ В. Н., доц., канд. тех;;, наук МЕТЕЧКО В. И.

Ведущая организация — Быковский завод средств логического управления.

Защита диссертации состоится « > . 1994 г.

в . I.'$. час. на заседании специализированного совета Д.053.12.12 Московского государственного горного университета 'по адресу: 117935, Москва, Ленинский проспект, 6.

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

Автореферат разослан « . . . »

Ученый секретарь специализированного совета

проф., докт. техн. наук ТОРХОВ В. Л.

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

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

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

Однако традиционная архитектура программной реализации, используемая в 70 - 80-е гг., требует чрезвычайно высоких объемов памяти, что приводило к дорогой реализации СЛУ на базе микрокомпьютера. Положение усугубляется тем, что для современных СЛУ характерны расширение функций и явное введение параллелизма, усложнение их функционирования, влекущее за собой повышение размерности моделей управления.

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

Таким образом, несомненно актуальной является задача декомпозиции модели управления при программной реализации ее в СЛУ.

В диссертационной работе поставлена цель:

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

Для достижения этой цели необходимо решить следующие задачи:

• развить архитектуру программной реализации СЛУ, ориентированную на

сквозное проектирование СЛУ с явным параллелизмом и обеспечивающую

компактное представление управляющего автомата в виде управляющей диаграммы;

•разработать методы оптимального распределения информации об управляющей диаграмме в памяти программно-реализованной СЛУ и выполняющие тем самым оптимальную декомпозицию управляющего • автомата;

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

Работа выполнялась в рамках темы 12.9.1.1.15 "Создание элементов автоматизированного проектирования горнодобывающими предприятиями" программы РАН исследований в области естественных наук до 2000 г., раздела 6 "Разработка теоретических основ проектирования и создания автоматизированных и роботизированных технологий добычи и переработки твердых полезных ископаемых" программы Комитета по высшему образованию РФ "Экологически чистое горное производство", госбюджетной темы "Разработка концепций и принципов математического и программного обеспечения САПР и управления в горном деле на основе искусственного интеллекта" и двух хоздоговорных тем.

Научная новизна работы заключается в:

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

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

Результаты работы внедрены в практику автоматизированного проектирования программно-реализованных контроллеров систем управления ячейками гибких производственных систем в ВНПО "Альтаир". Внедрение позволило сократить время проектирования контроллеров в среднем с 3 месяцев до 2 недель, сократить на 15% их стоимость и на 20% размеры, что весьма важно в ряде случаев для обеспечения заданных технических требований.

Внедрение подтверждено соответствующим актом.

Апробация работы. Результаты работы доложены и обсуждены на Всемирном конгрессе 1ТБ-93 "Информационные коммуникации, сети, системы и технологии" (Москва - 1993), XII, ХШ Всесоюзных симпозиумах "Логическое управление с использованием ЭВМ" (1989 - Симферополь, 1990 -Симеиз), 2-й международной конференции по безопасности атомных электрических станций и подготовке персонала" (Обнинск - 1991), семинаре "Отказоустойчивость и живучесть аппаратуры и программного обеспечения вычислительных машин, систем и сетей в процессе их разработки и эксплуатации" (Ленинград - 1991).

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

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

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

Исследование моделей представления управляющего автомата

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

Традиционно в качестве модели управляющего автомата берется граф переходов автомата в в < V, 5>. Однако его размерность в случае присутствия параллельных процессов в описании резко возрастает. В диссертации иссле-

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

п-1 и „ ¿(к-1) I

р\п- 1) к\(п-к)\

Из этой оценки видно, что пр>. характерных для практики размерностях управляющих диаграмм (т.е. описаний алгоритмов функционирования СЛУ): п й 50, р = 4,5,6, число вершин графа переходов (состояний автомата) превышает 1010. Это делает невозможными программную реализацию СЛУ.

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

Развитие архитектуры программной реализации СЛУ

Предложим новые архитектурные решения, ориентированные на естественную декомпозицию модели СЛУ, основанную на использовании явного параллелизма в управляющей диаграмме. Эта идея предполагает отличную от традиционной модель устройства управляющего автомата. _

Будем моделировать состояние конечного автомата параллельным множеством операций, т.е. дуг управляющей диаграммы. Начальное состояние представляется множеством из одной дуги {о0}, исходящей из начальной вершикл. Каждый шаг функционирования СЛУ выполняется следующим образом.

Для каждой операции о/, входящей в текущее состояние, выполняется ее действие ) и осуществляется переход к следующей за ней. Для этого рассматриваются все дуги оу, исходящие из вершины V/, в которую заходит дуга 01. Проверяются их входные условия «Ц/ на соответствие с текущим входным вектором X, поступающим на вход СЛУ. Если есть дуги с соответствующим X входными условиями ац , :о операция о/ заменяется в текущем состоянии СЛУ на операции оу, представляющие эти дуги.

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

(или счетчика, или совокупности триггеров), а нескольких регистров.

Архитектурное решение управляющего автомата показано на рис. 1. Здесь S - множество регистров, хранящих информацию о состоянии автомата, М - память, в которой содержится информация об управляющей диаграмме, F - блок формирования сигналов: выходных сигналов Y и сигналов, поступающих в и из памяти для определения очередного состояния и L-лхода в зависимости от X и S.

В памяти М содержится информация об управляющей диаграмме. Она организована следующим образом. Каждой дуге oi соответствует последовательность ячеек в памяти М. Начиная с это.й начальной ячейки хранятся:

ki - число заходящих дуг (в вершину, из которой исходит данная дуга о/);

к'i - счетчик числа заходящих дуг;

т/ - число следующих дуг (исходящих из вершины, в которую заходит данна»дуга);

а; - последовательность ячеек, представляющая входной набор, взвешивающий дугу Oi\

Pi - последовательность ячеек, представляющая выходной набор, взвешивающий дугу oi (точнее ту часть выходного вектора Y, в которую вносит вхлад oi);

ац,..., aimi - последовательность указателей на следующие за о> дуги (исходящие из вершины, в которую заходит о/). Каждый указатель ац состоит из двух ячеек: в первой содержится адрес ячейки в М, с которой начинается представление дуги оц (идентификатор дуги оф, во второй -'номер регистра Si, в который поместится идентификатор оц.

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

Это архитектурное решение позволяет достичь гораздо более компактной программной реализации СЛУ по сравнению с традиционной архитектурой за счет моделирования текущего состояния множеством одновременно выполняемых операций.'

Оптимальное распределение информации об управляющей диаграмме по блокам памяти программно реализованной СЛУ

Предложенная арихитектура программной реализации СЛУ ставит задачу

Рис. 1. Архитектура программно реализованной СЛУ с параллелизмом

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

Следовательно, их количество должно быть минимизировано.

Задачг минимизации параллельно функционирующих компонентов яв-ляет'ся по существу задачей оптимальной декомпозиции программно реализованной СЛУ.

Задача минимизации числа регистров относится к классическому случаю минимизации объема памяти на основе теоретико-графовой модели. Построим по управляющей диаграмме £)1'я# = < У,0> граф временного совмещения операций <3 с ° < О, 1 >. Две вершины оио) смежны в Сс, если выполняются три условия:

1) существует путь в из корня в конечную вершину, проходящий через ту о!, но не проходящий через дугу о/;

2) существует путь в из корня в конечную вершину, проходящ.. < через дугу оу, но не проходящий через дугу о(;

3) дуги, исходящие из последней общей вершины в путях их кор; я к 01 и О/, взвешены входными условиями сч, а/, не противоречащими друг Другу, т.е. возможен такой входной набор X , при котором одновременно будут справедливы и а/, и а/.

Очевидно, что если текущее состояние управляющего автомата определяется некоторым множеством О' дуг управляющей диаграммы 1)/а£, то все вершины О' в Сс попарно несмежны. Отсюда следует, что смежные вершины в Сс представляют случай потенциального вхождения этих вершин в множество, соответствующее некоторому состоянию управляющего автомата. Таким образом, их идентификаторы нужно помещать в разные регистры. Следовательно, нас интересует такое распределение дуг диаграммы по минимальному числу регистров, что всякие две смежные в Сс вершииы сопоставляются различным регистрам. Эта задача равносильна классической задаче раскраски графа Сс. •

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

Следует отметить, что в соответствии с предложенной архитектурой

программной реализации СЛУ, нам необходимо найти такое разбиение множества дуг управляющей диаграммы на классы, что дуги, соответствующие (потенциально) параллельным операциям, должны попасть в разные классы, а мощность каждого класса ограничена некоторым заданным числом дуг. Отсюда видно, что распределение дуг по классам должно определяться раскраской графа совмещения операций. Число классов {Л/}, определяемых раскраской, должно быть минимально при условии выполнения ограничения I Л; I ■< 5 для всех Л/, где $ - заданная величина.

Найдем внутренне устойчивые множества вершин графа Сс- Найдем минимальное покрытие ими вершин Сс.Построим двудольный граф Сл с множеством вершин X V ¥ , где У - множество вошедших в покрытие л внутренне устойчивых множеств, X - множество вершин Сс, каждая из которых принадлежит более чем одному внутренне устойчивому множеству. Ребро связывает верщину уче У и х/ е X, если о/ е Е\. Распределение вершин графа в? по классам соцветности определяется таким множеством Э рёбер графа Сл, в котором для каждой вершины ху е X находится только одно инцидентное ребро.

Пусть 5 - заданное ограничение по числу вершин в классе соцветности Л/ графа Сс. Взвесим вершины уч е У графа Сл, установив вес ич каждой вершины у1 как 5 минус шсло вершин Сс, входящих только в одно внутренне устойчивое множество в покрытии п. (Смысл веса - количество вершин из X, которые можно насытить в распределении £> вершиной уч). Тогда множество ребер Сл, насыщающих X и соответствующих допустимому распределению вершин в Сс, должно включать для каждой у,- не более т ребер.

Таким образом, показана однозначная связь понятия оптимального распределения вершин Сс по классам соцветности со свойством графа Сл иметь такое насыщающее х множество ребер, т.е. распределяющее все вершины ху е X, что каждой вершине инцидентно не более ич ребер в этом множестве. Назовем это свойство свойством распределимости, а множество £> ребер Сл, насыщающее все вершины X и включающее для каждой >•/ е- У не более ребер, полным распределением.

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

Если двудольный граф Сл = <Х,(У,)У),и> не обладает свойством

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

Исследование и характеризация свойства распределимости

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

Пусть в =<Х ,(У,Цг),и > - двудольный граф, С =<Х ',( Г ),и'> -полученный из него граф такой, что X' С X, У'*=0(Х'), - множество весов вершин из У, £/' £ I/ - множество ребер, соединяющих вершины X' и >". Назовем граф С сужением графа <3.

Утверждение. Двудольный граф О т<Х,( У, \У),С1> имеет полное

распределение тогда и только тогда, когда он не имеет сужений О =

» # * *

<Х ,( У , IV ),и > с числом х-вершин, превышающим сумму весов у-вершин: . усУ'

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

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

Шаг 1. Построить по управляющей диграмме граф совмещения операций <7С.

Шаг 2. Найти все внутренне устойчивые множества Сс.

Шаг 3. Построить таблицу внутренне устойчивых множеств и найти ее

покрытие л.

Шаг 4. Построить двудольный граф Сл ■< X ,(У,№),1/>.

Шаг 5. Если Сл обладает свойством распределимости, то найти допустимое распределение О в С7Л , насыщающее X. Оно будет определять раскраску Сг, удовлетворяющую заданному ограничению 5 на число вершин в классе.

Шаг 6. Если Сл не обладает свойством распределимости, то минимальным, дублированием вершин }'(«• У достичь свойства распределимости и выполнить действия, указанные в п.5.

Для обеспечения шага 5 разработан алгоритм порождения максимального распределения.

Назовем вершину уче У ненасыщенной по отношению к £>, если число инцидентных у,- входящих в О ребер меньше ич. (Вершина лг* е X ненасы-щена, если инцидентные ей ребра не входят в £>.) Назовем цепь, начинающуюся в нбнасыщенной вершине X и кончающуюся ненасыщенной вершиной у^еУ, в которой ребра поочередно входят и не входят в распределение Д чередующейся. Понятие чередующейся цепи позволяет получить механизм порождения максимального распределения. Добавление чередующейся цепи к распределению дает новое распределение с числом ребер на 1 больше.

Алгоритм состоит из двух шагов:

1. Взять начальное распределение Оо тривиальным образом: в цикле по вершинам х/ е X включать ребро (ху.уп у, с К, в Оо, если это возможно. Пусть 1£>о1=А. Считать начальное распределение текущим й(к).

2. Если'* < то проверить, существует ли чередующаяся по отношению в к О(к) цепь. Если ее нет, то О(к) - максимальное распределение. Если такая цепь Р есть, то перейти от 0(к) к й(к) + Р. Установить к:=к+1. Выполнить п. 2 с начала. Если то Р(к) - максимальное и полное распределение.

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

Шаг I. Найти в двудольном графе Ся = <Х,(У,№)М> все запрещенные

фигуры для свойства распределимости - сужений С?ь

Шаг 2. Построить семантическую таблицу. Столбцам ее соответствуют

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

Шаг 3. Найти минимальное покрытие столбцов семантической табл..цы строками е -{учиуа-Лк }• <

Шаг 4. Дублировать вершины уц ее .

Для задач высокой размерности разработан локально оптимальный метод нахождения распределени..;

Шаг 1. Найти максимальное распределение D в =<Х,( Y, W),U>. Пусть X - подмножество насыщенных вершин, а; - число насыщенных вершиной У№ У вершин xje X', bi - число смежных с уче У вершин xje X \ X'.

Шаг 2. Если IX - X' I > 0, то выбрать у еУ, для которой шах min (к»/ - сцМ) . i<cY

Продублировать выбранную вершину у е У, получив преобразованный граф Ся. Перейти к шагу 1.

Если Х'тХ, то конец.

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

1

Программные средства оптимальной декомпозиции программно реализованной СЛУ и их внедрение

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

Работа подсистемы "Декомпозиция" начинается с выполнения модуля . DiagPaths, который выделяет все пути упр вляющей диаграммы и проводит анализ, определяя минимально возможно; заполнение блока памяти СЛУ при максимальном распараллеливании. Эта величина определяется как максимальное число дуг диаграммы £min, принадлежащих только одному пути. Она играет важную роль, поскольку

- И -

определяет ограничения на размер блока памяти: I Emit I * I Л") * I У), где I Х\, I У1 - размерности входного и выходного векторов СЛУ соответственно. Эта характеристика выдается пользователю, который может учесть ее при определении размера блоха памяти IMI. По найденным путям модулем DGraph строится двудольный граф Сл , с помощью которого будет «скаться оптимальное распределение дуг диаграммы по блокам памяти СЛУ.

Затем в зависимости от установки, даваемой пользователем САПР, будет применяться точный или приближенный локально оптимальный алгоритм. В первом случае выполняется последовательность модулей Stable, MinCover, DgraphTrans, MaxDistr. Во втором случае итерационно применяются модули'МахОЫг.ООгарЬМос!, пока модуль MaxDistr не даст полное распределение. Согласно этому распределению модуль DAlloc строит окончательное распределение.

Программные модули подсистемы "Декомпозиция" написаны на языке Турбо Си для MS DOS.

Применение подсистемы и экспериментальное ее исследование проводились на ПК AT-386DX-40/4. На практике применялись и в процессе тестирования исследовались обе части подсистемы, реализующие точный и приближенный методы порождения распределения, Для разных значений размерности управляющей диаграммы п и степени параллелизма р осуществлялось различное количество тестов, однако проведенные тесты позволяют утверждать об экспоненциальной зависимости времени t от и, р в.точном и "слабо" степенной зависимости t(п,р) в локально оптимальном методе. В частности, в точном методе при «=30, р=5 время решения составляет 2 - 5 103 с, в локально оптимальном методе при >i £ 150 время решения составляет не более 3-мин.

Разработанные программные средства внедрены- в практику автоматизированного проектирования программируемых контроллеров в системах управления ячейками гибких производственных систем в ВНПО "Альта-ир". Программируемый контроллер представляет собой программно реализованную СЛУ, реализуемую на одной плате стандартного размера. Требования по перепрограммируемости касаются изменения условий выполнения некоторых операций. В функции контроллера входят обработка сообщений диспетчера и выработка управляющих и синхронизирующих воздействий на рабочие органы четырех' компонентов ячейки: обрабатывающего центра (ОЦ); локального накопителя (Н), служащего для временного хранения деталей и заготовок, обрабатываемых ОЦ; те-

лежек Т1 и Т2, перемещающихся по монорельсовым линиям, соединяющим ОЦ со складом и участком штамповки соответственно; робота-манипулятора, обеспечивающего прием и передачу деталей и заготовок между ОЦ, Н, Т1 и Т2. Для обеспечения требований по перенастройке на предприятии разработано 18 плат, реализующих функции контроллера, 7 из них осуществляют чисто логическое управление. С помощью предложенных методов было получено оптимальное решение по программной реализации СЛУ для этих режимов.

Для 8 режимов на платах г 'ализованы микропроцессорные системы с традиционным программным управлением. В оставшихся трех случаях управление логическое, но условия и операции управляющего автомата связаны с выполнением микропрограмм, которые нужно хранить не отдельно в ПЗУ, а вместе с моделью управления - как информацию о дугах управляющей диаграммы. В отличие от обычных систем логического управления здесь вход и выход представляются входными и выходными векторами не постоянной длины, а существенно различной - от 0,5 до 45 Кб. Для этих режимов применялось автоматизированное проектирование. Па первом этапе при решении задачи декомпозиции разработчиками осуществлялось распределение информации об управляющей диаграмме "вручную". На втором этапе в диаграмме остались только дуги, различиями в объеме информации для которых можчо было пренебречь, поэтому стало возможным применить разработанные в диссертации методы и программные средства оптимальной декомпозиции.

Внедрение позволило сократить время проектирования контроллеров в среднем с 3 месяцев до 2 недель, сократить на 15% их стоимость и на 20% размеры, что весьма важно в ряде случаев для обеспечения заданных технических требований.

ЗАКЛЮЧЕНИЕ

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

желаемой эффективности, что требует декомпозиции СЛУ.

Для решения задачи оптимальной декомпозиций программной реализации СЛУ потребовались:

• исследование и сове^ше- тгвовакие архитектуры программно реализованных СЛУ, допускающей декомпозицию модели управления; •разработка методов декомпозиции, ориентированных на архитектуру программной реализации СЛУ, основанной на представлении модели управления в виде управляющей диаграммы.

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

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

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

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

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

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

6. Предложена методика сквозного проектирования программно реализованных СЛУ, ориентированная на применение развитой архитектуры СЛУ и разработанных методов декомпозиции СЛУ.

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

Методика и подсистема "Декомпозиция" внедрены в практику автоматизированного проектирования СЛУ в ВНПО "Альтаир". Внедрение позволило повысить качество проектов СЛУ и сократить сроки проектирования.

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

1. Москатов А.Г. Декомпозиция программно реализованных систем логического управления. - В кн.: Информационные коммуникации, сети, системы и технологии. М.: Межд. акад. информатизации, 1993, 232-237. f_s

2. Москатов А.Г. Алгоритм раскраски графа и его использование в обеспечении безопасности систем управления ядерными реакторами. - В сб.: Труды 2-й международной конференции по безопасности атомных электрических станций и подготовке персонала, Обнинск: Обнинский ИАЭ, 1991, 56-57.

3. Москатов А.Г. Ускоренный алгоритм раскраски графов и его применение для параллельной декомпозиции вычислительных и управляющих систем. - В сб.: Материалы семинара "Отказоустойчивость и живучесть аппаратуры и программного обеспечения вычислительных машин, систем и сетей в процессе их разработки и эксплуатации". - Л.: ЛДНТП, 1991, 80-81.

4. Кулиев Г.Б., Москатов А.Г. Проектирование пневмоавтоматов управления аэрологическими системами. - В кн.: Логическое управление с использованием ЭВМ. М.- Симферополь, Изд-во АН СССР, 1989, 318-320.

5. Москатов А.Г., Алейников В.А. Алгоритм бь'-трои раскраски вершин графа. - В кн.: Логическое управление с использованием ЭВМ. - М.-Симеиз, Изд-во АН СССР, 1990, 38-39.

к