Разработка и исследование алгоритмов эволюционного синтеза комбинационных схем
Диссертация
Наряду с программной реализацией систем автоматизированного проектирования необходимо рассматривать возможность реализации САПР в аппаратной области, когда аппаратные системы проектирования будут выполнять синтез схем в режиме реального времени, функционируя автономно и без участия человека, используя в своей основе хорошо зарекомендовавшие себя современные технологии, обогащенные… Читать ещё >
Содержание
- 1. АЛГОРИТМЫ ЭВОЛЮЦИОННОГО СИНТЕЗА КАК СРЕДСТВО АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
- 2. 1. Классификация алгоритмов синтеза
- 2. 2. Постановка задачи диссертационной работы
- 2. 3. Специфика проектирования эволюционных аппаратных средств
- 2. 4. Классификация эволюционных аппаратных средств
- 2. РАЗРАБОТКА АЛГОРИТМОВ ЭВОЛЮЦИОННОГО СИНТЕЗА КОМБИНАЦИОННЫХ СХЕМ
- 2. 1. Разработка бинарного генетического алгоритма для ПЛМ
- 2. 1. 1. Разработка бинарных генетических операторов
- 2. 1. 2. Разработка структуры генетического алгоритма для ПЛМ
- 2. 2. Разработка десятичного генетического алгоритма для ПЛМ
- 2. 3. Разработка десятичного генетического алгоритма синтеза комбинационных схем для логических элементов
- 2. 3. 1. Разработка методов передачи наследственной информации
- 2. 3. 2. Разработка алгоритма генерации популяции
- 2. 3. 3. Разработка структуры генетического алгоритма для логических элементов
- 2. 1. Разработка бинарного генетического алгоритма для ПЛМ
- 3. 1. Разработка устройства автоматизированного синтеза комбинационных схем для ПЛМ
- 3. 1. 1. Разработка параллельных генетических операторов
- 3. 1. 2. Разработка структурной схемы алгоритма автоматизированного синтеза комбинационных схем для ПЛМ
- 3. 1. 3. Анализ разработанного устройства автоматизированного синтеза комбинационных схем для ПЛМ
- 3. 2. Особенности разработанного генетического алгоритма автоматизированного синтеза комбинационных схем
- 3. 2. 1. Структура взаимодействия генетического материала
- 3. 2. 2. Анализ генетических операторов
- 3. 2. 3. Временная сложность функционирования алгоритма синтеза
- 3. 2. 4. Схемотехническое представление синтезированных комбинационных схем
Список литературы
- Cohoon, J.P. and Paris. W.D., Genetic Algorithms in Engineering Systems, The Institute of Electrical Engineers, London, 1997.
- Grimbleby, J. B, Automatic analog network synthesis using genetic algorithms, in Proc. of the First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (GALESIAS 95), England, 1995, 53.
- Brandon Blondet, Philip James-Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform //Field-Programmable Logic and Applications. 13th International Conference, FPL 2003 Proceedings, pp. 565−574.
- Grimbleby, J. В., Automatic analog network synthesis using genetic algorithms, in Proc. of the First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (GALESIAS 95), England, 1995, 53.
- Thompson A., Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al., Eds., MIT Press, Cambridge, 1996,444.
- Европейская патентная классификация: http://ep.espacenet.com/
- Vassilev V.K., Fogarty T.C., and Miller J.F., Information characteristics and the structure of landscapes, in Evolutionary Computation, 8, 1, MIT Press, Cambridge, 2000,31.
- Kirkpatrick S., Gelatt C.D., Jr. and Vecchi M.P., Optimization by simulated annealing, Science, 220, 1983, 671.
- Winston P. H., Artificial Intelligence, 3rd ed., Addison-Wesley, Reading, MA, 1992.
- Thompson A., Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al., Eds., MIT Press, Cambridge, 1996,444.
- Курейчик B.M. Генетические алгоритмы и их применение. Монография. Таганрог: изд-во ТРТУ, 2002, 242 с.
- T. Higuchi, M. Murakawa, M. Iwata, I. Kajitani, W. Liu, and M. Salami. Evolvable Hardware at Function Level// Proc. of 1997 IEEE Int. Conf. on Evolutionary Computation (ICEC97), pp. 187−192,1997.
- T. Higuchi et al. Evolvable hardware: A first step towards building a Darwin machine. In Proc. of the 2nd Int. Conference on Simulated Behaviour, pages 417 424. MIT Press, 1993.
- H. Iba, M. Iwata, and T. Higuchi. Machine Learning Approach to Gate-Level Evolvable Hardware// Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1259 (Proc. of ICES 1996), pp.327−343, Springer-Verlag, 1997.
- X. Yao and Т. Higuchi. Promises and Challenges of Evolvable Hardware// Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1259 (Proc. of ICES 1996), pp.55−78, Springer-Verlag, 1997.
- H. Sakanashi, M. Tanaka, M. Iwata, D. Keymeulen, M. Murakawa, I. Kajitani and T. Higuchi. Evolvable Hardware Chips and their Applications// Proc. of the 1999 IEEE Systems, Man, and Cybernetics Conference (SMC'99), pp. V559-V564, 1999.
- H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, «Rectangular-packing-based module placement,» in Proc. IEEE Inl. Conf. on Computer-Aided Design, 1995, pp. 472−479.
- J. Xu, P. N. Guo, and С. K. Cheng, «Rectilinear block placement using sequence-pair,» in Proc. 1998 ACM/IEEE Int. Symp. on Physical Design, Monterey, CA, Apr. 6−8, 1998, pp. 173−178.
- H. Shin, A. L. Sangiovarmi-Vincentelli, and С. H. Sequin, '"Zone-refining' techniques for 1С layout compaction," IEEE Trans. Computer-Aided Design, vol. 9, Feb. 1990.
- Stephen D. Brown, Robert J. Francis, Jonathat Rose, Zvonko G. Vranesic. Field-Programmable Gate Arrays// Kluwer Academic Publishers, USA 1992. 206 s.
- П. Хоровиц, У. Хилл «Искусство схемотехники». Москва Мир 2001 г.
- В.Б. Стешенко «Плис фирмы ALTERA: проектирование устройств обработки сигналов». Москва Додека 2000 г.
- S.J. Louis and G.J.E. Rawlins, «Syntactic Analysis of Convergence in Genetic Algorithms,» Foundations of Genetic Algorithms 2 ed. by L.D. Whitley, San Mateo, CA: Morgan Kaufmann, pp. 141, 1993.
- Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.
- Hamilton, A., Papathanasiou, K., Tamplin, M.R., and Brandtner, Т., Palmo: field programmable analog and mixed-signal VLSI for evolvable hardware, in
- Proc. of the Second International Conference on Evolvable Systems: From Biology to Hardware (ICES98), Lausanne, Switzerland, Sipper, M., Mange, D, and Perez-Uribe, A., Eds, vol. 1478, LNCS, Springer-Verlag, 1998, 335.
- J.G. Eldredge and B.L. Hutchings «Run-Time Reconfiguration: A Method for Enhancing the Functional Density of SRAM-Based FPGAs», in Journal of VLSI Signal Processing, Volume 12, 1996. Pages 67−86.
- R.S. Zebulum, M.A. Pacheco, M.M. Vellasco. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms// USA, CRC Press LLC, 2002
- Brandon Blondet, Philip James-Roxby, Eric Keller, Scott McMillan, Prasanna Sundararajan. A Self-reconfiguring Platform //Field-Programmable Logic and Applications. 13lh International Conference, FPL 2003 Proceedings, pp. 565−574.
- M.J. Wirthlin, B. L. Hutchings. «DISC: The dynamic instruction set computer», in Field Programmable Gate Arrays (FPGAs) for Fast Board Development and Reconfigurable Computing, John Schewel, Editor, Proc. SPIE 2607, pp. 92−103 (1995).
- В.В. Гудилов, JI.A. Зинченко. Повышение эффективности генетических алгоритмов на основе инструментального комплекса//Техническая кибернетика, радиоэлектроника и системы управления, Таганрог, 2002, стр. 127.
- В.В.Гудилов, В. М. Курейчик. Устройство аппаратной реализации вероятностных генетических алгоритмов// Методы и средства обработки информации. Труды Второй Всероссийской научной конференции. МГУ им. М. В. Ломоносова. Москва 2005. стр. 596−601.
- В.В. Гудилов, Л. А. Зинченко. Аппаратная реализация вероятностных алгоритмов эволюционного поиска//Известия ТРТУ, № 2 Интеллектуальные САПР Материалы международной научно-технической конференции, Таганрог 2003, стр 209−215.
- В.В. Гудилов, Л. А. Зинченко. Аппаратная реализация вероятностных генетических алгоритмов с параллельным формированием хромосомы/ЯТерспективные информационные технологии и интеллектуальные системы, № 4, 2003, стр 34−38
- Virtual Computer Corporation. The Reconfigurable Computer Company. http://www.vcc.com
- Stephen D. Scott, Ashok Samal, Sharad Seth. HGA: A Hardware-Based Genetic Algorithm // Dept. of Computer Science Washington University St. Louis, MO 63 130−4899, 7 p. 2001.
- A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27−30, 2001, pp.624−629.
- John C. Gallagher, Saranyan Vigraham and Gregory Kramer. A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware // IEEE Transactions on Evolutionary Computation, vol. 8, No. 2, April, 2004
- В. Стешенко, А. Самохин. Язык описания аппаратуры AHDL: www: http://ce.cctpu.edu.ru/msclub/pld/steshenko/ahdl.html53. www: http://altera.com54. www: http://xilinx.com
- Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ имени Н. Э. Баумана, 2000.- 360с.
- Гудилов В.В., Зинченко JI.A., Курейчик В. В., Курейчик В. М. Устройство аппаратной реализации вероятностных генетических алгоритмов. Патент Российской Федерации на изобретение № 2 294 561, заявка № 2 005 108 760 от 28.03.2005.
- Корячко В.П., Курейчик В. М., Норенков И. П. Теоретические основы САПР.-М.: Энергоатомиздат, 1987.
- Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. -М.: Радио и связь, 1990.
- Норенков И.П., Маничев В. Б. САПР ЭВА. М.: Высшая школа, 1983.
- Brayton R.K. Factoring logic functions // IBM Journal of Research and Development. Vol. 31. № 2. March 1987. P. 187−198.
- Miihlenbein Н., Kureichik V.M., Mahnig Т., Zinchenko L.A., A Comparison of Different Fitness Functions for Evolutionary Analog Circuit Design, Evolutionary Methods for Design, Optimization and Control, CIMNE, Barcelona, Spain, 2003, pp.49−50.
- Зинченко JI.A. Интеллектуальные системы схемотехнического проектирования. Десятая национальная конференция по искусственному интеллекту с международным участием. Труды конференции, Москва, Физматлит 2006. стр. 984−992.
- J. R. Koza. Genetic Programming II Automatic Discovery of Reusable Programs// A Bradford Book The MIT Press Cambridge, Massachusetts London, England 746 s
- J. R. Koza et al. Genetic Programming III//. San Francisco, CA: Morgan Kaufmann Publishers, 1999. P. 130.
- Holland J.H. «Genetic Algorithm, Scientific American, July 1992.
- B.B. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.
- Курейчик В.М. Генетические алгоритмы. Обзор и состояние// Новости искусственного интеллекта, М, № 3,1998, с.14−64.
- Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы// Известия АН. Теория и системы управления, № 1,1999, с. 144 160.
- Курейчик В.В. Генетические алгоритмы в проектировании СБИС: Учебное пособие. Таганрог: Изд-во ТРТУ, 1997.
- В.М. Курейчик. Генетические алгоритмы// Таганрог, 1998.
- Sripramong Т., Toumazou С. The Invention of CMOS Amplifiers Using Genetic Programming and Current-Flow Analisis //IEEE Trans. CAD, 2002.
- Vieira P.F., Sa L.B. Botelho J.P.B., Mesquita A. Evolutionary synthesis of analog circuits using only MOS Transistors //Proc. EH'04. 2004
- H. Muhlenbein. The Equation for Response to Selection and its Use for Prediction// Evolutionary Computation, May 1998, pp.303−346.
- Гладков JI.A. Курейчик, В.М. Курейчик Генетические алгоритмы// Ростов-на-Дону, Ростиздат. 2004 год.
- Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: Изд-во ТРТУ, 2000. 192 с.
- Лебедев Б.К. Методы поисковой адаптации на основе механизмов генетики, самообучения и самоорганизации. // Программные продукты и системы, 2002, № 1, с.16−20.
- J.D. Hadley, В. L. Hutchings. «Designing a partially reconfigured system,» in Field Programmable Gate Arrays (FPGAs) for Fast Board Development and Reconfigurable Computing, John Schewel, Editor, Proc. SPIE 2607, pp. 210−220 (1995).
- Joseph Hawkins, Scott Hemmert, Brent Nelson, and Mike Rytting «A CAD Suite for High-Performance FPGA Design», in Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines, April 1999.
- Higuchi, Т. Niwa, Т., Tanaka, Т., Iba, H., de Garis, H., Furuya, Т.: Evolvable Hardware with Genetic Learning// Proc. Sinmlation of Adaptive Behavior, MIT Press (1993) 417−424.
- I. Kajitani and other. An evolvable hardware chip and its application as a multi function prosthetic hand controller// In Proc. of 16th National Conference on Artificial Intelligence (AAAI-99), 1999.
- A. Mark H. Kikuo. Genetic design method and apparatus//Patent number: US2004049472. Application number: US20030649936 20 030 828
- I. Takashi, S. J. Barry, 0. Etsuko, Y. Mitsuhiro. Fitness function circuit//Patent number: US6185547. Application number: US 19 970 909 830 19 970 812
- I. Takashi, S. J. Barry, 0. Etsuko, Y. Mitsuhiro. Genetic algorithm machine and its production method, and method for executing a genetic algorithm//Patent number: US5970487. Application Number: US 19 970 910 103 19 970 813
- G. Harik, F. Lobo and D. Goldberg. The Compact genetic Algorithm // IEEE Transactions on Evolutionary Computation, vol. 3, Nov, 1999, pp. 287−309
- K.A. DeJong. An analysis of the behavior of a class of genetic adaptive systems // Ph.D. dissertation, Univ. Michigan, Ann Arbor, MI, 1775
- D. E. Goldberd. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 412 p.
- C. A. Coello. An Empirical Study of Evolutionary Techniques for Mul-tiobjective Optimization in Engineering Design. PhD thesis, Department of Computer Science, Tulane University, New Orleans, LA, apr 1996.
- T. Kalganova, J. F. Miller, and N.Lipnitskaya. «MultipleValued Combinational Circuits Synthesised using Evolvable Hardware,» in Proceedings of the 7th Workshop on Post-Binary Ultra Large Scale Integration Systems, 1998.
- Hollingworth, G. S., Smith, S. L. and Tyrrell, A. M., «The Intrinsic Evolution of Virtex Devices Through Internet Reconfigurable Logic,» in Proceedings of the Third International Conference on Evolvable Systems. Vol. 1801,2000, pp. 72−79.
- Черун C.B. Синтез комбинационных логических схем на основе эволюционного подхода. Диссертация, Таганров 2005, 157 стр.
- David Е. Goldberg. Genetic Algorithms in search, optimization, and machine learning. Addison Wesley, 1989.
- M. Murakawa et al. The grd chip: Genetic reconfiguration of dsps for neural network processing//IEEE Transactions on Computers, 48(6):628−638, June 1999.
- J.D. Lohn and S.P. Colombano. A circuit representation technique for automated circuit design// IEEE Trans, on Evolutionary Computation, 3(3):205−219, September 1999.
- Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования // Новости искусственного интеллекта. 2000. -№ 3. — С. 159−170.
- M. Iwata et al. A pattern recognition system using evolvable hardware// In Proc. of Parallel Problem Solving from Nature IV (PPSN IV). Springer Verlag, LNCS 1141, September 1996.
- Mining, and Complex Systems, Proc. of ANNIE'99. ASME Press, November 1999.
- E. Takahashi et al. An evolvable-hardware-based clock timing architecture towards gigahz digital systems// In Proc. of the Genetic and Evolutionary Computation Conference, 1999.
- J. F. Miller. Digital filter design at gate-level using evolutionary algorithms// In Proc. of the Genetic and Evolutionary Computation Conference, 1999.
- Sakanashi et al. Evolvable hardware chip for high precision printer image compression// In Proc. of 15th National Conference on Artificial Intelligence (AAAI-98), 1998.
- J. Torresen. Scalable evolvable hardware applied to road image recognition// In Proc. of the 2nd NASA/DoD Workshop on Evolvable Hardware. Silicon Valley, USA, July 2000.
- D. Keymeulen et al. On-line model-based learning using evolvable hardware for a robotics tracking systems//In Genetic Programming 1998: Proc. of the Third Annual Conference, pages 816−823. Morgan Kaufmann, 1998.
- E. Угрюмов. Цифровая схемотехника. Санкт-Перербург, «БХВ-Петербург» 2000 г. 528 стр.
- Ю.В. Капитонова и др. Лекции по дискретной математике. Санкт-Перербург, «БХВ-Петербург» 2004 г. 624 стр.
- Иванов Б.Н. Дискретная математика. М.: Лаборатория базовых знаний, 2001.
- Кузнецов О.П. Дискретная математика для инженера. СПб.: Лань, 2004.
- I. Kajitani, T. Hoshino, D. Nishikawa, H. Yokoi, S. Nakaya, T. Yamauchi, T. Inuo, N. Kajihara, M. Iwata, D. Keymeulen, T. Higuchi. A gate-level EHW chip: Implementing GA operations and reconfigurable hardware on a single LSI//
- Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1478 (Proc. ofICES1998), pp. 1−12, Springer Verlag, 1998.
- Д. Кнут. Искусство программирования для ЭВМ. Том 3. «Сортировка и поиск"// Москва Мир 1978 г.
- Баталов Б. В, Щемелинин В. М. Проектирование топологии интегральных схем на ЭВМ. М.: Машиностроение, 1979.
- Основные обозначения и сокращения1. ГА генетические алгоритмы
- ГП генетическое программирование1. ЛЭ логический элемент1. ММ математическая модель
- ПЛМ программируемая логическая матрица
- ПЛИС программируемые логические интегральные схемы FPGA1. П&bdquo- текущая популяция
- С величина схемы, определяющая количество используемых элементовс количество входных переменных аналитической функции