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

• Калитин, Денис Владимирович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Калитин, Денис Владимирович

Введение.

Глава 1. Подходы к проблеме проектирования параллельной декомпозиции управляющих автоматов (ПДУА).

1.1. Синтаксический подход.

1.2. Семантический подход.

1.3. Последовательная стратегия проектирования параллельной декомпозиции автоматов при семантическом подходе.

1.4. Расширение терминальных символов.

1.5. Вычисление сложности функциональной декомпозиции.

1.6. Выводы по первой главе.

Глава 2. Параллельная стратегия синтеза предельной параллельной декомпозиции автоматов.

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

2.2. Кластеры, их структура и свойства.

2.3. Параллельная стратегия синтеза связной предельной параллельной декомпозиции в трёхзначной логике.

2.4. Выводы по второй главе.

Глава 3. Параллельная стратегия проектирования минимальносвязной ПДУ А.

3.1. Произведение кластеров, их структура и свойства.

3.2. Технология параллельной стратегии проектирования минимальносвязной ПДУ А.

3.3. Программный инструментарий параллельной стратегии проектирования минимальносвязной ПДУА и его внедрение.

3.4. Выводы по третьей главе.

Глава 4. Автоматизированное проектирование реальных минимальносвязных ПДУА.

4.1. Трёхзначный однородный нейрон сотовой структуры и его проектирование.

4.2. Автоматизированное проектирование автоматного управления системой сжигания твёрдого топлива в плотном слое.

4.3. Автоматизированное проектирование логической компоненты системы мониторинга морской акватории.

4.4. Выводы по четвёртой главе. 131 Заключение. 132 Литература.

Введение диссертации (часть автореферата) на тему «Автоматизированное проектирование минимальносвязной параллельной декомпозиции управляющих автоматов в k-значных логиках на основе теоретико-графового вложения»

Повышение производительности и безотказности цифровых бортовых систем, систем жизненного обеспечения горного, морского, космического базирования и других информационно-вычислительных комплексов определяет необходимость автоматизированного проектирования параллельно функционирующих управляющих автоматов с ослабленной, в пределе минимальной, связностью. [2, 10, 12-26] Эта проблема, как проблема проектирования параллельной декомпозиции управляющих автоматов, впервые была поставлена Дж. Хартманисом (1961 г.), для решения которой им был предложен специальный алгебраический аппарат разбиений внутренних состояний автомата (нетерминальных символов) со свойством подстановки (СП-разбиений). Развитие этого аппарата совместно с Р. Стирнсом привело к созданию алгебры пар, явившейся математической основой результатов, связанных с построением параллельной декомпозиции автоматов. Недостатками этого подхода являются комбинаторный перебор возможных разбиений и малая доля автоматов, обладающих свойством подстановки и процедура, основанная на алгебре пар, по существу, является процедурой не проектирования, а распознавания свойства подстановки автомата, которая, быть может, только на последнем шаге преобразования даст отрицательный результат, т.е. что автомат не обладает свойством подстановки и не может быть построен. [6, 15, 42, 44, 50]

Для устранения этих недостатков японскими учёными К. Нобуёки, А. Тадаши, Е. Нориоши (1974 г.) [7] было предложено расширение алгебры пар до алгебры троек, четвёрок, ., n-ок, но аппарат расширенных алгебр не устранил недостатки алгебры пар. Модификации этого подхода, проведённые отечественным учёными (70-е годы) А.Н. Мелиховым, О.П. Кузнецовым, В.Г. Лазаревым, Е.И. Пийль, Э.Б. Ершовой и др. так же не привели к положительным результатам. [3, 4, 5, 9, 38-56, 57]

Цель работы

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

Идея работы

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

Задачи исследования:

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

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

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

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

• Разработать алгоритм вложения графа сцепления в кластер при минимальном сужении сигнатуры графа сцепления;

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

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

Методы исследований

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

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

Защищаемые научные положения и их новизна

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

• Предложена структура кластеров, являющихся основой проектирования параллельной минимальносвязной декомпозиции управляющих автоматов, и доказаны их свойства;

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

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

Научное значение состоит в следующем:

• Развита декомпозиционная теория параллельно функционирующих управляющих автоматов с учётом минимизации их функциональной связности;

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

• Найдена характеризация декомпозируемости управляющих автоматов для общего случая — повторной мультипликативной декомпозиции.

Практическая ценность заключается:

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

