Введение

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

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

Задача исследования

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

Понятие самой системы автоматизированного проектирования

Под данной системой (САПР) понимают организационно–техническую систему, состоящую из совокупности комплекса средств автоматизации проектирования и коллектива специалистов подразделений проектной организации, способную решать задачи проектирования [1]. На данный момент существуют несколько популярных САПР, каждая из них имеет свои особенности и возможности.

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

Первая группа связана с совершенствованием методов проектирования на основе математического моделирования и автоматизации поиска решений. На этом уровне обеспечивается:

–автоматизация синтеза проектных решений;

– автоматизация анализа принимаемых проектных решений.

Вторая группа связана с заменой трудоёмких работ программными операциями. К такой задаче относятся работы по формированию и выпуску проектной документации.

В САПР имеет место довольно чёткое процедурное разделение этих этапов: выбор решения, выполняемый с использованием математических моделей, отделяется от выпуска документации. САПР – сложная техническая система, качественное функционирование которой возможно при выполнении ряда требований к объектам проектирования.

Требование модели-пригодности для объекта должны быть возможны:

-разработка адекватных математических моделей объектов и отдельных его элементов, определение вычислительных ресурсов модели;

-необходимых объёмов памяти и машинного времени для осуществления моделей;

-возможность реализации для объекта операций синтеза;

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

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

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

Методы размещения элементов на печатной плате

Исходной информацией при решении задач размещения элементов являются:

-данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления данной сборочной единицы в аппаратуре;

количество и геометрические размеры конструктивных элементов, подлежащих размещению;

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

Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества и обеспечивается наиболее благоприятные условия для последующего электрического монтажа. Особое значение эта задача приобретает при проектировании аппаратуры на печатных платах [2]

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

Следовательно, если для оценки качества размещения[6] элементов выбрать критерий, непосредственно связанный с получением оптимального рисунка металлизации печатной платы, то конечный результат может быть найден только при совместном решении задач размещения, выбора очерёдности проведения соединений и трассировки, что практически невозможно вследствие огромных затрат машинного времени [3].

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

-минимум суммарной взвешенной длины соединений;

-минимум числа соединений, длина которых больше заданной;

-минимум числа пересечения проводников;

-максимальное число соединений между элементами, находящимися в соседних позициях либо в позициях, указанных разработчиком;

-максимум числа цепей простой конфигурации.

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

Структура учебной САПР печатных плат

Для построения математической модели[7] электрической схемы используется теория графов. Электрическая схема интерпретируется в виде ненаправленного графа G (X, U), в котором множество вершин графа Х – конструктивные элементы схемы, а множество рёбер U – электрические связи. В связи с трудностями, при разработке программного продукта, которые вызывает описание схем с помощью графов, для выполнения задач используется матрица смежности R и матрица геометрии Q [4].

Проектирования печатных плат можно разделить на пять этапов.

-проектирование схемы, редактор;

-компоновка печатных плат;

-размещение элементов печатной платы;

-трассировка модулей печатной платы;

-расслоение печатной платы.

В редакторе схемы можно спроектировать типы корпусов сколько входов и выходов будет использоваться dip14, dip16, dip18, dip24. Соединения элементов, по принципу какой номер входа элемента подключается проводников к другому элементу, например: D1.1-D4.1 - таким образом видно, что элемент D1 соединён с элементом D4 проводником через первые номера входов корпуса.

В результате выполнения компоновки определяется[8], какие элементы схемы будут находиться в каждом конструктивном узле, а также связи внутри каждого узла и связи между узлами.

Существуют два варианта компоновки:

компоновка схем типовой конструкции, не имеющие схемной унификации;

компоновка схем в модуле заданного схемно-унифицированного набора.

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

После компоновки конструктивных элементов для каждой ячейки, платы и так далее, происходит этап размещение элементов в узле.

Цель размещения заключается в определении наилучшего расположения элементов и связей между ними в монтажном пространстве конструкции. Обязательно должны быть соблюдены конструктивно-технологические ограничения.

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

Этап трассировки соединений, чаще всего является заключительным этапом проектирование схемы. Он состоит в определении линий, которые соединяют контакты элементов и компонентов, которые являются составляющими проектируемого устройства.

Математическая точка зрения трассировки определяется как задача выбора[9] наилучшего решения из многочисленного числа вариаций.

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

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

