Оптимизация многокомпонентных дискретных систем на основе решения автоматных уравнений
Диссертация
Диссертация посвящена разработке методов оптимизации многокомпонентных дискретных систем на основе решения автоматных уравнений. Введено понятие автоматного уравнения для автоматной сети с произвольной структурой и произвольным числом компонент. Показано, что операция синхронной композиции является ассоциативной, что позволяет свести многокомпонентное автоматное уравнение к бинарному автоматному… Читать ещё >
Содержание
- 1. Основные определения. Постановка задачи оптимизации на основе автоматной модели
- 1. 1. Основные определения
- 1. 1. 1. Конечные автоматы
- 1. 1. 2. Операции над автоматами и полуавтоматами
- 1. 1. 3. Синхронная композиция двух автоматов
- 1. 1. 4. Многокомпонентная синхронная композиция
- 1. 2. Постановка задачи оптимизации на основе решения автоматных уравнений
- 1. 2. 1. Задача оптимизации
- 1. 2. 2. Определение автоматного уравнения для двухкомпонентной сети
- 1. 3. Методы решения бинарных автоматных уравнений
- 1. 3. 1. Решение уравнения на основе безразличных последовательностей
- 1. 3. 2. Решение уравнения на основе Е-автомата
- 1. 3. 3. Языковый подход к решению автоматных уравнений
- 1. 4. Критерии оптимизации
- 1. 5. Выводы по главе
- 1. 1. Основные определения
- 2. Использование автоматных уравнений для оптимизации многокомпонентной композиции
- 2. 1. Многокомпонентная синхронная композиция
- 2. 1. 1. Методы построения многокомпонентной синхронной композиции
- 2. 1. 2. Свойства многокомпонентной композиции
- 2. 2. Автоматные уравнения для многокомпонентной композиции
- 2. 2. 1. Решение автоматных уравнений для многокомпонентной композиции
- 2. 2. 2. Сведение автоматного уравнения для многокомпонентной композиции к бинарному автоматному уравнению
- 2. 2. 3. Разрешимость автоматного уравнения относительно различных алфавитов
- 2. 3. Упрощенные методы решения автоматных уравнений для оптимизации автоматных сетей
- 2. 3. 1. Комбинационное решение автоматного уравнения
- 2. 3. 2. Экспериментальные результаты по нахождению комбинационного решения
- 2. 3. 3. Решение автоматного уравнения на основе безразличных последовательностей
- 2. 3. 4. Экспериментальные результаты по нахождению безразличных последовательностей
- 2. 4. Основные результаты главы
- 2. 1. Многокомпонентная синхронная композиция
- 3. Покомпонентная оптимизация дискретных систем относительно различных критериев
- 3. 1. Глобальная оптимизация
- 3. 2. Локальная оптимизация
- 3. 2. 1. Локальная оптимизация посредством решения множества автоматных уравнений
- 3. 2. 2. Локальная оптимизация посредством решения системы уравнений
- 3. 3. Критерии оптимизации.94*
- 3. 3. 1. Число связей в автоматной сети
- 3. 3. 1. 1. О минимизации числа связей на основе решения автоматного уравнения
- 3. 3. 1. 2. Нахождение наибольшего решения автоматного уравнения с заданным множеством входных алфавитов
- 3. 3. 1. 3. Минимизация числа входных переменных компоненты.98'
- 3. 3. 2. Отказоустойчивость компоненты
- 3. 3. 3. Число вентилей в логической реализации компоненты
- 3. 3. 1. Число связей в автоматной сети
- 3. 4. Основные результаты главы
- 4. Прогрессивные решения автоматных уравнений и систем автоматных уравнений
- 4. 1. Наибольшее прогрессивное решение автоматного уравнения
- 1. 4.2 Характеризация прогрессивных решений
- 4. 3. Прогрессивные решения системы уравнений
- 4. 4. Экспериментальные результаты по существованию прогрессивных решений
- 4. 5. Основные результаты главы
Список литературы
- Глушков В.М. Синтез цифровых автоматов / В. М. Глушков. -М.: Физматгиз, 1962.-476 с.
- Скобцов Ю.А. Логическое моделирование и тестирование цифровых устройств / Ю. А. Скобцов, В. Ю. Скобцов. Донецк: ИПММ НАН Украины, ДонНТУ, 2005. — 436 с.
- Закревский А. Д. Алгоритмы синтеза дискретных автоматов / А. Д. Закревский. М.: Гл. ред. физ.-мат. лит., 1971. — 416 с.
- Колдуэлл С. Логический синтез релейных устройств / С. Колдуэлл. — М.: ИЛ, 1962.-740 с.
- Лазарев В.Г. Синтез управляющих автоматов / В. Г. Лазарев, Е. И. Пийль. М.: Энергия, 1970. — 400 с.
- Закревский А.Д. Логический синтез каскадных схем / А. Д. Закревский. -М.: Наука, 1981.-416 с.
- Автоматизированное проектирование цифровых устройств / С. С. Бадулин и др. М.: Радио и связь, 1981. — 240 с.
- Киносита К. Логическое проектирование СБИС / К. Киносита, К. Асада, О. Карацу. М.: Мир, 1988. — 309 с.
- Черемесинова Л.Д. Синтез и оптимизация комбинационных структур СБИС / Л. Д. Черемесинова. Минск: ОИПИ НАН Беларуси, 2005. -241 с.
- Gao M. The optimization of multi-valued multi-level networks / M. Gao, J-H. Jiang, Y. Jiang, Y. Li, A. Mishchenko, S. Sinha, T. Villa, R. Brayton // Proceedings of the 32nd IEEE ISMVL. 2002. — P. 168−177.
- Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации / А. А. Шалыто. СПб.: Наука, 2000. — 780 с.
- Grasselli A. A method for minimizing the number of internal states in incompletly specified sequential networks / A. Grasselli, F. Luccio // IEEE Transactions on electronic computers. 1965. — Volume EC-14. — № 3. -P. 350−359.
- Devadas S. Approaches to multi-level sequential logic synthesis // Proceedings of the 26th design automaton conference. USA, 1989. -P. 270−276.
- PaulinP.G. Algorithms for high-level synthesis / P.G. Paulin, J.P. Knight // IEEE design & test. 1989. — Volume 6. — Issue 6 — P. 18−31.
- Jozwiak L. An efficient method for the decomposition of sequential machines / L. Jozwiak, J. Kolsteren // Microprocessing and microprogramming. 1991. -Vol. 32.-P. 657−664.
- Yang W.-L. Multi-way FSM decomposition based on interconnect complexity / W.-L. Yang, R.M. Owens, M.J. Irwin // Proceedings of the design automation conference. 1993. — P. 390−395.
- Baumgartner J. Min-area retiming on flexible circuit structures / J. Baumgartner, A. Kuehlmann // Proceedings of the ICCAD. 2001. -P. 176−182.
- Jiang J.-H. Retiming and resynthesis: A complexity perspective / J.-H. Jiang, R. Brayton // IEEE TCAD. 2006. — Volume 25 (12). — P. 2674−2686.
- Petrenko A. Nondeterministic state machines in protocol conformance testing / A. Petrenko, N. Yevtushenko, A. Lebedev, A. Das // Proceedings of the IFIP 6th IWPTS. France, 1993. — P. 363−378.
- Watanabe Y. The maximum set of permissible behaviors for FSM networks / Y. Watanabe, R.K. Brayton // Proceedings of the 1993 IEEE/ACM international conference on computer-aided design. USA, 1993. — P. 316 320.
- Petrenko A. Testing strategies for communicating finite state machines / A. Petrenko, N. Yevtushenko, R. Dssouli // Proceedings of the International-workshop on protocol test systems. Tokyo, Japan, 1994. Chapman & Hall, 1995.-P. 193−208.
- Решение уравнений в логическом синтезе / Н. Евтушенко и др. -Томск: Изд-во «Спектр», 1999. 27 с.
- Жарикова (Тихомирова) С. Оптимизация элементов цифровых схем посредством решения систем автоматных уравнений // Вестник ТГУ. Приложение. 2002. — № 1 (Ц). — С. 255−259.
- Жарикова (Тихомирова) С. К синтезу отказоустойчивых элементов цифровых схем // Вестник ТГУ. Приложение. 2003. — № 6. — С. 114— 118.
- Вилла Т. Характеризация живых решений синхронного- автоматного уравнения / Т. Вилла, Н. Евтушенко, С. Жарикова (Тихомирова) // Вестник ТГУ. Сентябрь 2003. — № 278. — С. 129−133.
- Жарикова (Тихомирова) С. Решение автоматных уравнений в различных приложениях / С. Жарикова, Н. Евтушенко // Вестник КрасГУ. Физико-математические науки. 2004. -№ 3. — С. 35−39.
- Жарикова (Тихомирова) С. Автоматные уравнения и минимизация связей в автоматных сетях // Вестник ТГУ. Приложение: — 2004. -№ 9 (I). С. 209−213.
- Жарикова (Тихомирова) С. В. Оптимизация бинарной композиции автоматов // Вестник ТГУ. Приложение. 2005. — № 14. — С. 222−225.
- Ветрова М.В. Исследование отношений совместимости между недетерминированными автоматами / М. В. Ветрова, Н. В. Евтушенко, С. В. Жарикова (Тихомирова), Н. В. Спицына // Вестник КрасГУ. Физико-математические науки. 2006. — № 4. — С. 20−27.
- Жарикова-(Тихомирова) С. В. Метод нахождения прогрессивного решения системы автоматных уравнений // Вестник ТГУ. Приложение. -2006.-№ 17.-С. 20−24.
- Жарикова (Тихомирова) С. В. Решение автоматного уравнения для многомодульной композиции / С. В. Жарикова, Н. В. Евтушенко // Вестник ТГУ. Приложение. 2007. — № 23. — С. 6265.
- Жарикова (Тихомирова) С. Решение автоматных уравнений в различных приложениях / С. Жарикова // Тезисы докладов региональной научной конференции студентов, аспирантов, молодых ученых «Наука. Техника. Инновации». Новосибирск, 2001. — С. 6−7.
- Yevtushenko N. Multi component digital circuit optimization by solving FSM equations / N. Yevtushenko, S. Zharikova (Tikhomirova), M. Vetrova // Proceedings of the Euromicro symposium on digital system design. Turkey, 2003. P. 62−68.
- Zharikova (Tikhomirova) S. Minimization of communication wires by FSM equations solving / S. Zharikova, N. Yevtushenko // Proceedings of the work in progress session, Euromicro symposium on digital system design. France, 2004.
- Евтушенко Н.В. Достаточные условия существования комбинационного решения автоматного уравнения / Н. В. Евтушенко, С. В. Жарикова (Тихомирова) // Труды VI Международной конференции «Дискретные модели в теории управляющих систем». М., 2004. — С. 100−103.
- Жарикова (Тихомирова) С.В. К оптимальной реализации цифровых схем // Сборник тезисов 11-й Всероссийской научной конференции студентов-физиков и молодых ученых. Екатеринбург, 2005. — С. 461— 462.
- Kolomeets A.V. Digital controller for multiphase inverters / A.V. Kolomeets, M.L. Gromov, S.V. Zharikova (Tikhomirova), D.D. Popov // Proceedings of IEEE east-west design & test workshop. Ukraine, 2005. — P. 165−168.
- Zharikova (Tikhomirova) S.V. Minimization of Communication Wires in FSM Composition / S.V. Zharikova, N.V. Yevtushenko // Proceedings of IEEE east-west design & test workshop. -Sochi, 2006. P. 397−402.
- Дорофеева М.Ю. Декомпозиция цифровых схем для оптимизации на основе безразличных последовательностей / М. Ю. Дорофеева, С. В. Жарикова (Тихомирова) // Материалы V Всесибирского конгресса женщин-математиков. Красноярск: РИО СФУ, 2008. — С. 136−139.
- Мур Э. Ф. Умозрительные эксперименты с последовательными машинами / Э. Ф. Мур. М.: Изд-во иностр. лит., 1956. — С. 179−210.
- Гилл А. Введение в теорию конечных автоматов / А. Гилл. М.: Изд-во «Наука», 1966. — 272 с.
- Трахтенброт Б.А. Конечные автоматы: поведение и синтез / Б. А. Трахтенброт, Я. М. Барздинь. М.: Наука, 1970. — 400 с.
- Агибалов Г. П- Лекции по теории конечных автоматов: учеб. пособие / Г. П. Агибалов, A.M. Оранов. Томск: Изд-во Томского Университета, 1984.- 184 с.
- Hartmanis J. The algebraic structure theory of sequential machines / J. Hartmanis and R.E. Stearns. N.Y.: Prentice-Hall Inc. Englewood Cliffs, 1966.-210 p.
- Kim J. The simplification of sequential machines with input restrictions / J. Kim and M.M. Newborn // IRE transactions on electronic computers. -1972.-P. 1440−1443.
- Hassoun S. Optimization of synchronous circuits / S. Hassoun, T. Villa // Logic synthesis and verification. 2001. — P. 225−253.
- West C.H. An automated technique of communication protocols validation // IEEE transactions on communications. 1978. — Volume 26. — P. 1271−1275.
- BochmannG.v. Formal methods in communication protocol design /• G.v. Bochmann, C.A. Sunshine // IEEE transactions on communications. -1980. Volume 28. — P. 624−631. >.
- Merlin P. On the construction of submodule specification and Communication protocols / P. Merlin, G.v. Bochmann // ACM transactions on programming languages and systems. 1983. — Volume 5. — Issue 1. -P. 1−25.
- Kumar R. A discrete event systems approach for protocol conversion / R. Kumar, S. Nelvagal, S.I.Marcus // Discrete event dynamic systems: Theory & applications. 1997. — Volume 7 (3). — P. 295−315.
- MangF. Games in open systems: Verification and synthesis: Ph.D. thesis / F. Mang. England, 1995. — 129 p.
- Yevtushenko N. Synthesis by language equation solving: extended abstract / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Proceedings of annual Intern, workshop on logic synthesis. -2000.-P. 11−14.
- Brand D. On communicating finite state machines / D. Brand, P. Zafiropulo I I J. ACM. 1983. — Volume 30 (2). — P. 323−342.
- Агибалов Г. П. Декомпозиция конечных автоматов / Г. П. Агибалов, Н. В. Евтушенко. Томск: Изд-во Томского Университета, 1985. — 128 с.
- Synthesis of finite state machines: Functional optimization / Kam T. and et.al. Kluwer academic publishers, 1997. — 296 p.
- WonhamW.M. Supervision of DES Электронный ресурс. / W.M. Wonham. Электрон, дан. — Торонто, 1999 — Режим доступа: http://www.control.utoronto.ca/DES, свободный.
- Евтушенко Н.В. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей / Н. В. Евтушенко, А. Ю. Матросова // АВТ. 1991. — № 2. — С. 3−7.
- Лялин И.В. О решении автоматных уравнений / И. В. Лялин // Дискретная математика. 2004 — Т. 16, вып. 2. — С. 1−21
- Yevtushenko N. Solution of synchronous language equations for logic synthesis / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Вестник ТГУ. Приложение. 2002. -№ 1 (II).-С. 132−138.
- Yevtushenko N. Compositionally progressive solutions of synchronous language equations / N. Yevtushenko, T. Villa., R.K. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Proceedings of the IWLS. 2003. — P. 148 155.
- Rho J. Don’t care sequences and the optimization of interacting finite state machines / J. Rho, G. Hatchel, F. Somenzi // Proceedings of the International conference on computer-aided design. 1991. — P. 418−421.
- Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов: дис.. канд. техн. наук / Н.В. Спицына- Томский государственный ун-т. Томск, 2004. -160 с.
- Gill A. Introduction to the theory of finite state machines / A. Gill. New York: McGraw-Hill, 1962.
- El-Fakih Kh. Progressive solutions to a parallel automata equation / Kh. El-Fakih, N. Yevtushenko, S. Buffalov, G.v. Bochmann // Theoretical computer science. 2006. — Volume 362. — Issues 1−3. — P. 17−32.
- Евтушенко H.B. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции: учебное пособие / Н. В. Евтушенко, А. Ф. Петренко, М. В. Ветрова. Томск: Томский государственный университет, 2006. — 142 с.
- Starke Р.Н. Abstract Automata / Р.Н. Starke. N.Y.: American Elsevier publishing company, 1972. — 419 p.
- Hopcroft J.E. Introduction to automata theory, languages and computation / J.E. Hopcroft, J.D. Ulman. Addison-Wesley publishing company, 1979. -418 p.
- Khatri S. Engineering change in a non-deterministic FSM setting / S. Khatri, A. Narayan, S.C. Krishnan, K.L. McMillan, R.K. Brayton, A. Sangiovanni-Vincentelli // Proceedings of the IEEE/ACM'design automation conference. -USA, 1996.-P. 451−456.
- Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ. 1996. — № 6. — С. 34−50.
- Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов: дис.. канд. техн. наук / М.В. Ветрова- Томский государственный ун-т. Томск, 2004. — 150 с.
- Каравай М.Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // АиТ. 1996. — № 6. — С. 159−173.
- Cohen P.R. Trial by fire: understanding the design requirements for agents in complex environments / P.R. Cohen, M.L. Greenberg, D.M. Hart, A.E. Howe // AI Magazine. 1989. — Volume 10. — Issue 3. — P. 34−48.
- Corno F. RT-level ITC99 benchmarking and first ATGP results / F. Corno, M. Sonza Reorda, G. Squillero // IEEE design & test. Special issue on benchmarking for design and test. 2000. — P. 44−53.
- Закревский А.Д. Основы логического проектирования. Оптимизация в булевом пространстве. Кн. 2. / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. Минск: ОИПИ НАН Беларуси, 2004. — 240 с.
- Benchmarks Электронный ресурс. Электрон, дан. — Режим доступа: http://wwwxbl.ncsu.edu/benchmarks/LGSynth93/testcases/fsm/, свободный.
- Павлов В.Л. Синтез комбинационных схем в произвольном базисе // Алгоритмы решения задач дискретной математики. 1987. — Вып. 2. -С. 53−58.
- Синтез асинхронных автоматов на ЭВМ / под общ. ред. А. Д. Закревского. Минск: Наука и техника, 1975. — 184 с.
- BraytonR.K. The decomposition and factorization of Boolean expressions / R.K. Brayton, C. McMullen // Proceedings of the ISCAS. 1982. — P. 29−54.
- MishchenkoA. SAT-based complete don’t-care computation for network optimization / A. Mishchenko, R. Brayton // Design, automation and test in Europe. 2005. — Volume 1. — P. 412−417.
- Yevtushenko N. Compositionally progressive solutions of synchronous FSM equations / N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, A. Sangiovanni-Vincentelli // Journal of discrete event dynamic systems. -2007.