авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 |

Разработка и исследование интегрированных алгоритмов размещения элементов на основе методов эволюционного моделирования

-- [ Страница 1 ] --

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

БАЛЮК Любовь Владимировна

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

ИНТЕГРИРОВАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ НА ОСНОВЕ МЕТОДОВ ЭВОЛЮЦИОННОГО МОДЕЛИРОВАНИЯ

Специальности: 05.13.12 – Системы автоматизации проектирования, 05.13.17 – Теоретические основы информатики

Автореферат

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

кандидата технических наук

Таганрог 2007

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

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

Курейчик Владимир Викторович.

Научный консультант: кандидат технических наук, доцент

Нужнов Евгений Владимирович.

Официальные оппоненты: доктор технических наук, профессор
Ковалев Сергей Михайлович (Ростовский государственный университет путей и сообщений, г. Ростов-на-Дону),


кандидат технических наук, доцент
Родзин Сергей Иванович (Технологический институт Южного федерального университета в г. Таганроге).

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

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

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

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

Автореферат разослан « 1 » июня 2007 г.

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

диссертационного совета Д 212.208.22,

доктор технических наук, профессор Целых А.Н.

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

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

Большой вклад в разработку и исследование интеллектуальных систем автоматизированного проектирования (САПР) ЭВС внесли В.И. Анисимов, Б.В. Баталов, Д.И. Батищев, А.М. Бершадский, Л.С. Берштейн, Ю.Х. Вермишев, В.М. Курейчик, В.В. Курейчик, Н.Я. Матюхин, А.Н. Мелихов, И.П. Норенков, В.А. Селютин, Ш. Айкерс, М. Бреуэр, Н. Шервани и многие другие.

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

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

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

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

Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института Южного федерального университета в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 – 2008 гг.) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

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

  1. Построена архитектура интегрированного бионического поиска решения задачи размещения фрагментов БИС.
  2. Разработаны бионические алгоритмы размещения.
  3. Построены модифицированные генетические операторы.

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

Научная новизна работы заключается в решении задачи размещения фрагментов БИС на основе интегрированного подхода. В работе:

  1. Построена архитектура интегрированного поиска решений задачи размещения фрагментов БИС, основанного на методах эволюционного моделирования.
  2. Разработаны новые и модифицированные методы эволюционного моделирования, позволяющие частично решать проблемы предварительной сходиомсти алгоритмов.
  3. Разработан модифицированный алгоритм Ant Colony размещения фрагментов БИС, позволяющий получать множество квазиоптимальных решений.
  4. Построены новые и модифицированные операторы генетического поиска, ориентированные на задачи автоматизированного конструкторского проектирования и позволяющие сокращать область поиска.
  5. Разработаны стратегия интегрированного поиска на основе заданных критериев оптимизации с использованием параллельных вычислений и механизм синхронизации полученных решений на всех этапах поиска (оператор миграции).

К числу наиболее важных научных результатов диссертации относятся:

    • новая интегрированная архитектура процесса размещения фрагментов и/или групп фрагментов БИС, основанная на методах эволюционного моделирования;
    • новая модифицированная архитектура алгоритма Ant Colony для решения задачи размещения фрагментов БИС;
    • новые и усовершенствованные операторы генетического поиска на основе «Золотого сечения», кодов Хаффмана, метода «Простых чисел», обеспечивающие уменьшение времени поиска.

Практическая ценность работы заключается в реализации программного комплекса «In4Placement», использование которого позволяет на 10-30% ускорить процесс синтеза сложных систем, повысить качество размещения на 29% по сравнению с существующими аналогами, благодаря использованию интегрированного подхода к решению задачи размещения. Данная среда позволяет автоматизировать процесс размещения, сделать его доступным для специалистов различных областей науки, не обладающих навыками программирования.

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Таганрогского государственного радиотехнического университетаТехнологического института Южного федерального университета «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при преподавании следующих дисциплин: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях: «Интеллектуальные САПР», (г. Таганрог, 2003 - 2005 гг.); VII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», (г. Таганрог, 2004г.); II Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2004 г.); Международная конференция «Интеллектуальные системы (IEEE AIS’04)», (с. Дивноморское, 2004 г.); III Всероссийская научная конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», (г. Таганрог, 2005 г.); 1 ежегодная научная конференция студентов и аспирантов базовых кафедр ЮНЦ РАН, (г. Ростов-на-Дону, 2005 г.), Международная конференция «Интеллектуальные системы (IEEE AIS’05)», (с. Дивноморское, 2005 г.); Международная конференция «Интеллектуальные системы (IEEE AIS’06)», (с. Дивноморское, 2006 г.); Международная научно-техническая конференция «Интеллектуальные САПР», (г. Таганрог, 2006 г.).

Получено свидетельство об официальной регистрации программы для ЭВМ № 2006613139, 2006 г.

Публикации. По теме диссертационной работы опубликовано 10 печатных работ, из них 6 статьей, сделано 4 доклада на Всероссийских и Международных научно-технических конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 157 страницах, содержит 51 рисунок, 4 таблицы, 112 наименований библиографии и приложения.

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

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

