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

• Воронин, Егор Ильич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Воронин, Егор Ильич

Список иллюстраций.

Введение.

Глава 1. Анализ проблем проектирования СБИС. Задача глобальной трассировки СБИС.

1.1 Современные технологии производства субмикронных СБИС.

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

1.3 Постановка задачи глобальной трассировки.

1.4 Два подхода к решению задачи многослойной глобальной трассировки.

1.5 Обзор методов решения задачи глобальной трассировки.

1.6 Выводы.

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

2.1 Многоуровневый подход к решению задачи трассировки. Трассировка по всему кристаллу.

2.2 Биоинспирированные методы.

2.3 Муравьиный алгоритм решения задачи глобальной трассировки простыми формами.

2.4 Муравьиный алгоритм глобальной трассировки для соединений сложной конфигурации.

2.5 Выводы.

Глава 3. Разработка генетического алгоритма распределения соединений по слоям при глобальной трассировке.

3.1 Постановка задачи распределения соединений по слоям.

3.2 Генетические алгоритмы.

3.3 Генетический алгоритм распределения соединений по слоям.

3.4 Иерархическая структура генетического поиска.

3.5 Дополнительные модификации иерархического генетического алгоритма.

3.6 Выводы.

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

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

4.2 Теоретические исследования разработанных алгоритмов.

4.3 Библиотека для использования генетических алгоритмов GALib.

4.4 Библиотека параллельного программирования PPL.

4.5 Описание комплекса программных продуктов.

4.6 Экспериментальные исследования с помощью комплекса программных продуктов.

4.7 Выводы.

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

Автоматизация проектирования в электронике (electronic design automation) насчитывает около 50 лет. Микроэлектроника развивалась поэтапно, от малых и средних схем до сверхбольших (СБИС), а также ультра больших (УБИС) интегральных схем [1], [2]. Первые интегральные схемы выполняли какую-либо простую логическую функцию. Сейчас ИС способны выполнять комбинации сложнейших функций. В настоящее время идет работа по технологическому процессу 22 нанометра, в то время как по технологическому процессу 32нм уже налажено серийное производство ИС. Современная технология позволяет разместить более 15-ти миллионов транзисторов на схеме размером 25мм. х 25мм. В мае 2011го года фирмой Altera была выпущена самая большая в мире микросхема, содержащая 3.9млрд. транзисторов, при этом использовался технологический процесс 28нм. Кроме того, в последнее время активно развивается направление по разработке схем с трехмерной интеграцией (3D-integration). При таком подходе схема имеет несколько логических слоев, расположенных один над другим. Такой подход позволяет построить на одной схеме целое устройство с различными функциональными блоками, расположенными на различных уровнях. Кроме того, значительно снижается длина максимального соединения на схеме, а также общая длина межсоединений. Быстрая эволюция в производстве ИС тесно связана с использованием автоматизации различных этапов проектирования. Сейчас, на всех стадиях проектирования топологии сверхбольших ИС (СБИС) интенсивно используют средства автоматизации проектирования, и многие фазы могут быть полностью или частично автоматизированы [1], [3], [4].

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

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

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

На следующем этапе осуществляется описание проекта с помощью одного из языков описания аппаратного обеспечения (hardware description language, HDL) на уровне регистровых передач (register transfer level, RTL). Чаще всего используются такие языки описания как VHDL и Verilog. Данный этап называется этапом логического проектирования. В полученном описании отражены булевы функции и временные задержки, определяется размер слов, арифметические и логические операции и т.д. Данное описание моделируется и верифицируется в соответствии с исходной спецификацией. Часто используется модель на языке высокого уровня, например, языке С.

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

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

На последних этапах производится тестирование и контроль полученных схем, осуществляется сборка, помещение в защитный корпус и маркировка [5], [6], [7], [8].

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

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

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

60% общей временной задержки приходится на задержки в межсоединениях.

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

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

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

Глобальная трассировка является важнейшим этапом, поскольку от ее результата зависит дальнейшее распределение соединений на кристалле, загруженность отдельных областей, общая длина и другие параметры, напрямую влияющие на качество конечного продукта. Однако двухэтапный подход не всегда позволяет достигать положительных результатов при современной степени интеграции. В связи с этим был предложен многоуровневый иерархический подход. При этом вся область трассировки делится на подобласти. В каждой из подобластей выполняется глобальная, а затем и детальная трассировка, после чего производится объединение смежных областей в одну (способ снизу вверх) или разбиение области на более мелкие (способ сверху вниз). Чаще, однако, используется смешанный подход. Сначала выполняется стадия укрупнения (ячейки объединяются в более крупные при переходе на следующий уровень), а затем стадия детализации (обратный процесс). На каждом уровне трассируются только соединения, лежащие внутри каждой из подобластей. Соединения, которые 9 не удалось протрассировать на стадии укрупнения, откладываются до стадии детализации [8], [9], [11].

