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

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

Воронин Егор Ильич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ МНОГОСЛОЙНОЙ ГЛОБАЛЬНОЙ ТРАССИРОВКИ СБИС НА ОСНОВЕ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ ПРИРОДНЫХ СИСТЕМ

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

АВТОРЕФЕРАТ

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

-8 НОЯ 2012

Таганрог - 2012

005054645

Работа выполнена в Южном федеральном университете

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

Лебедев Борис Константинович

Официальные оппоненты: Чернышев Юрий Олегович

Заслуженный деятель науки РФ, доктор технических наук, профессор. ДГТУ, профессор кафедры Автоматизации Производственных Процессов

Витиска Николай Иванович доктор технических наук, профессор. ТГПИ имени А.П. Чехова, профессор кафедры Информатики

Ведущая организация: ОАО «Таганрогский

научно-исследовательский институт связи» (ТНИИС), г. Таганрог

Защита состоится /Г~ НАЯ-брЯ_2012г. в /£'¿¿7 на заседании

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

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

Автореферат разослан:

й

октября 2012 г.

Ученый секретарь

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

Целых А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

Технология производства интегральных схем насчитывает около пятидесяти лет. Все эти годы схемы усложнялись, при этом постоянно усложнялся и процесс их производства. В результате возникло целое направление - автоматизация проектирования в электронике (electronic design automation, EDA), занимающееся разработкой и исследованием систем автоматизированного проектирования (САПР). Современные САПР позволяют проектировать сложнейшие схемы, содержащие миллиарды элементов на кристалле. Создание подобных систем требует постоянной разработки новых алгоритмов, позволяющих в автоматическом режиме проводить различные стадии проектирования СБИС, в частности, стадию конструкторского проектирования. На стадии конструкторского проектирования реализуются конечные геометрические элементы, а также физические связи между ними на кристалле. В результате получается готовая топология схемы. Данная стадия состоит из нескольких этапов. Классический маршрут стадии конструкторского проектирования, как известно, включает разбиение, размещение и трассировку.

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

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

автоматическом режиме. Большое внимание задаче трассировки уделяется в работах Курейчика В.М., Курейчика В.В., Лебедева Б.К., Лебедева О.Б., Chris Chu, Minsik Cho, Tai-Chen Chen, Yao-Wen Chang и других российских и зарубежных ученых. Несмотря на множество работ, проводимых в этой области, в настоящее время практически не существует алгоритмов трассировки, удовлетворяющих всем современным требованиям.

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

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

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

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

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

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

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

работе, заключается в следующем:

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

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

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

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

Положения, выносимые на защиту

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

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

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

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

Практическая значимость работы

На основе разработанных методов и алгоритмов был реализован комплекс

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

5

трассировки СБИС. При создании данного комплекса использовались языки программирования С++ и С#, среда разработки Visual Studio версии 2008 и 2010. Отладка и тестирование проводились на ЭВМ типа IBM PC со следующей конфигурацией: процессор Intel Core i3, 2.2ГГц, ОЗУ 4Гб, система Windows 7. Результаты исследований показали, что разработанный комплекс программ позволяет получить решения, превосходящие в качестве известные аналоги на 10-12%. На части бенчмарок также сокращено время поиска на 8-15%.

Внедрение результатов работы

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

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

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

• Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУ СУР - 2009», Томск, 12-15 мая 2009 года.

• Конгресс по интеллектуальным вычислениям и информационным технологиям AIS-IT'09, IS-IT'10, IS-lT'll, IS-IT'12, Дивноморское, 2-10 сентября, 2009-2012 г.

• VII, VIII, IX Всероссийские научные конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», Таганрог, 9-10 декабря 2009-2011 г.

• Всероссийская школа-семинар аспирантов, студентов и молодых ученых ИМАП-2011, Ульяновск, 25-26 октября 2011 года.

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы, сформулированы цели работы, показана научная новизна, приведены сведения о практической значимости полученных результатов, дано общее описание выполненной работы, раскрыта структура диссертации.

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

