Размещение элементов электронных узлов методом многоуровневой декомпозиции и макромоделирования и реализация на его основе ППП для САПР РЭА

• Автор: Николов, Николай Пенчев
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Львов
• Количество страниц: 196 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

ГЛАВА I. АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ

ЭЛЕМЕНТОВ ЭЛЕКТРОННЫХ УСТРОЙСТВ.II

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

анализ методов ее решения . II

1.2. Вычислительная сложность задачи размещения

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

1.3. Особенности применения методов декомпозиции и макромоделирования при размещении

элементов электронных устройств . .

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


Кроме того, в некоторых случаях при плохом начальном размещении возможно "вырождение” метода и появление патологических задач, в которых эффективность резко падает из-за необходимости реализации почти полного перебора всех вариантов. Большинство реализации метода ветвей и границ применительно к размещению элементов ориентировано на решение задачи квадратичного назначения. Идеи метода применимы и к задаче размещения в общем виде (наличие многозвенных соединений), однако за счет усложнения оценки функционала и поиска нижней границы размерность решаемой задачи снижается [] . Реальные задачи размещения имеют размерность, значительно превышающую возможности точных методов. Эти методы используют интуитивные подходы конструктора к оценке качества получаемого решения. Сам результат обычно не является оптимальным, но, с другой стороны, он удовлетворяет потребности практики или, по крайней мере, является лучшим по сравнению с результатами других методов. Широкое распространение получили последовательные конструктивные алгоритмы размещения элементов [,,,]). Качество получаемого решения и эффективность указанных алгоритмов вполне удовлетворительны для задач небольших размерностей. Такие алгоритмы не требуют начального размещения и их основная идея состоит в следующем. Все элементы упорядочиваются по некоторому признаку. В установленной очередности для каждого из них отыскивается наилучшая позиция. Критерием может служить суммарная длина связей с уже размещенными элементами. Далее процесс повторяется для остальных элементов и свободных позиций и так до тех пор, пока не будет получено размещение для всех элементов. Структура любого последовательного алгоритма размещения определяется правилами выбора очередного элемента и позиции для его установки [,] . Пусть Р = {р4} рг^. Отметим, что в первом случае должен быть особо определен способ установки первого элемента. Любое правило выбора элемента для размещения основано на вычислении "меры связности” еще не размещенных элементов с размещенными. Мера связности может иметь различные формы представления и в тривиальном случае измеряется количеством соединений между элементами и . Очередным размещаемым элементом является элемент, имеющий максимальное значение характеристики (I. I), т. Выбор в данном случае осуществляется на основе максимального значения характеристики (1. Существует также ряд других модификаций правила выбора элемента [,] . Выбранный для размещения элемент должен быть установлен в одну из незанятых позиций. Эта позиция выбирается с учетом минимизации значения критерия размещения. В принципе возможен подход [], когда при установке элемента в позицию рассчитываются трассы соответствующих соединений, что является критерием для выбора позиции. Однако большая вычислительная сложность процесса построения трасс резко снижает эффективность процесса размещения и ограничивает применимость указанного подхода. Поэтому на практике используются приближенные оценки для соединений (площадь соединения, полупериметр охватывающего прямоугольника, конфигурация соединения и т. Последовательные алгоритмы хорошо работают при относительно небольшой размерности задачи размещения. Повышение размерности ведет к ухудшению качества получаемого размещения из-за неполного учета всех связей мевду элементами. Особенно затруднен поиск подходящего элемента и позиция для него на последних этапах работы алгоритма. Этот недостаток отсутствует в алгоритмах размещения, основанных на разбиении схемы. Ввиду особого интереса к этим алгоритмам, они будут рассмотрены отдельно в третьем параграфе настоящей главы. Результатом работы конструктивных алгоритмов (последовательных и основанных на разбиении схемы) является начальное размещение элементов. Сущность итерационных алгоритмов состоит в многошаговом улучшении локально оптимального значения функционала, по которому оценивается качество размещения. Для этой цели исследуется подмножество вариантов размещения в некотором смысле близких к начальному, с целью выделения варианта размещения элементов с лучшим значением функционала.