Сложность задачи трассировки ведет к постоянному поиску новых методов и подходов к ее решению. Перспективным для исследований является научное направление с названием «Природные вычисления» (Natural Computing), объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. К таким методам можно отнести, прежде всего, методы моделирования отжига, методы эволюционного моделирования, генетические алгоритмы, методы эволюционной адаптации, алгоритмы роевого интеллекта, а также муравьиные (Ant Colony Optimization - ACO) и пчелиные (Bee Colony Optimization - ВСО) алгоритмы [12], [13].

В основе муравьиных алгоритмов лежит имитация самоорганизации муравьиной колонии. Каждый отдельный агент действует по очень простым правилам, в то время как вся многоагентная система способна решать сложные задачи. Эффективность муравьиных алгоритмов сравнима с эффективностью общих метаэвристических методов, а в ряде случаев - и с проблемно-ориентированными методами. Наилучшие результаты муравьиные алгоритмы показывают для задач с большими размерностями областей поиска. Муравьиные алгоритмы хорошо подходят для применения вместе с процедурами локального поиска, позволяя быстро находить начальные точки для них. Первой задачей, успешно решенной с помощью муравьиного алгоритма, была задача коммивояжера. Как показывают опыты, применение муравьиного алгоритма также приводит к положительным результатам при решении задач на различных этапах конструкторского проектирования, в частности, задачи трассировки, позволяя улучшать качество решений. Наиболее перспективными направлениями дальнейших исследований муравьиных алгоритмов следует считать анализ способа выбора настраиваемых параметров, а также модифицирование структуры поиска в зависимости от конкретной задачи [13], [14].

10

Еще один класс алгоритмов, приводящих к улучшению качества получаемых решений для задач трассировки - это генетические алгоритмы (ГА). ГА это эвристические алгоритмы поиска, используемые для решения задач оптимизации. Они являются разновидностью эволюционных вычислений, моделирующей методы естественной эволюции, такие как наследование, мутацию, кроссинговер. ГА основаны на селекции лучших особей из полученной популяции решений. ГА широко применяются для решения задач в самых различных областях, в том числе для решения задач конструкторского проектирования СБИС [17-29]. ГА имеют следующие отличия от других оптимизационных и поисковых процедур: осуществляют поиск из множества точек, а не из единственной точки; используют целевую функцию, а не ее различные приращения; для оценки информации используют не детерминированные, а вероятностные правила; дают не одно решение, а целый спектр решений. Гибкость структуры генетических алгоритмов, возможность её настройки и перенастройки дают возможность получения структур, обеспечивающих получение высокого результата [14].

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

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

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

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

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

1. Разработка общей парадигмы решения задачи многослойной глобальной трассировки СБИС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в: Грант РФФИ № 12384 (№ 11 - 01 - 00122) «Разработка теории и принципов построения интеллектуальных гибридных нечетких генетических, эволюционных и адаптивных методов принятия решений при проектировании и оптимизации», Грант РФФИ (№ 12 - 01 - 00100) «Разработка теории и принципов коллективного интеллекта на основе моделей адаптивного поведения муравьиной колонии для решения оптимизационных задач», фундаментальные НИР № 37.04.54 «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений» и № 37.04.53 «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе методов и моделей адаптивного поведения биологических систем».

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

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2009», Томск, 12-15 мая 2009 года, Конгрессах по интеллектуальным вычислениями и информационным технологиям AIS-IT'09 Дивноморское 2-10 Сентября 2009 года, IS-IT'10 Дивноморское 2-10 Сентября 2010 года, IS-IT'll Дивноморское 2-10 Сентября 2011 года, IS-IT'12 Дивноморское 2-10 Сентября 2012 года, VII Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАиУ-09 Таганрог 9-10 декабря 2009 года, VIII Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАиУ-10 Таганрог 9-10 декабря 2010 года, IX Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАиУ-11 Таганрог 9-10 декабря 2011 года, Всероссийской школе-семинаре аспирантов, студентов и молодых ученых ИМАП-2011 Ульяновск 25-26 октября 2011 года.

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

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

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

4.7 Выводы.

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

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

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

Проведено сравнение разработанного метода с аналогами на известных бенчмарках, использовавшихся на симпозиуме "International Symposium on Physical Design (ISPD'07)", таких как adapted - adaptec4, newbl - newbB. Результаты сравнения показали, что предложенный метод позволяет уменьшить потребление ресурсов для прокладки соединений в среднем на 811%, а также сократить число межслойных переходов в среднем на 9-13%.

Заключение

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

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

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

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

