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

• Баринов, Сергей Владимирович
• кандидат технических наук
• 2008

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

Содержание

Введение

1. Анализ и состояние проблемы компоновки СБИС

1.1. Состояние и тенденции развития полупроводниковой отрасли

1.2.Графовые и гиперграфовые модели СБИС

1.3.Анализ алгоритмов разбиения графовых моделей для задачи разбиения схем

1.4. Выводы

2. Разработка архитектуры, стратегии и выбор модели эволюционного поиска для этапа компоновки СБИС

2.1. Определения, понятия генетических алгоритмов

2.2.Преимущества генетических алгоритмов над традиционными методами оптимизации

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

2.4.Эволюционные модели для задачи разбиения СБИС.

2.5.Этапы проектирования архитектуры эволюционного моделирования для задачи разбиения СБИС.

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

2.7.Выводы

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

3.1.Разработка многоуровневой структуры поиска для задачи разбиения схем

3.2.Алгоритм разбиения схем на основе кластеризации с учетом временных задержек.

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

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

3.5.Разработка модифицированных генетических операторов для задачи разбиения СБИС

3.6.Разработка алгоритма поэтапного развертывания разбиения схемы на исходные условия задачи на основе локальной эвристики улучшения

3.7.Выводы 109 4. Экспериментальные исследования разработанного программного комплекса разбиения СБИС.

4.1. Теоретическая оценка разработанного комплекса генетических алгоритмов разбиения схем на фрагменты

4.2.Краткое описание программной и аппаратной среды

4.3.Цель экспериментальных исследований

4.4.Этапы экспериментальных исследований

4.5.Результаты экспериментальных исследований

4.6.Выводы 140 Заключение 142 Список использованной литературы 144 ПРИЛОЖЕНИЕ

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

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

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

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

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

В этой связи, тема работы, связанная с разработкой новых методов решения задачи разбиения схем на фрагменты является АКТУАЛЬНОЙ.

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

Достижение указанной цели предполагает решение следующих основных задач:

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

• Разработка поисковых методов разбиения схем с учетом временных задержек.

• Построение архитектур эволюционного поиска для решения задачи разбиения схем.

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

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

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

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

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

3. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч. Дарвина, использующий принципы Парето оптимизации.

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

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

6. Предложен новый гибридный генетический алгоритм разбиения схем, включающий в себя «жадную» эвристику улучшения разбиения.

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

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

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

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

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

3. Генетические алгоритмы, использующие принципы Парето оптимизации, а также механизм варьирования размера популяции на основе учета «времени жизни» хромосом.

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

5. Модифицированные генетические операторы на основе фигурных чисел.

Практическая ценность результатов диссертационной работы определяется созданием комплекса алгоритмов разбиения схем с учетом временных задержек, позволяющих использовать разработанные математические модели, стратегии, концепции, принципы, методы и эвристики. Разработана программный комплекс «PGAComplex» для решения поставленной задачи на основе объектно-ориентированного языка Java 1.6 в среде NetBeans IDE 6.0. Отладка и тестирование проводились на ЭВМ типа IBM PC с процессором AMD Sempron 3500+ с ОЗУ объемом 512Мб. Проведенные экспериментальные исследования показали преимущество разработанных методов для решения задачи разбиения схем с учетом временных задержек. Время получения лучших результатов разбиения схем соответствует полиномиальному времени и лежит в пределах от O(nlogn) до 0(п2).

Реализация результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных и хоздоговорных работах, проводимых в Таганрогском Технологическом Институте Южного Федерального Университета: грант РФФИ № 01-01-00044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».

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

Апробация основных теоретических и практических результатов работы. Основные результаты диссертационной работы обсуждались и были одобрены на Всероссийской научно-технической конференции «Проблемы разработки перспективных микроэлектронных систем» (2005-2006 гг.),

Международной научно-технической конференции «Интеллектуальные САПР» (г. Дивноморск, 2005 - 2007 гг.), IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте»(г. Коломна, 2007г.).

Публикации. Результаты диссертации отражены в 9 печатных работах.

Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложения. Работа содержит 155 стр., а также 55 рисунков, 15 таблиц, список литературы из 106 наименований, 2 стр. приложений и актов об использовании.

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

4.6. Выводы.