В разделе 1.1 описываются современные технологии производства субмикронных СБИС, а также сферы их применения. Рассматриваются основные подходы, используемые в проектировании интегральных схем (заказные и полузаказные схемы), и, соответственно, их разновидности. Также приведен классический маршрут проектирования СБИС, рассмотрены этапы такого маршрута. Помимо классической методологии дано описание подхода, основанного на концепции абстракции проекта. Кроме того, в разделе 1.1 приведены основные принципы трехмерной интеграции. Трехмерная интеграция является одной из основных тенденций в производстве современных интегральных схем. При таком подходе весь чип разрезается на части, которые затем располагаются одна над другой. Описаны основные достоинства и недостатки данной методологии. Трехмерная или «вертикальная» интеграция (three-dimensional integration, 3D integration) — это способ увеличить производительность и расширить возможности современных интегральных схем. Основной ее плюс - это уменьшение длины межсоединений за счет снижения площади кристалла, кроме того, этот подход

7

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

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

В разделе 1.3 приводится постановка задачи многослойной глобальной трассировки СБИС. Цель глобальной трассировки состоит в распределении соединений по областям коммутационного поля без нарушения ограничений. В современных СБИС на каждом логическом уровне используется шесть и более слоев металлизации. То есть, соединения распределяются по областям и по слоям. Для решения задачи распределения соединений по областям на одном логическом уровне в качестве модели КП используется трехмерный граф Ск=(Хк,Цк). Число уровней графа соответствует числу слоев металлизации. Вершины графа х,еХ соответствуют областям а^Л. Если две области а, и о, имеют общую границу Ь:, то вершины х, и х, , соответствующие этим областям, связываются ребром и^Ц1. Множество ребер (/ состоит из двух

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

8

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

В разделе 1.4 рассматриваются два подхода к решению задачи многослойной трассировки СБИС.

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

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

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

возможных решений данной задачи (справа)

В разделе 1.5 приводится обзор современных алгоритмов глобальной трассировки СБИС. Существует множество алгоритмов для решения задачи глобальной трассировки. Каждый из алгоритмов имеет как достоинства, так и недостатки. Основным общим недостатком почти всех алгоритмов является их узкая направленность. То есть, данные алгоритмы предназначены либо для трассировки в 1-2 слоях (например, муравьиный алгоритм глобальной трассировки), либо для решения задачи распределения соединений по слоям (COLA). Еще одним недостатком является отсутствие гарантии стопроцентной трассируемости. Среди положительных особенностей названных алгоритмов стоит отметить: комбинирование роевого интеллекта и генетических процедур; граф поиска решений, разработанный с учетом специфики муравьиных алгоритмов; согласованный поиск с использованием оценочной функции и др

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

В разделе 2.1 приведен многоуровневый подход к решению задачи

трассировки на плоскости, описан принцип трассировки по всем кристаллу

(чипу). Общепринятым подходом при трассировке СБИС является разделение

задачи на два этапа: глобальную и детальную трассировку. Так как сложность

СБИС постоянно увеличивается, классический двухэтапный подход не может

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

подход. При таком подходе процесс трассировки проводится также в две

стадии: укрупнение или огрубление (coarsening, на этой стадии компоненты

схемы пошагово группируются) и детализация или разделение (uncoarsening,

обратный укрупнению процесс). Каждая стадия в свою очередь делится на

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

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

размера, которые называются глобальными ячейками уровня 0 (Global Cells -

GCso). Затем начинается стадия укрупнения. На нулевом уровне производится

трассировка только тех соединений, которые находятся внутри одной такой

ячейки, не выходя за ее границы. Соединения, которые не удается

распределить, фиксируются и откладываются до стадии детализации. При

10

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

Кроме того, в разделе дана постановка задачи глобальной трассировки на плоскости. Моделью коммутационного поля (КП) является граф С=(Х,Е). Каждая вершина графа х,6Х соответствует области а,ЁА на коммутационном поле. Если две области являются смежными, то есть имеют границу, вершины на графе, соответствующие этим областям, соединены ребром екЕЕ. Граф С является взвешенным, то есть, для каждого ребра задается вес рь. Имеем следующие исходные данные: список цепей Т, дополненная ширина для каждой цепи и», и координаты выводов (пинов). Множеству областей, связываемых цепью на графе С соответствует множество вершин Х,ЕХ. Выполнить

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

1

С1 ~ '

где pJ - пропускная способность (вес) ребра 4 - сумма ресурсов, необходимых сетям Е] для прохождения через ребро е) (сумма ресурсов, которая будет затрачена на прокладку множества цепей 7} через границу 6,). Найдем максимальную относительную перегруженность стах = {тах(с) \ 2, ..., т}. Тогда критерий оптимизации <р2 будем определять как <р2 = стах.

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

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

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

