Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Воронин Егор Ильич
РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ МНОГОСЛОЙНОЙ ГЛОБАЛЬНОЙ ТРАССИРОВКИ СБИС НА ОСНОВЕ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ ПРИРОДНЫХ СИСТЕМ
05.13.12 - Системы автоматизации проектирования
(вычислительная техника и информатика)
АВТОРЕФЕРАТ
диссертации на соискание ученой
степени кандидата технических наук
Таганрог - 2012
Работа выполнена в Южном федеральном университете
Научный руководитель: доктор технических наук, профессор
ебедев Борис Константинович
Официальные оппоненты: Чернышев Юрий Олегович
Заслуженный деятель науки РФ,
доктор технических наук, профессор.
ДГТУ, профессор кафедры Автоматизации Производственных Процессов
Витиска Николай Иванович
доктор технических наук, профессор.
ТГПИ имени А.П. Чехова,
профессор кафедры Информатики
Ведущая организация: ОАО Таганрогский
научно-исследовательский
институт связи (ТНИИС), г. Таганрог
Защита состоится ________________ 2012г. в _______ на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.
Автореферат разослан: _________________________________
Ученый секретарь
диссертационного совета Д 212.208.22,
доктор технических наук, профессор Целых А.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы
Технология производства интегральных схем насчитывает около пятидесяти лет. Все эти годы схемы усложнялись, при этом постоянно усложнялся и процесс их производства. В результате возникло целое направление - автоматизация проектирования в электронике (electronic design automation, EDA), занимающееся разработкой и исследованием систем автоматизированного проектирования (САПР). Современные САПР позволяют проектировать сложнейшие схемы, содержащие миллиарды элементов на кристалле. Создание подобных систем требует постоянной разработки новых алгоритмов, позволяющих в автоматическом режиме проводить различные стадии проектирования СБИС, в частности, стадию конструкторского проектирования. На стадии конструкторского проектирования реализуются конечные геометрические элементы, а также физические связи между ними на кристалле. В результате получается готовая топология схемы. Данная стадия состоит из нескольких этапов. Классический маршрут стадии конструкторского проектирования, как известно, включает разбиение, размещение и трассировку.
Общая площадь межсоединений неуклонно растет с постоянным усложнением интегральных схем. В настоящее время межсоединения занимают больше 50% от общей площади кристалла. Задержка сигнала в соединениях стала значительно больше задержек в транзисторах. Качество трассировки в такой ситуации играет определяющую роль. Как правило, для упрощения процесса трассировки используется двухэтапный подход: сначала выполняется глобальная трассировка, за которой следует детальная трассировка. Глобальная трассировка является важнейшим этапом, поскольку от ее результата зависит дальнейшее распределение соединений на кристалле, загруженность отдельных областей, общая длина и другие параметры, напрямую влияющие на качество конечного продукта.
Задача трассировки является самой сложной и времязатратной на стадии конструкторского проектирования. В связи с этим ведется постоянный поиск новых методов и алгоритмов, позволяющих осуществлять трассировку в автоматическом режиме. Большое внимание задаче трассировки уделяется в работах Курейчика В.М., Курейчика В.В., Лебедева Б.К., Лебедева О.Б., Chris Chu, Minsik Cho, Tai-Chen Chen, Yao-Wen Chang и других российских и зарубежных ученых. Несмотря на множество работ, проводимых в этой области, в настоящее время практически не существует алгоритмов трассировки, удовлетворяющих всем современным требованиям.
Подводя итог всему вышесказанному, отметим, что разработка нового метода глобальной трассировки, удовлетворяющего современным ограничениям и критериям оптимизации, является актуальной. Необходим подход к решению задачи глобальной трассировки, который обеспечит стопроцентную трассируемость схемы и позволит максимально упростить дальнейшую детальную трассировку, не нарушая при этом ограничений, присущих производству современных нанометровых СБИС.
Цель диссертационной работы состоит в разработке такого подхода к решению задачи глобальной трассировки СБИС, который позволял бы учитывать современные критерии оптимизации, удовлетворял ограничениям, накладываемым нанометровыми технологиями на разработку СБИС, а также обеспечивал возможность успешной детальной трассировки в дальнейшем. Для достижения поставленной цели в работе решались следующие задачи:
- разработка общей парадигмы решения задачи многослойной глобальной трассировки СБИС;
- разработка модифицированного многоуровневого подхода к решению задачи глобальной трассировки на плоскости;
- разработка муравьиных алгоритмов трассировки для соединений простой и сложной конфигурации, учитывающих специфику многоуровневого подхода;
- разработка генетического алгоритма для решения задачи распределения соединений по слоям металлизации при многослойной глобальной трассировке СБИС, позволяющего учитывать особенности задачи;
- разработка дополнительных модификаций генетического алгоритма для ускорения процесса поиска и получения более качественных решений.
Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем:
- разработана новая парадигма решения задачи глобальной многослойной трассировки СБИС с разбиением ее на два этапа, отличающаяся от известных применением многоуровневого подхода к трассировке по всему чипу, учетом числа межслойных переходов, а также последовательным использованием алгоритмов, инспирированных природными системами;
- предложен многоуровневый подход к решению задачи глобальной трассировки на плоскости, отличающийся от известных наличием дополнительной стадии и позволяющий, таким образом, распределить все соединения, при этом максимально эффективно используя трассировочные ресурсы;
- разработаны муравьиные алгоритмы для трассировки соединений простой и сложной конфигурации, учитывающие специфику задачи и многоуровневого подхода;
- разработан генетический алгоритм для решения задачи распределения соединений по слоям при многослойной глобальной трассировке, отличающийся от известных использованием иерархической структуры хромосом, иерархической процедурой генетического поиска, а также использованием модифицированного оператора миграции, разработанного с учетом конкретной задачи.
Положения, выносимые на защиту
- Общий подход к решению задачи глобальной многослойной трассировки СБИС, использующий идею разбиения задачи на два этапа: трассировку на плоскости и распределение соединений по слоям.
- Многоуровневый подход к решению задачи глобальной трассировки на плоскости.
- Муравьиные алгоритмы для трассировки на плоскости соединений простой и сложной конфигурации.
- Генетический алгоритм решения задачи распределения соединений по слоям, использующий иерархическую структуру и модифицированный оператор миграции.
Практическая значимость работы
На основе разработанных методов и алгоритмов был реализован комплекс программных продуктов для решения задачи глобальной многослойной трассировки СБИС. При создании данного комплекса использовались языки программирования C++ и C#, среда разработки 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-ITТ11, 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) - это способ увеличить производительность и расширить возможности современных интегральных схем. Основной ее плюс - это уменьшение длины межсоединений за счет снижения площади кристалла, кроме того, этот подход позволяет объединить различные технологии внутри одной системы, что является большим шагом вперед по сравнению с обычными СБИС.
В разделе 1.2 описываются технологические проблемы изготовления СБИС. Нанометровые технологии позволили преодолеть предел в один миллиард транзисторов на кристалле. Рабочие частоты процессоров при этом превысили 6 ГГц. Несмотря на снижение напряжения электропитания, общая потребляемая мощность микросхем постоянно растет. Существенной проблемой являются нежелательные оптические эффекты. В большинстве установок фотолитографии используются источники света с длиной волны 193 нм. Дифракционные эффекты в оптической системе - основная причина искажений рисунка при фотолитографии нанометровых элементов. Еще одна проблема - проблема энергосбережения, включающая в себя много аспектов. При современных технологиях производства большую часть площади кристалла СБИС занимают межсоединения, от качества их разводки зависят характеристики изделия и экономическая выгода компании.
В разделе 1.3 приводится постановка задачи многослойной глобальной трассировки СБИС. Цель глобальной трассировки состоит в распределении соединений по областям коммутационного поля без нарушения ограничений. В современных СБИС на каждом логическом уровне используется шесть и более слоев металлизации. То есть, соединения распределяются по областям и по слоям. Для решения задачи распределения соединений по областям на одном логическом уровне в качестве модели КП используется трехмерный граф Gk=(Xk,Uk). Число уровней графа соответствует числу слоев металлизации. Вершины графа xiX соответствуют областям aiA. Если две области ai и aj имеют общую границу bl, то вершины xi и xj , соответствующие этим областям, связываются ребром ulUk. Множество ребер Uk состоит из двух непересекающихся подмножеств: Ubk и Uvk. Множество Ubk включает в себя вершины, соответствующие ребрам графа, расположенным на одном уровне. Uvk включает в себя ребра, соединяющие вершины разных уровней. Ребра, расположенные на одном уровне, контролируют пропускную способность границ областей, в то время как ребра, соединяющие вершины разных уровней, контролируют число межслойных переходов. Основными критериями оптимизации являются трассируемость (процент распределенных соединений), загруженность схемы - суммарное число использованных ресурсов на границах областей, а также общее число межслойных переходов. Также накладываются ограничения на использование ресурсов одного ребра и число межслойных переходов внутри одной области. Таким образом, необходимо получить распределение соединений по областям и по слоям такое, что оно будет оптимальным с точки зрения вышеупомянутых критериев, и при этом будет удовлетворять указанным ограничениям.
В разделе 1.4 рассматриваются два подхода к решению задачи многослойной трассировки СБИС.
В первом случае трассировка цепей осуществляется непосредственно на многослойной графовой модели. На рисунке 1 показан пример такого подхода. В данном случае имеется четыре пина (терминала) P1, P2, P3 и P4 одной цепи, которые необходимо соединить. Пины разнесены по трем слоям металлизации.
Рисунок 1. Пример задачи глобальной трассировки цепи с тремя пинами на графовой модели для трех слоев металлизации (слева), а также одно из возможных решений данной задачи (справа)
Поскольку такой подход непосредственно ищет решение для многослойной глобальной трассировки, он может учитывать количество межслойных переходов (via) во время процедуры поиска. Однако это метод может оказаться слишком времязатратным при большом размере задачи. При другом подходе многослойный граф сначала сжимается в однослойных граф, затем используется глобальный однослойный трассировщик для решения задачи однослойной трассировки, после чего выполняется стадия распределения по слоям, во время которой каждая цепь определяется на многослойном графе.
В разделе 1.5 приводится обзор современных алгоритмов глобальной трассировки СБИС. Существует множество алгоритмов для решения задачи глобальной трассировки. Каждый из алгоритмов имеет как достоинства, так и недостатки. Основным общим недостатком почти всех алгоритмов является их узкая направленность. То есть, данные алгоритмы предназначены либо для трассировки в 1-2 слоях (например, муравьиный алгоритм глобальной трассировки), либо для решения задачи распределения соединений по слоям (COLA). Еще одним недостатком является отсутствие гарантии стопроцентной трассируемости. Среди положительных особенностей названных алгоритмов стоит отметить: комбинирование роевого интеллекта и генетических процедур; граф поиска решений, разработанный с учетом специфики муравьиных алгоритмов; согласованный поиск с использованием оценочной функции и др
Вторая глава посвящена описанию модифицированного многоуровневого подхода, используемого в работе для решения задачи трассировки на плоскости, а также описанию муравьиных алгоритмов, используемых при многоуровневом подходе.
В разделе 2.1 приведен многоуровневый подход к решению задачи трассировки на плоскости, описан принцип трассировки по всем кристаллу (чипу). Общепринятым подходом при трассировке СБИС является разделение задачи на два этапа: глобальную и детальную трассировку. Так как сложность СБИС постоянно увеличивается, классический двухэтапный подход не может давать качественные результаты. В связи с этим используется многоуровневый подход. При таком подходе процесс трассировки проводится также в две стадии: укрупнение или огрубление (coarsening, на этой стадии компоненты схемы пошагово группируются) и детализация или разделение (uncoarsening, обратный укрупнению процесс). Каждая стадия в свою очередь делится на этапы, включающие как глобальную, так и детальную трассировку. В первую очередь коммутационное поле разбивается на множество областей одинакового размера, которые называются глобальными ячейками уровня 0 (Global Cells ЦGCs0). Затем начинается стадия укрупнения. На нулевом уровне производится трассировка только тех соединений, которые находятся внутри одной такой ячейки, не выходя за ее границы. Соединения, которые не удается распределить, фиксируются и откладываются до стадии детализации. При переходе на первый уровень смежные ячейки группируются по 4, образуя новую ячейку уровня 1. После чего производится трассировка соединений в ячейках первого уровня. Процесс продолжается до тех пор, пока не будет достигнут заданный уровень k. Затем начинается обратный процесс - стадия детализации. На этой стадии ячейки итеративно разгруппируются. При этом осуществляется распределение соединений, которые не были протрассированы на стадии укрупнения.
Кроме того, в разделе дана постановка задачи глобальной трассировки на плоскости. Моделью коммутационного поля (КП) является граф G=(X,E). Каждая вершина графа xiX соответствует области aiA на коммутационном поле. Если две области являются смежными, то есть имеют границу, вершины на графе, соответствующие этим областям, соединены ребром ekE. Граф G является взвешенным, то есть, для каждого ребра задается вес pkнн. Имеем следующие исходные данные: список цепей T, дополненная ширина для каждой цепи wi и координаты выводов (пинов). Множеству областей, связываемых цепью tiT, на графе G соответствует множество вершин XiX. Выполнить глобальную трассировку для цепи ti или распределить цепь ti по областям - значит построить в графе G на множестве вершин Xi связывающую сеть. Первый критерий оптимизации при глобальной трассировке при многоуровневом подходе определим как сумму 1 относительных перегруженностей для всех ребер графа G. Цель оптимизации - минимизация критерия 1. Относительная перегруженность в данном случае определяется как
где pнj - пропускная способность (вес) ребра j, djн - cумма ресурсов, необходимых сетям Ej для прохождения через ребро ej (сумма ресурсов, которая будет затрачена на прокладку множества цепей Tj через границу bj). Найдем максимальную относительную перегруженность cmax = {max(cj) | j=1, 2, Е, m}. Тогда критерий оптимизации 2 будем определять как 2 = cmaxн.
Также в разделе 2.1 описаны основные принципы метода глобальной трассировки, используемого в работе. Главной отличительной особенностью модифицированного многоуровневого подхода является наличие дополнительной стадии укрупнения, которая введена для получения стопроцентного распределения соединений по областям.
В разделе 2.2 дан краткий обзор биоинспирированных методов поиска и оптимизации. Биоинспирированные методы решения оптимизационных задач - это алгоритмы и методы, в той или иной мере моделирующие поведение систем в живой природе. К ним относятся методы пчелиной и муравьиной колоний, метод роя частиц, метод на основе моделирования перемещения бактерий, а также методы эволюционного моделирования.
В разделе 2.3 описан муравьиный алгоритм решения задачи глобальной трассировки простыми формами. Данная модификация муравьиного основана на комбинаторном подходе. На каждом уровне kc стадии укрупнения первого этапа формируется массив всех локальных двухтерминальных соединений (ДС) данного уровня Dkc={dkcg|g=1,2, Е, nkc}. Затем строится граф поиска решений Q=(V,U). Каждому ДС в графе соответствует группа вершин, каждая вершина представляет собой вариант маршрута на графе G. Граф Q представляет собой кольцо, вершины каждой группы связаны с вершинами двух соседних групп. Дополнительно в граф вводится по одной стартовой вершине для каждой группы. Необходимо построить на графе Q ориентированный маршрут, который будет включать по одной вершине из каждой группы. Такой маршрут соответствует распределению соединений по областям коммутационного поля. На модифицированном графе поиска решений феромон будет откладываться непосредственно на вершинах. На каждом шаге выбирается одна из вершин (альтернатив) в зависимости от уровня феромона, а также исходя из некоторых эвристических правил. Отметим, что выбор очередной вершины для маршрута осуществляется на основе колеса рулетки. Стоимость каждой из альтернатив оценивается по формуле:
где и - управляющие параметры, hj - уровень феромона на ребре в графе Q, p(uj) - минимальная пропускная способность среди ребер, входящих в маршрут на графе G, соответствующий вершине графа Q. После завершения последней итерации алгоритма выбирается наилучшее с точки зрения критериев оптимизации решение.
В разделе 2.4 приведен муравьиный алгоритм глобальной трассировки для соединений сложной конфигурации. Поиск маршрута осуществляется непосредственно на графе G, то есть, сразу ищется реализация двухтерминального соединения для ребра rikz. Построим граф D=(X1,E1), где |X1| = |X|, |E1| = |E|, на графе D будем моделировать движение муравьев. Пусть xi1X и xi2X - узлы графа G, которые необходимо связать. На каждой итерации i алгоритма в соответствующие узлы xнi11 и xнi21 графа D назначается по nнcl муравьев (агентов). Разделение колонии на 2 части позволяет одновременно просматривать большее количество вариантов маршрута, так как поиск выполняется параллельно. Остановимся подробно на принципе выбора агентом очередной вершины в маршрут.
На шаге t агент anum выбирает вершину xnumz(t+1) с вероятностью Pnumz(t+1).
где параметр Фnumz(t+1) рассчитывается по формуле:
где numz(t+1) - уровень феромона на ребре enum1z(t+1), соответствующем ребру enumz(t+1); numz(t+1) - отношение количества ресурсов на ребре enumz(t+1) до его включения в маршрут Mnum к количеству ресурсов на данном ребре после его включения в маршрут Mnum; = 1, если расстояние от конечной вершины маршрута (xнi1 или xнi2) до вершины xnumz(t+1) меньше, чем до вершины x(t) и =-1 в противном случае; , , - управляющие параметры.
Алгоритм завершает работу по достижении заданного числа итераций.
Третья глава посвящена описанию генетического алгоритма для решения задачи распределения соединений по слоям.
В разделе 3.1 дана постановка задачи распределения соединений по слоям. Имеется топология СБИС с k слоями металлизации и одним логическим слоем. Для моделирования процесса глобальной трассировки используется слойный граф Gk=(Vk,Ek), где Vk - множество вершин и Ek - множество ребер. Каждая вершина соответствует области на одном из слоев металлизации. Множество ребер Ek состоит из двух непересекающихся подмножеств Ekv и Eke. Множество Ekv включает все ребра, соединяющие вершины разных слоев, это так называемые ребра межслойных переходов. Множество Eke включает в себя ребра, которые соединяют вершины в одном слое. Такие ребра определяют пропускную способность c(eke) границы между двумя соседними областями трассировки (граничные ребра). Пусть G1(V1,E1) - однослойный граф глобальной трассировки, полученный путем сжатия графа Gk=(Vk,Ek). Все слои графа Gk проецируются на первый (нижний) слой. При этом емкости лежащих друг над другом граничных ребер складываются, определяя емкость граничного ребра на графе G1. Пусть имеется некоторое решение задачи глобальной трассировки на графе G1, представляющее собой множество протрассированных цепей N1. Необходимо распределить все соединения для каждого Ti на многослойном графе Gk без нарушения ограничений и с учетом заданных критериев оптимизации: общей относительной перегруженности всех граничных ребер, а также общего числа межслойных переходов.
В разделе 3.2 приведен краткий обзор генетических алгоритмов. Генетический алгоритм (ГА) моделирует процесс эволюции. Каждая особь (хромосома) в популяции соответствует одному из вариантов решения задачи. Поскольку для задач САПР, оптимизации, принятия решений и т.п. пространство поиска очень велико, возможность оперировать сразу множеством решений оказывается очень полезной и даже необходимой.
В разделе 3.3 описан генетический алгоритм распределения соединений по слоям. Целевая функция представляет собой аддитивную свертку двух критериев оптимизации. Хромосома имеет следующую структуру. Каждая из имеющихся цепей состоит из набора двухтерминальных соединений. Ген в хромосоме соответствует такому соединению, а значение гена определяет номер слоя. Генерация начальной популяции осуществляется случайным образом, часть полученных нелегальных решений исключается из популяции. В работе используется два вида кроссинговера: обмен отдельными генами и обмен участками хромосомы. Участок соответствует целой цепи. Мутация заключается в случайном изменении отдельного гена. Селекция выполняется по принципу колеса рулетки. В конце раздела дан псевдокод алгоритма.
В разделе 3.4 приводится иерархическая структура генетического поиска, разработанная для решения задачи распределения соединений по слоям. Суть метода состоит в последовательном разделении трассировочных ресурсов по принципу дихотомии. При этом образуются суперслои. Каждый суперслой является некоторой абстракцией, объединяющей один, два или больше слоев и представляющей их как единое целое. Сначала решается задача распределения по слоям с помощью генетического алгоритма для двух суперслоев Lr1 и Lr2. Затем каждый суперслой делится на два новых, и снова решается задача распределения соединений. Формируются две новые непересекающиеся популяции. Процесс продолжается до тех пор, пока не будет достигнуто конечное разбиение. Такой подход позволяет распараллелить процесс поиска, а также упростить задачу. Также приведено описание модифицированного оператора миграции, используемого в алгоритме. В разделе приведены схемы иерархического ГА, а также процедуры параллельного выполнения генетических операторов. Дан псевдокод алгоритма формирования начальной популяции.
В разделе 3.5 описаны дополнительные модификации генетического алгоритма. В частности, оператор дальней миграции, представляющий собой обмен генами между популяциями, не являющимися соседними.
В четвертой главе описана практическая реализация разработанных алгоритмов, а также проведенные экспериментальные исследования.
В разделе 4.1 описана цель экспериментальных исследований. Целью экспериментальных исследований является определение эффективности предложенных алгоритмов и методов решения задачи глобальной трассировки в нескольких слоях металлизации.
В разделе 4.2 описаны теоретические исследования разработанных методов и алгоритмов. Даны оценки временной сложности для муравьиных и генетического алгоритма. Для муравьиных алгоритмов сложность примерно оценивается как O(n2), где n - число агентов в колонии, для генетического алгоритма сложность оценивается как O(n), где n - размер популяции.
В разделе 4.3 дано краткое описание использовавшейся библиотеки GALib, данная библиотека имеет открытый исходный код, распространяется бесплатно и предоставляет методы для работы с генетическими алгоритмами.
В разделе 4.4 приведено краткое описание библиотеки параллельного программирования PPL, предоставляющей императивную модель программирования, обеспечивающую масштабируемость и повышающую удобство разработки параллельных приложений.
В разделе 4.5 описан комплекс разработанных программ, приведена общая схема данного комплекса.
В разделе 4.6 рассмотрены результаты экспериментальных исследований, полученных с помощью разработанного комплекса программ. Экспериментальные исследования проводились в несколько этапов. В первую очередь были определены оптимальные значения для управляющих параметров алгоритма. В частности, было выявлено, что оптимальное число муравьев в колонии для муравьиных алгоритмов 35 и 45 агентов соответственно.
Рисунок 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, Т.3. - С. 213-214.
7. Воронин Е.И. Программный комплекс для решения задачи бинарного разбиения графа муравьиным алгоритмом с использованием автоматов адаптации //Материалы докладов VII Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАУ. Таганрог: Изд-во ТТИ ЮФУ, 2009. С. 283 - 285.
8. Воронин Е.И. Трассировка в коммутационном блоке методом муравьиной колонии //Технологии Microsoft в теории и практике программирования: труды VII-ой Всероссийской конференции студентов, аспирантов и молодых ученых. Южный регион, Таганрог, 2010г. - Таганрог: Изд-во ТТИ ЮФУ, 2009. С.9-13.
9. Воронин Е.И., Лебедев Б.К. Разработка метода трассировки в коммутационном блоке на основе моделирования поведения муравьиной колонии //Труды Конгресса по интеллектуальным системам и информационным технологиям УAIS-ITТ10Ф. Научное издание в 4-х томах. - М.: Физматлит, 2010, Т.3. - С. 31-32.
10. Воронин Е.И. Модификация муравьиного алгоритма для решения задачи трассировки в коммутационном блоке //Материалы докладов VIII Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАУ. Таганрог: Изд-во ТТИ ЮФУ, 2010.
11. Воронин Е.И., Лебедев Б.К. Муравьиный алгоритм глобальной трассировки при многоуровневом подходе //Труды Конгресса по интеллектуальным системам и информационным технологиям УIS-ITТ11Ф. Научное издание в 4-х томах. - М.: Физматлит, 2011, Т.3
12. Воронин Е.И. Применение модификации муравьиного алгоритма при многоуровневом подходе к решению задачи трассировки //Труды третьей Всероссийской школы-семинара аспирантов, студентов и молодых ученых ИМАП-2011. - УГТУ, 2011 - С. 90-93.
13. Воронин Е.И. Оптические эффекты современной фотолитографии и их учет на этапе конструкторского проектирования //Материалы докладов IX Всероссийской научной конференции молодых ученых, аспирантов и студентов ИТСАУ. Таганрог: Изд-во ТТИ ЮФУ, 2011.
14. Воронин Е.И., Лебедев Б.К. Муравьиный алгоритм глобальной трассировки простыми формами при многоуровневом подходе //Труды Конгресса по интеллектуальным системам и информационным технологиям УIS-ITТ12Ф. Научное издание в 4-х томах. - М.: Физматлит, 2012, Т.3 - С. 47-50.
Свидетельства о регистрации программ на ЭВМ:
15. Воронин Е.И., Лебедев Б.К., Лебедев О.Б. Программа для решения графовых оптимизационных задач на основе муравьиных алгоритмов (РЗГМА). Свидетельство №2010610065, 2010г.
16. Воронин Е.И., Лебедев Б.К., Лебедев О.Б. Программа разбиения графа муравьиным алгоритмом на подграфы с использованием механизма автоматов адаптации (МАРГ). Свидетельство №2010610066, 2010г.
Личный вклад автора в работах 1-14 состоит в разработке части методов и механизмов решения задач, используемых в описанных алгоритмах. В работах 15-16 автору принадлежит частичная разработка алгоритмов, а также практическая реализация программных продуктов.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям