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

Введение к работе

Актуальность темы диссертации. Классическая модель конечного

івтомата является хорошо зарекомендовавшим себя способом

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

:сли необходимо создание устройства для управления несколькими

ізаимодействующими и развезвляюшймися асинхронными процессами.

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

шисание устройства как одного конечного автомата также оказывается

іеприемлсммм, поскольку число его состояний может быть слишком

іелико. В этих случаях целесообразно использование матемагических

юделей, отражающих параллелизм; наиболее удобной и популярной из

nix являются сети Петри. Имеется много работ, посвященных

ірименению таких моделей для разработки и реализации параллельных

'іірашіякнцих алгоритмов. Методы решения ряда задач, связанных с

онечными автоматами, неприменимы для этих моделей; кроме того, для

их возникают новые, специфические задачи. В частности, по

тношению к параллельным алгоритмам весьма сложна задача анализа

орректности. Существующие методы ей решения неэффективны: одни

з них не позволяют локализовать нарушения корректности, тогда как

ругие крайне трудоемки. Не разработан и способ конструирования таких

лгоритмов, который бы обеспечивал их корректность. Имеющиеся

егоды анализа и оптимизации секвенциальных автоматов относятся в

сновном к синхронной интерпретации и требуют адаптации для

:инхронного случая. Данная рабетга посвящена решению перечисленных

некоторых других задач, относящихся к указанной области.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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