1. Разработан программный комплекс для решения задачи компоновки СБИС с учетом временных задержек. Как показали исследования, программа PGAComplex обладает линейной пространственной сложностью и квадратичной временной сложностью. Кроме того, результаты разработанного комплекса обладают лучшими характеристиками по сравнению с известными алгоритмами - аналогами разбиения СБИС.

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

3. Комплекс генетических алгоритмов при разбиении СБИС с учетом временных задержек показали преимущество по сравнению с аналогичным алгоритмом разбиения hMetis. Качество получаемых решений удалось повысить ориентировочно на 5%-10%.

Заключение

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

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

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

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

4. Предложен модифицированный генетический алгоритм на основе модели эволюции Ч. Дарвина, использующий принципы Парето оптимизации.

5. Представлены новые и усовершенствованные алгоритмы свертки гиперграфа на основе нахождения сжатия гиперребер, агрегации фракталов.

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

7. Предложен новый гибридный генетический алгоритм разбиения схем, включающий в себя «жадную» эвристику улучшения разбиения.

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

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

10.Разработана инструментальная среда по исследованию характеристик комплекса генетических алгоритмов компоновки СБИС, обладающая лучшими характеристиками по сравнению с известными аналогами в области разбиения СБИС. При создании программы использовалась среда разработки NetBeans IDE 6.0, что позволило обеспечить удобный интерфейс пользователя и визуализацию работы алгоритма.

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

•л близка к 0(п ), а объем требуемой памяти линейно зависит от размерности задачи.

12.Иерархический комплекс генетических алгоритмов при разбиении СБИС с учетом временных задержек показали преимущество по сравнению с аналогичным алгоритмом разбиения hMetis. Качество получаемых решений удалось повысить ориентировочно на 5%-10%.

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

1. Норенков И.П. Принципы построения и структура САПР. М.: Высшая школа, 1986.

2. Норенков И.П. Основы автоматизированного проектирования. -М.: Изд-во МГТУ имени Н.Э.Баумана, 2000.-360с.

3. IBM Moves Moore's Law into the Third-Dimension. http.Y/www-03 .ibm.com/press/us/en/21350.wss.

4. Шаг в новое измерение: IBM совершает переворот в полупроводниковой отрасли, http://www.ixbt.eom/news/all/index.shtml705/44/l 0.

5. Сергей Шашлов. Закону Мура — 40 лет!. 20.04.2005, http://www.ixbt.com/editorial/moorelaw40th.shtml.

6. В. Немудров, Г. Мартин. Системы-на-кристалле. Проектирование и развитие. Москва: 2001.

7. В. А. Овчинников. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Москва: Изд-во МГТУ им. Баумана, 2001.

8. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

9. Фридман А. Д., Менон П. Р. Теория и проектирование переключательных схем.-М.: Мир, 1978.

10. Charles J. Alpert, Andrew В. Kahng. Recent directions in netlist partitioning. Integration, the VLSI Journal, 19(1-2):1-81,1995.

11. Баринов С. В., Иванько А.В., Щеглов С.Н. Основные средства автоматизированного проектирования печатных плат компании CADENCE DESIGN SYSTEMS. Перспективные информационные технологии и интеллектуальные системы, №1(25)/ 2006, -с. 52-57.

12. Т. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley-Teubner, 1990.

13. J. Cong, L. Hagen, A. B. Kahng. Net partitions yield better module partitions. In Proc. ACM/IEEE Design Automation Conf. Computer-Aided Design, p. 56-62,1994.

14. C. W. Yeh, C.-K. Cheng, T.-T. Y. Lin. A general purpose, multiple-way partitioning algorithm. IEEE Trans. Computer-Aided Design, 13(12), p. 14801487, 1994.

15. J. Cong, Z. Li, R. Bagrodia. Acyclic multi-way partitioning of Boolean networks. In Proc. ACM/IEEE Design Automation Conf., p. 47-52, 1992.

16. S. Iman, M. Pedram, C. Fabian, J. Cong. Finding uni-directional cuts based on physical partitioning and logic restructuring. Zin Proc. ACM/SIGDA Physical Design Workshop, p. 187-198, Los Angeles, 1993.

17. P. K. Chan, M. D. F. Schlag, J. Y. Zien. Spectral k-way ratio-cut partitioning and clustering. IEEE Trans. Computer-Aided Design, 13(8), p. 1088-1096, 1994.