В разделе 2.3 описан муравьиный алгоритм решения задачи глобальной трассировки простыми формами. Данная модификация муравьиного основана на комбинаторном подходе. На каждом уровне кс стадии укрупнения первого этапа формируется массив всех локальных двухтерминальных соединений (ДС) данного уровня ..., пкс}. Затем строится граф поиска решений

(2=(У,и). Каждому ДС в графе соответствует группа вершин, каждая вершина представляет собой вариант маршрута на графе й. Граф <3 представляет собой кольцо, вершины каждой группы связаны с вершинами двух соседних групп. Дополнительно в граф вводится по одной стартовой вершине для каждой группы. Необходимо построить на графе Q ориентированный маршрут, который будет включать по одной вершине из каждой группы. Такой маршрут соответствует распределению соединений по областям коммутационного поля. На модифицированном графе поиска решений феромон будет откладываться непосредственно на вершинах. На каждом шаге выбирается одна из вершин (альтернатив) в зависимости от уровня феромона, а также исходя из некоторых эвристических правил. Отметим, что выбор очередной вершины для маршрута осуществляется на основе колеса рулетки. Стоимость каждой из альтернатив оценивается по формуле:

сяу=(й,)л-о*и,))г.

где Л и у - управляющие параметры, А,- - уровень феромона на ребре в графе С>, р(и¡) — минимальная пропускная способность среди ребер, входящих в маршрут на графе й, соответствующий вершине графа Q. После завершения последней итерации алгоритма выбирается наилучшее с точки зрения критериев оптимизации решение.

В разделе 2.4 приведен муравьиный алгоритм глобальной трассировки для соединений сложной конфигурации. Поиск маршрута осуществляется непосредственно на графе й, то есть, сразу ищется реализация двухтерминального соединения для ребра г,к,. Построим граф 0=(Х1,Е1), где \ХГ\ = \Х\, \Е'\ = |£|, на графе О будем моделировать движение муравьев. Пусть хиеХиха£Х-узлы графа б, которые необходимо связать. На каждой итерации / алгоритма в соответствующие узлы х,/ и х,/ графа О назначается по пс, муравьев (агентов). Разделение колонии на 2 части позволяет одновременно просматривать большее количество вариантов маршрута, так как поиск выполняется параллельно. Остановимся подробно на принципе выбора агентом очередной вершины в маршрут.

На шаге / агент атт выбирает вершину хттг0+1) с вероятностью

пит V '

е

где параметр Ф„Л$+1) рассчитывается по формуле:

где цт,т(1+1) ~ уровень феромона на ребре етт'*(1+1), соответствующем ребру 0+1); Хп„т(1+1) - отношение количества ресурсов на ребре ет,т2(1+1) ДО его включения в маршрут Мтт к количеству ресурсов на данном ребре после его включения в маршрут Мтт\ а = 1, если расстояние от конечной вершины маршрута (хц или х,2) до вершины хттг('+1) меньше, чем до вершины х(1) и а=-1 в противном случае; а, Д у - управляющие параметры.

Алгоритм завершает работу по достижении заданного числа итераций.

Третья глава посвящена описанию генетического алгоритма для решения задачи распределения соединений по слоям.

