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

На правах рукописи

Кныш Данил Сергеевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ГИБРИДНЫХ

ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ТРАССИРОВКИ КОММУТАЦИОННЫХ БЛОКОВ

05.13.12 - системы автоматизации проектирования (вычислительная техника и информатика)

АВТОРЕФЕРАТ 4852332

диссертации на соискание ученой степени кандидата технических наук

2 5 ДВГ 2011

Таганрог - 2011

4852332

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

Научный руководитель: доктор технических наук, профессор

Курейчик Виктор Михайлович

Официальные оппоненты: доктор технических наук, профессор

Витиска Николай Иванович (ГОУ ВПО ТГПИ г. Таганрог)

доктор технических наук, профессор Карелин Владимир Петрович (ТИУиЭ г. Таганрог)

Ведущая организация: Таганрогский научно-исследовательский

институт связи, г. Таганрог.

Защита состоится на заседании диссертационного совета Д 212.208.22 при Южном федеральном университетепо адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Ученый секретарь диссертационного совета Д 212.208.22,доктор технических наук, профессор

Целых А.Н.

АКТУАЛЬНОСТЬ РАБОТЫ

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

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

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

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

нечеткие множества применяются и для распараллеливания генетических алгоритмов.

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

ЦЕЛЬ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

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

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

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

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

ПОЛОЖЕНИЯ ВЫНОСИМЫЕ НА ЗАЩИТУ

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

2. Принципы формирования начальной популяции (альтернативных решений топологий коммутационного блока). Для генерации разнообразных альтернативных топологий коммутационного блока с учетом технологических ограничений.

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

4. Новая модель параллельного генетического алгоритма и оператор миграции на основе нечетких множеств. Которая позволяет максимально эффективно использовать многоядерные процессоры для выполнения задачи трассировки.

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ

На основе разработанных методов и алгоритмов создан программно-алгоритмический комплекс для решения трассировки коммутационных блоков с цепями различной ширины. При построении программного комплекса использовался объектно-ориентированный язык С++ и среда разработки Borland С++ 6.0. Отладка и тестирование проводилось на ЭВМ типа IBM PC, с процессором Intel ¡3 , 2.2 ГГц, ОЗУ 3ГБ. Отличительная особенность разработанного программного комплекса - это эффективное использование многоядерной вычислительной системы, что позволило сократить время решения трассировки коммутационных блоков на 30%.

ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

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

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

МЕТОДЫ ИССЛЕДОВАНИЯ

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

АПРОБАЦИЯ РАБОТЫ

Основные результаты, полученные в ходе работы, докладывались и обсуждались на:

1. IV Всероссийской научно-технической конференции «Проблемы разработки перспективных микро- и наноэлектронных систем - 2010».

2. 11-ой Национальной конференции по Искусственному интеллекту с международным участием, КИИ-2008. Дубна. 29 сентября - 3 Октября 2008 года.

3. Конгресс по интеллектуальным вычислениями и информационным технологиям AIS-IT'09 Дивноморское 2-10 Сентября 2009 года.

4. XV Международная конференция по нейрокибернетике Ростов-на-Дону 23-25 сентября 2009 года.

5. Вторая всероссийская научная конференция с международным участием «Нечеткие системы и мягкие вычисления». Ульяновск, УлГТУ, 2008.

ПУБЛИКАЦИИ

Основные положения и результаты диссертационной работы опубликованы в 22 источниках, включающих 7 статей, 13 материалов конференций и семинаров, 2 свидетельства о регистрации программ. Четыре работы из них опубликованы в рецензируемом журнале из списка ВАК.

ОБЪЕМ И СТРУКТУРА ДИССЕРТАЦИИ

Диссертация состоит из введения, списка рисунков, 4 глав, заключения, списка литературы, включающего 102 наименования и 6 приложений. Основной текст диссертации изложен на 170 страницах, включая 63 рисунок и 8 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

В параграфе 1.3 приводится обоснование актуальности задачи в соответствии с новыми проблемами производства СБИС нанометрового диапазона. Под воздействием перекрестных помех задержка сигнала в шине может измениться более чем вдвое. С уменьшением размеров транзисторов уменьшается и число зерен поликремния в одном затворе (менее 10).

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

трассировку (прокладка соединений внутри областей).

Для оценки качества результатов трассировки в алгоритме используются четыре критерия оптимизации:

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

F1 = Е С,-. (3)

