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

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

УДК 519.7$Г 6 ОД 1 4 АПР 1998

Короткевяч Андрей Геннадьевич

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

05.13.01 - Управление в технических системах

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

Минск -1998

Работа выполнена в Белорусском Государственном Университете информатики и радиоэлектроники.

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

профессор, члсн-корреспондснт АНБ Закрсяскин А. Д.

Официальные оппоненты: доктор технических наук,.

Оппонирующая организация: Белорусская государственная

Защита состоится 16 апреля 1998 г. в 14 часов на заседании совета по защите диссертаций Д 02.15.01 в Белорусском государственном университете информатики и радиоэлектроники по адресу:

2200027, Минск, П. Бровки, 6. БГУИР, корп. 1, ауд. 232.

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

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

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

совета по защите диссертаций,

доцент Пашкевич А. II.

кандидат технических наук, доцент Супрун В. П.

политехническая академия

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

Кешишьян В. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуачьиость темы диссертации. Классическая модель конечного нзтомата является хорошо зарекомендовавшим себя способом 1бстрактного представления устройств на базе цифровых схем. Однако ;сли необходимо создание устройства для управления несколькими наимодействующими и разветвляющимися асинхронными процессами, де нельзя обойтись описанием нескольких независимых автоматов, >писание устройства как одного конечного автомата также оказывается 1еприемлсмым, поскольку число его состояний может быть слишком юлико. В этих случаях целесообразно использование математических юделей, отражающих параллелизм; наиболее удобной и популярной из [их являются сети Петри. Имеется много работ, посвященных фименению таких моделей для разработки и реализации параллельных правлякицих алгоритмов. Методы решения ряда задач, связанных с онечными автоматами, неприменимы для этих моделей; кроме того, для их возникают новые, специфические задачи. В частности, по тношению к параллельным алгоритмам весьма сложна задача анализа орректности. Существующие методы ее решения неэффективны: одни з них не позволяют локализовать нарушения корректности, тогда как ругие крайне трудоемки. Не разработан и способ конструирования таких лгорнтмов, который бы обеспечивал их корректность. Имеющиеся егоды анализа и оптимизации секвенциальных автоматов относятся в сновном к синхронной интерпретации и требуют адаптации для :инхронного случая. Данная работа посвящена решению перечисленных некоторых других задач, относящихся к указанной области.

Связь работы с крупными научными программами, темами. езультаты диссертационной работы связаны с выполнением НИР Логическое управление динамическими системами", проводимой в аучном центре проблем механики машин НАНБ и лаборатории 312 ГК НАИБ в рамках Республиканских программ фундаментальных следований "Механнка-51", "Механика-37''.

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

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

3) определение праиил эквивалентных преобразований параллельных автоматов;

4) разработка алгоритмов анализа асинхронных секвенциальных автомагов;

5) разработка алгоритмов оптимизации асинхронных секвенциальных автоматов.

Научная новизна_помученных ре зулыпатов. И диссертации

предложены и обоснованы:

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

2) формальный метод создания синтаксически корректных параллельных алгоритмов логического управления;

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

Практическая значимость полученных результатов:

1) создано программное обеспечение для анализа корректности ПРАЛУ-алгоритмов, реализующее разработанный метод, позволяющий анализировать параллельные алгоритмы логического управления с возможностью получения последовательности выполнения цепочек алгоритма, приводящей к некорректной ситуации, если таковая возможна;

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

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

Результаты работы внедрены в учебный процесс на кафедре УМФ БГУ, на кафедре вычислительной техники Минского высшего военного инженерного училища и на кафедре "Тракторы" БГПА. Результаты использованы в САПР дискретных устройств в Институте технической кибернетики ПАН Беларуси. Также результаты внедрены в Центре проблем механики машин НАИБ, где используются для анализа способов управления скоростными характеристиками перспективных магистральных автопоездов Минского автозавода Акты о внедрении приведены в приложении к работе.

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

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

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

3) предложена методика оптимизации параллельных автоматов на абстрактном уровне и мйнимизации числа внутренних переменных секвенциальных автоматов;

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

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

Апробация результатов диссертации. Основные результаты работы цокладывались. на научно-методической конференции "Новые информационные технологии в учебном процессе" - Минск, 1994; на тучно-технической конференции "Теория и методы создания 1нтеллектуальных САПР" - Минск, 1994; на научно-технической сонференции "Современные проблемы радиотехники, электроники и :вязи" - Минск, 1995; на международной конференции "Автоматизация фоектирования дискретных систем" - Минск, 1995; на V межгосударственной научной конференции "Актуальные проблемы шформатики: математическое, программное и информационное •бесиечение" - Минск, 1996; на международной научно-технической хжференции "Моделирование интеллектуальных процессов фоектирования и производства" - Минск, 1996; на VII Белорусской

