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

• Кныш, Данил Сергеевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Кныш, Данил Сергеевич

Список иллюстраций Введение.

Содержание

Глава 1. Анализ проблем проектирования СБИС. Задача трассировки коммутационных блоков.

1.1. Введение.

1.2. Современные технологии производства и использования СБИС.

1.3. Технологические проблемы изготовления и проектирования нанометровых СБИС.

1.4. Постановка задачи трассировки коммутационных блоков.

1.5. Анализ алгоритмов трассировки.

1.6. Выводы.

Глава 2. Разработка гибридного генетического алгоритма трассировки коммутационных блоков.

2.1. Введение.

2.2. Решения задач многокритериальной оптимизации.

2.3. Постановка задачи разработки гибридного генетического алгоритма

2.4. Целевая функция.

2.5. Структурная схема гибридного генетического алгоритма.

2.6. Кодирование и декодирование хромосомы.

2.7. Создание начальной популяции.

2.8. Модифицированные генетические операторы.

2.9. Параллельные вычисления в генетических алгоритмах.

2.10. Анализ существующих моделей параллельных генетических алгоритмов.

2.11. Модифицированная модель параллельного генетического алгоритма

2.12. Выводы.

Глава 3. Нечеткая логика и генетические алгоритмы.

3.1. Введение.

3.2. Функции принадлежности лингвистических переменных.

3.3. Схема использования аппарата нечетких множеств.

3.4. Расчет нечеткой функции качества топологии коммутационного блока

3.5. Модифицированный оператор кроссинговера.

3.6. Модифицированный оператор селекции.

3.7. Распределенные вычисления и нечеткие методы.

3.8. Теоретические оценки алгоритма.

3.9. Выводы.

Глава 4. Практическая реализация комплекса алгоритмов трассировки коммутационных блоков с цепями различной ширины.

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

4.2. Описание работы с программной реализацией комплекса алгоритмов

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

4.4. Результаты исследований.

4.5. Выводы.

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

Возникшая в 60-х годах нашего века технология создания интегральных схем развилась за короткое время, от создания интегральных схем, объединяющих несколько транзисторов, до интеграции миллионов транзисторов в одной* схеме. Первые интегральные схемы (ИС) представляли собой объединение одиночного транзистора с* набором сопротивлений, предназначенное для выполнения какой-либо логической функции. Сейчас ИС способны выполнять сложнейшие функции. В настоящее время, технология достигла размеров в 0.35 нанометра [1]. В ближайшие пять лет ожидается уменьшение до размеров одного слоя атомов. Современная технология позволяет разместить 10-15 миллионов транзисторов на схеме размером 25 мм. х25мм. Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных* этапов проектирования [2]. Сейчас, на всех стадиях проектирования топологии сверхбольших ИС (СБИС) интенсивно используют средства автоматизации проектирования, и многие фазы могут быть полностью или частично автоматизированы [3].

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

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

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

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

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

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

Этап конструкторского проектирования подразделяется на разбиение, планирование, размещение, трассировку, упаковку и верификацию.

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

Задача планирования заключается в определении взаимного расположения блоков относительно друг друга. Задачей размещения является определение конкретного места для каждого блока на кристалле. Трассировка заключается в конструктивной реализации связей между элементами. 9

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

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

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

В связи с большой сложностью и размерностью задачи трассировки, при проектировании, используется иерархический подход к трассировке. Существует два уровня трассировки: глобальная и детальная трассировки. На первом уровне вся область трассировки разбивается на подобласти. Задача глобальной трассировки заключается в распределении соединений по подобластям [5]. При этом учитываются такие факторы, как временные задержки и фактор реализуемости соединений в подобластях. Детальная трассировка заключается в реализации соединений в каждой подобласти. Обычно детальная трассировка делится на канальную трассировку [35-53, 8687] и трассировку коммутационных блоков (8-ш1:с11Ьох) [53-59]. В последнее

10 время стали актуальны так называемые коммутационные блоки, в которых терминалы располагаются сверху и снизу коммутационного блока.