В формуле (3) F1 определяет суммарную паразитную емкость проводников

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

пересекающихся проводников, расположенных на противоположных слоях, и рассчитывается по формуле (4), an- кол-во таких пар,

С = 0,0085 (4)

где er - диэлектрическая постоянная, А - площадь перекрытия, ¿-расстояние

между слоями.

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

NumVia

F2= I Via: . (5)

/=1 '

В формуле (5) значение функции F2 определяет количество межслойных переходов. Via; - обозначает i-межслойный переход, i=[l,NumVia].

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

NumNet ...

F3 = I LenghtNetj (°)

¿=1

F3 - сумма длин проводников всех цепей в коммутационном блоке.Ьеп§М№1| -длина проводников цепи i, где i меняется в периоде от 1 до количества цепей NumNet.

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

Сопротивлениепроводникабезучетатехнологическихфакторовможнорассчитатьк

ак:

Ri=p-d7

(7)

где р - удельное сопротивление, а /,□> - длина и ширина проводника соответственно. Тогда суммарное сопротивление всех цепей коммутационного

блока можно рассчитать по формуле: ЫитЫе1

Г*= (8) Оптимизационная задача трассировки коммутационного блока описана следующим кортежем: <Х, Б, 0>. Где X — является множеством всех решений (хромосом) для данной задачи, О — ограничения, накладываемые на множество X, для получения допустимых решений и 0 - целевая функция, с помощью которой можно определить наилучшее (оптимальное) решение.

X - множество всех хромосом из всех популяций. Пусть Рш - некоторая популяция на шаге т, Р1={Ьь Ь2 ... ¿1}, где Ь) - хромосома из этой популяции, т=[1,М]; 1=[1,Ь] (М -число популяций, Ь -число хромосом в популяции) Тогда множество всех решений можно определить по формуле 2.1.

X = {Pm-,m = \,2,-,NumPop} = {hlm\l = \,2,:.,L-,m = \,2,...,M}. (9)

Множество допустимых решений ^Допустимыми решениями для данной задачи будем называть те, в которых соблюдены следующие условия:

• нет пересечений цепей на совместном слое;

• нет наложений участков топологии различных цепей;

• соблюден заданный интервал между цепями;

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

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

В параграфе 1.5 Произведен сравнительный анализ существующих алгоритмов решения задач трассировки коммутационного блока. Отмечены перспективные для исследований методы и алгоритмы, а также их достоинства и недостатки. Проведен анализ алгоритмов трассировки коммутационного блока таких как: жадный трассировщик (Greedy), геометрический трассировщик (Beaver), алгоритм основанный на разрыве и перетрассировке и алгоритм поэтапной перетрассировки (Packer). Выявлены недостатки этих алгоритмов - эти трассировщики не могут учитывать физические критерии топологии коммутационного блока (межслойную емкость, сопротивление проводников) и не могут изменять ширину проводников.

Во второй главе приводится описание решения задачи трассировки коммутационного блока

В параграфах 2.1 и 2.2 приводится описание методов многокритериальной оптимизации применительно к задаче трассировки. Приводится описание основных задач и проблем решаемых при проектировании генетического алгоритма решения задачи трассировки.

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

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

функции. Целевая функция Q - вычисляется в зависимости от суммарной

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

Q = kl*Fl+k2*F2+k3*F3+k4*F4, (10)

где krk4 — коэффициенты локальных критериев, с их помощью можно регулировать влияние того или иного критерия на качество решения, в сумме они должны быть равны единице. F/ - суммарная межслойная емкость рассчитывается по формуле, F2 -количество межслойных переходов рассчитывается по формуле, F3 — суммарная длины проводников в коммутационном блоке, и F4 - суммарное сопротивление проводников. Критерии нормализуются по верхней границе. Для учета взаимной компенсации критериев применяется ограничение на минимально допустимое значение каждого критерия. Оптимизация задачи сводится к минимизации функции Q, т.е. Q(X)—>min Q(h

ОПТ )=minQ(hij), где fycS.

В параграфе 2.5 приводится структурная схема гибридного генетического алгоритма (рис. 1) с описанием основных этапов работы.