18. C. W. Yeh, C.-K. Cheng, T.-T. Y. Lin. A probabilistic multi-commodity flow solution to circuit clustering problems. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 428-431, 1992.

19. W. Sun, C. Sechen. Efficient and effective placements for very large circuits. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 170-177, 1993.

20. D. J.-Huang, A. B. Kahng. When clusters meet partitions: New density-based methods for circuit decomposition. In Proc. European Design and Test Conf,1995.

21. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

22. N.-C. Chou, L.-T. Liu, C.-K. Cheng, W.-J. Dai, R. Lindelof. Circuit partitioning for huge logic emulation systems. In Proc. ACM/IEEE Design Automation Conf., p. 244-249,1994.

23. D. J.-Huang, A. B. Kahng. Multi-way system partitioning into single or multiple type FPGAs. In Proc. ACM/SIGDA International Workshop on Filed-Programmable Gate Arrays, p. 140-145, 1995.

24. R. Kuznar, F. Brglez, K. Kozminski. Cost minimization of partitions into multiple devices. In Proc. ACM/IEEE Design Automation Conf, p. 315-320, 1993.

25. B. W. Kemigan, S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. Journal, 49(2), p. 291-307,.1970.

26. С. M. Fidduccia, R. M. Mattheyses. A linear time heuristic for improving network partitions. In Proceedings ACM/IEEE Design Automation Conference, p. 175-181, 1982.

27. S. Dutt. New faster kernigan-lin-type graph-partitioning algorithms. In Proc. IEEE International Conference Computer-Aided Design, p. 370-377, 1993.

28. B. Krishnamurthy. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Computers, 33(5), p. 438-446,1984.

29. S. Kirkpatrick, C. D. Gellat, Jr., M.P. Vecchi. Optimization by simulated annealing. Science, 220, p. 671-680, 1983.

30. S. Geman, D. Geman. Stochastic relaxation, gibbs distribution, and the Bayesian restoration of images. IEEE Trans. Pattern Analysis and Machine Intelligence^, p. 721-741, 1984.

31. B. Hajek. Cooling schedules for optimal annealing. Mathematics of Operations Research, 13(2), p. 311-329, 1988.

32. P. J. M. Laarhoven, E. H. L. Aarts. Simulated Annealing: Theory and Applications. D. Reidel, Boston, 1987.

33. D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Shevon. Optimization by simulated annealing: An experimental evaluation part i, graph partitioning. Operations Research, 37, p. 865-892, 1989.

34. F. Glover. Tabu search part i. ORSA Journal on Computing, 1, p. 190-206, 1989.

35. P. E. Gill, W. Murray, M. H. Wright. Practical Optimization. Academic Press, 1981.

36. M. Shih, E. Kuh. Quadratic Boolean programming for performance-driven system partitioning. In Proc. ACM/IEEE Design Automation Conf., p. 761-765, 1993.

37. L. T. Liu, M. Shih, С. K. Chen, N>-C. Chou, W. Ku. Perfomance driven partitioning using retiming and replication. In Proc. IEEE International Conference Computer-Aided Design, o. 296-299, 1993.

38. C. Kring, A. R. Newton. A cell-replicating approach to mincut-based circuit partitioning. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 2-5, 1991.

39. J. Hwang, A. El Gamal. Optimal replication for min-cut partitioning. In ICC AD, p. 432-435,1992.

40. R. Kuznar, F. Brglez, B. Zajc. Multi-way netlist partitioning into heterogeneous fpgas and minimization of total device cost and interconnect. In Proc. ACM/IEEE Design Automation Conf., p. 238-243, 1994.

41. D. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Proc. ACM/SLAM Symposium Discrete Algorithms, p. 21-30, 1993.

42. T. Bui, S. Chaudhuri, T. Leighton, M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2), p. 171-191, 1987.

43. T. Bui, C. Heigham, C. Jones, T. Leighton. Improving the performance of the Kernigan-lim and simulated annealing graph bisection algorithms. In Proc. ACM/IEEE Design Automation Conf., p. 775-778, 1989.

44. K. Roy, C. Sechen. A timing-driven n-way chip and multi-chip paititioner. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 240-247, 1993.

45. S. Hauck, G. Borriello. An evaluation of bipartitioning techniques. In Proc. Chapel Hill Conference on Advance Research in VLSI, 1995.

