Конференции ИВТ СО РАН



VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

27 - 29 ноября 2007 года, Новосибирск

Тезисы докладов


Математическое моделироваие

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

Шандриков А.С.

Витебский государственный политехнический техникум (Витебск)

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

Автоматизированное решение задачи размещения осуществляется с использованием математической модели в виде графа G = (X, U), у которого множество вершин X обозначает множество РЭК, подлежащих размещению, а множество рёбер U – электрические цепи в соответствии с принципиальной электрической схемой. Исходной информацией для решения данной задачи являются:
1) количество позиций, полученное в результате решения задачи компоновки (распределения РЭК по узлам и блокам);
2) размеры коммутационного пространства. Коммутационное пространство как правило имеет прямоугольную форму и его размеры для размещения РЭК задаются в виде n × m, где n – количество позиций по оси абсцисс, а m – по оси ординат координатной решётки, накладываемой на коммутационное пространство.

Всё решение задачи размещения сводится к отображению подграфа проектируемого узла в решётку заданных размеров. Критерием качественного размещения является минимальная суммарная длина соединений (МСД).

Для размещения вершин подграфа в позициях координатной решётки используется большое количество алгоритмов, ориентированных на обеспечение критерия МСД. Однако предпосылки для минимизации суммарной длины соединений могут быть заложены ещё на этапе построения исходного графа принципиальной электрической схемы. Формирование графа как математической модели принципиальной электрической схемы можно условно разделить на четыре этапа:
1 этап – развязка электрических узлов.
2 этап – построение связывающих деревьев.
3 этап – объединение полученных связывающих деревьев.
4 этап – проведение рёбер, обозначающих связи между последовательно соединёнными РЭК во всех отдельных ветвях принципиальной электрической схемы.

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

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

γ(G) = r – n + p                 (1)

где r – количество рёбер в полном подграфе; n – количество вершин подграфа; p – компонента связности. Для полного подграфа (графа) компонента связности всегда равна единице.

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

Операции, выполняемые на третьем и четвёртом этапах, в дальнейших пояснениях не нуждаются.

Оптимальность конструкторских решений, в частности, размещение РЭК, зависит от принятых конфигураций связывающих деревьев на втором этапе формирования графа принципиальной электрической схемы. Для получения связывающего дерева в каждом полном подграфе удаляются любые «лишние» ребра, количество которых определяется по формуле (1). Известно, что таким путём для полного подграфа можно получить d = nn – 2 вариантов связывающих деревьев. Правила дискретной математики не накладывают каких-либо ограничений, указывающих, какие именно рёбра следует удалять. По этой причине выбор конкретного варианта связывающего дерева чаще всего осуществляется произвольно, без предварительной оценки последующих результатов размещения РЭК с точки зрения критерия МСД. Объяснить это можно неочевидностью влияния выбранного варианта связывающего дерева на получение оптимальных размещения графа и отсутствием пояснений по данному вопросу в литературных источниках.

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

Результаты проведённых исследований показывают, что:
1) суммарная длина соединений зависит от выбранных вариантов связывающих деревьев для подграфов, интерпретирующих электрические узлы принципиальной электрической схемы;
2) аналитический подход к выбору варианта связывающего дерева для каждого узла с учётом особенностей соединений РЭК позволяет минимизировать суммарную длину соединений печатной платы и во многих случаях (в зависимости от сложности принципиальной электрической схемы) обеспечить планарность отображённого в решётку графа. Планарность размещённого на коммутационном пространстве графа позволит выполнить трассировку соединений печатной платы в пределах одного слоя и тем самым повысить качество РЭС при одновременном снижении их стоимости.

Литература
1. Мелихов А.Н. Применение графов для проектирования дискретных устройств /А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик – М. : Наука, 1974 – 304 с.
2. Абрайтис Л.Б. Автоматизация проектирования ЭВМ. / Л.Б. Абрайтис, Р.И. Шейнаускас, В.А. Жилевичюс; под ред. Л.Б. Абрайтиса – М. : Сов. радио, 1978 – 272 с.
3. Шандриков А.С. Особенности построения графа принципиальной электрической схемы, влияющие на результаты компоновки РЭС / А.С. Шандриков // Современная радиоэлектроника: научные исследования, подготовка кадров: материалы международной научно-практической конференции: в 3 ч. Ч 1, Минск, 20- 21 апреля 2006 г. / Минский государственный высший радиотехнический колледж. – Минск. : 2006. – С. 354-358.

Дополнительные материалы: Полный текст доклада
Примечание. Тезисы докладов публикуются в авторской редакции



Ваши комментарии
Обратная связь
[ICT SBRAS]
[Головная страница]
[Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск