Разработка и исследование интегрированных квантовых и генетических алгоритмов размещения компонентов СБИС

• Автор: Неупокоева, Наталия Викторовна
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Таганрог
• Количество страниц: 163 с. : ил.

Оглавление
Оглавление
Введение.

1. ПРОБЛЕМЫ, ПЕРСПЕКТИВЫ И АНАЛИЗ ЗАДАЧ

РАЗМЕЩЕНИЯ ПРИ КОНСТРУКТОРСКОМ ПРОЕКТИРОВАНИИ

1.1. Анализ задач размещения компонентов СБИС

1.2. Постановка задачи размещения.

1.3. Выводы.

2. ИСПОЛЬЗОВАНИЕ КВАНТОВОГО И ГЕНЕТИЧЕСКОГО ПОИСКА

ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

2.1. Модель задачи размещения.

2.2. Анализ квантового и генетического поиска
при размещении элементов
2.3. Модифицированная архитектура генетического поиска
для размещения элементов
2.4. Алгоритмы анализа квантовых алгоритмов при исследовании графовых моделей
2.5. Выводы.
3. ПОСТРОЕНИЕ КОМБИНИРОВАННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ НА ОСНОВЕ МОДЕЛИРОВАНИЯ ОТЖИГА,
КВАНТОВОГО И ГЕНЕТИЧЕСКОГО ПОИСКА.
3.1. Модифицированный алгоритм размещения на основе
моделирования отжига
3.3. Модифицированные генетические операторы для размещения1
3.4. Выводы
4. АНАЛИЗ РЕЗУЛЬТАТОВ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА
ПРИ РАЗМЕЩЕНИИ ЭЛЕМЕНТОВ.
4.1. Экспериментальные исследования квантового и
генетического алгоритма размещения.
4.2.Анализ вычислительных экспериментов алгоритма
размещения на основе моделирования отжига
4.3. Описание программного комплекса для размещения
разногабаритных элементов
4.4 Выводы.
ЗАКЛЮЧЕНИЕ.
Список литературы


Для эффективного решения задач размещения требуется разработка таких эвристических методов и алгоритмов, которые эффективно реализовывались на ЭВМ. В этой связи используются абстрактные математические модели схем соединений монтажно-коммутационного пространства. Часто задачи размещения решают путем разбиения исходной коммутационной схемы на уровни. Для создания формальной модели в этом случае используются методы оптимального свертывания и разворачивания схем [,]. Опишем идею модифицированного метода свертывания коммутационной схемы. Исходные элементы множества конструкций Б, которые подлежат размещению, отнесем к первому уровню Б1 е Б прадерева свертки. В качестве целевой функции примем отношение локальной степени элемента к числу мультисвязей этого элемента. Такие группы называются центрами наращивания ядра. На втором шаге производится объединение двух или более элементов. Сформированные группы относятся ко второму уровню Б2. Процесс иерархического свертывания аналогичен процессу кристаллизации, когда параллельно выделяются центры, которые в дальнейшем расширяются и объединяются с другими центрами. Процесс продолжается до полного размещения заданного объекта. Приемлемой моделью для размещения, как известно [8,,-,-], являются графы различного вида. Граф должен адекватно отражать конструктивные свойства схемы и нести в себе определенные знания о решаемых задачах. Существует большое число методов построения графовых моделей коммутационных схем, подлежащих размещению. Широко используемый метод [8,,-] заключается в том, что элементам схемы соответствуют вершины графа х;єХ, а электрические цепи представляются ребрами цеи, X—{х,,Х2,. Х|=п, и={и,,и2,. Заметим, что каждый узел в схеме соединений в общем случае должен представляться в графе в полными подграфами. При переходе от схемы соединений к графу за счет развязки узлов (узел соответствует соединению всех элементов между собой), в графе появляются «лишние» ребра, т. Это с одной стороны вносит избыточную информацию, а с другой стороны может позволить перестраивать структуру графа после каждого этапа алгоритма. Например, для условной схемы соединений (рис. С, имеет вид, показанный на рисунке 1. Устраняем в С, в соответствии с цикломатичесмим числом у(С)=6, такие шесть ребер, чтобы в полученном графе не осталось ни одного цикла и он остался связанным. Рис. Условная схема. Рис. Полный подграф. Рис. Первое дерево. Рис. Второе дерево. Очевидно, что в соответствии с формулой Коли (1=пп*2 )| -] можно получить =6 изоморфных деревьев. Часть этих деревьев повторяется, а большее число имеет различную структуру. Пошаговая перестройка дерева подграфа позволяет изменять структуру при размещении элементов. Можно использовать указанный метод для перестройки структуры математической модели. Часто используется метод перехода от схемы соединений к графу, когда контактные площадки под элементы СВИС представляются вершинами графа, а соединения между ними - ребрами. При этом полученный граф в представляет собой объединение полных подграфов схемы. Возможно использовать перестроение деревьев и поддеревьев после каждого шага алгоритма [-]. На рис. Контакты (вершины графа) соединяются друг с другом по цепочечной структуре, образуя множество 8={<1,2>, <2,3>, <3,4>, <4,5>, <5,6>, <6,7>, <7,8>,<8,1>}. Элементы этого множества являются кортежами. Каждый кортеж задает ребро графа или упорядоченное соединение. На рис. При этом 8={<1,4>, <2,3>, <6,7>, <5,8>}. На основе информации о таком расположении контактов определим два типа бинарных отношений ф= <Б,М> . В первом отношении ]/1= <Б ЬМ> реализуется отношение соседнего следования (рис. Во втором отношении і|/2= <Р 2,М> реализуется отношение вложения соединений (рис. Здесь Р, Рі, Р 2 - графики отношений, М - множество, М= {1, . Аналогично отношение 1 \i на рис. Можно описать любые возможные способы представления коммутационных моделей СБИС на кристалле. При анализе соединений внутри блока используются вертикальные (рис. При расположении компонентов внутри друг друга предлагается модель, показанная на рис.