46. G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. Technical Report TR 95-037, Department of Computer Science, University of Minnesota, 1995. http://www.cs.umn.edu/lcarypis/papers/mlevel analysis.ps.

47. Karypis, G. and Kumar, V. (1999b). Multilevel k-way hypergraph partitioning. In Proceedings of the Design and Automation Conference http://www.cs.umn.edu/Tcarypis.

48. Karypis, G. Multilevel algorithms for multiconstraint hypergraph partitioning. Technical Report TR 99-034, Department of Computer Science, University of Minnesota, 1999.

49. Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. Multilevel hypergraph partitioning: Application in vlsi domain. IEEE Transactions on VLSI Systems, 20(1), 1999.

50. J. Cong, H. Li, C. Wu. Simultaneous circuit partitioning/clustering with retiming for performance optimization. In Proc. ACM Design Automation Conference, 1999.

51. J. Cong, S. K. Lim. Perfomance driven multiway paertitioning. In Proc. IEEE/ASM Asia South Pacific Design Automation Conference, 2000.

52. C. N. Sze, T.-C. Wang, L.-C. Wang. Multilevel circuit clustering for delay minimization, In Proc. IEEE Trans. On Computer-Aided Design, 23, p. 10731085.'

53. R. Rajaraman, D. F. Wong. Optimal clustering for delay minimization. In Proc. ACM/IEEE Design Automation Conference, p. 309-314,1993.

54. E. L. Lawler, K. N. Levitt, J. Turner. Module clustering to minimize delay in digital networks. IEEE Transactions Computers, 18, p. 47-57, 1969.

55. R. Murgai, R. K. Bray ton, A. Sangiovanni-Vincentelli. On clustering for minimum delay/area. In Proc. IEEE Intl. Conf. Computer-Aided Design, p. 6-9, 1991.

56. J. Cong, Y. Ding. An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. In Proc. IEEE Itl. Conf. Computer-Aided Design, p. 48-53, 1992.

57. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. —М.: ФИЗМАТЛИТ, 2003. 432 с.

58. Курейчик В.М. Генетические алгоритмы и их применение: Монография. -Таганрог: Изд-во ТРТУ, 2002.

59. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

60. Курейчик В.В.,Сороколетов П.В. Эволюционные алгоритмы разбиения графов и гиперграфов. Известия ТРТУ,№3, 2004, с.23-32.

61. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. -М.: Эдиториал УРСС, 2002. -352с.

62. Хакен Г. Тайны природы. М.: Институт компьютерных исследований, 2003.

63. Курейчик В. В., Полупанов А.А. Эволюционные методы разбиения схем на основе адаптивных генетических процедур.- Таганрог: Изд-во Технологического института ЮФУ, 2007 160 с.

64. Дубинин Н.П. Избранные труды, Т.1. Проблемы гена и эволюции. М.: Наука, 2000.

65. Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs, Third, Revised and Extended Edition, Springer- Verlag Berlin Heidelberg New York, 1996, 388p.

66. Andreas Rummler, Adriana Apetrei. Graph Partitioning Revised a Multiobjective Perspective, In Proc. IEEE Itl. Conf. Computer-Aided Design, p. 45-51,2001.

67. Grefenstette, J.J., Optimization of Control Parameters for Genetic Algorithms, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 16, No.l, pp. 122128, 1986.

68. Goldberg, D.E., Optimal Initial Population Size for Binary-Coded Genetic Algorithms, TCGA Report No.85001, Tuscaloosa, University of Alabama, 1985.

69. Goldberg, D.E., Sizing Populations for Serial and Parallel Genetic Algorithms, in Proceedings of the Third International Conference on Genetic Algorithms (edited by Schaffer J.), Morgan Kaufmann Publishers, San Mateo, CA, 1989, pp.70-79.

70. Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

71. Lance Chambers. Practical handbook of genetic algorithms : new frontiers. Volume 2, 1996, 421 p.

72. Brindle, A., Genetic Algorithms for Function Optimization, Doctoral Dissertation, University of Alberta, Edmonton, 1981.

73. Baker, J.E., Adaptive Selection Methods for Genetic Algorithms, in Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, 1985., pp.101-111.

74. Рутковская Д., Пилиньский M., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского. М.: Горячая линия - Телеком, 2006. -452с.

