Содержание к диссертации
Введение
ГЛАВА I. АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ЭЛЕКТРОННЫХ УСТРОЙСТВ 11
1.1. Постановка задачи размещения элементов и анализ методов ее решения 11
1.2. Вычислительная сложность задачи размещения элементов электронных устройств и пути ее уменьшения для задач большой размерности 19
1.3. Особенности применения методов декомпозиции и макромоделирования при размещении элементов электронных устройств 24
1.4. Выводы 33
ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ЭЛЕКТРОННЫХ УСТРОЙСТВ НА ОСНОВЕ МЕТОДА МНОГОУРОВНЕВОЙ ДЕКОМПОЗИЦИИ И МАКРОМОДЕЛИРОВАНИЯ 34
2.1. Математические модели, применяемые в алгоритмах размещения 34
2.1.1. Описание исходной схемы 34
2.1.2. Описание пространства для размещения элементов 45
2.2. Постановка задачи оптимального размещения элементов 52
2.3. Алгоритмы размещения на основе многоуровневой декомпозиции и макромоделирования 57
2.4. Вычислительная сложность алгоритмов размещения 84
2.5. Выводы 87
ГЛАВА 3. РАЗРАБОТКА БАЗОВЫХ ПРОЦЕДУР АЛГОРИТМОВ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ 88
3.1. Разбиение схемы на части 88
3.2. Формирование макромоделей 98
3.3. Формирование обобщенного пространства для размещения макромоделей 103
3.4. Базовая процедура размещения 110
3.5. Организация обхода макромоделей и оптимизация размещения 124
3.6. Выводы 129
ГЛАВА 4. ОРГАНИЗАЦИЯ И ФУНКЦИОНИРОВАНИЕ ДЛЯ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ЭЛЕКТРОННЫХ УСТРОЙСТВ НА ОСНОВЕ МЕТОДА МНОГОУРОВНЕВОЙ ДЕКОМПОЗИЦИИ И МАКРОМОДЕЛИРОВАНИЯ 131
4.1. Архитектура пакета и особенности его функционирования 132
4.2. Структуры данных 148
4.3. Экспериментальные исследования особенностей функционирования пакета 164
4.3.1. Исследование алгоритмов размещения макромоделей 165
4.3.2. Исследование влияния формы участков для макромоделей на результаты размещения 167
4.3.3. Исследование особенностей базовой процедуры размещения элементов 171
4.4. Выводы 180
ЗАКЛЮЧЕНИЕ 182
ЛИТЕРАТУРА 185
- Постановка задачи размещения элементов и анализ методов ее решения
- Математические модели, применяемые в алгоритмах размещения
- Разбиение схемы на части
- Архитектура пакета и особенности его функционирования
Введение к работе
Разработка современной сложной радиоэлектронной аппаратуры немыслима без всестороннего использования автоматизированных систем на всех этапах проектирования, включая конструирование. Решениями ХХУІ съезда КПСС и XII съезда БКП предусмотрено расширять автоматизацию проектно-конструктор-ских и научно-исследовательских работ с применением электронно-вычислительной техники. Непрерывное совершенствование технологии производства и возрастание сложности и степени интеграции радиоэлектронной аппаратуры требуют повышения эффективности САПР на основе применения новых средств и методов.
Многие из задач конструкторского проектирования трудно формализуются и не существует единого развитого математического подхода к их решению. Возможность прямого поиска оптимальных решений исключена из-за большой сложности современных конструкций. Для преодоления этих трудностей эффективными являются декомпозиционные методы и методы макромоделирования, позволяющие сократить количество неизвестных в задачах конструкторского проектирования.
Одной из наиболее важных является задача размещения элементов электронных устройств, качественное ее решение обеспечивает благоприятные условия для последующей трассировки соединений. Недостатком существующих методов начального размещения является отсутствие глобальных оптимизационных процедур, что не обеспечивает получения качественного результата. В связи с этим актуальной для задач размещения большой размерности является дальнейшая разработка и применение методов многоуровневой декомпозиции и макромоделирования, сущность которых состоит в иерархическом многоэтапном начальном размещении на уровне блоков (макромоделей), представляющих некоторые группы сильно связанных между собой элементов схемы, с последующей его оптимизацией на каждом уровне разбиения.
Целью диссертационной работы является разработка и исследование методов и алгоритмов размещения элементов электронных устройств на основе многоуровневой декомпозиции и макромоделирования и их реализация в виде ШШ для применения в системах автоматизации проектирования сложных конструктивных узлов электронной аппаратуры.
Для достижения указанной цели в диссертационной работе решаются следующие задачи.
Анализ существующих методов размещения элементов электронных устройств с целью оценки их пригодности для решения задач большой размерности.
Разработка математической модели для многоуровневого иерархического размещения элементов электронных устройств с применением макромоделирования.
Разработка алгоритмов размещения элементов на основе метода многоуровневой декомпозиции и макромоделирования.
Разработка базовых процедур алгоритмов размещения.
Разработка ППП для размещения элементов электронных устройств.
Разработка структур данных, обеспечивающих эффективное функционирование пакета при решении задач большой размерности.
Апробация разработанных алгоритмов путем исследования их эффективности при реальном проектировании конструктивных узлов электронной аппаратуры.
При решении поставленных задач применялись теория множеств, теория графов, теория систем, методы исследования операций. Реализация алгоритмов проводилась с использованием методов структурного программирования.
В итоге проведенных исследований получены следующие новые научные результаты:
Развит метод многоуровневой декомпозиции и макромоделирования применительно к решению задач размещения большой размерности без ограничения на число частей разбиения и число уровней иерархии, а также без ограничения на геометрические характеристики конструктива.
Разработан рекурсивный алгоритм многоуровневого размещения элементов, обеспечивающий эффективную реализацию, программного обеспечения.
Предложены точечная и распределенная макромодели, позволяющие размещать элементы на всех уровнях иерархии с учетом или без учета их геометрических характеристик.
На основе выявленной корреляции между структурой дерева оптимального свертывания схемы и результатами размещения элементов предложен алгоритм разбиения схемы, сохраняющий естественно сформировавшиеся группы элементов.
Рассмотрены возможные способы формирования обобщенного пространства для размещения макромоделей и разработан подход, позволяющий эффективно разбивать дискретное поле на части и формировать топологию участков.
Разработан алгоритм оптимизации размещения с использованием метода сканирующей области для нерегулярного дискретного рабочего поля, получаемого на верхних уровнях процесса многоуровневого размещения.
7. Разработана компактная иерархическая управляемая структура данных, обеспечивающая универсальность и расширяемость пакета.
Значение полученных результатов для практики заключается в следующем: применение разработанного ІШП для размещения элементов на основе метода многоуровневой декомпозиции и макромоделирования позволяет повышать качество узлов и устройств сложной радиоэлектронной аппаратуры; наличие расширяемой библиотеки критериев размещения позволяет настраивать пакет на конкретные конструктивно-технологические требования; развитая методология решения задачи применима к широкому кругу объектов проектирования: печатным платам, панелям, интегральным схемам ( в том числе матричным БИС), а также для размещения групп связанных объектов в других областях техники; разработанный пакет реализован на языке Фортран и может эксплуатироваться в среде ОС на ЕС ЭВМ. Пакет обладает средствами для включения в действующие САПР в качестве составной части прикладного программного обеспечения. Управляемая структура данных облегчает его модификацию и сопровождение .
Теоретические и практические результаты диссертационной работы использовались в ряде научно-исследовательских работ, выполнявшихся в I98I-I984 гг. на кафедрах конструирования и технологии производства радиоаппаратуры и прикладной математики Львовского политехнического института, а также используются в настоящее время в работах, выполняющихся по Целевьм комплексным научно-техническим программам
ГКНТ СССР и Минвуза СССР на 1981 - 1985 гг. На базе основных результатов диссертационной работы реализован пакет прикладных программ для ЕС ЭВМ, использующийся в учебном процессе.
Основные результаты диссертационной работы докладывались на следующих научно-технических конференциях и семинарах: Всесоюзной конференции "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации САПР радиоэлектронной аппаратуры", г.Ереван, 1983 г.; У Всесоюзном совещании по автоматизации проектирования электротехнических устройств "Моделирование и оптимизация проектных решений в САПР", г.Таллин, 1983 г.; XI Всесоюзном совещании-семинаре "Современная элементная база ЭВМ и методы ее проектирования с помощью САПР", г.Симферополь, 1983 г.; Всесоюзном научно-техническом совещании "Автоматизация проектирования микро-злектронной аппаратуры", г.Владимир, 1983 г.; областном семинаре "Автоматизация конструкторского проектирования РЭА и ЭВА", г.Пенза, 1983 г.; XII Всесоюзном совещании-семинаре "Автоматизация проектирования микропроцессоров, микропроцессорных систем и СБИС", г.Симферополь, 1984 г.; республиканской конференции "Автоматизация технического проектирования цифровой аппаратуры", г.Каунас, 1984 г.; научно-технических конференциях Львовского политехнического института, г.Львов, 1982-1984 гг.
По материалам диссертации опубликовано 5 печатных работ.
Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 85 наименований. В работе 50 рисунков и б таблиц.
В первой главе дан анализ существующих методов размещения элементов узлов электронной аппаратуры с целью оценки их пригодности для решения задач большой размерности. Рассматриваются пути уменьшения вычислительной сложности задачи размещения и особенности применения методов, основанных на разбиении схемы на части.
Во второй главе предложена математическая модель задачи размещения, обеспечивающая идентичное представление информации на всех уровнях декомпозиции устройства. Определены понятия "точечная" и "распределенная" макромодели. Разработано семейство рекурсивных алгоритмов для размещения элементов электронных устройств на основе метода многоуровневой декомпозиции и макромоделирования. Дана оценка вычислительной сложности выбранного алгоритма размещения.
В третьей главе разработаны основные процедуры алгоритма размещения элементов, а именно: процедура разбиения схемы на части, процедура формирования макромоделей, процедура формирования обобщенного пространства для размещения макромоделей, процедура обхода макромоделей, базовая процедура размещения макромоделей (элементов) и процедура оптимизации размещения.
В четвертой главе рассмотрены организация и особенности функционирования разработанного ПШ для размещения элементов электронных устройств. Обоснована важность принципов развития и инвариантности. Дан подробный анализ влияния структур данных на качество программного обеспечения. Приведены результаты экспериментальных исследований.
В работе автор защищает:
I. Математическую модель задачи размещения, обеспечивающую идентичное представление информации на всех уровнях декомпозиции устройства.
Семейство рекурсивньк алгоритмов для размещения элементов электронных устройств на основе метода многоуровневой декомпозиции и макромоделирования.
Базовые процедуры алгоритмов размещения элементов.
Пакет прикладных программ для размещения элементов электронных устройств на основе метода многоуровневой декомпозиции и макромоделирования.
Экспериментальные результаты исследования разработанных алгоритмов.
Постановка задачи размещения элементов и анализ методов ее решения
Основной целью задачи размещения элементов следует считать создание наилучших условий для последующей трассировки соединений и удовлетворение основных требований, обеспечивающих работоспособность и высокое качество устройства [1,24,46,53,56,64].
В общем виде задачу размещения элементов можно описать следующим образом [1,24,46,53,56,64] . Дано множество конструктивных элементов, связанных между собой в соответствии с принципиальной электрической схемой узла. Требуется разместить элементы на некотором коммутационном поле таким образом, чтобы выбранный показатель качества достигал экстремального значения. Предполагая, что на монтажно-коммутаци-онном поле заданы фиксированные позиции, в которых допускается установка элементов, все алгоритмы размещения элементов можно разделить на точные и приближенные (эвристические). Со своей стороны, приближенные алгоритмы могут быть конструктивные (формирующие начальное размещение) и итерационные (оптимизирующие размещение элементов).
Точное решение задачи размещения элементов на фиксированном множестве позиций обеспечивает полный перебор вариантов с оценкой их по заданному критерию качества размещения. Однако экспоненциальный рост количества вычислений делает такой подход неприменимым на современных ЭВМ (10 оп./сек.) при разумном времени счета в один час уже для П II, где П - количество размещаемых элементов
Г 33,74] . Повышение быстродействия ЭВМ незначительно передвигает верхнюю границу применимости полного перебора вариантов.
Полного перебора всех вариантов можно избежать, если между размещаемыми элементами не существует связей. В таком случае задача размещения элементов сводится к задаче линейного назначения, для которой существуют эффективные точные методы [35] , позволяющие получить решение даже для
П 100. Однако на практике для электронных схем такая ситуация нереальна и может быть использована только в частных случаях при декомпозиции сложной задачи размещения на отдельные подзадачи.
Математические модели, применяемые в алгоритмах размещения
Адекватным теоретико-множественному описанию схемы (2.1, 2.8, 2.10) является представление схемы гиперграфом Н-(Р, Е), где г - множество вершин гиперграфа, соответствующее элементам, а Б - множество ребер гиперграфа. Множество Е порождается набором многоарных отношений, существующих на множестве г и соответствующих цепям схемы. Обычно ребра гиперграфа Н=(Р,Е) задаются в виде описания цепей (2.10). Гиперграф, соответствующей схеме из рис.2.4,а, показан на рис.2.4,в.
Для упрощения алгоритмической обработки схемы в некоторых случаях гиперграф трансформируют в граф [56 ] . Для этой цели каждую цепь, связывающую множество элементов, перобразуют в полный граф на этом множестве. Мультиграф всей схемы получается путем объединения полных графов цепей (рис. 2.4,г). Кратность ребер между вершинами мультиграфа равна количеству цепей, связывающих соответствующие элементы. Поскольку для соединения выводов одной цепи используется дерево, а не полный граф, представление схемы в виде мультиграфа является неточным. Поэтому всем ребрам полного графа описания цепи Є присваивается некоторый вес J4 ) учитывающий вероятность реализации отдельного ребра где (і(в ) - количество элементов в описании цепи. В таком случае вес каждого ребра графа схемы получают путем сложения весов всех кратных ребер [56] . Взвешанный граф схемы показан на рис. 2.4,д. Такой граф может быть описан с помощью матрицы смежности где С ; - вес ребра, связывающего элементов и .
Описание схемы в виде матрицы (2.22) используется для многих алгоритмов размещения [46,56,64,72] . Однако такое представление также является не совсем точным [64] , поэтому в дальнейшем будем использовать описание цепи в виде множества элементов, связанных с данной цепью (2.10). Принятое нами описание цепей является более естественным, гибким и универсальным, а в перспективе предоставляет возможность связать процесс размещения элементов с трассировкой цепей.
Разбиение схемы на части
Последовательных методов разбиения схемы [44, 56] заключается в выборе по определенному правилу элемента или группы элементов, к которым присоединяются другие элементы схемы с целью образования первой части. Далее процесс повторяется. Последовательные алгоритмы допускают различные модификации, связанные с представлением схемы и вычислением оценок, управляющих процессом разбиения. Они хорошо работают при небольшом количестве элементов. Увеличение размерности задачи приводит к неравноправному выбору элементов и к ухудшению качества разбиения. Для оптимизации полученного решения используются итерационные алгоритмы [44,56 ] , суть которых состоит в перестановке по некоторым правилам элементов из одной части в другую, с целью минимизации числа внешних соединений.
Третья группа алгоритмов разбиения параллельно-последовательного типа основана на методе оптимального свертывания схемы, позволяющего эффективно выделять группы сильно связанных между собой элементов [3] . Результат свертывания схемы представляется деревом I (рис.3.1). Метод построения дерева Т заключается в следующем. Все исходные элементы схемы (множество г ) относятся к первому уровню дерева свертки Р = Р .На первом шаге по выбранному критерию из множества г выделяются равноценные группы, соедражщие два или более элементов, которые относятся к множеству вершин Р второго уровня дерева свертки. "Несвернутые" вершины первого уровня считаются условно принадлежащими второму уровню. На следующем шаге из множества вершин второго уровня г (включая и несвернутые вершины г ) формируется множество третьего уровня и так до тех пор, пока все вершины не будут объединены в одноэлементном множестве г э соответствующем корню дерева свертки. Тривиальными вершинами дерева являются вершины уровня г и корень дерева. Все остальные вершины представляют естественным образом сформированные группы элементов, позволяющие эффективно выполнять разбиение схемы на части.
На основе полученного дерева оптимального свертывания схемы возможны различные алгоритмы разбиения по критерию минимума числа межсоединений Г 3,8] . G другой стороны, применение указанного критерия часто приводит к "расформированию" некоторых вершин дерева с целью минимизации количества межсоединений Г 6] . Полученные макромодели являются неустойчивыми и при последующей оптимизации размещения часть из них распадается (рис. 3.2), т.е. разбиение схемы по указанному критерию неполностью соответствует требованиям последующего размещения элементов.
Архитектура пакета и особенности его функционирования
Предметная область пакета включает задачи получения начального размещения элементов РЭА и его оптимизацию. Пакет не привязан к конкретному типу конструктива и в соответствии с принятой моделью пространства размещения (параграф 2.1.2) позволяет размещать одногабаритные элементы с регулярным и нерегулярным расположением (ТЭЗ с односторонним и двусторонним размещением элементов, матричные БИС, панели и др.). При соответствующей модификации алгоритма разбиения существует возможность размещения разногабраитных элементов до уровня групп с примерно одинаковой суммарной площадью. Постановка задачи (параграф 2.2) допускает также применение пакета для размещения группы связанных объектов в других областях народного хозяйства (размещение объектов промышленных предприятий и т.п.).
Пакет реализован в виде программного комплекса [26J, использующего базовые средства операционной системы EG ЭВМ для управления вычислительным процессом и работы с данными. По мере развития пакета допускается его перерастание в программную систему.
Пакет имеет многоуровневую иерархическую структуру, каждый уровень которой включает следующие компоненты (рис.4.I):
- входной язык;
- транслятор с входного языка;
- управляющую программу;
- функциональное обеспечение;
- базу данных.
Входной язык пакета является искусственным и проблемно ориентированным f37]. Краткость искусственного языка и полный контроль данных и управляющих параметров, осуществляемый транслятором, при сравнительно узкой предметной области пакета более предпочтителен для пользователя по сравнению с развернутым естественным языком [70]. При необходимости транслятор с естественного языка может быть разработан и подключен к пакету в виде интерфейсного модуля (рис.4.2,а). Стандартизованная форма записи данных и управляющих параметров во входном языке позволяет осуществлять связь пакета с банком данных САПР [51] на уровне входного языка при помощи интерфейсных модулей (рис.4.2,б). Представляется возможным также непосредственное взаимодействие интерфейсного модуля с базой данных пакета. При этом, однако, необходимо реализовать в интерфейсе полный контроль данных, выполняемый обычно транслятором пакета.