Математической конференции - Минск, 1996; на Второй международной конференции "Автоматизация проектирования дискретных систем" -Минск, 1997; на постоянно действующем семинаре "Логическое проектирование" в ИТК НАНБ - Минск, 1994-1997.

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

Структура и объём диссертации. Диссертация состоит из введения,, общей характеристики работы, четырёх глав, заключения, списка использованных источников и приложения. Диссертационная работа изложена на 140 страницах машинописного текста и содержит 3 рисунка, расположенных на 2 страницах; 7 таблиц, занимающих 6 страниц; список литературы, размещённый на 11 страницах, включает 114 наименований.

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

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

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

Под параллельным автоматом1 понимается множесгво переходов вида Ц|: -р1 ->А| ->У(, где р* и А; - элементарные конъюнкции булевых переменных, определяющие условие срабатывания перехода и выходные сигналы, соответственно; р; и V* - метки, представляющие множества частичных состояний параллельного автомата.

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

1 Закрсвский А Д. Параллельный автомат //Докл. АН БССР - 1984,- Т. 28 - № 8 -С. 717-719.

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

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

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

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

Закревский А.Д. Элементы теории а-сетей// Проектирование систем югического управления.- Минск: Ин-ттехн. кибернетики АН БССР, 1986.- С. 412.'

Под секвенцией понимается выражение вида 1' |— к, где Г - булева функция. Эго выражение используется для обозначения причинно -следственной связи между комбинациями значений булевых переменных. Обращение левой части секвенции в 1 является причиной обращения в 1 ев правой части. Секвенция, левой частью которой также является элементарная конъюнкция, называется простой секвенцией. Система секвенций, или секвенциальный автомат3, есть множество Б секвенций интерпретируемое следующим образом. В синхронном случае -обращение в некотором такте левой части некоторой секвенции в 1 означает обращение в 1 её правой части в следующем такте. В случае асинхронной интерпретации полагается, что обращение в 1 левой части некоторой секвенции приводит к обращению в 1 её правой части через некоторый неопределённо малый промежуток времени. Поскольку в правой части - элементарная конъюнкция, выполнение секвенции означает присвоение значений булевым переменным. Множество всех булевых переменных, входящих в секвенции системы, как и в случае параллельного автомата, распадается на три подмножества. X входных, У выходных и Z внутренних переменных.

Во второй главе рассматриваются вопросы анализа а-сетей. Для данной предметной области основной интерес представляют такие вопросы: анализ корректности сети и анализ достижимости корректной сети.

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

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

1 Закревский А Д. Логический синтез каскадных схем - М : Наука, 1981.-416 с.

Алгоритм 1. Анализ корректности а-сети.

1. Построить вершину, соответствующую начальному состоянию а-сети. Она добавляется к множеству V вершин строящегося графа (изначально пустому)

2. Пока ( в V имеется вершина V, которая не помечена как

исследованная) {

Если (в соответствующем V состоянии есть возбуждённые предложения) {выбрать одно (любое) из них. Для каждого принадлежащего ему перехода построить состояние, получающееся из данного в случае его срабатывания. Если (в этом состоянии нарушается условие безопасности) {зафиксировать нарушение безопасности, определить путь к данному состоянию из начального по дугам графа, перейти к п. 6} Иначе {провести дугу от данной вершины к вершине, соответствующей полученному состоянию; если такой вершины нет, ввести ее в граф. Дуге поставить в соответствие переход. Данную вершину пометить как

исследованную.}} }

3. Полученный граф проверить на сильную связность. Если (он не сильно связен) {найти путь от начальной вершины к ближайшей вершине, из которой недостижима начальная, или к тупиковой, если такая есть; сеть объявляется невосстанавливаемой, а найденный путь -ведущим к нежелательному состоянию, затем перейти к п. б}.

4. Для каждого перехода сети искать соответствующую дугу графа. Если (для некоторых переходов дуги не найдены) {эти переходы объявляются избыточными; перейти к п. 6}.

5. Сеть корректна. Конец.

6. Сеть некорректна. Конец.

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

Данные вычислительного эксперимента по сравнительному анализу имеющихся и предлагаемой методик, проведенного на [ВМ-совместимом компьютере с процессором ГШе! 486 (язык программирования С), позволяют сделать вывод, что предлагаемый метод значительно выигрывает по времени у метода, предполагающего построение полного графа достижимости (для сети из 60 переходов - в среднем более чем

вдвое. Выигрыш для конкретной сети зависит от ее структуры: для паралельно-последовательных сетей предлагаемый метод оказывается полиномиальным).

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

Таблица 1

48, 10 60, 20 72, 30 84, 40 96, 50

Полный гра4 10.5 21.6 34.5 67.7 86.6

Подграф 9.7 17.4 27.2 31.9 38.1

Далее рассматривается задача анализа достижимости корректной а-сети. Показано, что для такой сети можно получить компактное описание множества достижимости.

Предлагается следующий алгоритм.

Алгоритм 2. Построение формулы достижимости Ьва-сети.

1) Р - множество подсетей; Р=0; пока (существует переход т\ -> V,)

такой, что для любого перехода ту. =>

{

• Пометить т, и все его выходные места.

• Выполнять {пометить все переходы, все входные места которых помечены} до тех пор, пока (множество помеченных объектов увеличилось при последней итерации).

• Все помеченные места, не являющиеся входными для помеченных переходов, образуют множество Б'«^; если (для любого непомеченного перехода тк: ЦкП8'ои1*0 => Цк^Б'ош), то {помеченные объекты образуют искомую подсеть, включаемую в Р} }

2) Выполнять

{

В множестве Р найти сеть, внутри которой не содержатся другие сети из Р, заменить еб одним местом, которому поставить в соответствие сеть, состоящую из всех мест этой подсети и переходов, все входные и выходные места которых принадлежат ей (поиск и замена ведется для

всех сетей); для этой сети запомнить начальную маркировку и удалить сеть из Р. } до тех пор, пока (Р * 0).

3) Построить множества достижимости для всех полеченных сетей и выразить функцию достижимости через ДНФ.