4. Разработан муравьиный алгоритм решения задачи глобальной трассировки для соединений сложной формы, особенностями которого

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

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

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

7. На основе предложенных алгоритмов разработан комплекс программ для решения задачи глобальной многослойной трассировки. Комплекс программ реализован с использованием среды разработки Visual Studio 2010 для семейства ОС Windows. Проведенные исследования с использованием данного комплекса показали эффективность предложенного метода. Улучшение качества решений на известных бенчмарках составляет 10%, тогда как время поиска сокращается в среднем на 8-10%, в отдельных случаях до 15%. Вычислительная сложность муравьиных алгоритмов на одной итерации не превышает 0(п ), генетического - О(п).

Список литературы диссертационного исследования кандидат технических наук Воронин, Егор Ильич, 2012 год

1. Vasilis F. Pavlidis, Eby G. Friedman. Three-Dimensional integrated circuit design. Burlington : Elsevier, 2009.

2. Sadiq M Sait, Habib Youssef. VLSI Physical design automation. Theory and Practice. Singapore : World Scientific Publishing, 1999.

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

4. Yuan Xie, Jason Cong, Sachin Sapatnekar. Three-Dimensional integrated circuit design. EDA, Design and Microarchitectures. New York : Springer, 2010.

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

6. Layout decomposition for double patterning lithography. Andrew B. Kahng.6.м. : ICCAD, 2008.

7. C. Spanos, G. May. Fundamentals of Semiconductor Manufacturing and Process Control. 2008 r.

8. Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting Cheng. Electronic Design Automation: Synthesis, Verification and Test. Burlington : Morgan Kaufmann Publishers is an imprint of Elsevier, 2009.

9. D. Mehta S. Sapatnekar C. Alpert. Handbook of Algorithms for Physical Design Automation. New York : CRC Press, 2009.

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

11. Huang-Yu Chen, Yao-Wen Chang. Routing for Manufacturability and Reliability. IEEE Circuits and Systems Magazine. September 2009 г., 09, с. 20-31.

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

13. Дж. МакКоннелл. Основы современных алгоритмов. Москва: Техносфера, 2004.

14. Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации. Москва : Физмалит, 2009.

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

16. Neil H.E. Weste, David Harris. CMOS VLSI Design. A Circuits and Systems Perspective. Boston : Pearson Education, 2005.

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

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

19. Воронин Е.И. Таганрог: Изд-во Технологического института Южного федерального университета, 2011, с 35-37.

20. А.А. Лежебоков, А.Н. Дуккардт. Проблемы учета временных задержек в задачах конструкторского проектирования. Известия ЮФУ. Технические науки. №7, 2011 г., с. 108-113.

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

22. Лебедев Б.К., Лебедев В.Б. Глобальная трассировка на основе роевого интеллекта. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». №7, 2010 г., с. 32-39.

23. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». №7, 2011 г., с. 37-44.

24. Лебедев О.Б. Глобальная трассировка на основе муравьиного алгоритма. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». №7, 2011 г., с. 94-102.

25. Logan Rakai, Laleh Behjat. A Multilevel Congestion-Based Global Router. ACM Transactions on Design Automation of Electronic Systems. September 2009 г., pp 245-251

26. Fast Route 2.0: A High-quality and Efficient Global Router, ASP-DAC '07 Proceedings of the 2007 Asia and South Pacific Design Automation Conference. Min Pan, Chris Chu. Washington : б.н., 2007. pp. 250 255.

27. FastRoute 3.0: A fast and high quality global router based on virtual capacity, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design. Yue Xu, Yanheng Zhang, Chris Chu. NJ : IEEE Press Piscataway, 2008. pp. 344-349.

28. Tsung-Hsien Lee, Ting-Chi Wang. Congestion-Constrained Layer Assignment for Via Minimization in Global Routing. IEEE transactions on computer-aided design of integrated circuits and systems. September 2008 г., pp 151-157

29. Курейчик B.M., Кныш Д.С. Параллельные генетические алгоритмы: обзор и состояние проблемы. Известия РАН. №4, 2010 г., с. 1-25.

30. BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability, ACM Transactions on Design Automation of Electronic Systems. Minsik Cho, Katrina Lu, Kun Yuan, David Z. Pan. 2009.

31. FastRoute 4.0: Global Router with Efficient Via Minimization, IEEE transactions on computer-aided design of integrated circuits and systems. Yue Xu, Yanheng Zhang, Chris Chu. 2009.

32. Wire Density Driven Global Routing for CMP Variation and Timing, in IEEE International Conference on Computer-Aided Design. Pan D Z, Xiang H Cho Minsik. San Jose : б.н., 2006. с. 487-492.

33. A parallel integer programming approach to global routing, Proceedings of the 47th Design Automation Conference. Wu, Tai-Hsuan. Anaheim : ACM/IEEE, 2010. pp. 194-199.