Одним из новых направлений, которые могут привести к улучшению качества получаемых решений для задач детальной трассировки, является применение генетических алгоритмов (ГА). ГА основаны на аналогиях принципов адаптации биологических и технических систем. Они представляют собой мощный оптимизационный метод, моделирующий естественный процесс эволюции в качестве средства достижения оптимума. ГА основаны на селекции лучших решений из полученной популяции решений. Сравнительно недавно, их начали широко применять для решения задач в самых различных областях [65-71], в том числе для решения задач проектирования СБИС [38, 41, 43-47, 51, 72-83, 87].

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

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

Новым этапом развития теории генетических алгоритмов стали гибридные системы. Они основаны на совмещении таких теорий как генетические алгоритмы, нечеткие системы и нейронные сети. Существуют различные способы гибридизации этих трех подходов. Один из них это нечеткие генетические алгоритмы, в которых нечеткие системы используются для настройки параметров ГА, работы генетических операторов или для построения критериев окончания работы ГА.

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

ЦЕЛЬЮ диссертационной работы является, разработка, новых и модифицированных, методов и алгоритмов трассировки коммутационных блоков, позволяющих учитывать ширину проводников и физические характеристики проводников, такие как: межслойная емкость и сопротивление проводников:

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

1. Постановка задачи трассировки коммутационных блоков.

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

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

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

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

6. Исследование гибридных генетических алгоритмов трассировки. .

Для решения поставленных задач используют следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории алгоритмов, элементы теории генетического поиска, теория нечетких множеств.

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

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

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

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

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

12

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

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в Г/б № 12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска»; Г/б № 12355 (12.8.08) «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений»; Грант РФФИ' № 12388 (№ 08 - 01 - 00473) «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе интегрированных нечетких генетических и эволюционных методов»; Г/б № 12363 (РНП 2.1.2.1652) «Разработка теории и когнитивных принципов принятия решений на основе распределенных алгоритмов, инспирированных природными системами»; Грант РФФИ № 12382 (№ 09- 01 - 00492) «Разработка общей теории и когнитивных принципов эволюционных вычислений»; Грант РФФИ № 12383 (№ 09 - 07 - 00318) «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта»; РНП № 2.1.2.1652 «Разработка теории и когнитивных принципов принятия решений на основе распределенных алгоритмов, инспирированных природными системами».

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

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на конференции МЭС 2010; 11-ой Национальной конференции по Искусственному интеллекту с международным участием, КИИ-2008, Дубна. 29 сентября - 3 Октября 2008 года; Научно практическая конференция студентов, аспирантов и молодых ученых и специалистов «Интегральные модели, мягкие вычисления, вероятностные системы и сложные программы в искусственном интеллекте» Коломна, 26-27 Мая 2009 года; Конгресс по интеллектуальным вычислениями и информационным технологиям А18-1Т'09 Дивноморское 2-10 Сентября 2009 года; XV Международная конференция по нейрокибернетике Ростов-на-Дону 23-25 сентября 2009 года.

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

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ1. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения.

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

4.5. Выводы

Апробация комплекса алгоритмов на реальных примерах доказала его эффективность. Для проведения исследований была разработана программа на языке С++.

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

Разработанная программа трассировки цепей различной ширины в коммутационном блоке СБИС позволяет исследовать эффективность предложенного комплекса алгоритмов. Алгоритм имеет квадратичную зависимость 0{Ы) времени решения от числа выводов коммутационного блока.

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

Заключение;

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

1. Представлен-, анализ существующих алгоритмов решения задачи трассировки, цепей различной, ширины в коммутационном- блоке: в> СБИС; Выявлены основные достоинства' и недостатки? существующих, алгоритмов. Отмечены перспективные для исследований методы и алгоритмы эволюционного моделирования, в . частности методы генетического поиска; Сформулирована задача трассировки коммутационных блоков, с учетом использования технологии формирования сквозных межслойных* переходов. На основе проведенного анализа предложен и обоснован поиск на основе генетических алгоритмов и нечетких систем для решения задачи трассировки коммутационных блоков СБИС.