4) Конец.

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

В третьей главе речь идёт о ПРАЛУ-алгоритмах и параллельных автоматах.

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

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

Операция введения петли. В любое предложение может быть введена цепочка, конечная метка которой совпадает с начальной меткой этого предложения.

Операция введения предложения. В сеть может быть добавлено новое предложение следующим образом: определяется Я - множество подмножеств Р (где Р - множество мест сети) такое, что существует одно или несколько множеств цепочек, мощность каждого из которых равна и внутри каждого из которых цепочки принадлежат к одному предложению, а множества их конечных меток, если из них удалить некоторое их общее подмножество р (возможно, р-0), образуют в совокупности множество Я; каждое из таких множеств цепочек заменяется одной, конечная метка которой равна лир, где л - начальная метка нового предложения, целиком состоящая из вновь вводимых мест, а конечные метки цепочек нового предложения образуют в совокупности множество Я.

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

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

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

Теорема. Если для двух переходов Xi и Tj живой и безопасной а-сетн, таких, что все места, принадлежащие pj и щ, попарно

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

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

Сформулируем её в виде алгоритма.

Алгоритм 3. Конструирование корректного ПРАЛУ-алгоригма.

1. В качестве исходного объекта принять элементарную сеть 1 -» 1.

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

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

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

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

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

6. Конец.

Рассмотрены вопросы конструирования иерархических алгоритмов и алгоритмов - двухполюсников; рассмотрен также вопрос об оптимальном представлении конструируемого алгоритма в памяти ЭВМ. На основе данной методики может быть создана диалоговая система проектирования ПРАЛУ-алгоритмов.

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

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

Здесь получены следующие теоретические результаты:

Теорема. Если одна и та же последовательность входных сигналов подана на входы параллельного автомата, который в одном случае находится в полном состоянии М], а в другом - в состоянии'^гэГ^, то множество переходов, выполненных в каждый момент времени в первом случае, является подмножеством переходов, выполненных в соответствующие моменты во втором, если соответствующая автомату а-сеть остается самосогласованной в любом состоянии, достижимом из N1

или N2.

Теорема. Если множества частичных состояний 8] и &2 параллельного автомата эквивалентны, то и множества 8]иР и БгиР, где Р - любое множество частичных состояний автомата, такое, что 8]иР и

- безопасные состояния, эквивалентны.

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

Алгоритм 4. Проверка множеств частичных состояний параллельного автомата на эквивалентность.

1. Дан параллельный автомат и пара (0, р) множеств его частичных состояний, проверяемая на эквивалентность. Получить системы секвенций, описывающие реакции автомата, находящегося в частичных состояниях 6 и р; для этого найти для каждого из этих множеств декартовы произведения предложений, начальные метки которых входят в них; логически перемножить условия операций ожидания и действия цепочек из каждого элемента декартова произведения; исключить секвенции, левые части которых тождественно равны нулю; отразить в системе возможность того, что ни одна цепочка предложения не сработает, если дизъюнкция условий операций ожидания всех цепочек предложения не равна тождественно 1.