34. Fast Route: A step to integrate global routing into placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design. Min Pan, Chris Chu. New York : ACM New York, 2006. стр. 464 471.

35. MR: A new framework for multilevel full-chip routing, IEEE Trans, on Computer-Aided Design. Lin, Y.-W. Chang and S.-P. 2004. pp. 793-800.

36. High-Performance routing at the nanometer scale, IEEE Trans. Comput.-Aided Design Integr. Syst. Roy J.A. 2008.

37. High-Performance routing at the nanometer scale, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design. Roy J.A., Igor L. Markov. NJ : IEEE Press Piscataway, 2007. pp. 496-502.

38. J. Cong, J. Fang, M. Xie, and Y. Zhang. MARS—A multilevel full-chip gridless routing system. IEEE Trans. Comput.-Aided Design Integr. Syst. March 2005 г., pp. 382-394.

39. Tai-Chen Chen, Yao-Wen Chang. Multilevel Full-Chip Gridless Routing With Applications to Optical-Proximity Correction. IEEE Trans. Comput.-Aided Design Integr. Syst. June 2007 г., pp. 1041-1053.

40. Воронин Е.И., Лебедев Б.К. Многоуровневый подход к решению задачи трассировки по всему чипу с использованием модификаций муравьиного алгоритма. Известия ЮФУ. Технические науки. 7, 2011 г., с. 73-80.

41. Курейчик В.М., Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». №7, 2011 г., с. 30-36.

42. Б.К. Лебедев, О.Б. Лебедев. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями. Известия ЮФУ. Технические науки. №7, 2012 г., с. 27 35.

43. Гибридный алгоритм разбиения на основе муравьиной колонии // Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT'09". Лебедев Б.К., Воронин Е.И. Москва : Изд-во Физматлит, 2009. Т. III, с. 213-214.

44. Лебедев О.Б. Планирование СБИС на основе метода муравьиной колонии. Известия ЮФУ. Технические науки. №3, 2010 г., стр. 67-73.46. —. Трассировка в канале методом муравьиной колонии. Известия ЮФУ. Технические науки. №4, 2009 г., с. 46-52.

45. Лебедев О.Б., Зорин В.Ю. Упаковка на основе метода муравьиной колонии. Известия ЮФУ. Технические науки. №12, 2010 г., с. 25-30.

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

47. Bohringer, K. F. Modeling and controlling parallel tasks in dropletbased microfluidic systems. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. №2, 2006 г., pp. 334-344.

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

49. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. б.м. : Госиздат, 2004. с. 7-12.

50. Б.К. Лебедев, Е.И. Воронин. Генетический алгоритм распределения соединений по слоям при многослойной глобальной трассировке СБИС. Известия ЮФУ. Технические науки. №7, 2012 г., с. 14-22.

51. BoxRouter: A new global router based on Box Expansion and Progressive ILP, Proceedings of the 43rd annual Design Automation Conference. Minsik Cho, David Z. Pan. New York : б.н., 2006. pp. 373-378.

52. Поляков A.K. Языки VHDL и Verilog в проектировании цифровой аппаратуры. Москва : СОЛОН-Пресс, 2003.

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

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

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

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

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

58. 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. S.S. Sapatnekar, C.L. Yang, Y.W. Chang, P.H. Yuh. 2008. c. 284-289.

59. Novel Full-Chip Gridless Routing Considering Double-Via Insertion , in DAC. Huang-Yu Chen. 2006.

60. Муравьиный алгоритм глобальной трассировки при многоуровневом подходе //Труды Конгресса по интеллектуальным системам и информационным технологиям "IS-IT'll". Воронин Е.И., Лебедев Б.К. Москва : Физматлит, 2011. с. 147-148.

61. Levin М. Sh. Combinatorial optimization in system configuration design. Automation and Remote Control. №3, 2009 г., с. 519-561.

62. Литвиненко В.А., Ховансков С.А., Норкин О.Р. Оптимизации мультиагентной системы распределенных вычислений. Известия ЮФУ.

63. Технические науки. Тематический выпуск «Интеллектуальные САПР». №4, 2009 г., с. 226-235.

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

65. Нему дров В.Г. Основные проблемы, задачи и этапы формирования современной инфраструктуры проектирования СБИС "система на кристалле". №3, 2003 г.

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

67. Y. W. Chang, S. J. Chen, and D. T. Lee. Crosstalk- and performance-driven multilevel full-chip routing. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 2005 г., pp. 869-878.

68. Лебедев Б.К., Лебедев О.Б., Курейчик В.М. Решение задачи покрытия на основе эволюционного моделирования. Известия РАН. 2009 г., с. 119-134.