В параграфе 2.6 приводится методика кодирования и декодирования хромосомы. Каждый ген представляет собой набор участков трасс отдельной цепи. Количество генов равно количеству цепей коммутационного блока. Участком трассы может быть горизонтальный проводник, вертикальный проводник и межслойный переход. Количество участков зависит от количества терминалов цепи, количества слоев, общего количества цепей в коммутационном блоке и размеров коммутационного блока. Участок может быть трех типов горизонтальный — Н, вертикальный - V и межслойный переход - VIA. Участок трассы задается с помощью координат узлов сетки коммутационного блока которые он соединяет. Хромосома имеет матричную структуру:

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

X1 1 H

х' 2 '2

х' П: А 4,-

NumNets

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

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

1. для каждой цепи формируется список занимаемых ею терминалов Tj ={tl,t2,...,tj);

2. для каждой цепи формируется список промежуточных дополнительных узлов У/ = {У\> У2 '■••> У j ) ' К0Т0Рые являются точками пересечения продолжений

координат х и у терминалов;

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

4. выбирается случайным образом цепь;

5. выбираем из множества дополнительных узлов г, наименее удаленный от всех терминалов узел у •, заносим этот узел в список основных узлов гх„ ;

6. случайным образом выбирается терминал / ■ из множества п , и соединяем его с узлом у j прямым или L-образным участком цепи;

7. исключаем терминал из списка не рассмотренных терминалов 7) = Г(- \ t у ;

8. случайным образом выбирается терминал «', формируем временный список опорных узлов Увр (точки пересечения продолжений координат х,у терминала с

уже существующими трассами) и добавляем в него узлы из Уосн ;

9. выбираем из Yep ближайший узел у^ и соединяем его с терминалом прямым

или L-образным участком цепи, добавляем новые опорные узлы в Y0CH ;

10. если рассмотрены все терминалы, переходим к п. 10, в противном случае к п. 7;

11. если рассмотрены все цепи то переходим к п. 11, в противном случае к п. 3;

12. КРА;

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

равна 0(п2).

В параграфе 2.8 рассматриваются модифицированные генетические операторы. Рассмотрим подробнее оператор кроссинговера, предложенный в работе. Два родителя, необходимых для оператора кроссинговера, выбираются независимо друг от друга, кроме того, каждая хромосома может участвовать в нем любое число раз в одной генерации. Пусть Р, и ?2 - копии родителей (рис. 2); Р3 - полученный в результате применения ОК потомок (рис. 3). Сначала произвольно выбирается точки кроссинговера (ТК) - точки разрыва родительских хромосом, или другими словами количество цепей для обмена хс: 1 <х<.<хы, где Х|п(^— число цепей коммутационного блока. Затем в Р3 наследуется из хромосомы Р]выбранные на предыдущем этапе цепи и из Р2 все остальные цепи.

Рассмотрим оператор мутации, используемый в разработанном алгоритме. В его основе лежит принцип удаления трассировочной структуры цепей и замена их структурой полученной на основе алгоритма генерации начального решения с последующим размещением цепей по слоям. В результате селекции выбирается хромосома-родтиель (рис. 4). Как и в операторе кроссинговера первоначально определяются удаляемые цепи их количество так же лежит в пределе 1 <хс<х|п(Ь где х1п(Г- число цепей коммутационного блока.

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

Рис. 2. Родительские

гт А

1 И: 1II

С 1Ш1

г II 11 II !1 ' •

Рис. 4 Родительская хромосома

Рис. 3. Результат работы оператора кроссинговера

-н

ри

ш щ

-4- м ■

Рис. 5. Результат работы оператора мутации

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

Если рассмотреть пример коммутационного блока, в котором число цепей равно 4,

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

^(0= (а,*1с + а2*ус + а3*сс), (12)

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

После подсчета ЦФ для цепей каждого родителя формируется упорядоченный список ЦФ. Для нашего примера он отображен в таблице 1.

Табл. 1. Примерный список ЦФ хромосом участвующих в операторе сегрегации

^(0 ИаО) Ив (3) РвО) Ра (1) Ра (4) Рв(2) Рв(4) Ра (2)

Значение ЦФ 5,0833 3,0714 6,0625 5,0588 3,0588 4,0555 2,0555 5,0526

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

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

Параграф 2.9 посвящен методом параллельных вычислений в генетических алгоритмах. Приводится известные модели параллельных генетических алгоритмов.

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

В параграфе 2.11 приводится описание новой модели параллельного генетического алгоритма. В алгоритме используется модифицированная модель на основе модели «островов». Модель не имеет жестко заданных связей между популяциями. Оператор миграции работает через так называемый буфер хромосом. Использование буфера позволяет упростить синхронизацию работы популяций и делает возможной их асинхронную работу. Модифицированная модель схематически изображена. Процесс взаимодействия популяции с буфером можно описать следующим образом: формируется начальная популяция. Начинается эволюция популяции в асинхронном режиме; по наступлению необходимости миграции, популяция обменивается хромосомами с буфером. При таком подходе следует определить механизм регулирования размера буфера на основе оператора отбора.

Для оценки эффективности предложенной модели использовалась фундаментальная теорема ГА. Пусть в результате миграции популяция к получила С хромосом, и число хромосом в популяции стало Р+С. В этом случае вероятность, что хромосома I перейдет в другую популяцию во время следующего оператора миграции, равна 1 — (вероятность того, что она никогда не покинет исходную популяцию), т.е.

11 1 Р С

1 - [0 - т^Х1 - ~ р+с-{с-1))] = 1 ~ Т+с = ~р+с ■

Соответственно вероятность, что хромосома останется в популяции, равна . Таким образом, число представителей схемы Н равно

«<я,* + 1)= Г £ Е

