Разработка и исследование гибридных методов размещения фрагментов сбис с учётом трассируемости соединений
На правах рукописи
Лисовцова Анастасия Евгеньевна
Разработка и исследование гибридных методов размещения фрагментов СБИС с учётом трассируемости соединений
05.13.12 – системы автоматизации проектирования
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Таганрог – 2011
Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге.
Научный руководитель: кандидат технических наук, доцент
Гладков Леонид Анатольевич
Официальные оппоненты: кандидат технических наук, доцент
Родзин Сергей Николаевич
(Технологический институт Южного
федерального университета в г.Таганроге)
доктор технических наук, профессор
Витиска Николай Иванович
«Таганрогский Государственный
Педагогический Институт им. А.П. Чехова»
Ведущая организация: Федеральное государственное
унитарное предприятие Таганрогский НИИ
Связи.
Защита состоится «10» ноября 2011 г. в 14:20 на заседании диссертационного совета Д 212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.
Автореферат разослан 8 «октября» 2011 г.
Ученый секретарь
диссертационного совета Д 212.208.22,
доктор технических наук, профессор Целых А.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Проектирование новых видов и образцов машин, оборудования, устройств, аппаратов, приборов и других изделий представляет сложный и длительный процесс, включающий в себя разработку исходных данных, чертежей, технической документации, необходимых для изготовления опытных образцов и последующего производства и эксплуатации объектов проектирования. В настоящее время наибольшее распространение при проектировании сложных объектов получило проектирование, при котором происходит взаимодействие человека и ЭВМ.
Довольно распространённым представлением процесса проектирования является следующее: на каждом уровне проекта решаются две задачи — синтез и анализ. Например, при схемотехническом проектировании структура системы представляется списком цепей, соединяющих транзисторы, резисторы, ёмкости и другие компоненты, а анализ заключается в построении математической модели схемы в виде системы обыкновенных дифференциальных уравнений и её численного решения, что позволяет рассчитать функциональные параметры схемы. Учитывая, что реализация процедур параметрической оптимизации и статистического анализа осуществляется путем многократного решения уравнений математических моделей, процесс проектирования требует колоссальных вычислительных ресурсов, даже с учетом достижений в области разработки современных эффективных вычислительных средств.
Для снижения суммарных затрат при проектировании сложных технических систем (в т.ч. сверхбольших интегральных схем (СБИС), систем на кристалле и других изделий микроэлектроники) широко применяется блочно-иерархический подход. При блочно-иерархическом подходе процесс проектирования разделяется на уровни (этапы). На высшем уровне используется наименее детализированное представление, отражающее только самые общие черты проектируемой системы. На каждом из последующих (более низких) уровней проектирования система последовательно разделяется на отдельные, как правило, функционально законченные блоки, причем степень детализации в каждом из этих блоков возрастает. Такой подход позволяет на каждом этапе формулировать и решать задачи приемлемой сложности.
Одним из направлений, которое улучшает качество получаемых решений для задач размещения и трассировки, является использование генетических алгоритмов. Генетический алгоритм (ГА или Genetic Algorithm, GA) представляет собой адаптивный поисковый метод, который основан на принципах естественного отбора лучших элементов в популяции по аналогии с эволюционной теорией Дарвина Ч.
В настоящее время генетические алгоритмы успешно применяются для решения различных научных и технических задач. Одним из самых эффективных направлений использования генетических алгоритмов является оптимизация многопараметрических функций. Часто при решении практических задач оптимизации не обязательно осуществлять поиск глобального оптимума, вполне достаточно найти одно или несколько квазиоптимальных решений, удовлетворяющих заданным ограничениям. В таких случаях генетические алгоритмы весьма эффективны. Одно из основных преимуществ генетического алгоритма – это возможность оперировать в процессе поиска не одним, а множеством решений.
В настоящее время эволюционные и генетические алгоритмы широко используют для решения ряда сложных задач оптимизации. Благодаря своему разнообразию подходов к нахождению решений, генетические алгоритмы представляют собой весьма эффективное средство решения задач оптимизации и проектирования. Нечеткие генетические алгоритмы с успехом применяют в современных средствах автоматизации проектирования изделий электронной техники, которая содержит сложнейшие электронные системы.
В этой связи разработка новых алгоритмов методов решения задачи размещения, эффективных в решении САПР имеет важное экономико-социальное значение и является в настоящее время актуальной и важной.
Цель диссертационной работы является разработка новых и модифицированных методов и алгоритмов решения задачи размещения фрагментов СБИС с учётом трассируемости соединений на основе нечётких генетических алгоритмов, позволяющих производить расчёты на основе вещественных чисел и нечётких правил.
Указанная цель достигается решением следующих задач:
- Разработка новых методов и алгоритмов задачи размещения фрагментов СБИС с учетом трассируемости соединений.
- Построение новых структурных схем процесса гибридного генетического поиска для решения задачи размещения с учётом трассируемости.
- Разработка модифицированных генетических операторов и поисковых процедур (стратегии поиска, операторов кроссинговера, сегрегации, формирование начальной популяции).
- Создание новых структур и принципов кодирования и декодирования альтернативных решений на основе вещественных чисел и построение модели логического контроллера.
- Разработка новой инструментальной среды формирования фрагментов СБИС с учётом трассируемости соединений.
Методы исследования. В диссертационной работе для решения поставленных задач используются элементы теории процессов проектирования, аппарат теории чётких и нечётких графов, экспертных систем и эволюционного моделирования. В исследованиях широко использовался вычислительный эксперимент и моделирование на основе нечётких генетических алгоритмов, нечёткой логики и информационных технологий.
Научная новизна работы заключается в теоретическом обобщении и решении научной проблемы поддержки принятия решений в условиях недостаточности и нечёткости исходных данных, имеющих важное значение, в области проектирования САПР и информационных технологий:
- Разработана новая схема гибридного генетического алгоритма с использованием нечётких вычислений и генетических операторов, позволяющая получить решение поставленной задачи один из наиболее удобных способов для, лица принимающего решение.
- Разработана структура и принципы кодирования и декодирования решений для задачи размещения с учетом трассируемости с применением вещественных чисел в генетических операторах, что позволит получить лучшее решение и повысить качество получаемых решений.
- Построен оператор кроссинговера «hill-climbing», использующего метод локального поиска с применением вещественных чисел, разработаны стратегии поиска популяции: минимальный разрыв между поколениями и обобщение поколений, позволяющие повысить устойчивость генетического поиска.
- Разработан нечёткий логический контроллер, позволяющий корректировать результаты работы программы.
- Построена новая инструментальная среда системы формирования фрагментов СБИС с учётом трассируемости соединений
Положения выносимые на защиту:
- Усовершенствованные процедуры выполнения генетического оператора кроссинговера, обеспечивающие уменьшение времени поиска.
- Модифицированная схема генетического поиска и разработанный модифицированный генетический оператор кроссинговера «hill-climbing».
- Интегрированная архитектура для решения задачи размещения с учётом трассируемости, основанную на методах эволюционного моделирования.
Практическая значимость работы заключается в реализации интегрированного программно-алгоритмического комплекса в виде законченного программного продукта, использование которого позволяет решать поставленные задачи размещения фрагментов СБИС, позволяющего использовать разработанные алгоритмы, стратегии и эвристики, проводить сравнительный анализ с существующими аналогами.
Проведённые результаты вычислительных экспериментов, показали преимущество предложенного в работе интегрированного подхода к решению задач размещения фрагментов СБИС с учётом трассируемости соединений, в сравнении с используемыми классическими вариантами.
Внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе интегрированных нечетких генетических и эволюционных методов», грант «Разработка общей теории и когнитивных принципов эволюционных вычислений», Грант «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования», грант «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», «Разработка теории и когнитивных принципов принятия решений на основе распределённых алгоритмов, инспирированных природными системами».
Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Автоматизация конструкторского и технологического проектирования», «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».
Апробация работы. Основные результаты, полученные в ходе работы, докладывались и обсуждались на VII-ой научно практическая конференции студентов, аспирантов и молодых ученых и специалистов «Интегральные модели, мягкие вычисления, вероятностные системы и сложные программы в искусственном интеллекте» Коломна, 26-27 Мая 2009 года. Конгресс по интеллектуальным вычислениями и информационным технологиям AIS-IT’09 Дивноморское 2-10 Сентября 2009 года. Всероссийской научно-технической конференции "Проблемы разработки перспективных микро- и наноэлектронных систем» с 4 по 8 октября 2010 года в Подмосковье. IX-й научно-практической конференции студентов, аспирантов и молодых ученых и специалистов «Интегральные модели, мягкие вычисления, вероятностные системы и сложные программы в искусственном интеллекте» Коломна 26-27 мая 2011 год.
Публикации. Основные положения и результаты диссертационной работы опубликованы в 13 источниках, включающих 10 статей, 3 материалов конференций и семинаров, 2 свидетельства о регистрации программ. Четыре работы из них опубликованы в рецензируемом журнале из списка ВАК.
Объем и структура диссертации. Диссертация состоит из введения, списка рисунков, 4 глав, заключения, списка литературы, включающего 106 наименования и 6 приложений. Основной текст диссертации изложен на 164 страницах, включая 85 рисунок и 11 таблиц.
Содержание работы
Во введении обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы. Приведены основные научные положения, выносимые на защиту. Дано краткое содержание глав диссертации.
В первой главе приведено описание имеющихся проблем задачи размещения, приведена классификация методов решения задачи размещения.
В параграфе 1.1 описываются основные задачи решаемые при проектировании СБИС. Приводятся самые распространённые типы полузаказных СБИС, иерархическая структура проектирования.
В параграфе 1.2 описывается общая постановка задачи размещения. В общем виде задача размещения заключается в определении оптимального в смысле некоторого критерия положения элементов и связей между ними. При этом должны быть удовлетворены заданные конструктивно-технологические ограничения. Задачу размещения условно разбивают на две части: размещение конструктивных элементов и оценка возможной длины связей между ними.
В параграфе 1.3 рассмотрены классификации методов размещения. Обилие методов решения задач размещения объясняется желанием их разработчиков создать наиболее благоприятные условия для выполнения следующих этапов автоматизированного проектирования, и в частности этапа размещения. Методы решения задачи размещения можно разделить на следующие три основные группы: конструктивные, итерационные и реализующие математические или физические аналоги.
В параграфе 1.4 представлено описание самых первых и самых актуальных критериев размещения. Представлены факторы которые необходимо учитывать при решении задач конструкторского проектирования СБИС.
В параграфе 1.5 приводится описание методов трассировки, В процессе трассировки современных сверх и ультрабольших интегральных схем принято выделять следующие два этапа: глобальная (назначение цепей в определённые регионы) и детальная (прокладка соединений внутри областей) трассировки. В настоящее время для решения задачи глобальной трассировки используют различные варианты волнового алгоритма, в частности, лучевой, маршрутный алгоритм, комбинаторный и т.д.
Во второй главе приводится решение многокритериальной оптимизации задачи размещения с учётом трассируемости соединений.
В параграфе 2.1 представлено решение задачи размещения с учётом трассируемости, как многокритериальную задачу оптимизации. Приведены методы решения, выделены важные аспекты при решении данных задач оптимизации.
В параграфе 2.2 представлено решение многокритериальной задачи размещения с использованием градиентных методов. Выявлены особенности работы градиентных методов для решения задачи размещения с учетом трассируемости соединений. Преимуществами градиентных методов являются: небольшие затраты машинного времени и наличие стандартных программ для решения задачи, а так же итерационный процесс можно начать с любого допустимого, а не обязательно с опорного решения.
В параграфе 2.3 представлено решение задачи размещения с учётом трассируемости соединений с применением генетических и эволюционных методов. Оптимальное решение практических задач проектирования может быть получено только с помощью полного перебора. Поэтому количество альтернативных решений столь велико, что явное представление решений невозможно. Генетический алгоритм оперирует популяцией - подмножеством альтернативных решений (хромосом) мощности N. Представлены стратегии отбора: пропорциональный отбор, турнирный отбор, отбор усечением, особенности работы каждой стратегии.
В параграфе 2.4 разработан алгоритм решения оптимизационной задачи проектирования. Определён этап процесса проектирования на котором решается задача размещения. Представлено решение процесса проектирования, выполненный как автоматически, так и вручную. При этом используются нечеткая логика, нечеткость полученных изначальных данных не четкое время обработки задания и т.д.
На первом этапе проектирования определяется функциональный состав серии интегральных схем (ИС), устанавливаются технические требования к каждой схеме данной серии.
На втором этапе проектирования решаются вопросы логического проектирования сложных сверх больших интегральных схем (СБИС): логическое моделирование, синтез тестов, логический синтез.
На третьем этапе проектирования рассматривается задача синтеза принципиальной электрической схемы. Применение ЭВМ на данном этапе проектирования ИС может дать значительные экономические выгоды.
На четвёртом этапе проектирования ЭВМ эффективно применяется для разработки топологии ИС и решения задачи оптимального (с точки зрения площади или других критериев) расположения компонентов на кристалле, оптимального (с точки зрения суммарной длины проводников или других критериев) соединения компонентов в схему. Задача размещения является одной из самых важных и трудоемких в процессе проектирования. Применение ЭВМ на этапе разработки топологии дает значительный экономический эффект. по двум причинам: 1) разработка топологии – это очень трудоемкий процесс; 2)возможно получение безошибочных проектов, тем самым мы сократим время на решение задачи размещения.
Параграф 2.5 представлено построение нечёткого логического контроллера. Представлены этапы работы нечёткого логического контроллера, и его программная реализация. Поскольку каждое нечеткое правило представляется нечетким отношением, поведение нечеткой системы управления характеризуется набором данных отношений. Процедура получения результата нечеткого вывода при использовании базы знаний состоит из следующих шагов:
- Определение уровня срабатывания каждого из правил.
- Определение результата нечеткого вывода по каждому из правил.
- Агрегирование индивидуальных результатов нечеткого вывода в общий результат, характерный для всей базы нечетких правил.
Рис. 1 Представление адаптивного ГА как системы нечеткого контроля процесса эволюции
Проектирование НК основывается на качественном описании процесса управления начиная с определения диапазонов изменения значений измеряемых и управляемых переменных, определения необходимого количества термов ЛП и первоначальный вид функций принадлежностей. Параллельно происходит формализация знаний в виде нечетких правил.
В третьей главе представлена разработка алгоритма решения задачи размещения с учетом трассируемости
В параграфе 3.1 описана постановка задачи размещения с учетом трассируемости. Для решения задачи размещения имеются множество конструктивных элементов: Э={эi / i=1, N} и множество соединяющих их цепей: С={сk / k=1, K}.
Свободное пространство между элементами определено множеством фиксированных позиций для установки элементов: T={tj / j=1, M}, причем M N. Нужно найти такое отображение множества Э в множество Т, при котором достигается экстремум целевой функции F.
Для задачи трассировки имеется множество цепей схемы, которое разбивает множество В выводов элементов на непересекающиеся подмножества Bi так, что В = {Bi/i= 1,M}, Вi={bi, k = 1/ki}, где M – число цепей; ki – число контактов, соединяемых i-й цепью. Пространство представлено множеством E = {Er /r = 1,R}.
В задаче размещения с учетом трассируемости рассматривается двухслойная модель коммутационного поля, прямоугольная модель элемента с фиксированными позициями элементов. Оценка длины цепи рассчитывается по алгоритму Прима (описан ниже), данный алгоритм выбран из-за того, что ему соответствует единственно верное решение.
Для решения поставленной многокритериальной задачи оптимизации будем указывать принцип сравнения любых допустимых решений, данный способ будем задавать с помощью критерия оптимальности.
Математическая модель задачи оптимизации представляет собой кортеж <X, D, Q>, где Х – является множеством всех решений (хромосом) для данной задачи, D – ограничения, накладываемые на множество X, для получения допустимых решений и Q – целевая функция (ЦФ), с помощью которой можно определить наилучшее (оптимальное) решение.
При решении задачи размещения с учетом трассируемости данный вектор можно рассмотреть следующим образом:
Х – множество всех хромосом из всех популяций. Пусть Рm – некоторая популяция на шаге m, Pt={h1, h2 … hl}, где hl – хромосома из этой популяции, m=[1,N]; l=[1,M] (N – число популяций, M –число хромосом в популяции).Тогда множество всех решений можно определить: 
.
Множество допустимых решений S. Множество ограничений D. Каждый ген представляет собой структуру размещения каждого отдельного элемента.
Определим математическую задачу оптимизации:
Q:M’R,
где Q – функция, М – пространство решений, R – множество неотрицательных вещественных чисел.
Нам необходимо минимизировать значение критерия Q, т.е. найти такое допустимое решение m'' M', что 
.
Таким образом, можно записать задачу в виде кортежа длины три: <M,D,Q>,
где M пространство решений; D-ограничения, выделяющие в M область допустимых решений M'M; 
: M'R – критерий оптимизации.
Параграф 3.3 представлена разработка гибридного генетического алгоритма решения задачи размещения с учетом трассируемости. Основную роль в решении задачи размещения с учетом трассируемости имеет нечёткий генетический алгоритм с вещественным кодированием. Основную роль в решении задачи размещения с учетом трассируемости имеет нечёткий генетический алгоритм с вещественным кодированием.
- Ввод начальных данных (количество элементов каждого типа, количество цепей, количество контактов и т.д.).
- Задание начального размещения элементов.
- Построение начального множества решений.
- Улучшение качества за счёт использования нечётких генетических операторов.
1) Задание начальных значений управляющих параметров генетического алгоритма;
2) Выбор решений для выполнения операторов;
3)Выбор стратегии поиска оптимальных решений;
4)Применение генетических операторов;
5)Отбор лучших решений;
6)Формирование нового множества решений.
- Переход к задаче трассировки.
- Применение лучевого алгоритма.
- Расчёт полученного значения целевой функции.
- Проверка соблюдения критерия остановки.
- Изменение управляющих параметров алгоритма.
- Возврат к шагу 4 для улучшения качества текущего размещения либо завершение работы алгоритма.
Общая схема решения задачи размещения с учетом трассируемости представлена на рисунке 2.
Рис. 2 Общая схема решения задачи размещения с учётом трассируемости соединений
После улучшения размещения элементов схемы в результате выполнения генетических процедур информация о размещении сохраняется в буфере. Затем проводится трассировка соединений с помощью лучевого алгоритма, оценка качества полученного решения и, при необходимости возврат на этап размещения.
Параграф 3.4 приводится разработанный гибридный нечёткий генетический алгоритм. Входными параметрами алгоритма являются необходимые конструктивные ограничения, управляющие параметры генетического алгоритма, а также топологические параметры схемы.
На вход алгоритма подаются начальные данные для формирования начальной популяции.
Развитие популяции решений происходит на основе двух предложенных стратегий: минимальный разрыв между поколениями или на основе обобщения поколений (формирование стратегий описано ниже).
Основным механизмом получения новых решений является оператор кроссинговера. После применения одного из предложенных генетических операторов кроссинговера: оператор поиска экстремумов, hill-climbing, арифметический кроссинговер и линейный кроссинговер, описанные ниже, рассчитывается целевая функция.
Полученная целевая функция проходит проверку на улучшение решения и проверку на количество заданных итераций, если улучшение есть и количество заданных итераций пользователем закончено, то алгоритм завершает свою работу, в противном случае выполняется повторение.
Рис. 3 Схема работы модифицированного алгоритма размещения
Параграф 3.5 описано кодирование и декодирование решения. Гены представляются напрямую в виде вещественных чисел, т.е. генотип объекта становится идентичным его фенотипу. Вектор хромосомы состоит из вектора вещественных чисел, и точность найденного решения будет определяться не количеством разрядов для кодирования битовой строки, а будет ограничена возможностями ЭВМ, на которой реализуется вещественный ГА.
Применение вещественного кодирования может повысить точность найденных решений и повысить скорость нахождения глобального минимума.
Представим структуру хромосомы в виде векторной структуры в соответствии с площадками, на которых расположены элементы, при этом, когда проектируем хромосому, необходимо учитывать использование хромосомы в нечётких генетических операторах.
Пример генов:
x|0.63222|0.16464|0.9325....
y|0.13334|0.46561|0.7568....
где х=0.63222 и у=0.13334 являются координаты первого элемента
Расположение элементов и свободных посадочных мест для перемещения элементов представлено на рисунке 4.
1,2,3 - свободные посадочные места
Рис. 4 Элементы до расчёта
Производится перерасчёт каждого гена в координату:
G=Sx*xi,
где Sx-размер платы по х, xi – i-й ген.
Рис.5 Перемещение элементов после расчёта
После получения расчётной точки ищем ближайшее свободное поле от полученной точки, и перемещаем элемент, учитывая связь между самими элементами рисунке 4. Данный метод позволяет генерировать хромосомы, не содержащие неприемлемых решений.
В параграфе 3.6 приводится разработка нечётких операторов. Оператор кроссинговера является основным механизмом поиска и создания новых решений в генетических алгоритмах. Применение вещественного кодирования решений при оптимизации и проектировании, позволяет строить множество различных специальных операторов поиска, использующих вероятностные критерии оценки разнообразия популяции решений и «близости» различных решений по отношению друг к другу, основанных на некоторой мере расстояния между родителями. В качестве критериев «близости» решений могут быть использованы, например, расстояние Хэмминга или код Грея.
Модели формирования новой популяции применяют для нахождения наилучших особей в популяции, в алгоритме используем несколько модифицированных моделей операторов поиска: минимальный разрыв между поколениями (ММП), обобщение поколений (ОП).
Модель на основе минимального разрыва между поколениями (ММП).Чередование поколений осуществляется с помощью оператора кроссинговера,
1. Выбираем родителей из популяции произвольно.
2. Создание потомства с использованием оператора кроссинговера.
3. Из родителей и их потомков выбираются лучшие индивидуумы. Отобранные индивидуумы впоследствии заменят своих родителей, происходит отбор “элитных” индивидуумов из полученных потомков заданной популяции.
Модель на основе (ОП). В данной модели поиска выбор рулетки заменяется на выбор решений из двух лучших. При этом модель ОП сохраняет полученные решения с предыдущей итерации. Перекомбинация и выбор оператора происходит следующим образом:
1. Из популяции P(t) выбирается два родителя: лучший родитель и выбранный произвольно.
2. Создаем потомство с использованием оператора кроссинговера.
3. Сравниваем родителей и потомков, производим замену худших наилучшими.
4. Произвольно выбираем два элемента из популяции P(t).
5. Создаём новую подпопуляцию, в которую входят лучший результат, полученные на этапе 3, и выбранные элементы на этапе 4, где количество родителей является начальным задаваемым параметром.
Предлагается модифицированный оператор кроссинговера, который является модификацией оператор поиска экстремума – hill-climbing.
Пусть X = (x1…, xn) и Y = (y1...yn) (xi,yi Є [ai,bi], i=1…n) являются двумя хромосомами с вещественным кодированием, выбранные на основе некой стратегии для выполнения оператора кроссинговера. В результате получаем потомков:
Z1 = (z11... zn1) или Z2 = (z12... zn2),
где zi1 – произвольным образом выбранное число на интервале [li1, ui1], причём
l1i = max{ai,xi - I*} и u1i = min{bi,xi + I* },
а zi2 выбирается на интервале [li2, ui2] и
l2i = max{ai,yi - I*} и u2i = min{bi,yi + I* },
где I = [xi - yi].
| Алгоритм работы оператора кроссинговера: |
Crossover-hill-climbing (p1, p2, noff, nu)
|
Алгоритм работы оператора кроссинговера представлен на рисунке 6.
Рис. 6 Работа оператора кроссинговера
В параграфе 3.7 представлены методы улучшения решения. Для повышения качества улучшения получаемых интегрированных схем предлагается использовать этап трассировки элементов как один из критериев улучшения полученного результата размещения. При этом критерием для процесса трассировки будет процент проведённых трасс и общая длина связи, которая рассчитываться по дереву Прима.
Для ускорения процесса поиска в алгоритме используется нечеткий логический контроллер (НЛК). Используя набор хромосом и их целевые функции, мы можем задать некоторый диапазон значений целевой функции, который нам необходим. Используя понятие нечеткой логики «плохое» и «хорошее» решение, определяем изменение параметров алгоритмов поиска при нахождении каждого решения. При прохождении итерации алгоритма выявляем лучшую целевую функцию, и нечеткий логический контроллер проверяет на попадание ЦФ под какое-либо нечёткое понятие («плохо»/»хорошо»). Если нет, он ничего не делает, и поиск идет с теми же параметрами, что и раньше. Если лучшее решение с лучшим результатом ЦФ подпадает под какое-либо нечёткое понятие, НЛК изменяет параметры поиска в соответствии с теми правилами, которые были определены в начале алгоритма, (рисунок 7).
Рис. 7 Работа нечеткого контроллера
В четвертой главе рассмотрена разработка программных модулей и тестовых систем для оценки практической ценности разработанных алгоритмов.
В параграфе 4.1 представлена теоретическая оценка разработанного комплекса алгоритмов для решения задачи размещения с учетом трассируемости. Алгоритм как объект разработки с одной стороны и средство решения задачи с другой является таким же предметом исследования, как те задачи, которые с помощью него решаются. Вычислив временную сложность алгоритма и определив теоретическую оценку временной сложности можно сделать выводы о практической полезности любого разработанного алгоритма.
В параграфе 4.2 представлены цели экспериментальных исследований. Представлены основные исходные параметры при которых проводились эксперименты.
Параграф 4.3 посвящён описанию разработанного программного продукта. Приводятся основные экранные формы, функциональные возможности программы и форматы файлов используемые в программе.
В параграфе 4.4 содержится описание этапов исследования и их результатов. Результат работы алгоритма с использованием различных операторов кроссинговера и разными поисками популяции. Для анализа качества решений создаваемых оператором hill- climbing было проведён сравнительный анализ с работой операторов арифметического и линейного кроссинговера, при размере популяции – 100, количество потомков -40 и 100 итераций. При этом работа алгоритма с оператором hill- climbing на 10% быстрее, чем работа других операторов кроссинговера.
Было проведено тестирование для определения какой вариантов поиска поколений наиболее эффективен в отношении одного из критерий. Тестирование проводилось со следующими параметрами: размер популяции – 100, количество потомков -40, оператор кроссинговера - hill- climbing.
Таблица 1. Процент не проведённых трасс в различных операторах поисках
| Процент не проведённых трасс | |||||||||
| количество элементов | 30 | 5 | 60 | 5 | 90 | 105 | 120 | 35 | 150 |
| MMg | 0 | 0 | 11 | 1 | 16 | 19 | 18 | 5 | 12 |
| G3 | 0 | 0 | 10 | 0 | 30 | 18 | 19 | 2 | 14 |
Рис. 8 Эффекстивность работы MMg и G3
Из полученных результатов (таблица 1 и рисунок 8) можно сказать, что ММП справляется с поставленной задачей наиболее успешно на схемах с маленьким количеством элементов, ОП удобно использовать для схем с большим объёмом элементов.
В результате проведения экспериментов были определены параметры алгоритмов. Собранные данные позволили определить временную сложность для каждого из алгоритмов. Проведённые исследования показали пригодность к прикладному применению алгоритмов и программы для решения задачи размещения с учётом трассируемости.
Тестирование и экспериментальные исследования проводились с помощью специализированного программного обеспечения (ПО), разработанного на объектно-ориентированном языке C++ в среде Borland Builder 6.0 и Visual C++. Отладка и тестирование проводилось на ЭВМ типа IBM PC c процессором Intel (R) Core (TM) 2Duo CPU с ОЗУ-4,00 GB. Для тестирования использовалась операционная система Microsoft Windows 7 Professional.
В заключении изложены основные выводы и результаты диссертационной работы.
В приложении № 1 даны копии свидетельств о регистрации программ и акты о внедрении результатов диссертационной работы.
В приложении № 2 приведены примеры задачи размещения с учетом трассируемости соединений.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В ходе выполнения диссертационной работы получены результаты:
1. На основе анализа существующих методов размещения обоснована актуальность разработки интегрированных алгоритмов, обеспечивающих получение квазиоптимальных решений за полиномиальное время.
2. Сформулированы стратегии и принципы, построена архитектура интегрированного поиска, позволяющая эффективно управлять поиском, повышать быстродействие системы, получать квазиоптимальных решений за полиномиальное время.
3. Разработана математическая модель нечёткого логического контроллера. Применение нечёткого логического контроллера позволяет использовать нечеткую информацию на каждом шаге эволюции в задаче размещения с учётом трассируемости соединений, с целью обеспечения сходимости целевой функции ГА к глобальному экстремуму.
4. Разработан комплекс алгоритмов решения задачи размещения с учётом трассируемости соединений на основе применения методов генетического поиска и нечёткой логики. Разработаны модифицированные процедуры выполнения генетического оператора кроссинговера на основе вещественного кодирования, позволяющие повысить качество получаемых решений, а так же устойчивость генетического поиска.
5. Разработаны стратегии поиска: минимальный разрыв между поколениями и обобщение поколений, которые позволяют улучшить отбор полученных решений.
6. Построена архитектура интегрированной инструментальной подсистемы, позволяющий проводить сравнительный анализ предложенного алгоритма с уже существующими на основе тестовых задач.
7. Разработанные генетические алгоритмы решения задачи размещения с учётом трассируемости соединений показали преимущество работы по времени и качеству полученных решений. Процесс решения задачи размещения с учётом трассируемости соединений позволяет не только получить решение задачи размещения, но и учесть полученный результат протрассированных соединений. Такая работа позволяет получить улучшенный конечный результат для поставленной задачи пользователем.
8.Возможность управления основными параметрами для задания изначальной схемы и управление процессом генетического поиска позволяет находить оптимальные параметры алгоритмов и повысить качество решений в среднем на 1,5%. –2% по сравнению с представленными методами.
Публикации по теме диссертации:
I. Публикации в центральных изданиях, включенных в перечень периодических изданий ВАК РФ
- Лисовцова А.Е., Гладков Л.А. Грибридные нечеткие генетические системы. Известия ЮФУ. Технические науки. Таганрог: №4, 2008. С.39-42.
- Лисовцова А.Е. Нечеткие генетические алгоритмы в задачах размещения. Известия ЮФУ. Технические науки. Таганрог: №4, 2009. С. 57-62.
- Лисовцова А.Е. Размещение элементов ЭВА с применением вещественного кодирования. Известия ЮФУ. Технические науки. Таганрог: №, 2010. С. 76-81.
- Лисовцова А.Е., Гладков Л.А. Решение задач оптимизации и проектирования схем ЭВА на основе использования гибридных интеллектуальных методов. Всероссийская научно-техническая конференция "Проблемы разработки перспективных микро- и наноэлектронных систем"2010г.
II Свидетельства о регистрации программ на ЭВМ
- Лисовцова А.Е., Гладков Л.А. Программа построения временного графика процесса проектирования с использованием нечеткого генетического алгоритма. Свидетельство о государственной регистрации программы для ЭВМ №2009611076, 2008.
- Лисовцова А.Е., Гладков Л.А. Программа интегрированного решения задач размещения и трассировки. Свидетельство о государственной регистрации программы для ЭВМ №2011611966, 2011.
III. Публикации в других изданиях
- Гладков Л.А., Криницкая А.Е., Кныш Д.С. Решение задач оптимизационных на основе нечетких генетических алгоритмов. «Интеллектуальные системы». Коллективная монография. Выпуск третий./Под ред. В.М. Курейчика – М.: Физматлит, 2009. – с. 86 – 99.
- Лисовцова А.Е. Решение задачи построения временного графика с использованием нечетких алгоритмов. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, и комплексы программ в искусственном интелекте» (ИММВИИ-2009) 1 том, С. 163-170
- Лисовцова А.Е. Задача размещения с использованием вещественного кодирования. Перспективные информационные технологии и интеллектуальные системы, 2009,
№3/4(39/40) с. 72-74
- Лисовцова А.Е. Нечеткие генетические алгоритмы с вещественным кодированием. X всероссийская научная конференция «Техническая кибернетика, радиоэлектроника и системы управления» сборник материалов Таганрог Изд-во ТТИ ЮФУ, 2010. Т.1. -260с. УДК 621.37/39(06)Т382 С. 124-125
- Гладков Л.А., Лисовцова А.Е. Решение задачи размещения с учетом последующей трассировки на основе гибридных нечетких алгоритмов. Интеллектуальные системы. Коллективная монография. Выпуск 5./Под ред. В.М. Курейчика. - М.:Физматлит, 2011. - с.245-262.
- Гладков Л.А., Лисовцова А.Е. Применение нечетких генетических алгоритмов с вещественным кодированием для решения задач оптимизации. Информационные системы и технологии. Теория и практика:/ сборник научных трудов/редколлегия: А.Н. Береза [и др.]. – Шахты: ФГБОУ ВПО «ЮРГУЭС»,2011. – 283с. 113-119
Личный вклад диссертанта в работы, опубликованные в соавторстве:
[4] – разработка алгоритма решения задачи оптимизации и проектирования схем ЭВА с использованием гибридных интеллектуальных методов.
[2-3, 9] методика вещественного кодирования для решения задач размещения.
[7-8] алгоритм решения задач оптимизации с использованием нечетких генетических алгоритмов.
[10-12] комплекс алгоритмов для интегрированного решения задач размещения фрагментов СБИС с учетом трассируемости.
| ЛР 02205665 от 23.06.1997г. | Подписано к печати ___ ________ 2011г. |
| Формат 60х84 1/16 | Печать офсетная. |
| Бумага офсетная. | Усл.п.л. – |
| Заказ № ______ | Тираж 100 экз. |
___________________________________©___________________________________
Издательство Технологического института Южного федерального университета в г. Таганроге
Таганрог, 28, ГСП 17А, Некрасовский, 44
Типография Технологического института Южного федерального университета в г. Таганроге
Таганрог, 28, ГСП 17А, Энгельса,1
