автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование интегрированных алгоритмов разбиения СБИС на фрагменты

ВВЕДЕНИЕ.

1. АНАЛИЗ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ РАЗБИЕНИЯ

4 СХЕМ ЭВА.

1.1. Постановка задачи разбиения схем.

1.2. Классификация методов и алгоритмов решения задачи разбиения.

В настоящее время во многих отраслях таких, например, как электронная 4 промышленность, приборо- и машиностроение широко применяются интегральные микросхемы (ИС) большой (БИС) и сверхбольшой (СБИС) степени интеграции. Это повышает надежность электронно-вычислительной аппаратуры (ЭВА), снижает ее габариты, потребляемую мощность, улучшая, таким образом, технико-экономические характеристики выпускаемых изделий.

Под «интегральной микросхемой (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и(или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная- микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1000 и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выделенная!в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.

Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом Мура [76]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [4—10].

Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных эле*ментов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры ♦ кристаллов. Подсчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора — два десятилетия.

Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [7-9]. Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы.

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

Иерархический подход подразумевает разбиение задачи проектирования СБИС на несколько последовательных этапов [4, 7]. Одним из важнейших этапов проектирования СБИС является этап конструкторского проектирования. А

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

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

Совершенно очевидно, что эффективность решения переборных задач непосредственно зависит от выбора формальной математической модели схемы. В настоящее время при создании структурных математических моделей схем используется аппарат теории графов. Это дает возможность строить математически обоснованные алгоритмы проектирования, находить простые и высококачественные решения, рационально и эффективно использовать ЭВМ [9, Ю]. Использование математических методов служит гарантией создания качественных систем. Эти методы состоят, в основном, из математических моделей, адекватных объектам проектирования, и алгоритмов оптимальных преобразований этих моделей с целью получения желаемого качества.

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

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

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

Большой вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли российские и зарубежные учёные такие, как: Бершадский A.M., Казеннов Г.Г., Курейчик В.М., Норенков И.П., Селютин В.А., Шервани Н. и др. В основном известные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещения разногабаритных объектов (формирования базового плана кристалла) и межблочной трассировки межсоединений по критерию минимизации занимаемой площади и длины связей [13-16]. В связи с увеличением сложности и размерности задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач.

С точки зрения повышения эффективности САПР, представляет интерес разработка новых алгоритмов и методов проектирования, для так решения называемых NP-полных задач, т.е. задач, в которых нахождение оптимального решения возможно только полным перебором. К числу таких методов можно отнести методы эволюционного моделирования, которые появились в начале 70-х годов двадцатого века. В настоящее время они получили широкое распространение при решении задач в самых различных областях [17 — 23], поскольку такие алгоритмы позволяют обрабатывать множество решений при учёте множества критериев [24-36]. Данными свойствами обладают генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Уже имеются примеры успешного применения ГА для решения самых различных задач [40 - 52], в том числе и задач автоматизированного проектирования СБИС [53 - 78].

Значительный вклад в развитие методов эволюционного поиска внесли такие учёные, как: Холланд Д., Гольдберг Д., Растригин Л.А., Букатова И.Л, Батищев Д.И., Курейчик В.М. и др. Сущность генетических алгоритмов заключается в моделировании естественных эволюционных процессов как средства достижения оптимума. Основная проблема при этом - поиск баланса между эффективностью и качеством для "выживания" в различных условиях. Пожалуй, одним из главных свойств ГА является, то что, они в силу своей "природы" достаточно легко преодолевают локальные оптимумы. Гибкость структуры ГА, возможность её настройки и перенастройки дают возможность создания структур, обеспечивающих получение наилучшего результата за приемлемое время. Это, в свою очередь, предоставляет исследователям широкие возможности для поиска в этом направлении [44, 50, 55 - 60, 63 - 66].

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

ЦЕЛЬЮ диссертационной работы является исследование и разработка методов разбиения схем ЭВА на основе модифицированных схем и операторов генетического поиска и эволюционного моделирования, по критерию суммарного числа внутренних (внешних) связей, позволяющих повысить качество решений для задач большой размерности.

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

1) Проведен анализ поставленной задачи и определено ее место в общей задаче проектирования ЭВА, а также комплексный анализ существующих алгоритмов разбиения схем (последовательных, параллельных, последовательно-параллельных, смешанных).

2) Провёден анализ и обоснование выбора математической модели схем для решения поставленной задачи. Предложен ряд графовых и гиперграфовых математических моделей для решения задачи разбиения'схем ЭВА. Проведен анализ существующих алгоритмов решения задачи выделения независимых и доминирующих подмножеств в специальных графовых и гиперграфовых моделях схем ЭВА.

