Исследование и разработка задач размещения разнотипных элементов при автоматизированном проектировании узлов ЭВМ

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

Глава I. ОБЗОР ЗАДАЧ И МЕТОДОВ РАЗМЕЩЕНИЯ РАЗНОГАБА

РИТНЫХ ЭЛЕМЕНТОВ .

1.1. Постановка задачи .

1.2. Алгоритмы , используюшие методы оптимального

раскроя материалов

Методы плотного размещения

Размещение с использованием аналитических и дискретной моделей элементов

1.3. Анализ задачи и известных алгоритмов

Глава 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ С УЧЕТОМ ТРЕБОВАНИЙ ТРАССИРОВКИ

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


Во введении обоснована актуальность темы, сформулированы основные цели и направления исследований, кратко изложено содержание диссертационной работы. В первой главе приведен обзор известных постановок задач и методов размещения разногабаритных элементов. Показано, что в задаче, первоначально возникшей при размещении электрорадиоэлементов, преобладают методы,заимствованные из теории раскроя материалов. Описаны разработанные постановки и модели, два алгоритма, заимствованные из методов оптимального раскроя, алгоритм плотного размещения, алгоритмы, использующие аналитические и дискретные модели элементов. Главу завершает анализ задачи и известных алгоритмов ее решения. Вторая глава посвящена разработке математической модели задачи, учитывающей требования и ограничения трассировки печатных плат современных цифровых узлов. Разработаны модели схемы и печатной платы цифрового узла применительно к наиболее распространенному в цифровой аппаратуре виду печатных плат - двухсторонним. Описаны точная формальная постановка задачи и ванней-шие оптимизационные алгоритмы, используемые в приближенном подходе к решению задач реальной сложности. Сформулирована и решена задача оптимального представления ортогонального графа (печатной платы) упрощенной клеточной моделью. Материал главы является теоретической основой для описанного в заключении приближенного алгоритма размещения. В четвертой главе приведены результаты реализации, экспериментального исследования и внедрения разработанных моделей и алгоритмов. Описаны организация системы автоматизированного проектирования и входящая в нее подсистема программ размещения элементов, основу которой составляют разработанные в диссертации алгоритмы. Приведены результаты экспериментального исследования разработанных алгоритмов и программ и их внедрения в ряде научно-исследовательских и опытно-конструкторских организаций. В заключении сформулированы основные результаты диссертационной работы. В приложении помещены акты о внедрении результатов диссертации и полученном экономическом эффекте. Апробация работы. МАИ в и гг. Всесоюзном совещании „Автоматизация конструирования устройств и узлов радиоэлектронной и электронно-вычислительной аппаратуры", г. Каунас, г. МАИ - г. Публикации. По теме диссертации опубликовано во всесоюзных, республиканских и ведомственных журналах и изданиях 5 печатных работ. Кроме того, отдельные вопросы, исследованные лично автором и вошедшие в диссертацию, отражены в четырех отчетах по ОКР. Глава I. Эта задача, первоначально возникшая при размещении элект-рорадиоэлементов на платах радиоэлектронных узлов, приобрела в настоящее время особую актуальность и значение для проектирования современной цифровой аппаратуры с использованием больших интегральных схем, микросборок, микропроцессоров и микропроцессорных систем. В известных работах [-] в основном рассматриваются модели плотного размещения элементов, заимствованные из методов оптимального раскроя материалов. Такие модели обеспечивают решение задачи размещения при высокой плотности и сложной конфигурации элементов, но при этом плохо учитывают связность элементов, требования и ограничения трассировки, имеющие решающее значение цри проектировании указанных выше типов цифровой аппаратуры. Рассмотрим вначале известные методы [-] решения задачи. При этом будем придерживаться принятой в указанных работах терминологии и использовать приведенные в них постановки задачи. В наиболее простом виде постановка задачи выглядит следующим образом. Р< параллельны осям координат. При этом возможно 4 различных положения элемента, отличающиеся поворотом последнего на °; два из них считаются эквивалентными двум другим. Нинняя левая вершина прямоугольника называется его опорной точкой Т; . П-? Необходимо любому элементу Е поставить во взаимооднозначное соответствие пару координат опорной точки и параметр ориентации так, чтобы максимизировать критерий размещения Н при отсутствии пересечений между описывающим элемннт прямоугольником Р* с другими прямоугольниками Р/ для всех /^//,. Ео и С* , т.