Ь=1,=1,/еЯ Р+С 4 Ц

к=\^НР+СГк 1еСк Р+С Л

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

т(Н, г + 1) > т(Я, 0 • Ш1 ■ ^¡р- ■ [1 -Р(ОКуШ&-ЦНуР(ОМ)\

где Р(М) - вероятность миграции, а К - число связанных островов. В нашем случае миграция через каждые пять итераций имеет вероятность наступления события 0.2.

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

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

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

• На вход модуля поступает параметр либо множество параметров

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

• На основе базы правил рассчитывается нечеткий критерий или множество нчетких критериев

• Нечеткий критерий или множество нечетких критериев преобразуются к четкому виду

• На выходе получаем сигнал или управляющее воздействие.

Параграф 3.4 содержит описание алгоритма расчета нечеткой функции качества топологии коммутационного блока. Первоначально надо определить следующие составляющие: одно или набор правил; определить правила предпочтения критериев; определить функции принадлежности для каждого критерия.

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

В параграфе 3.5 приводится описание модифицированного оператора кроссинговера, в котором используются нечеткие оценки топологии коммутационного блока. Основная проблема оператора кроссинговера состоит в том, что точки кроссинговера выбираются случайным образом. Для решения этой проблемы предлагается использовать нечеткую оценку топологии каждой цепи, поскольку каждый ген в хромосоме представляет собой топологию цепи. Рассмотрим пример. Пусть имеются две родительские хромосомы с векторами оценок (рис. 6). Пусть пороговый коэффициент равен 0,75, в таком случае имеем одну точку кроссинговера. И в результате выполнения, которого хромосома потомок унаследует цепи № 1,2,3 из первой родительской хромосомы и цепи 4,5 из второй родительской хромосомы.

pi рШ1|5^[57ё1ЕШ1Г0в2| pz [0Ж1[02э1 рдо] ЩхПЕоЖ!

Пороговый ксоффиииеит 0,75 Р1 fÖÜ4[[ä45] (ä78ll[Ö32lfÖ82l

Р2 Га45~1 |сШ1 [Го5Г|1[5Ж| 10.56 [

I

Точкэ кроссинговера

Рис. б.Пример работы нечеткого оператора кроссинговера

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

Для разработки оператора селекции с направленным выбором предлагается использовать нечеткие оценки топологии цепей коммутационного блока. Алгоритм работы нечеткого оператора селекции направленного для оператора кроссинговера следующий:

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

2. Установление начального значения порогового коэффициента (начальное значение равно 0.75);

3. Определение точек предполагаемого кроссинговера в соответствии с пороговым коэффициентом для всех хромосом в популяции;

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

5. Если выбрана точка кроссинговера то переход к пункту 6, в противном случае уменьшение порогового коэффициента и переход к пункту 3;

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

7. Выбор хромосом имеющих минимальное значение нечеткой оценки определенное на предыдущем шаге;

8. КРА.

Для оператора мутации направленная селекция определяет самую «плохую» (имеющую наибольшую нечеткую оценку топологии) цепь коммутационного блока из всех хромосом. И таким образом для оператора мутации выбирается та хромосома, которая ее содержит.

В параграфе 3.7 рассматривается методы использования нечетких множеств для распараллеливания генетических алгоритмов. Для нечеткого оператора миграции вводится нечеткое понятие «степень разнообразия популяции» представляемое нечетким множеством М={низкая степень, высокая степень}. Далее формируется база правил, например «если степень разнообразия низкая, то необходима миграция с 3 островами». На каждой итерации рассчитывается значение разнообразия, которое поступает в нечеткий логический контроллер. На выходе, которого управляющее воздействие, выполнять миграцию и если да то с каким числом популяций. Преимущество метода заключается в возможности учета различных параметров популяции (кроме степени разнообразия). Отличие от других методов в том, что это не адаптация параметров работы алгоритма, как это наиболее часто встречается в литературе, а реальная оценка эволюции в популяции. Степень разнообразия в популяции определяется как генотипическое расстояние между всеми хромосомами. Если популяция стремится к вырождению (низкая степень разнообразия) то для предотвращения вырождения нужен оператор миграции. Степень разнообразия будем рассчитывать по формуле:

М " I М /,1 = ^ /=1+1/=1' 1 ¿=1 N

(13)

где N - количество хромосом в популяции в ЦФ, п - число генов в хромосоме, х'I — х} I - разница значения генов двух хромосом. Если хромосомы в популяции отличаются друг от друга, значит степень разнообразия в популяции достаточная для дальнейшей оптимизации. Кроме степени разнообразия в популяции надо учитывать уровень развития популяции, другими словами отличие ЦФ в популяции от лучшего значения среди всех популяций. Обозначим этот критерий миграции как уровень развития, и будем рассчитывать по формуле:

_ mM(fxJ2,-JN)

dev max(Fj,F2,—'

где fN - это ЦФ хромосомы в популяции, a FK - лучшее значение ЦФ среди всех популяций. Уровень развития представим нечетким множеством {низкий уровень развития, высокий уровень развития}.

В параграфе 3.8 приводятся теоретические оценки временной сложности алгоритма расчета нечеткой фукнции качества топологии коммутационного блока, которая составляет 0(4п) где п это количество цепей в коммутационном блоке, 4 - количество критериев топологии коммутационного блока.

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

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

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

Параграфы 4.3 и 4.4 содержат описание этапов исследования и их результатов. Результат работы алгоритма генерации начальной популяции. Формирование начальной популяции производится разработанным алгоритмом генерации начальной популяции. Для анализа качества решений создаваемых данным алгоритмов они сравнивались с результатами работы генетического алгоритма на 30 итерации. В среднем решения, полученные на начальной итерации, довольно разнообразны. Но качество решений на 1825% хуже, чем у генетического алгоритма. Время генерации коммутационного блока, с числом выводов равным 16, волновым алгоритмом равно 0,15 секунды. Анализируя затраченное время на генерацию решений, получим, что ВСА пропорционально 0(N2).

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

Для оценки было выполнено запуск алгоритма для стандартных коммутационных блоков (бенчмарки) difficulty и augmented_dense. Для анализа работы нечеткого оператора кроссинговера проводились сравнение работы генетического алгоритма с использованием n-точечного кроссинговера и с использованием нечеткого кроссинговера, использующей нечеткую ЦФ. Исследования проводились для коммутационных блоков с количеством выводов от 16 до 32. Для этого проводились серии из пяти опытов для каждого типа коммутационного блока для генетического алгоритма с нечетким оператором кроссинговера. В качестве окончательной оценки работы алгоритма используется ЦФ,

рассчитанная методом адъективной свертки.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

10%. ,

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ:

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

изданий ВАК РФ

1. D. S. Knysh, V. М. Kureichik Genetic Algorithm for Routing Switching Units.RussianMicroelectronics, 2011, Vol. 40, No. 7, pp. 49-53.

2. D. S. Knysh, V. M. KureichikParallel genetic algorithms: a survey and problem state of the art. Journal of computer and systems sciences international Volume 49, Number 4, 20010.-P. 579-589.

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

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

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

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

II Свидетельства о регистрации программ на ЭВМ

7. Кныш Д.С., Курейчик В.М. Программа нечеткого генетического алгоритма трассировки коммутационного блока, с цепями различной ширины (НГАТКБ). Свидетельство о государственной регистрации программы для ЭВМ №2009610459, 2009.

8. Кныш Д.С., Курейчик В.М. Программа трассировки каналов СБИС на основе

нечеткого генетического алгоритма (ТКоНГА). Свидетельство о государственной регистрации программы для ЭВМ №2010610938,2010.

III. Публикации в других изданиях

9. Knysh D.S. Fuzzy methods for genetic algorithm switch-box routing. CAD Systems in Microelectronics, 2009. CADSM 2009. 10th International Conference - The Experience of Designing and Application of Volume, Issue, 24-28 Feb. 2009 - P. 315 -321.

10. Кныш Д.С., Курейчик B.M. Комплексный алгоритм трассировки коммутационного блока. Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС)". Сборник трудов. 2010. № 1. С. 170-177.

11. Гладков JI.A., Криницкая А.Е., Кныш Д.С. Решение оптимизационных задач на основе нечетких генетических алгоритмов. «Интеллектуальные системы». Коллективная монография. Выпуск третий. - М.: Физматлит, 2009. - с. 86 - 99.

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

13. Кныш Д.С. «Мягкие» вычисления и генетические алгоритмы. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), т.2, 26-27 мая г.Коломна. Москва, Физматлит, 2009. С. - 141-150.

14. Кныш Д.С. Модель параллельного генетического алгоритма. Конгресс по интеллектуальным системам и информационным технологиям AIS-IT09. Труды конгресса. Т. 3 - М.:Физматли, 2009. - с. 132- 136.

15. Кныш Д.С., Курейчик В.М. Виды интеграции нечеткой логики в генетический алгоритм трассировки коммутационного блока. Конгресс по интеллектуальным системам и информационным технологиям AIS-IT09. Труды конгресса. Т. 3 -М.:Физматли, 2009. - с. 136 - 142.

16. Кныш Д.С. Использование нечеткой целевой функции для многокритериальных задач. 3-й Симпозиум по Нейроинформатике и Нейрокомпьютерам. Материалы XV Международной конференции по нейрокибернетике. Т. 2 - Ростов-на-Дону, ЮФУ, 2009-с. 81-83.

17. Кныш Д.С. Нечеткая целевая функция в генетических алгоритмах. Международная научно-техническая мультиконференция «Многопроцессорные вычислительные и управляющие системы (МВУС)». Материалы международной научно-технической конференции. Т. 2 - Таганрог, 2009 - с. 110-115.

18. Кныш Д.С., Курейчик В.М. Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока. Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008. Дубна: Труды конференции. Т. 1. -М.: ЛЕНАНД, 2008. - с. 179-191.

19. Кныш Д.С. Нечеткий метод селекции для задачи трассировки коммутационного блока. «Нечеткие системы и мягкие вычисления». Сборник научных трудов Второй всероссийской научной конференции с международным участием, т. 1. -Ульяновск: УлГТУ, 2008. - с. 150- 158.

20. Кныш Д.С. Селекция в нечетком генетическом алгоритме трассировки. IX

Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», т. 1, 23-24 октября, ТТИ ЮФУ, 2008.-С. 157.

21. Гладков Л.А., Кныш Д.С. Применение нечетких генетических алгоритмов для решения задачи канальной трассировки. Международные научно-технические конференции А18'07 и САО-2007. Труды конференций, т. 1. - М.: Физматлит, 2007.-с. 21-28.

22. Кныш Д.С. Алгоритм трассировки в коммутационном блоке. Перспективные информационные технологии и интеллектуальные системы №4(32), Таганрог, ТТИ ЮФУ, 2007. - С. 59-70.

Личный вклад автора в работах [4] и [21] состоит в анализе нечетких методов и разработка схемы нечеткого логического контролера для задачи канальной трассировки. В работах [1-3, 7-8, 10, 13, 16, 22] в анализе задачи трассировки коммутационных блоков, разработке нечетких генетических операторов, разработке алгоритма расчета нечеткой целевой функции, разработке новой модели параллельного генетического алгоритма. В работах [5-6] в разработке комплекса алгоритмов трассировки коммутационных блоков и трассировки канала, разработке программ комплекса алгоритмов. И в работе [18] в разработке нечеткого логического контроллера для задачи трассировки канала и разработке генетического алгоритма трассировки канала.

Тип.ТТИ ЮФУ Заказ №234 тир.ЮО экз.

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

Содержание

Глава 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%. Кроме того алгоритм учитывает такие критерии коммутационного блока как межслойная емкость и суммарное сопротивление проводников. Это позволяет сократить время этапа верификации и уменьшить число перетрассировок в цикле проектирования СБИС.

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.