Разработка графовых моделей автоматизированного проектирования абстрактного этапа блочной реализации систем логического управления тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Дзугкоева, Анна Альбертовна

• Дзугкоева, Анна Альбертовна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Дзугкоева, Анна Альбертовна

ВВЕДЕНИЕ.

ГЛАВА 1. СОСТОЯНИЕ ПРОБЛЕММЫ И ОБЗОР МЕТОДОВ

АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ.

1.1 .Моделирование систем управления.

1.2.Методы автоматизированного проектирования систем логического управления.

ГЛАВА 2 НАХОЖДЕНИЕ РАЗМЕЩЕНИЯ ПО СТАНДАРТНОЙ

СОСТАВЛЯЮЩЕЙ.

2.1. Нахождение изоморфного вложения графоида заданного автомата в декартово произведение графоидов заданного и стандартного автоматов.

2.2. Расширение носителя графоида заданного автомата.

2.3. Формирование подмножеств соцветных вершин на основе функционально несвязных пар состояний автомата.

ГЛАВА 3. ПОСТРОЕНИЕ ГРАФА УСЛОВИЙ СОЦВЕТНОСТИ ВЕРШИН ГРАФОИДА ЗАДАННОГО АВТОМАТА И НАХОЖДЕНИЕ РАЗМЕЩЕНИЯ ЕГО СОСТОЯНИЙ ПО КОМПОНЕНТАМ РАЗЛОЖЕНИЯ.

3.1. Нахождение системы ограничений на размещение состояний автомата

3.2. Нахождение нестандартной компоненты разложения.

ГЛАВА 4. РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ АБСТРАКТНОГО ЭТАПА РЕАЛИЗАЦИИ УСТРОЙСТВ УПРАВЛЕНИЯ НА

СТАНДАРТНЫХ СОСТАВЛЯЮЩИХ И ЕЁ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ.

4.1. Состав и функционирование системы проектирования.

4.2. Имитационная модель системы проектирования.

4.3. Примеры решения задач проектирования с использованием разработанной САПР.

Введение диссертации (часть автореферата) на тему «Разработка графовых моделей автоматизированного проектирования абстрактного этапа блочной реализации систем логического управления»

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

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

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

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

- разработка метода нахождения размещения состояний заданного автомата по стандартной компоненте разложения.

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

- разработка алгоритмов реализации предложенных методов.

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

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

Методы исследования. В работе использовались методы теории множеств, алгебры разбиений, теории графов, теории автоматов.

Научная новизна:

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

- сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения.

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

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

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

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

Обоснованность и достоверность научных положений, выводов и рекомендаций подтверждается соответствием результатов работы внедренной САПР результатам проведенного имитационного моделирования.

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

Результаты работы внедрены: на НПК «Югцветметавтоматика» при разработке АСУ процессом обжига электродного производства на ОАО «Новочеркасский электродный завод», что позволило получить экономический эффект в размере 570000 руб. в год. Основные научные и практические результаты используются в учебном процессе СКГМИ(ГТУ) при чтении лекций и проведении практических занятий по дисциплинам «Дискретная математика» и «Теоретические основы построения САПР».

Апробация работы. Основные результаты проведённых в диссертации исследований докладывались на межкафедральном научном семинаре «Декомпозиционная теория синтеза систем логического управления», на ежегодных научно-технических конференциях СКГМИ (ГТУ) (2004-2007 гг.), Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербургский государственный политехнический университет), V-й Международной конференции «Устойчивое развитие горных территорий: проблемы и перспективы интеграции науки и образования», г. Владикавказ.

Связь с государственными программами. Основные исследования выполнялись в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 г.)

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 87 наименований и 2 приложений. Общий объем диссертации 132 страницы, включая 49 рисунков и 4 таблицы.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Дзугкоева, Анна Альбертовна

Выводы

Описана возможность использования предложенных во 2-й и 3-й главах методов для создания системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих.

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

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

ЗАКЛЮЧЕНИЕ

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

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

- Сформулирована и доказана теорема существования размещения состояний заданного автомата по стандартной компоненте разложения.

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

- Проведён анализ графа условий соцветности вершин и обоснована предпочтительность его использования при решении задачи сужения сигнатуры графа сцепления.

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