2. Сравнить системы секвенций, полученные в предыдущем пункте. Если они различны, перейти к п. 5.

3. Найти все возможные пары множеств частичных состояний, в которые автомат перешел бы из множеств частичных состояний 6 и р. Включить те из них, которые еще не рассматривались, в очередь на проверку (равные множества считаются эквивалентными); если (очередь на проверку исчерпана) {перейти к п. 4}; иначе {выбрать следующую пару из очереди на проверку и перейти к п. 1}.

4. Множества 9 и р эквивалентны. Конец.

5. Множества 0 и р не эквивалентны. Конец.

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

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

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

Четвёртая глава посвящена системам секвенций. Рассматривается задача анализа корректности и достижимости таких систем. Предлагается алгоритм получения компактного описания (в виде троичной матрицы) множества достижимости асинхронной системы секвенций. По такому описанию непосредственно определяется отношение параллельности на множестве секвенций, атакж$ выполнение свойств корректности.

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

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

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

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

ВЫВОДЫ

Основные результаты, полученные в работе, таковы.

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

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

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

4. Разработана методика анализа секвенциальных автоматов, отличающаяся рассмотрением переходов между множествами состояний системы (а не между отдельными состояниями). Она позволяет анализировать асинхронные системы секвенций, получая компактное (в виде ДНФ или троичной матрицы) описание множества достижимости.

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

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

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

СПИСОК ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ РАБОТ 1.3акревский Л.А., Короткевич А.Г. Оптимизация обмена ресурсов в распределенной системе// Актуальные проблемы информатики: математическое, программное и информационное обеспечение: Материалы V межгосударственной научной конференции (14-18 мая 1996 г., Минск, Республика Беларусь).- Мн.: Белгосуниверситет, 1996,-С. 216.

2. Короткевич А.Г. Автоматизированный лабораторный пракгикум по минимизации булевых функций// Материалы научно-методической конференции "Новые информационные технологии в учебном процессе" (15-16 ноября 1994 г.)- Минск: Белорусский Государственный экономический университет, 1994 - С. 121-122.

3. Короткевич А.Г. Анализ достижимости живых и безопасных а-сетей// Сборник "Логическое проектирование", вып. 2 - Минск: Ин-г техн. кибернетики АНБ, 1997,-С. 134-143.

4. Короткевич А.Г. Анализ корректности а-сетей// Сборник "Логическое проектирование"- Минск: Ин-т техн. кибернетики АНБ, 1996 - С. 8696.

5. Короткевич А.Г. Анализ поведения асинхронного секвенциального автомата// Научно-техническая конференция "Современные проблемы радиотехники, электроники и связи". Тезисы докладов- Минск: БГУИР, 1995,- Т. 2.-С.364.

6 Короткевич А.Г. Анализ асинхронных секвенциальных автоматов// Теория и методы создания интеллектуальных САПР. Тезисы докладов -Минск: Ин-ттехн. кибернетики АНБ, 1994,-С. 12.

7. Короткевич А.Г. Асинхронные системы секвенций как модель параллельных процессов// Автоматизация проектирования дискретных систем,- Минск: Ин-ттехн. кибернетики АНБ, 1995,-С. 8-17.

8. Короткевич А.Г. Критерии оптимизации параллельных автоматов// Актуальные проблемы информатики: математическое, программное и информационное обеспечение: Материалы V межгосударственной научной конференции (14-18 мая 1996 г., Минск, Республика Беларусь).- Мн.: Белгосуниверситет, 1996.-С. 218.

9. Короткевич А.Г. Метод конструирования корректных ПРАЛУ-алгоритмов// Сборник 'Логическое проектирование"- Минск: Ин-т техн. кибернетики АНБ, 1996,- С. 97-106.

Ю.Короткевич А.Г. О параллельности между переходами в сетях Петри// VII Белорусская Математическая конференция. Тезисы докладов. Часть III.-Минск: Белгосуниверситет, 1996.-С. 189-190.

11.Короткевич А.Г. Проверка свойств асинхронных систем секвенций с помощью редукции// Автоматизация проектирования дискретных систем. Материалы международной конференции (15-17 ноября 1995 года). Минск. Том I. Тезисы докладов - Минск: Белгосуниверситет', 1995,-С. 45.