В первой главе рассмотрены основные проблемы и перспективы решения задач размещения, приведена постановка задачи размещения фрагментов БИС. Решаемая в диссертационной работе дискретная задача размещения может быть сформулирована следующим образом. На прямоугольную конструкцию накладывается Декартова система координат с осями s и t, определяющая граф Gr, задающий собой координатную решетку.

Задача размещения сводится к отображению заданного графа-модели G=(X,U) схемы в решетку Gr таким образом, чтобы множество вершин , , графа G размещалось в узлах решетки, число которых конечно, а также соблюдался интегрированный критерий Compl(G), представляющий собой интегрированную целевую функцию (ЦФ):

(1)

где:

  • L_Kr(G) – длина критических связей (длина гамильтоновых цепей в графе);
  • L_GA(G) – величина суммарной длины соединений стремилась к минимуму;
  • N_Kr>0 и N_GA=0 – условие оптимизации ЦФ, основанное на соблюдении критерия длин критических связей;
  • N_Kr=0 и N_GA>0 – условие оптимизации ЦФ, основанное на выполнении критерия суммарной длины соединений;
  • N_Kr>0 и N_GA>0 – условие оптимизации ЦФ, основанное на одновременном соблюдении критериев длин критических связей и суммарной длины соединений;
  • , – коэффициенты полезности вышеуказанных критериев, которые определяются на основании конструкторского опыта или экспертных оценок;
  • Compl_Kr(G) – комплексный критерий оценки качества размещения на основе длин критических связей, определяющийся формулой:

(2)

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

Суммарная длина (весовая функция) рассчитывается по формуле «достроенной» критической связи:

(3)

где:

  • - расстояние между вершинами и графа G, отождествленными с узлами i и j решетки;
  • - число кратных ребер между этими вершинами.

Выходная информация представляет собой список S, T координат на КП для всех модулей.

Требование оптимизации: Compl(G) min, т.е. чтобы весовая функция была наименьшей для всевозможных способов отождествления вершин графа и узлов решетки.

Пространство решений – множество всех целых чисел. Ограничения:

  • 2n10000, где n – число вершин в графе G;
  • , если ,
  • , если ,
  • >0, элементы в силу геометрических ограничений не могут накладываться друг на друга.

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

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

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

  1. анализ графовой модели коммутационной схемы, полученной на этапе выполнения предыдущего шага конструкторского проектирования (решения задачи компоновки), с использованием модифицированного алгоритма Ant Colony (MAАС);
  2. создание начальных популяций альтернативных решений размещения фрагментов БИС на основе результатов выполнения п. 1;
  3. реализация методов эволюционного моделирования в соответствие с выбранным критерием оценки качества размещения:
    1. реализация быстрого эволюционного поиска (использование оператора мутации);
    2. выполнение генетического поиска (использование различных генетических операторов);
  4. адаптация полученных решений к внешней среде на основе метаэволюции (использование оператора миграции);
  5. вывод окончательного размещения и переход на следующий шаг конструкторского проектирования – решение задачи трассировки.

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

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

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

В третьей главе разработан интегрированный алгоритм, представленный на рис. 1.

 Рис 1. Структурная схема интегрированного-15

Рис 1. Структурная схема интегрированного алгоритма размещения фрагментов БИС

Он основан на использовании методов эволюционного моделирования: модифицированного алгоритма Ant Colony (МАAC), усовершенствованного бионического поиска для решения задачи размещения фрагментов БИС. Здесь:

  • N_GA – число итераций генетического алгоритма размещения фрагментов БИС,
  • Nmax – число итераций интегрированного алгоритма,
  • t – текущая итерация интегрированного алгоритма,
  • N_om – число итераций эволюционного алгоритма размещения,
  • Compl – значение комплексного критерия оценки качества размещения,
  • N_Kr – число критических связей,
  • L_Kr(G) – длина критических связей в графовой модели схемы.

Модификация алгоритма Ant Colony (AC) используется как блок анализа перед моделированием модифицированного бионического поиска. Далее выполняется коррекция размещения на основе выбранных критериев оценки качества двумерного размещения: суммарной длины соединений и длин критических связей в графовой модели коммутационной схемы. Коррекция заключается в выделении и размещении «строительных блоков» и и/или фрагментов БИС, не входящих в сформированные строительные блоки (СБ).

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

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

Эвристика 1 эффективна при небольшом числе (n<1000) вершин графовой модели КС и заключается в том, что:

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

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

Эвристика 1 позволяет повысить быстродействие предложенного автором интегрированного алгоритма и при количестве вершин графа n<1000. При этом первые w<<n (w=1, 2,…, n) вершин графа группируются в строительные блоки, фиксируются в линейке на основе эвристики 1. Остальные (n–w) вершин графа размещаются на основе эволюционной части модифицированного бионического алгоритма. Отметим, что величину w задает экспертная подсистема размещения.

Эвристика 2 выполняется, если количество вершин больше 1000, и состоит в следующем:



Pages:   || 2 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.