- Предложен метод нахождения размещения состояний автомата по компонентам разложения, основанный на нахождении множества таких подмножеств множества состояний автомата, совместное размещение элементов которых не приведёт к недетерминированности переходов в компонентном автомате.

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

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

Список литературы диссертационного исследования кандидат технических наук Дзугкоева, Анна Альбертовна, 2007 год

1. Инан К.М., Варайя П.П. Алгебры дискретно-событийных моделей // ТИИЭР, т. 77, № 1, январь 1989.

2. ЗиглерБ.П. Представление динамических систем на основе дискретно-событийных описаний: Интеллектуальное управление на базе событий // ТИИЭР, т. 77, № 1, январь 1989.

3. Райтер Р., ВальранЖ.С. Распределённое имитационное моделирование дискретно-событийных систем // ТИИЭР, т. 77, № 1, январь 1989.

4. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.

5. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.

6. Варшавский В.И. и др. Поведение автоматов в периодических случайных средах и задача синхронизации при наличии помех. Сб. «Проблемы передачи информации», 1,1965.

7. Варшавский В.И., Мараховский В.Б, Песчанский В.А. О задаче голосования в цепи автоматов. Изв. АН СССР. Техн. Кибернетика, № 4,1968.

8. Гаврилов М.А. Построение релейных устройств и конечных автоматов из блоков. Изв. АН СССР. Техн. Кибернетика, 1963.

9. Гаврилов М.А. Об уточнении оценки для определения числа состояний при композиции конечных автоматов. Автоматика и телемеханика, № 11,1964.

10. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. М.: «Наука», 1977.

11. Глушков В.М. Введение в кибернетику. Киев, Изд-во АН УССР, 1964.

12. Глушков В.М. О применении абстрактной теории автоматов для минимизации микропрограмм. Изв. АН СССР. Техн. кибернетика, № 1,1964.

13. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика, № 5,1965.

14. Горбатов В.А. Схемы управления ЦВМ и графы. М.: Энергия, 1971.

15. Горбатов В.А., Дедегкаев А.Г. Запрещённые фигуры при параллельной декомпозиции автоматов / В кн.: Оптимизация дискретных систем управления. ГВЦ Госплана СССР, 1972.

16. Горбатов В.А., Дедегкаев А.Г. Метод расщепления запрещённых фигур при построении параллельной декомпозиции систем / Сб. Прикладные вопросы теории систем и системотехники. М.: МДНТП, 1973.

17. Горбатов В.А., Кафаров В.В., Павлов П.Г. Логическое управление технологическими процессами. -М.: Энергия, 1978.

18. Горбатов В.А. Теория частично упорядоченных систем. М.: Сов. радио, 1976.

19. Горбатов В.А. Семантическая теория проектирования автоматов. М.: Энергия, 1979.

20. Горбатов В.А., Останков Б.Л., Фролов С.А. Регулярные структуры автоматного управления. М.: Машиностроения, 1980.

21. Горбатов В.А. Информационная математика. -М.: Наука, 1997.

22. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. М.: Мир, 1997.

23. Горбатов В.А., Крылов А.В., Федоров Н.В. САПР систем логического управления. М.: Энергоизат, 1988.

24. Горбатов В.А., Смирнов М.И., Хлытчиев И.С. Логическое управление распределёнными системами. -М.: Энергоиздат, 1991.

25. Горбатов В.А. Синтез микропрограммных автоматов по временным диаграммам их функционирования. Цифровая вычислительная техника и программирование, вып. 5 -М.: Сов. радио, 1969.

26. Горбатов В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов // Изв. АН СССР. Техническая кибернетика. 1970. -№4.

27. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М.: Энергия, 1970.

28. Лазарев В.Г. О синтезе микропрограммных автоматов. Сб. «Проблемы передачи информации», 1965,1,2.

29. Лазарев В.Г., Пийль Е.И. Уменьшение числа состояний одного класса конечных автоматов. ДАН СССР, 1962,143, № 5.

30. Мелихов А.Н. Некоторые операции над графами // Изв. АН СССР. Техн. кибернетика, № 6, 1964.

31. Мелихов А.Н., Дворянцев Ю.А. Разложение графов и конечных автоматов относительно операции умножения // Кибернетика, № 3, 1965.