75. Schwefel, H.-P., Numerical Optimization for Computer Models, John Wiley, Chichester, UK, 1981.

76. Muhlenbein, H. and Schlierkamp-Vosen, D., Predictive Models for the Breeder Genetic Algorithm, Evolutionary Computation, Vol.1, No.l, pp.25-49, 1993.

77. Курейчик B.B. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. -Таганрог: Изд-во ТРТУ, 2001.

78. Erick Cantu-Paz. Efficient and accurate parallel genetic algorithms, Kluwer Academic Publishers. Second Printing 2001, 167 p.

79. Erick Cantu-Paz. Migration Policies, Selection Pressure, and Parallel Evolutionary Algorithms, 24 p., 1999.

80. Haupt R. L., Haupt S. E. Practical Genetic Algorithms, Second edition, Wiley publishers, 2004, 26 lp.

81. Гладков JI. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы,-М: Физматлит, 2006.

82. Hendrickson, В. and Leland, R. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.

83. Баринов C.B., Гладков JI.A. Компоновка МЭС на основе многоуровневого подхода. Проблемы разработки перспективных микроэлектронных систем 2005. Сборник научных трудов /под общ. ред. А.Л. Стемпковского. - М.: ИППМ РАН, 2005. С. 136-141.

84. Баринов С.В., Курейчик В.М., Гладков Л.А. Компоновка МЭС на основе итерационной кластеризации с учетом временных задержек. Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2006. №8(63). С. 120-127.

85. Баринов С.В., Гладков Л.А. Компоновка МЭС на основе многоуровневого подхода. Материалы IV-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М: Изд-во Физматлит 2007. С. 300-305.

86. Баринов С. В., Гладков Л. А. Компоновка МЭС на основе многоуровневого подхода. «Нано- и микросистемная техника», №2/2007 с. 33-39.

87. R. Bazylevych. The Optimal Circuit Reduction Method as an Effective Tool to Solve Large and Very Large Size Intractable Combinatorial VLSI Physical Design Problems. 10th NASA Symposium on VLSI Design, 2002.

88. C. J. Alpert. The ISPD-98 Circuit Beanchmark Suit,, in Proc. ACM/IEEE International Symposium on Physical Design, April 1998, pp.80-85.

89. Баринов C.B., Курейчик B.M. Обзор методов учета временных задержек при логическом синтезе. Известия ТРТУ.-Таганрог: Изд-во ТРТУ,2007, №1(73), с.75-77.

90. P. Pan, А. К. Karandikar, and С. L. Liu. Optimal Clock Period Clustering for Sequental Circuits with Retiming. IEEE Trans. On Computer-Aided Design of Integrated Circuits And Systems, 17(6):489-498, 1998.

91. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. М.: МЦМОДООО.

92. М. Шредер. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Научно-издательский центр «Регулярная и хаотичная динамика», 2001.

93. Chen С. P., Chen Y.P, Wong D. F. Optimal Wiresizing Under Elmore Delay Model // IEEE Trans. On CAD of Integrated Systems. 2002. - V. 21. - No.3. pp. 319-329.

94. J. Cong and D. Z. Pan. Interconnect estimation and planning for deep submicron designs. In Proc. ACM Design Automation Conf., pp. 507-510, 1999.

95. J. Rubinstein, P. Penfield, Jr., and M. A. Horowitz. Signal delay in RC tree networks. IEEE Trans. On CAD of Integrated Circuits and Systems, v. 2, pp. 202-211, 1983.

96. Semiconductor Industry Association. National Technology Roadmap for Semiconductors, 1997.

97. Ope. О. Приглашение в теорию чисел. Изд-во: Едиториал УРСС, 2003 г. 130с.

98. В.М. Курейчик. Гибридные генетические алгоритмы. Известия ЮФУ. Технические науки Тематический выпуск "Интеллектуальные САПР",-Таганрог: Изд-во ТТИЮФУ, 2007, №2(77). С. 5-12.

99. P. Mazumder and Е.М. Rudnick. Genetic Algorithms for VLSI Design, Layout and Test Automation. Prentice Hall, Toronto, Canada, 1999.

100. Баринов С. В., Гладков JI. А. Анализ разработанной структуры данных для решения задач схемной компоновки на основе многоуровневого подхода. -Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2005, №3(47). С. 141-144.