3) Выполнен анализ основных генетических операторов и их модификаций с точки зрения их пригодности для решения поставленной задачи, сформулированы основные принципы и схема работы ГА;

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

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

6) Разработан новый эволюционный алгоритм выделения ядер в нечетких графах и гиперграфах. Разработана новая двухуровневая схема поиска ядер в нечетких графах и гиперграфах. Разработаны новые генетические и эволюционные операторы (кроссинговер на основе логических операций, мутация на основе целевой функции и др.).

7) Выполнены экспериментальные исследования разработанных методов и алгоритмов, а также их сравнение с известными алгоритмами разбиения.

Для решения поставленных задач использовались следующие МЕТОДЫ

ИССЛЕДОВАНИИ: элементы высшей математики, теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска, статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1) Разработке новой схемы функционирования генетического алгоритма выделения независимых и доминирующих подмножеств;

2) Формировании структуры и принципов кодирования (декодирования) решений для» решения задачи выделения независимых и доминирующих подмножеств;

3) Построении новых эволюционных и генетических операторов и их модификаций, адаптированных к требованиям решаемой задачи;

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют: F

Пакет прикладных программ.

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

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

3) Пакет прикладных программ для решения задачи выделения

Jk различных экстремальных подмножеств в графовых и гиперграфовых математических моделях схем ЭВА для операционных систем Windows® 9х/МЕ/2000/ХР фирмы Microsoft Corporation, созданная в среде и объектно-ориентированного программирования Borland С++ Builder.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных работах «Разработка интеллектуальных систем проектирования на основе эволюционной адаптации» (№ ГР 01.9.60004346) и «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений» (№ ГР 01.2.00118499), а также научно-исследовательских работах, выполняемых по грантам Российского фонда фундаментальных исследований «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов» (№ 02-01-01275), «Эволюционное проектирование с адаптацией» (№ 01-01-00044), «Генетические алгоритмы в интеллектуальных САПР» (№ 99-01-00050), х/д между ТРТУ и Российским научно-исследовательским институтом информационных технологий и систем автоматизированного проектирования (ГУ Рос НИИ ИТ и АП) № 12301 «Разработка эволюционных алгоритмов на графах с динамическими параметрами» и научно-исследовательской работе «Разработка интеллектуальных систем проектирования и технологической подготовки производства на основе эволюционной адаптации» (№ ГР 01200111207), выполняемой в рамках научно-технической программы Министерства образования РФ «Научные исследования высшей школы по приоритетным направлениям науки и техники». Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций, а также лабораторных и практических занятиях по курсам «Эволюционное моделирование и генетические алгоритмы», «Методы оптимизации и генетические алгоритмы» и «Математические основы дискретной техники».

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах кафедры САПР "Генетические алгоритмы" (с 2000 по 2004 гг., ТРТУ), Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 2000, 2002 гг.), Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, 2000, 2001, 2003 г.), Всероссийской научной конференции молодых учёных и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002, 2003 гг.), Международной научно-технической конференции «Интеллектуальные САПР» (г. Геленджик, 2000 - 2004 гг.), Международной научной конференции «Искусственные интеллекиуальные системы» (г. Геленджик, 2002 - 2004 гг.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 10 печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 157 стр., включая 67 рис., 4 табл., список использованных источников из 110 наименований, 3 стр. приложений и актов об использовании. СОДЕРЖАНИЕ РАБОТЫ.

4.5. Выводы и рекомендации

1. На основе предложенных алгоритмов был разработан пакет прикладных программ на языке программирования высокого уровня Borland С++ для операционной системы Windows 95/98, 2000, NT, ХР. Было приведено описание интерфейса разработанных программ выделения экстремальных подмножеств в графах и гиперграфах.

2. Были проведены экспериментальные исследования разработанных алгоритмов, которые показали, что их временная сложность в худшем случае не превышает 0(п ). На основании этого можно утверждать, что разработанные алгоритмы являются эффективным и представляют практическую ценность.

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

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

• выход из локальных оптимумов;

• быстродействие;

• сходимость процесса поиска;

• снижение трудоемкости.

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

• увеличить число критериев;

• разработать новые стратегии.

ЗАКЛЮЧЕНИЕ

1. Выполнена постановка задачи разбиения схем ЭВА и определено место рассматриваемой задачи в общей схеме процесса автоматизированного проектирования ЭВА.

2. Проведен анализ существующих математических моделей схем ЭВА и выбран ряд модификаций математических моделей на основе нечетких графов и гиперграфов для решения задачи разбиения.

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

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

5. Были проведены экспериментальные исследования разработанных алгоритмов, которые показали, что их временная сложность в худшем случае л не превышает 0(п ). На основании этого можно утверждать, что разработанные алгоритмы являются эффективным и представляют практическую ценность.

1. Закон РФ № 3526 - 1 от 23.09.92г. «О правовой охране топологий интегральных микросхем»

2. ГОСТ 17021 75 «Микросхемы интегральные. Термины и определения».

3. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учеб. пособие для вузов. М.: Радио и связь, 1983.-280 е.: ил.

4. Петренко А.И., Лошаков В.Н., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.

5. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987.-400 е.: ил.

6. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6. Автоматизация конструкторского и технологического проектирования: Учеб. пособие для втузов/ Под ред. Норенкова И.П.-М.: Высшая школа, 1986.-160 с.:ил.

7. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем. Москва, Высшая школа, 1989.

8. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981. - 168 е., ил.

9. Sherwani N.A. Algoritms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

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

11. Под редакцией Морозова К.К. Методы разбиения схем РЭА на конструктивно законченные части. Москва, Советское радио, 1978.

12. Петренко А.И., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры (топологический подход).

13. Киев: Вища школа, 1980. 176 с.

14. Мелихов А.Н., Берштейи JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 304 с.

15. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: издательство Ростовского университета, 1981. - 112 с.

16. Горинштейн Л.Л. О разрезании графа. Известия АН СССР, Техническая кибернетика, 1969, №1.

17. Зыков А.А. Гиперграфы // Успехи математических наук. М. 1979, т.29, вып.6.

18. Youssef G. Saab, Vasant В. Rao. "Fast Effective Heuristics for the Graph Bisectioning Problem", IEEE, vol.9 N1, January 1990, Transaction on computer-aided design.

19. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

20. Y.C. Wei, С.К. Cheng. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

21. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th АСМЛЕЕЕ Design Automation Conference, paper 25/1, pp.421-425., 1991.

22. C.J. Alpert, A.B. Kahng. "Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning", in 30th АСМЛЕЕЕ Design automation conference, 1993, pp. 743-748.

23. Holland, John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

24. Goldberg David E., Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Inc. 1989.

25. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991,-385p.

26. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemesused in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, CA, 1991.

27. Syswerda G. Uniform Crossover in Genetic Algorithms. Proc. of the 3-rd Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1989. p.2-9.

28. Foundation of Genetic Algorithms, edited by Rawlins Gregory. Morgan Kaufman Publishers, San Mateo, California, 1991, -473p.

29. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.

30. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.

31. Practical Handbook of Genetic Algorithms Complex Coding Systems. Volume 3. / Edited by Lance D. Chambers. CRC Press, Boca Raton, London, New York, Washington D.C., 1999. - 572 p.

32. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992.

33. Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control, Plymouth, UK, 1996. pp. 294-296.

34. Liu, X., Sakamoto, A., Shimamoto, T. Restrictive Channel Routing with Evolution Programs. // Trans. IEICE, vol.E76-A, no. 10, 1993. pp.1738-1745.

35. Rahmani, A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem. // in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494-498.

36. Lieng, J., Thulasiraman, K. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293-311.

37. Курейчик В.М. Генетические алгоритмы и их применение в САПР. // Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7-11.

38. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения // XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff, 1995. c. 329-330.

39. Cohoon J.P. and Paris W.D. Genetic placement. // IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6, 1987. pp.956-964.

40. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. // Case Center Technical Report #940702, Michigan State University

41. Chan, H.M. and Mazmunder, P. A genetic algorithm for macro cell placement. // Technical report, Department of Electrical Engineering and Computer Science, University of Michigan, 1989

42. Kureichik, V.M. Genetic Algorithms In CAD. // Proc. Russia Conf. AI in CAD, Gelendzik, September 1993.

43. Lin S.C., Goodman E.P., Punch W.F. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. // Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 481-488.

44. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. // Proc. of the Second Intl. Conf. Adaptive Computing in Engeneering, Design and Control, Plymouth, UK, March 1996. pp. 53-58.

45. Батищев Д.И., Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов. // XXIII International School and Conference on Computer Aided Design.Yalta-Gurzuff, 1996. 354 с

46. Shahookar K., Mazmunder P. A Genetic Approach to standart Cell Placement

47. Using Meta-Genetic Parameter Optimization, IEEE Trans, on CAD, Vol.9, No.5, May, 1990, -377p.

48. Burstein, M. Channel routing, Layout Design and Verification. Elsevier Science, 1986. pp. 133-167.

49. Yoshimura, T. And Kuh, E.S. Efficient algorithms for channel routing. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.1, no.l, 1982. pp.25-35.

50. Автоматизация проектирования больших и сверхбольших интегральных схем. / А.И. Петренко, В.М. Курейчик, А .Я. Тетельбаум и др. // Зарубежная радиоэлектроника, 1981, № 6, с. 47 - 66.

51. Автоматизация проектирования топологии БИС на базовых матричных кристаллах / А.И. Петренко, А.Я. Тетельбаум, Б.Л. Шрамченко, Н.В. Луганский // Зарубежная радиоэлектроника, 1985, № 8, с. 26 - 40.

52. Селютин В.А. Автоматизированное проектирование топологии БИС. М.: Радио и связь, 1983. - 112с.

53. Крегер Д., Тозун О. Автоматизированное проектирование обостряет конкуренцию приборов со стандартами. //Электроника, 1980, т.ЗЗ, № 15, -с.28 34.

54. Мелихов А.Н., Берштейн Л.С. Конечные чёткие и расплывчатые множества. Таганрог, ТРТИ. 1980.

55. Букатова И.Л. Эволюционное моделирование: идеи, основы теории, приложения. Москва, Знание, выпуск 10, 1981.

56. В. Kernighan, S. Lin. "An efficient heuristic procedure for partitioning graphs", Bell Syst. Tech. J., vol 49, pp. 291-307, Feb., 1970.

57. C. Fiduccia, R. Mattheyses. "A linear time heuristics for improving network partitions", in 19th ACM/IEEE Design automation conference, 1982, pp. 175181.

58. Emanuel Falkenauer, "Setting New Limits in Bin Packing with a Grouping GA Using Reduction", Tech. report R0108, March 1994.

59. Кодачигов В.И., Карелин В.П., Пашкевич А.П., Курейчик В. М. О разрезании произвольного конечного графа на подграфы. — в кн.:

60. Цифровые модели и интегрирующие структуры. Под. ред. A.B. Каляева. Таганрог, Радиотехнический институт, 1970.

61. D. Schweikert, В. Kernighan, "A proper model for partitioning of electrical circuits", in 19th Design automation workshop, 1972, pp. 57-62.

62. Ope О. Теория графов. M.: Наука, 1980. 336.

63. Зыков A.A. Основы теории графов. М.: Наука, 1987. 384 с.

64. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.

65. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. 480 с.

66. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

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

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

69. Петров Д.Ф. Генетика с основами селекции. М.:Высшая школа, 1971 г. -410с.

70. Mange А.Р.,Mange E.J., Genetics: Human Aspects. Saunder Colledge, Philadelphia, 1982.-305 p.

71. Джеральд Ф. Джойс. "Направленная молекулярная эволюция". Журнал "В мире науки". №2,3 1993 г. стр.32/всего 160 стр. Издательство "Мир". Москва

72. Яблоков В.А. Фенетика. М.: Наука, 1980 г. 132 с.

73. Ауэрбах Ш. Проблемы мутагенеза. Пер. с англ. Гнездицкой Э.В., Маршак М.И., Полукаровой Л.Г. Под ред. Шапиро Н.И. М.:Мир, 1978 Г.-464 стр.

74. Ляпунова H.A. О мутациях случайных и направленных. Наука и жизнь. 1989 г. №8 с.60-61.

75. Бейсон Ж. Генетика. Пер с франц. Назарова В.И., М.: Атомиздат, 1978 г. -128 стр.

76. Ваганов А. Как понять генетическую информацию. // Инженерная газета. 1995 г. №43.

77. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: ОСНОВА, 1997. - 112 с.

78. Grefenstette D.E., Gopal G., Rosmaita В. et al. Genetic Algorithms for the Traveling Salesman Problem // Proc. 1st Intern. Conf. Of Genetic Algorithms and Their Applications. New Jersey, 1998.

79. Курейчик B.M. Генетические алгоритмы. Состояние. Проблемы. Перспективы. // Известия Академии Наук. Теория и системы управления. -М.: Наука, МАИК «Наука/Интерпериодика», № 1, 1999. стр. 144 - 160.

80. Курейчик В.М. Генетические алгоритмы в технике. // Методы кибернетики и информационной технологии. Саратов: РАЕН, 1997 - стр. 45 - 54.

81. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.-М.: Мир, 1985.-512 с.

82. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир,- 1979.-536 с.

83. Липский В. Комбинаторика для программистов/ Пер. с польского Евстигнеева В.А., Логиновой О.А.-М.: Мир, 1988.-213 с.:ил.

84. Митропольский А.К. Техника статистических исследований. М., "Наука"., 1971.-576 е.: ил.

85. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие./ Под общ. ред. Останина А.Н.Минск.: Вышэйшая школа., 1989. 218 е.: ил.

86. Львовский E.H. Статистические методы построения эмпирических формул: Учеб.пособие для втузов.-М.: Высшая школа, 1988.-239 е.: ил.

87. Адлер Ю.П. Введение в планирование эксперимента.-М.:Металлургия, 1969. 157 с.:ил.

88. Ежов И.И., Скороход A.B., Ядренко М.И. Элементы комбинаторики.-М.: Наука, 1977.-264 с.

89. Гроппен В.О. Принципы оптимизации комбинаторных процедур. Ростов-на-Дону : Издательство РГУ,-1988.-195 с.:ил.

90. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторныеаппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990 г. 216 с.

91. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа. Известия Академии наук. Теория и системы управления, №4, 1999.

92. Гладков Л.А., Зинченко Л.А., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Нужнов Е.В., Сорокин С.Н. Методы генетического поиска: Научное издание / Под редакцией В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2002. 122 с.

93. Зайченко Ю.П. Исследование операций. Киев: Вища школа, 1975. - 320 с.

94. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов.-М.: Наука, 1986.-544 с.:ил.

95. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений.-М.:Физматгиз, 1962. 349 с.:ил.

96. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий.-М.: Наука, 1971. 283 с.:ил.

97. Андерсон Т. Введение в многомерный статистический анализ./ Пер. с англ. Кичатова Ю.Ф.-М.:Физматгиз, 1963. 500 е.: ил.

98. Большов Л.Н., Смирнов Н.В. Таблицы математической статистики.-М.:Наука, 1965. 464 с.

99. Гурский Е.И. Теория вероятностей с элементами математической статистики.-М.: Высшая школа, 1971. 328 с.

100. Гренандер У. Случайные процессы и статистические выводы/ Пер. с англ. и доп. Яглоба А.М.-М.:Изд-во иностранной лит., 1961. 167 с.

101. Даймонд С. Статистика в науке/ Пер. с англ. Дружининой А.Л.-М.: Статистика, 1970. 155 с.

102. Подбельский В.В. Язык Си++: Учебное пособие. М., Финансы и статистика, 1995. - 560 с.

103. Голуб А.И. С и С++. Правила программирования. М., БИНОМ, 1996. -272 с.

104. Бабэ Б. Просто и ясно о Borland С-ь+. М.: БИНОМ, 1994. - 400 с.

105. Бентли Д. Жемчужины творчества программистов / пер. с англ. М., Радио и связь, 1990. - 244 с.

106. Лэнгсам Й., Огенстайн М., Тетельбаум А. Структура данных для персональных ЭВМ. М., Мир, 1989. - 568 с.

107. АКТЫ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ РАБОТЫ