32. Мелихов А.Н., Бернштейн JI.C., Карелин В.А. Разложение графов и конечных автоматов по операции суммирования // Изв. АН СССР. Техн. кибернетика, № 2,1968.

33. Мелихов А.Н., Дворянцев Ю.А. Теоретико-множественные и алгебраические операции над конечными автоматами // Изв. АН СССР. Техн. кибернетика, №3,1967.

34. Мелихов А.Н., Бернштейн JI.C., Карелин В.А. О декомпозиции абстрактных автоматов // Кибернетика, № 3,1969.

35. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.

36. Мелихов А.Н., Бернштейн JI.C. Последовательная декомпозиция конечных автоматов. Изв. АН СССР. Техн. кибернетика, 1968, № 3.

37. Мелихов А.Н., Бернштейн JI.C. Абстрактная декомпозиция конечных автоматов. Сб. «Вычислительные системы». Труды I Всесоюзной конференции по вычислительным системам, вып. 3. Программирование на вычислительных средах. Новосибирск, 1968.

38. ПийльЕ.И. О кодировании внутренних состояний конечного автомата. Изв. АН СССР. Техн. кибернетика, 1965, № 2.

39. Пийль Е.И. Способ размещения внутренних состояний асинхронного конечного автомата. Сб. «Проблемы передачи информации», 1964, вып. 17.

40. Поспелов Д.А. Логико-лингвистические модели в системах управления. -М.: Энергия, 1981.

41. Поспелов Д.А. Логические методы анализа и синтеза схем. Л. - М.: Энергия, 1964.42.3ахаров В.Н., Поспелов Д.А., Хазацкий В.Е. Системы управления. Задание. Проектирование. Реализация. Издание второе. М.: Энергия, 1977.

42. Поспелов Д.А. Большие системы. Ситуационное управление. М.: Знание, 1975.

43. Arbib М.А. Turing machines, finite automata and neural nets. JACM, 1961, № 4.

44. Quine W.V. Way to simplify truth functions. Amer. Math. Monthly, 1955, 62.

45. Миллер P. Теория переключательных схем.: Наука, 1970, т. 1, т. 2,1971. 47.Sechu S. Mathematical models of sequential machines. IRE Convent. Record,1959,7, part 2.

46. Hartmanis J. Symbolic analysis of a decomposition of information processing machines. Inform, and Control, № 2,1960.

47. Hartmanis J. On the state assignment problem for sequential machines I, IRE Trans. On Electronic Computers, EC-10, № 2,1961.

48. Hartmanis J. Minimal feedback realization of sequential machines. IEEE Trans., EC-15,№6,1966.

49. Hartmanis I., Stearns R.E. Pair algebra and its application to automata theory. Inform. and Control, 7, № 4,1964.

50. Hartmanis I., Stearns R.E. Algebraic structure theory of sequential machines. Prentice Hall, Inc., Englewood, Cliffs, New Jersey, 1966.

51. Huffman D.A. Synthesis of sequential switching circuits. J. Franklin Institute, 257, №4,1954.

52. Huffman D.A. The design and use of hazard-flue switching networks. JACM, №4,1957.

53. Таль A.A. Анкетный язык и абстрактный синтез минимальных последова-тельностных машин // Автоматика и телемеханика, № 6, т. XXV, 1964.

54. Таль А.А. Абстрактный синтез последовательностных машин по ответам на вопросы первого типа анкетного языка. «Автоматика и телемеханика, т. 26, № 4,1965»

55. К. Nabuyuki, A. Tadashi, Y. Noriyoshi. An extension of pair algebra. Bull. Fac. Eng. Hiroshima Univ., vol. 22, № 2,1974.

56. Yoli M. The cascade decomposition of sequential machines /1, IRE Trans. On Electronic Computers, EC-10, N4,1961.

57. Yoli M., Gansburg A. On homomorphic images of transition grafs /1. Franklin Inst, 278, N5, 1964.

58. Kohavi Z. Secondary state assignment for sequential machines. IRE Trans., EC-13, №3.

59. Kohavi Z., Smith E.J. Decomposition of sequential machines. IEEE. Conf. Rec. Switch. Circuit theory and logic design, Ann. Arbor, Mich.,, 1965.

60. Кузнецов О.П. Параллельная декомпозиция автоматов с разделением входов // Автоматика и телемеханика, № 3,1969.