12.Короткевич А.Г. Учет операции гашения при анализе АЛУ-алгоритмов// Формализация и автоматизация логического проектирования,- Минск: Ин-ттехн. кибернетики АНБ, 1993,-С. 52-61.

13.Короткевич А.Г. Эквивалентность состояний параллельного автомата// Международная научно-техническая конференция "Моделирование интеллектуальных процессов проектирования и производства". Тезисы докладов - Минск: Ин-ттехн. кибернетики АНБ, 1996,-С.44.

H.Korotkevich A. Checking properties of the asynchronous systems of sequents by using reduction// Proceedings of the International Conference on CAD DD'95.- Minsk-Szczecin, 1995,- P. 99-102.

15.Korotkevich A. An aspect of PLS realization of automata// Proceedings of the International Conference on CAD DD'97.- Minsk, 1997 - P. 74-76.

РЭЗЮМЕ Карагакич Андрэй Генадзьев1ч Анал1з { аптьжпзацыя паралельных алгарытмау лапчнага юравання

Юночаоыя словы: сетк1 Петры, паралелыш аутамат, С1Стэмы секвенцый, асшхронныя паралельныя працэсы, алгарытмы лапчнага 1иравання.

1снуе шэраг матэматычных мадэляу, як\а дазваляюць ашсваць паралельныя алгарытмы лапчнага шравання. Для гэтых мадэляу узшкаюць задачы ¡х анал1зу ды аптым1зуючых пераутварэнняу, ямя часткова яшчэ не вырашапы. Мэтай дысертацыПпай працы з'я^ляецца распрацоука метадау аналву \ аптымшцьн для асноуных з шх, менавгга для падкласа сетак Петры, паралельных аутаматау 1 сютэмау секвенцый. Для вырашэння пастауленых задач выкарысганы апарат тэорьп аутаматау, булевай алгебры, тэорьп сетак Петры Вьшчальныя эксперыменты праводзЫся на 1ВМ-сумяшчальным персанальным камп'ютары. У працы атрыманыя наступныя новыя рэзультаты: прапанаваны новыя алгарытмы аналву сетак Петры, належачых да падкласа, як\ ужываецца пры мадэлявапж алгарытмау юравання; гэтыя алгарытмы дазваляюць з невялшм1 затратам! лакал1зоуваць парушэнш карэктнасщ \ кампактна ашсваць мноства дасягальнасш, а таксама хутка атрымл1ваць гэткае ашсанне; распрацаваны метад стварэння сштакЫчна карэктных паралельных алгарытмау лапчнага юравання; разгледжаны экв1валентныя пераутварэнш паралельных аутаматау; прапанаваны метад мпимгзацьп секвенцыяльных аутаматау па колькасш упутраных пераменых. Рэзультаты дысертацьп можна выкарыстоуваць у САПР устройствау дыскрэтнага к1равання для павышэння эфектыунасщ працэсу распрацоукч ды наладк! алгарытмау; найбольш мэтазгодныя галшы прымянення - мраванне транспартиым1 сродкам^ аутаматызаванай вытворчасц'/о, ¡ншым! размеркаваным1 механ1чным1 астэмамг

РЕЗЮМЕ Короткевич Андрей Геннадьевич Анализ и оптимизация параллельных алгоритмов логического управления

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

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

SUMMARY Karatkevich Andrei

Analysis and Optimization of Parallel Logical Control Algorithms

Key words: Petri neis, parallel automaton, sisterns of sequents, asynchronous parallel processes, logical control algorithms.

There is a variety of mathematical models that allow to describe the parallel logical control algorithms. For those models the problems of analysis and optimizing transformations arise, and some of them are not yet solved. The matter of the thesis is development of the analysis and optimization methods for the main ones of those models, viz. a subclass of Petri nets, parallel automata and systems of sequents. For solving of the problems the automata theory, Boolean algebra and Petri nets theory have been used. For computer experiments an IBM-compatible PC was used. The next new results are obtained in the thesis: new analysis algorithms are proposed for analysis of the Petri nets belonging to the subclass used for simulation of the control algorithms; those algorithms allow to localize violations of correctness conditions with small expenses and to obtain quickly compact description of reachability set; the method of syntactic correct parallel logical control algorithms creation is designed; the equivalent transformations of the parallel automata are considered; the method of minimizing of internal variables number for the sequent automata is proposed. Obtained results can be used in CAD of the devices of discrete control for increasing effectively of the algorithms development and debug process; the most reasonable areas of application are the control of vehicles, automatic manufacturing, other distributed mechanical systems.