• В эффективном внедрении разработанного программного инструментария в реальное производство цифровой аппаратуры в ГУ НПО "Специальная техника и связь" МВД РФ и

ЗАО НПЦ "Альтаир" о чём имеются соответствующие акты о внедрении.

Апробация работы

Основные результаты работы были обсуждены:

• на конференциях, проводимых РАЕН, международной академией информатизации и МГГУ: "Логическое управление. Характеризационный анализ. САПР", М, 1999 г.; "Логическое управление. Характеризационный анализ. САПР", М, 2003 г., "Характеризационный анализ. Нейронные технологии. САПР", М, 2005 г.;

• на семинарах отделения "Теоретическая информатика и информационные технологии и стратегии" Международной академии информатизации.

Публикации

По теме диссертации опубликовано шесть научных работ.

Объём и структура работы

Диссертационная работа состоит из введения, 4 глав и заключения, содержит 20 таблиц, 53 рисунка и список литературы из 83 наименований.

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

Основные результаты диссертации, полученные лично аспирантом, внедрены в проект программно-технического комплекса мониторинга морских акваторий Российской Федерации, в виде

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

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

Главный конструктор

ОКР "Р—С", канд. техн. наук

Заключение

В диссертации получены следующие научные результаты.

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

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

3. Исследованы свойства кластеров и найдена характеризация их структур, оформленных в виде реляционной базы знаний.

4. Предложена эффективная процедура вложения в кластер графа сцепления при минимальном сужении его сигнатуры.

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

6. Созданное математическое обеспечение проектирования минимальносвязной параллельной декомпозиции управляющих автоматов доведено до программной реализации на основе использования стандарта ANSI С, что позволило легко преобразовать её разработанные модули в библиотеки динамического подключения (DLL), в компоненты объектного программирования (COM, DCOM, ActivX и т.д.) при синтезе параллельной декомпозиции управляющих автоматов с допустимой мощностью нетерминальных символов до 4096 со скоростью обработки одного нетерминального символа в среднем до 0,1 с.

7. Разработанный программный инструментарий успешно внедрён в Главном управлении НПО "Специальная техника и связь" МВД РФ и Научно—техническом производственном центре "Альтаир" при реальном проектировании систем мониторинга дорожно-транспортных ситуаций г. Москвы и Московской области и морских акваторий РФ соответственно, работающих в реальном масштабе времени и требующих высокую производительность и отказоустойчивость, о чём имеются соответствующие акты о внедрении.

Утверждаю"

Генеральный директор научно-технического производственного центра "Лльтаир", академик НЛ,

•4

ЖВ. Воскресенский "23" марта 2005г.

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

Список литературы диссертационного исследования кандидат технических наук Калитин, Денис Владимирович, 2005 год

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

2. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраевоемой структурой. М.: Энергия, 1974.

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

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

5. Алгебраическая теория автоматов, языков и полугрупп. Под ред. М.А. Арбиба, М.: Статистика, 1975.

6. Hartmanis J., Stearns R.E. Pair algebra and its application to automata theory. — Information and Control, 1964, №7.

7. Kurose Nobuyuki, Ae Tadashi, Yoshida Noriyoshi. An extension of pair algebra/ Bull/ Fac/ Eng/ Hirosima Univ., 1974.

8. McCluskey E.J., Unger S.H. A note on the number of internal variable assignments for sequential switching circuits. — IRE Trans. On Electonic Computers, 1959.

9. Миллер P. Теория переключательных схем.: Наука,1970.

10. Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977.

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

12. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Наука, 1999.

13. Горбатов В. А. Дискретная математика. М.: ООО "Издательство ACT", 2003.

14. Горбатов А.В. Характеризационная теория синтеза функциональных декомпозиций в k-значных логиках. М.: ООО "Издательство ACT", 2000.

15. Huffman D.A. The synthesis of sequential switching circuits// J. of the Franklin Inst 1954. Vol. 257. №3. P. 161-190; №4. P. 275-303.

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

17. Kochen М. Extension of moore-shannon model for relay circuits//IBM Journ. Res. and Devel. 1959. Vol. 3. №2. P. 169-186.

18. Щукин А.А. Промышленные печи и газовое хозяйство заводов, М., Энергия, 1973.

19. Андерсон Р. Доказательство правильности программ. М. Мир., 1982.

20. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М. Мир., 1978.

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

22. Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации, М., Советское Радио, 1974, 432с.