61. Дедегкаев А.Г. Некоторые свойства автоматных операторов, не допускающих параллельную декомпозицию. В кн.: Оптимизация дискретных систем управления. - ГВЦ Госплана СССР, 1972.

62. Дедегкаев А.Г. Алгоритмы разложения микропрограммного автомата. В кн.: Автоматизированные системы проектирования . -МДНТП, 1977.

63. Дедегкаев А.Г. Уменьшение связности графа зацепления автоматного графоида. - В кн.: Оптимизация дискретных систем управления. - МДНТП, 1979.

64. Дедегкаев А.Г. Расщепление запрещённых фигур параллельной декомпозиции абстрактных автоматов оптимальным расширением памяти. В кн.: Разработка и внедрение систем автоматизированного проектирования в машиностроении. - Ижевск, ИМИ, 1983.

65. Использование зависимой раскраски графов при построении декомпозиции автоматных операторов. В кн.: Логическое управление в промышленности -Ижевск, ИМИ, 1984.

66. Дроздов Е.А. Оптимизация структур цифровых автоматов. М.: Советское радио, 1975.

67. Баранов С.Н., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986.

68. Девятков В.В. Реализация конечных автоматов на сдвиговых регистрах. Автоматика и телемеханика, 1968, № 11.

69. Девятков В.В. Реализация конечных автоматов на двух циклических автономных автоматах. Автоматика и вычислительная техника, 1969, № 5.

70. Девятков В.В. Методы реализации конечных автоматов на сдвиговых регистрах. «Энергия», 1974.

71. Ларин Л.К., Осинский Л.М., Экономичное кодирование состояний конечного автомата, Кибернетика, 1966, № 3.

72. Ларин Л.К., Осинский Л.М., Автоматы с последовательной однородной структурой. Техническая кибернетика, 1969, № 1.

73. Горбатов В.А., Грехнёв В.А., Метечко В.И. Проектирование регулярных управляющих автоматов. В сб. Автоматизированные системы проектирования, М., МДНТП им Ф.Э. Дзержинского, 1975.

74. Грехнёв В.А. Проектированиеуправляющих автоматов на композиции сдвиговых регистров и распределителей. В сб.: Общая теория систем и интеграция знаний, М., МДНТП им Ф.Э. Дзержинского, 1976.

75. Грехнёв В.А. Повышение регулярности логических устройств цифровой автоматики. Логическое управление в промышленности, М., МДНТП им Ф.Э. Дзержинского, 1977.

76. Останков Б.Л. Оптимизация систем управления на основе регулярных и квазирегулярных МЭП. Оптимизация дискретных систем управления, М., МДНТП им Ф.Э. Дзержинского, 1979.

77. Горбатова М.В. Быстродействующий алгоритм раскраски вершин графа / В кн.: Логическое управление в промышленности. Ижевск: ИМИ, 1984.

78. Бондаренко Н.Н., Братолюбов В.Г. Низковольтные преобразователи для гальванотехники и электрохимических станков. М.: Энергоатомиздат, 1987.

79. Бахвалов Л.А. Моделирование систем. Высшее горное образование, М.: Изд. МГГУ, 2006.

80. Харари Ф. Теория графов. -М.: Мир, 1973.

81. Дзугкоева А.А. Частные задачи разложения графа в декартово произведение. Труды молодых ученных, Владикавказ, Вл. науч. центр РАН, № 4,2006.

82. Дзугкоева А.А. Исследование процедур расщепления запрещённых фигур раскраски графа сужением его сигнатуры. Известия высших учебных заведений Северо-Кавказский регион. Ростов-на-Дону, Технические науки, №4, 2006

83. Дзугкоева А.А Разложение автоматных графоидов (функций на графах) в декартово произведение стандартных компонент. Приборы и системы. М.: Научтехлитиздат, №9,2007.

84. Дзугкоева А.А., Пагиев К.Х. Использование СП-разбиений в САПР систем логического управления. Сборник научных трудов СООАНВШРФ, Владикавказ, № 5,2007.

85. Дзугкоева А.А. Имитационная модель системы автоматизированного проектирования абстрактного этапа реализации устройств управления на стандартных составляющих. Труды молодых ученных, Владикавказ, Вл. науч. центр РАН, № 4,2007.