Этап расслоения последовательно по слоям и по мере заполнения очередного слоя происходит переход на другой слой, либо проводится предварительное расслоение; все соединения межу парами контактов пролагаются только в одном слое.

Структурная схема учебной САПР приведена на рис 1. Из схемы видно, что учебная САПР состоит из пяти подсистем.

1. Ветвлению в первую очередь подвергается подмножество с номером, которому соответствует наименьшее значение нижней оценки целевой функции.

2. Если для некоторого i-го подмножества выполняется[10] условие, то ветвление его необходимо прекратить.

3. Ветвление подмножества прекращается, если найденное в задаче оптимальное решение.

4. Если, где-то выполняются условия оптимальности для найденного к этому моменту лучшего допустимого решения. Обоснование такое же, как и пункта 2 настоящих правил.

5. После нахождения хотя бы одного допустимого решения исходной задачи может быть рассмотрена возможность остановки работы алгоритма с оценкой близости лучшего из полученных допустимых решений к оптимальному, пример выполнения решения путём данного метода (рис. 2).

Основные способы ветвления:

-Разбиение множества вариантов на подмножества по методу «в ширину» и выбор вершины ветвления по минимуму (максимуму) оценочной функции.

-Разбиение множества вариантов по методу «в глубину с возвращением», т. е. последовательное построение ветвей.

-Комбинация двух рассмотренных способов.

Метод ветвей и границ как сокращение полного перебора

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

Достоинством данного метода является гарантированное нахождение оптимального размещения.

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

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

Различия модификации общего метода применительно к задаче размещения (квадратичного назначения) отличаются способами расчёта нижних границ функционала способами разбиения поля решений. На рисунке 4 показана часть дерева полного дерева решений.

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

Если в процессе продвижения по дереву нижние границы не рассчитываются и соответственно не производится усечений дерева, то метод ветвей и границ сводится к полному перебору

Можно выделить следующие способы отсечения ветвей:

1) Сравнение оценки со значением целевой функции для уже найденного решения. Опорное решение можно получить приближенным алгоритмом заранее либо в ходе решения задачи методам ветвей и границ.

2) Сравнение двух оценок.

Литература

1 В.В. Муленко учебное пособие для студентов вузов «Компьютерные технологии и автоматизированные системы в машиностроении». - РГУ нефти и газа им. И.М.Губкина, М., 2015. – С. 3

2 Н.П. Курочка, В.Н. Шипилов, Б.А. Шиянов научная статья «Задачи оптимального размещения ресурсов организации» - Воронежского государственного технического университета 2009

(https://cyberleninka.ru/article/n/zadachi-optimalnogo-razmescheniya-resursov-organizatsii/viewer)

3 В.М. Бондарик «Система автоматизированного проектирования» уч.пособие Мн. БГУИР, 2006- 46 с.

4 В.Е. Алексеев, В.А. Таланов «Графы. Модели вычислений. Структуры данных» Учебник Нижний Новнгород,2004 – 12 с.

5 А.В. Григорьев Методы поиска новых решений в специализированной инструментальной оболочке для создания интеллектуальных САПР Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006г., Обнинск): Труды конференции. В 3-т. Т.3. -- М.: Физматлит, 2006. С. 1031-1046.

6 И.М. Трифоненко, Н.В. Горячев, И.И. Кочегаров, Н.К. Юрков Обзор систем сквозного проектирования печатных плат радиоэлектронных средств Трифоненко И.М., Горячев Н.В., Кочегаров И.И., Юрков Н.К - Пензенский государственный университет

7 Норенков И.П. Основы автоматизированного проектирования: Учеб.для вузов / И.П. Норенков. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2002.-336 c.

8 СабунинА.Е.Altium Designer. Новые решения в проектировании электронных устройств / А.Е. Сабунин. — М.: Солон-Пресс, 2009. – 432 с.

9 Горячев Н.В., Проектирование топологии односторонних печатных плат, содержащих проволочные или интегральные перемычки / Н.В. Горячев, Н.К. Юрков // Труды международного симпозиума "Надежность и качество". 2011. Т. 2. С. 122-124.

10 Горячев Н. В. Опыт применения систем сквозного проектирования при подготовке выпускной квалификационной работы / Н. В. Горячев, Н. К. Юрков // Известия ПГПУ им. В.Г. Белинского. Физикоматематические и технические науки. 2011. № 26. С. 534–540.