2. Разработан комплекс алгоритмов трассировки коммутационных блоков, на основе применения методов генетического поиска и аппарата нечетких множеств. Генетический алгоритм основан* на проблемно-специфическом; представлении схемы и проблемно-ориентированных генетических операторах. Создан алгоритм расчета нечетких оценок топологий цепей коммутационного блока. Разработан нечеткий оператор кроссинговера, использующий нечеткие оценки топологии; цепей. Нечеткий? оператор кроссинговера за счет целенаправленного выбора, точки кроссинговера позволяет получать потомков с лучшими частями родителей. Это,способствует генерации минимальной топологии коммутационного блока за счет использования оптимальных топологий цепей из хромосом родителей (альтернативных решений).

3. Разработан новый оператор селекции:, направленный на выбор хромосом из; популяции с учетом специфики генетического- оператора. Нечеткий, направленный! оператор селекции основан, на нечетких- оценках топологии цепей коммутационного блока и схемы работы нечеткого оператора кроссинговера. За счет использования направленного выбора хромосом для оператора кроссинговера и мутации удалось сократить время; "сходимости алгоритма на 10%.

4. Разработан алгоритм генерации, начальной. топологии коммутационного блока, (популяции хромосом). Он основан на методе дерева Штейнера (и в, частном случае, столба Штейнера) и алгоритме размещения по слоям с последовательной трансформацией топологии цепи. Определена теоретическая и экспериментальная оценки временной сложности разработанного алгоритма. Разработана целевая функция для оценки пригодности решения. Она учитывает длину проводников цепей, количество межслойных переходов, межслойную емкость и суммарное сопротивление проводников. Созданы модифицированные генетические операторы, позволяющие улучшить решения на 10-30% по сравнению с начальными решениями.

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

6. Для реализации предложенного комплекса алгоритмов было разработано программное . обеспечение. При разработке . программы трассировки коммутационных блоков СБИС были учтены критерии создания пользовательского интерфейса (интуитивность, непротиворечивость, гибкость). Программа написана на языке программирования- С++ в среде Borland С++ 6 для ОС Windows ХР, Vista. Проведенные исследования показали эффективность предложенного комплекса алгоритмов. Применение разработанных алгоритмов и методик позволяет уменьшить сроки проектирования СБИС на 5-10%. Результаты работы комплекса алгоритмов для известных наборов тестов показали результаты, лучшие на 10-20%. Кроме того алгоритм учитывает такие критерии коммутационного блока как межслойная емкость и суммарное сопротивление проводников. Это позволяет сократить время этапа верификации и уменьшить число перетрассировок в цикле проектирования СБИС.

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