23. Рякин О.М., Скворцов И.В. Логические модели абстрактных типов данных при проектировании программ на языках высокого уровня. Материалы VII симпозиума "Логическое управление в промышленности", Ижевск, 1984.

24. Рякин О.М. Модельный подход к формальному определению ошибок проектирования. Материалы VII симпозиума "Логическое управление в промышленности", Ижевск, 1984.

25. Zvi Kohavi. Secondary state assignment for sequential machines// IEEE Trans/ on Electronic Сотр. 1964. Vol. EC-13. №3. P. 193-203.

26. Гусева А.И., Кольцов Д.В. Распределённые системы: декомпозиция и синтез. Материалы 17 Международного симпозиума "Логическое управление. Интеллектуальные информационные технологии и стратегии", Москва, Международная академия информатизации, 1994.

27. Серджвик Р. Фундаментальные алгоритмы на С. Алгоритмы на графах. СПб, ООО "ДиаСофтЮП", 2003.

28. Подбельский В.В. Язык С++, М. Финансы и статистика,1996.

29. Liu С. N. A state variable assignment method for asynchronous sequential switching circuits// ACM. 1963. Vol. 10. №2. P. 209-216.

30. Стивене У. UNIX: взаимодействие процессов, СПб, Питер, 2002.

31. Кейт Г. Использование Visual С++, М. "Вильяме", 1999.

32. Черносвитов A. Visual С++ и MFC, СПб, Питер, 2000.

33. Жоффрэн И. Кодирование внутренних состояний и декомпозиция последовательностных синхронных устройств в сб. "Булева алгебра и конечные автоматы", М. Мир., 1969, 114-152.

34. Круглов В.В., Борисов В.В. Искусственные нейронные сети. М. Телеком, 2001.

35. Mealy G. Н. A method for synthesizing sequential circuits// BSTJ. 1965. Vol. 34. №5. P. 1045-1079.

36. Агафонов B.H. Синтаксический анализ языков программирования. Уч. пособие, Новосибирск, НГУ, 1981. 91 с.

37. Paul М., Unger S. Н. Minimizing the number of states in incompletely specified sequential switching functions// IRE Trans, on Electronic Сотр. 1959 Vol. EC-8. №3. P. 356-367.

38. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 326 с.

39. Гладкий А.В. Формальные грамматики и языки. М.: Наука, 1973. 368 с.

40. Сигеру Омату, Марзуки Халидб Рубия Юсуф, Нейроуправление и его приложения, ИПРЖ "Радиотехника", М. 2000, 272с.

41. Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971.294 с.

42. Hartmanis J. On the State Assignment Problem for Sequential Machines I. IRE Transactions on Electronic Computers. Vol. EC-10, No.2, pp. 157-165.

43. Мартыненко Б.К. Синтаксически управляемая обработка данных. С.Пб: изд. СПбГУ, 1997. 362 с.

44. Hartmanis J. Loop-free structure of sequential machines// Information and Control, 1962. Vol. 5. №1. P. 25-43.

45. Ramamoorthy С. V., Ho G. S., Performance evaluation of asynchronous concurrent systems using petri nets, IEEE Trans. Software Eng., Vol. SE-6, №5, P. 440-449, 1980.

46. Закревский А.Д. Алгоритмы синтеза дискретных автоматов М.: Наука, 1971.

47. Языки и автоматы. Сб. переводов. М.: Мир, 1975. 358 с.

48. Greibach S.A. A note on undecidable properties of formal languages // Math. Systems Theory, 2, pp. 1-6.

49. Salomaa A. Formal languages. N.Y., 1973.

50. Stearns R. E., Hartmanis J., On the state assignment problem for sequential machinesll, IRE Trans. Elect. Comput., 1961, Vol. EC-10, №4.

51. Мартыненко Б.К. Языки и трансляции. СПб., СПбГУ,2001.

52. Hopcroft J.E., Ullman J.D. Formal languages and their relation to automata. Addison-Wesley Pub. Co., Inc. 242 p.

53. Шамашов M.A. Теория формальных языков. Грамматики и автоматы. Учебное пособие. Самара: Университет Наяновой, 1996.

54. Штернберг Л.Ф. Теория формальных грамматик. Учебное пособие.- Куйбышев: КуАИ, 1979.

55. Шамашов М.А., Штернберг Л.Ф. Синтаксический анализ автоматных языков. Куйбышев: КуАИ, 1990.