В разделе 3.1 дана постановка задачи распределения соединений по слоям. Имеется топология СБИС с к слоями металлизации и одним логическим слоем. Для моделирования процесса глобальной трассировки используется слойный граф Ск--'(Ук,Е':), где У* - множество вершин и £* - множество ребер. Каждая вершина соответствует области на одном из слоев металлизации.

Множество ребер £* состоит из двух непересекающихся подмножеств е!" и Множество Евключает все ребра, соединяющие вершины разных слоев, это так называемые ребра межслойных переходов. Множество включает в себя ребра, которые соединяют вершины в одном слое. Такие ребра определяют пропускную способность с(еке) границы между двумя соседними областями трассировки (граничные ребра). Пусть С'(У',Е') - однослойный граф глобальной трассировки, полученный путем «сжатия» графа Ск=(Ук,Е!'). Все слои графа (5* проецируются на первый (нижний) слой. При этом емкости лежащих друг над другом граничных ребер складываются, определяя емкость граничного ребра на графе С1. Пусть имеется некоторое решение задачи глобальной трассировки на графе С1, представляющее собой множество протрассированных цепей Л''. Необходимо распределить все соединения для каждого Г/ на многослойном графе & без нарушения ограничений и с учетом заданных критериев оптимизации: общей относительной перегруженности всех граничных ребер, а также общего числа межслойных переходов.

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

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

В разделе 3.4 приводится иерархическая структура генетического поиска, разработанная для решения задачи распределения соединений по слоям. Суть метода состоит в последовательном разделении трассировочных ресурсов по принципу дихотомии. При этом образуются суперслои. Каждый суперслой, является некоторой абстракцией, объединяющей один, два или больше слоев и представляющей их как единое целое. Сначала решается задача распределения по слоям с помощью генетического алгоритма для двух суперслоев ¿г/ и ¿/-2. Затем каждый суперслой делится на два новых, и снова решается задача распределения соединений. Формируются две новые непересекающиеся популяции. Процесс продолжается до тех пор, пока не будет достигнуто конечное разбиение. Такой подход позволяет распараллелить процесс поиска, а также упростить задачу. Также приведено описание модифицированного оператора миграции, используемого в алгоритме. В разделе приведены схемы иерархического ГА, а также процедуры параллельного выполнения генетических операторов. Дан псевдокод алгоритма формирования начальной популяции.

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

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

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

В разделе 4.2 описаны теоретические исследования разработанных методов и алгоритмов. Даны оценки временной сложности для муравьиных и генетического алгоритма. Для муравьиных алгоритмов сложность примерно оценивается как 0(п2), где п - число агентов в колонии, для генетического алгоритма сложность оценивается как О(п), где п - размер популяции.

В разделе 4.3 дано краткое описание использовавшейся библиотеки СА1_ЛЬ, данная библиотека имеет открытый исходный код, распространяется бесплатно и предоставляет методы для работы с генетическими алгоритмами.

15

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

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

В разделе 4.6 рассмотрены результаты экспериментальных исследований, полученных с помощью разработанного комплекса программ. Экспериментальные исследования проводились в несколько этапов. В первую очередь были определены оптимальные значения для управляющих параметров алгоритма. В частности, было выявлено, что оптимальное число муравьев в колонии для муравьиных алгоритмов 35 и 45 агентов соответственно.

S 101520253035404550556065707S 80 85

№ итерации

Рисунок 2. График сходимости муравьиного алгоритма №1 Оптимальный размер начальной популяции для генетического алгоритма определен как 120 особей, вероятность кроссинговера —0.3, вероятность мутации -0.12, вероятность миграции -0.14. Затем были определены временные сложности алгоритмов (результаты теоретических исследований были подтверждены), а также их сходимость.

Рисунок 3. График сходимости генетического алгоритма распределения соединений по слоям Выше приведены графики сходимости для муравьиного алгоритма трассировки простыми формами (МА №1) и генетического алгоритма распределения соединений по слоям. Заключительным этапом стало сравнение разработанного метода с известными аналогами, которое показало улучшение качества решений на 10-12%.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Настоящая диссертационная работа посвящена разработке методов решения задачи многослойной глобальной трассировки СБИС.

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Работы, опубликованные в изданиях из перечня ВАК:

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

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

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