1. Соколов А. Г. Казённов Г. Г., Принг{ипы и методология построения САПР БИС. Москва: Высшая школа, 1990.

2. Немудров В.Г., "Основные проблемы, задачи и этапы формирования современной' инфраструктуры проектирования СБИС «система на кристалле»," Электронная промышленность, №. 1, 2003.

3. Andrew В. Kahng, "Layout decomposition for double patterning lithography," in ICCAD, 2008.

4. Barry L. Nelson L. Jeff Hong, "A framework for locally convergent random-search algorithms for discrete optimization via simulation," in A CM 145 Transactions on Modeling and Computer Simulation, vol. 4, 2007, C. 19.

5. X. Yang, X. Huang, D. Sylveste Y. Cao, "Switch-Factor Based Loop RLC Modeling for Efficient Timing Analysis.," in IEEE Transactions on Very Large-Scale Integration (VLSI) Systems, vol. 9, 2005, C. 1072-1078.

6. Поляков А. К., Языки VHDL и Verilog в проектировании цифровой аппаратуры. Москва: COJIOH-Пресс, 2003.

7. С. Spanos G. May, Fundamentals of Semiconductor Manufacturing and Process Control.-. IEEE: John Wiley and Sones, 2008.

8. D. Mehta S. Sapatnekar C. Alpert, Handbook of Algorithms for Physical Design Automation. NY: CRC Press, 2009.

9. В. Стешенко, "Программируемые логические интегральные схемы: обзор архитектур и особенности применения," Схемотехника, №. 2, 2001.

10. Щемелинин В. М., Автоматизация топологического проектирования БИС. Москва: МИЭТ, 2001.

11. A.Sangiovanni-Vincentalli H.Shin, "Int. Conf. on Computer Aided Design," in Mighty: a rip-up and reroute detailed router., 1986, cc. 2-5.

12. H.M. Горшкова, O.C. Матвеенко Ю.Ф.Адамов, "Кремниевые гетероструктуры для наноразмерных транзисторов," Нано- и микросистемная техника, №. 7, С. 4—9, 2007.

13. Д. Радченко В. Кравченко, "Новое поколение физического синтеза 1С Compyler компании Synopsys," Электроника: Наука, технология, бизнес, №. 1,С. 76-79, 2006.

14. D. Drabold, Theory of Defects in Semiconductors. London: Springer, 2006.

15. В. Майская, "Транзисторы компании Intel с тройным затвором," ЭЛЕКТРОНИКА, №. 7, С. 50 52., 2006.

16. M.W. Bern, "18th Ann. Symp. Theory Computing," in Two probabilistic results on rectilinear Steiner tree, 1986, cc. 433-441.

17. B.M. Курейчик, Генетические алгоритмы, Монография ed. Таганрог: ТРТУ, 1998.

18. Курейчик В.М. Кныш Д.С., "Параллельные генетические алгоритмы: обзор и состояние проблемы," Известия РАН. ТиСУ, №. 4, С. 1 25, 2010.

19. R Schaefer, Foundations of Global Genetic Optimization. Berlin: Springer,2007.

20. J. Karro, J. Lienig J. P. Cohoon, "Evolutionary Algorithms for the Physical Design of VLSI Circuits," Advances in Evolutionary Computing: Theory and Applications, cc. 683-712, 2003.

21. R. Cheng L. Lin M. Gen, Network Models and Optimization: Multiobjective Genetic Algorithm Approach. New York: Springer, 2008.

22. Курейчик B.M., Сороколетов П.В. Курейчик В.В., "Анализ и обзор моделей эволюции," Изв. РАН. ТиСУ, №. 5, cc. 114-126, 2007.

23. D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Massachusetts: Addison-Wesley Publishing Company Inc., 1989.

24. Лебедев Б.К., Лебедев О.Б. Курейчик В.М., "Решение задачи покрытия на основе эволюционного моделирования," Изв. РАН. ТиСУ, №. 1, С. 119134, 2009.

25. N. Shervan, Algorithms for VLSI physical design automation. USA: Kluwer Academy Publisher, 1995.

26. R.C. Patón C. Setzkorn, "On the use of multi-objective evolutionaiy algorithms for the induction of fuzzy classification rule systems," BioSystems, №. 81, cc. 101-112, 2005.

27. S. Kwong, Y. Jin, W. Wei, K.F. Man H. Wang, "Multiobjective hierarchical genetic algorithm for interpretable fuzzy rule-based knowledge extraction," Fuzzy Sets and Systems, №. 149, cc. 149-186, 2005.

28. C. W. De Silva, Intelligent Control: Fuzzy Logic Applications. Boca Ration: CRC Press, 1995.

29. Курейчик В.М. Кныш Д.С., "Генетический алгоритм трассировки коммутационных блоков," Известия вузов. Электроника. Схемотехника и проектирование, №. 5(79), С. 28-34, 2009.

30. Р. Статников И. Соболь, Выбор оптимальных параметров в задачах со многими критериями. Москва: Дрофа, 2006.

31. В. Dorronsoro Е. Alba, Cellular Genetic Algorithms. New-York: Springer,2008.

32. W. Lu A. Antoniou, Practical Optimization. New York: Springer, 2007.

33. C.L. Yang, and Y.W. Chang P.H. Yuh, "BioRoute: A network-flow based routing algorithm for digital microfluidic biochips," in Int. Conf. Comput.-AidedDes., 2007, C. 752-757.

34. Кныш Д.С. Курейчик B.M., "Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока," in КИИ-08, vol. 1, 2008, cc. 179191.

35. J. Alcalá-Fdez., F. Herrera, J. Otero R. Alcalá, "Genetic Learning of the

36. Knowledge Base of a Fuzzy System by Using the Linguistic 2-Tuples Representation," in 14th IEEE International Conference on Fuzzy Systems, 2005, cc. 797-802.

37. P. Штойер, Многокритериальная оптимизация: теория, вычисления, прилоэ/сения. Москва: Наука, 1982.

38. Курейчик В.М. Кныш Д.С., "Генетический алгоритм трассировки коммутационных блоков Известия вузов," Электроника № 5(79). Схемотехника и проектирование, С. 28 — 34, 2009.

39. А. Андреев, "Арифметика создания процессов: 80 ядер лучше восьми?," ЭЛЕКТРОНИКА , №. 2, С. 82-89, 2007.

40. J. Hillman, W. Triggs, Е. Eichman D. Srinivas, "Advanced metallization for ULSI applications," Materials research society, C. 319-327, 1991.

41. D. Flagello, "SPIE Optical Microlithography," in Optimizing and enhancing optical systems to meet low K1 challenges. , 2003.

42. Wong A., "Resolution Enhancement Techniques in Optical Lithography," SPIE Press, 2001.

43. H. Yoda, S. Okazaki, N. Saitou, Y. Sakitani F. Mural, "Dose correction in e-beam lithography," Journal of Vacuum Science and Technology, vol. B, №. 6, C. 3072,1992.

44. Chin D., "IEEE International Solid-State Circuits Conference.," in Nanoelectronics for an Ubiquitous — Information Society, 2005, C. 22-26.

45. M. Casse, "Carrier Transport in Hf02/Metal Gate MOSFETs: Physical Insight Into Critical Parameters.," IEEE Transactions on Electron Devices, vol. 4, №. 53, C. 759-768, 2006.

46. Man H.D., "IEEE International Solid State Circuits Conference," in Ambient Intelligence: Gigascale Dreams andNanoscale Realities., 2005, C. 29-35.

47. S J. Lee, H.J. Yoo K. Lee, "IEEE Transactions on Very Large-Scale Integration (VLSI) Systems," in Low-Power Networkon-Chip for High-Performance SoC Design., vol. 2, 2006, C. 148-160.

48. Marek-Sadowska Malgorzata, Electrical and Computer Engineering Department. Santa Barbara, USA: University of California.

49. J. Soukup, "IEEE," in Circuit layout, vol. 10, 1981, cc. 128-134.

50. С. M. Fiduccin R. L. Rivest, "A greedy channel router.," Computer-Aided Design, vol. 3, №. 15, cc. 135-140, 1983.

51. Y.C. Hsu, F.S. Tsa Y.L. Lin, "Int. Conf. Computer Aided Design," in A detailed router based on simulated evolution., 1988, cc. 38-41.

52. H. Shin, "Two dimensional routing and compaction in computer aided design of integrated circuits," UCB/ERL M87.92, 1987.

53. H. Hellendoorn, M. Reinfrank D. Driankov, An Introduction to Fuzzy Control. Berlin: Springer-Verlag, 1993.

54. С. C. Lee, "IEEE Transactions on Systems, Man and Cybernetics," in Fuzzy1491.gic in Control Systems: Fuzzy Logic Controller — Part 1, vol. 2, 1990, cc. 419-435.

55. Э.Л. Хабина, Д.А. Шварц Ф.Т. Алескеров, Бинарные отношения, графы и коллективные решения. Москва: изд. дом ГУ ВЭШ, 2006.

56. К. Thulasiraman Jl Lienig, "A Genetic for Channel Routing in VLSI Circuits," Evolutionary Computation, vol. 4, №. 1, cc. 239-311, 1994.

57. B.M. Курейчик, В.В. Курейчик JI.А. Гладков, Генетические алгоритмы, Учебное пособие ed. Ростов-на-Дону: РостИздаст, 2004.

58. О. Е. Herrman S. Н. Gerez, "Int. Conf. Circuits and Systems," in Packer: a switch box routing based on conflict elimination by local transformation, 1989, cc. 961-964.

59. В.Д. Ногин, Принятие решений при многих критериях. СПб: «ЮТАС», 2007.

60. В.Д. Ногин В.В.Подиновский, Парето-оптгшалъные решения многокритериальных задач. Москва: Наука, 1982.

61. Хэмди А. Таха, Введение в исследование операций. Москва: Мир, 2001.

62. О.Е. Herrman S.H. Gerez, "Packer: a switch box routing based on conflict elimination by local transformation. ," in Int. Conf. Circuits and Systems, 1989, cc. 961-964.

63. С. H. Sequin P. S. Tzeng, "A congestion directed general area router.," in Int. Conf. Computer Aided Design, 1988, cc. 30-33.

64. Marek-Sadowska, "Global router for gate array," in Int. Conf. Computer Design, 1984, cc. 332-337.

65. P. L. Heck J. P. Cohoon, "Global router for gate array," in IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems CAD-7 (6) , 1988, cc. 684-697.

66. J. Kawa C.Chiang, Design for Manufacturability and Yield for Nano-Scale CMOS.: IEEE: Springer, 2007.

67. H. Kaeslin, Digital Integrated Circuit Design. Cambridge: Cambridge University Press, 2008.

68. A. Kahng B. Wong, Nano-CMOS Design for Manufacturability. New York: John Wiley & Sons, 2009.

69. L. Green R. Leventhal, Modeling Semiconductors: For Simulating Signal, Power, and Electromagnetic Integrity. New York: Springer, 2006.

70. Puneet Gupta, Andrew Kahng Saumil Shah, "Standard cell library optimization for leakage reduction," in DAC '06: Proceedings of the 43rd annual Design Automation Conference , New York, 2006, C. 983-986.

71. V. Oklobdzija, Digital Design and Fabrication. Boca Raton: CRC Press, 2008.

72. G. Lamont D. van Veldhuizen C. Coello, Evolutionary Algorithms for Solving Multi-Objective Problems. New York: Springer, 2007.

73. J. Branke, К. Miettinen, R. Slowinski K. Deb, Multiobjective Programming. New York: Springer, 2008.

74. M. Sh. Levin, "Combinatorial optimization in system configuration design," in Automation and Remote Control, vol. 3, 2009, C. 519-561.

75. L. Lavango, G. Martin L. Scheffer, EDA for 1С Implementation, Circuit Design, and Process Technology. Boca Raton: CRC Press, 2006.

76. Родзин С.И., "Организация параллельных эволюционных вычислений при поиске и оптимизации проектных решений," Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР», №. 4, сс. 39-45, 2009.

77. Сороколетов П.В. Курейчик В.В., "Концептуальная модель представления решений в генетических алгоритмах," Известия ЮФУ. Технические науки. Тематический выпуск ((Интеллектуальные САПР», №. 9, сс. 7-12, 2008.

78. Кныш Д.С. Курейчик В.М., "Параллельный генетический алгоритм. Модели и проблемы построения.," in Международная научно-практическая конференция ((Интегрированные модели и мягкие вычисления в искусственном интеллекте», vol. 1, 2009, С. 41 — 52.

79. Кныш Д.С., "Модель параллельного генетического алгоритма," in Конгресс по интеллектуальным системам и информационным технологиям AIS-IT'09, vol. 3, 2009, С. 132 136.

80. Кныш Д.С., "Алгоритм трассировки в коммутационном блоке," Известия ЮФУ. Технические науки. Тематический выпуск ((Интеллектуальные САПР», №. 9, сс. 107-112, 2008.

81. Y. W. Chang, S. J. Chen, and D. Т. Lee Т. Y. Hu, "Crosstalk- and performance-driven multilevel full-chip routing," in IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 6, 2005, C. 869-878.

82. Bin Liu, Qiang Zhou, Xianlong Hong Yici Cai, "A Two-Step Heuristic Algorithm for Minimum-Crosstalk Routing Resource Assignment," in IEEE Transaction on circuits and systems, vol. 10, 2006.

83. K. Chakrabarty, and R. B. Fair F. Su, "Microfluidics-based biochips: Technology issues, implementation platforms, and design-automation challenges," in IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 2, 2006, C. 211-223.

84. C.L. Yang, and Y.W. Chang P.H. Yuh, "Placement of digital microfluidic biochips using the T-tree formulation ," in Des. Autom. Conf, 2006, C. 931934.

85. C.L. Yang, Y.W. Chang P.H. Yuh, "Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation," in ACM J. Emerging Technol. Comput. Syst., vol. 3, 2007, C. 1—31.

86. K. F. Bohringer, "Modeling and controlling parallel tasks in dropletbased microfluidic systems," in IEEE Trans. Comput.-Aided Design Integr. Circuits

87. Syst., vol. 2, 2006, С. 334-344.

88. S. Akella, and M. K. Goldberg E. J. Griffith, "Performance characterization of a reconfigurable planar-array digital microfluidic system," in IEEE Trans. Comput.-AidedDesign Integr. Circuits Syst., vol. 2, 2006, C. 345-357.

89. W. Hwang, and K. Chakrabarty F. Su, "Droplet routing in the synthesis of digital microfluidic biochips ," in Des. Autom. Test Eur. , 2006, C. 323-328.

90. S.S. Sapatnekar, C.L. Yang, Y.W. Chang P.H. Yuh, "A progressive-ILP based routing algorithm for cross-referencing biochips," in Des.Autom. Conf, 2008 , C. 284-289.

91. Qing Su, Charles Chiang Jianfeng Luo, "A Layout Dependent Full-chip Copper Electroplating Topography Model," in International Conference on Computer Aided Design (ICCAD-2005), San Jose, 2005, cc. 133-140.

92. Jianfeng Luo, Charles Chiang Subarna Sinha, "Model Based Layout Dependent Metal Filling Algorithm for Improved Chip Surface Uniformity in the Copper Process," in International Conference on Computer Aided Design (ICCAD-2007), San Jose, 2007, cc. 1-6.

93. Xin Yuan Xiaoping Tang, "Technology Migration Techniques for Simplified Layouts with Restrictive Design Rules," in IEEE International Conference on Computer-AidedDesign (ICCAD'06), San Jose , 2006 , cc. 655-660.

94. Pan D Z, Xiang H Cho Minsik, "Wire Density Driven Global Routing for CMP Variation and Timing," in IEEE International Conference on Computer-Aided Design (ICCAD'06) , San Jose , 2006 , cc. 487-492.

95. Фролкин В. Т. Ильин В. Н., Автоматизация схемотехнического проектирования. Москва: Радио и связь, 1987.

96. Радченко Д. Кравченко В., "SYNOPSYS — Основные средства и возможности," ЭЛЕКТРОНИКА: Наука, Технология, Бизнес , №. 5, 2003.

97. Малышев И. В. Немудров В. Г., "Состояние и перспективы отечественных разработок СБИС типа «система на кристалле»," Системы и средства связи, телевидения и радиовещания, №. 1,2, 2003.

98. Гаврилов С.В., Глебов А.Л., Егоров Ю.Б. Стемпковский А.Л., "Методы многоуровневого анализа быстродействия цифровых КМОП СБИС," Известия ВУЗов. Электроника, №. 4, сс. 28-36, 2007.

99. Csiszar S., "Two-Phase Heuristic for the Vehicle Routing Problem with Time Windows," Acta Polytechnica Hungarica, №. 4, cc. 143-156, 2007.

100. Chen L. Chang Y., "Solve the vehicle routing problem with time windows via a genetic algorithm," Discrete and continuous dynamical systems supplement, C. 240-249,2007.

101. Kun Yuan, "Double patterning layout decomposition for simultaneous conflict and stitch minimization," in ISPD, 2009.

102. Huang-Yu Chen, "Novel Full-Chip Gridless Routing Considering Double-Via Insertion ," in ZMC, 2006.

103. G. Xu, "Redundant-Via Enhanced Maze Routing for Yield Improvement," in Asia and South Pacific Design Automation Conf, 2005.

104. F. Gomide, F. Herrera, F. Hoffmann, L. Magdalena O. Cordon, "Ten years of genetic fuzzy systems: Current framework and new trends," Fuzzy Sets and Systems, №. 41, cc. 5-31, 2004.