56. Кузин Л.Т. Основы кибернетики: В 2-х т. Т.2. Основы кибернетических моделей. Учеб. пособие для вузов. М.: Энергия, 1979.- 584 с.

57. Кузнецов О.П. и др. Дискретная математика для инженера. М.,1988.- 480с.

58. Донован Дж. Системное программирование. М.: Мир,1975.

59. Брой М. Информатика. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация: В 4-х чч. 4.4. М.: Диалог-МИФИ, 1998.-224с.

60. Методы нейроинформатики: Сб.научн. трудов / Под ред. А.Н.Горбаня. Красноярск: КГТУ, 1998.- 204с.

61. Карпов Ю.Г., Теория автоматов, СПб. Питер, 2002.

62. Кудрявцев В.Б., Алешин С.В.,Подколзин А.С. "Введение в теорию конечных автоматов".- М.: Наука, 1985 г.

63. Sasao Т., Input variable assignment and output phase optimization of PLA's, IEEE Trans, on Comput. Vol. C-33, №10, P. 879-894, 1984.

64. Автоматы, Сборник статей под редакцией Маккарти и Шеннона, ИЛ, Москва, 1956

65. Кудрявцев В.Б., О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами, ДАН СССР т. 151,N3,1963, с.493-496.

66. Бабин Д.Н., Вербальные подавтоматы и задача полноты, Вестник МГУ, Математика и механика, 1985, N 3, с.82-85.

67. Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.

68. Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992, выпуск 4, с.41-56, Наука, Москва.

69. Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.

70. Глушков В.М. Синтез цифровых автоматов, Наука, Физматлит, М., 1980.

71. Витушкин А.Г., Хенкин Г.М. Линейные суперпозиции функций. — Успехи матем. наук, 1967, т.22, вып. 1, стр.77-124.

72. Марченков С.С. Об одном методе анализа суперпозиций непрерывных функций. — Проблемы кибернетики., вып.37, М:Наука, 1980, стр.5-17.

73. Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы. М: Наука. 1970.

74. Успенский В. А. Теория алгоритмов. М.: Наука.

75. Гэри, Джонсон. Вычислительные машины и трудно решаемые задачи. М.: Мир.

76. Савельев А.Я. Прикладная теория цифровых автоматов. Учебник для вузов-М. Высшая школа, 1987, 272с.

77. Брауэр В. Введение в теорию конечных автоматов. Перевод с английского под редакцией Ю.И. Журавлева-М. Радио и связь, 1987, 392с.

78. Каган Б.М. Электронные вычислительные машины и системы .-М. Энергоавтомиздат, 1988, 551с.

79. Савельев Н.В., Коняхин В.В. Функционально-логическое проектирование БИС.-М. Высшая школа, 1990, 156с.

80. Джон фон Нейман, Теория самовоспроизводящихся автоматов. "Мир", 1971.

81. Бухараев Р.Г. Вероятностные автоматы, Казань, Изд. КГУ, 1970.

82. Глушков В.М. Логическое проектирование дискретных устройств, Киев, 1987.

83. Автоматизация проектирования систем управления, Финансы и статистика, М., 1982,204 с.

84. Калитин Д.В. Применение k-значных логик при разработке систем управления технологическими процессами систем обогащения, Информационная математика №1, Физматлит, М.2001, с. 150-153;

85. Калитин Д.В. Характеризация функциональной несвязности нетерминальных символов автоматных грамматик в к-значных логиках, Информационная математика №1(3), Физматлит, М.2003, с. 33-36;

86. Калитин Д.В. Вложение графа в кластер функциональной несвязности нетерминальных символов автоматной грамматики, Информационная математика №1(3), Физматлит, М.2003, с. 36-38;

87. Горбатов А.В. Калитин Д.В. Минимизация функциональной связности нетерминальных символов автоматных грамматик в k-значных логиках, Информационная математика №1(3), Физматлит, М.2003, с. 38-44;

88. Горбатов А.В., Калитин Д.В. Проектирование слабосвязанных параллельных декомпозиций автоматов управления энергосберегающими технологиями, Информационная математика №1(4), Физматлит, М.2004, с. 46-56;

89. Горбатов А.В, Калитин Д.В. Кодирование минимальносвязных нетерминальных символов автоматной грамматики. Информационная математика №1(5), АСТ-Физматлит, М.2005, с. 36-48.