3. Воронин Е.И. Сжатие топологии СБИС методом построения графа ограничений // Неделя науки - 2009: Сб. тезисов. Том 2. - Таганрог: Изд-во ТТИ ЮФУ, 2009. - С. 65-68

4. Воронин Е.И. Модифицированный алгоритм сжатия топологии СБИС //Технологии Microsoft в теории и практике программирования: труды VI-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Южный регион, Таганрог, 2009г. - Таганрог: Изд-во ТТИ ЮФУ, 2009. С.11-15

5. Воронин Е.И. Сжатие топологии СБИС с помощью модифицированного алгоритма //Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2009» Часть 2. Томск: Изд-во В-Спектр. 2009. С. 229-231.

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

7. Воронин Е.И. Программный комплекс для решения задачи бинарного разбиения графа муравьиным алгоритмом с использованием автоматов адаптации //Материалы докладов VII Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАУ. Таганрог: Изд-во ТТИ ЮФУ, 2009. С. 283-285.

8. Воронин Е.И. Трассировка в коммутационном блоке методом муравьиной колонии //Технологии Microsoft в теории и практике программирования: труды VII-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Южный регион, Таганрог, 2010г. - Таганрог: Изд-во ТТИ ЮФУ, 2009. С.9-13.

9. Воронин Е.И., Лебедев Б.К. Разработка метода трассировки в коммутационном блоке на основе моделирования поведения муравьиной колонии //Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT'lO". Научное издание в 4-х томах. - М.: Физматлит, 2010, Т.З. — С. 31-32.

10. Воронин Е.И. Модификация муравьиного алгоритма для решения задачи трассировки в коммутационном блоке //Материалы докладов VIII Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАУ. Таганрог: Изд-во ТТИ ЮФУ, 2010.

11. Воронин Е.И., Лебедев Б.К. Муравьиный алгоритм глобальной трассировки при многоуровневом подходе //Труды Конгресса по интеллектуальным

системам и информационным технологиям "IS-IT'll". Научное издание в 4-х томах. - М.: Физматлит, 2011, Т.З

12. Воронин Е.И. Применение модификации муравьиного алгоритма при многоуровневом подходе к решению задачи трассировки //Труды третьей Всероссийской школы-семинара аспирантов, студентов и молодых ученых ИМАП-2011. - УлГТУ, 2011 - С. 90-93.

13. Воронин Е.И. Оптические эффекты современной фотолитографии и их учет на этапе конструкторского проектирования //Материалы докладов ГХ Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАУ. Таганрог: Изд-во ТТИ ЮФУ, 2011.

14. Воронин Е.И., Лебедев Б.К. Муравьиный алгоритм глобальной трассировки простыми формами при многоуровневом подходе //Труды Конгресса по интеллектуальным системам и информационным технологиям "IS-1TM2". Научное издание в 4-х томах. - М.: Физматлит, 2012, Т.З - С. 47-50.

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

15. Воронин Е.И., Лебедев Б.К., Лебедев О.Б. Программа для решения графовых оптимизационных задач на основе муравьиных алгоритмов (РЗГМА). Свидетельство №2010610065, 2010г.

16. Воронин Е.И., Лебедев Б.К., Лебедев О.Б. Программа разбиения графа муравьиным алгоритмом на подграфы с использованием механизма автоматов адаптации (МАРГ). Свидетельство №2010610066, 2010г.

Личный вклад автора в работах 1-14 состоит в разработке части методов и механизмов решения задач, используемых в описанных алгоритмах. В работах 15-16 автору принадлежит частичная разработка алгоритмов, а также практическая реализация программных продуктов.

Типогр. ИПК ЮФУ Заказ Ы^^тир^'экз.

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

Введение.

Глава 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(п ), генетического - О(п).

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.