часть 3.3

4.6. Алгоритмы размещения.

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

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

      В монтажном пространстве задана область, которая разбивается      на множество позиций (посадочных мест) P={p  ,p  ,...p  }, число которых должно быть не меньше числа  размещаемых  элементов.

      Очевидно, что каждый элемент может занимать не более одного посадочного места,  расстояние между которыми описывается симметричной  матрицей  расстояний  D  =   d      .  Требуется  таким

образом  отобразить  имеющееся  множество  элементов  схемы      X ={x  ,x  ,...,x  }, связанных между собой множеством электрических цепей E = {e  ,e  ,...,e  }, на множестве P, чтобы обеспечивался экстремум целевой функции качества размещения.

      В качестве критерия оптимальности решения задачи размещения могут использоваться:

         - суммарная длина электрических соединений

         - суммарное число пересечений электрических соединений

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

      К данной группе алгоритмов относят итерационные,  последовательные и смешанные алгоритмы размещения.

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

      Схема последовательного  алгоритма  размещения  приведена на рисунке 4.6.2.

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

      Схема итерационного алгоритма размещения показана на рисунке  4.6.3.

      Пример и результат решения задачи размещения с помощью  итерационного алгоритма для графа схемы, первоначальное размещение и матрица расстояний которого показаны на рис. 4.6.4. - 4.6.5.,  приведены на рис. 4.6.6. - 4.6.7.

      Если невозможно выбрать перестановку отдельных вершин графа,  уменьшающую суммарную длину соединений,  то производят перестановку групп вершин.  Для этого производится операция факторизации  графа:  разбивая  все  множество  вершин  графа  на классы  X  ,X  ,...,X  , строится новый граф (мультиграф G ),  в  котором  вершинами являются  классы  X  ,  а ребрами - связи  между классами. Далее  производится  перестановка   групп   элементов (классов),  каждая из которых принимается за вершину мультиграфа. Пример и результат факторизации графа  схемы,  размещенного  на коммутационной плате так,  как показано на рис. 4.6.7., приведены на рис. 4.6.8. - 4.6.9.

4.7. Алгоритмы трассировки.

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

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

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

      Постановка задачи   трассировки печатных соединений.

      На   коммутационном   поле    заданы   своими   координатами    x   ,y     множество   размещенных   конструктивных   элементов      R ={r  ,r  ,...,r  }.  Выводы этих элементов образуют некоторое      множество из l связанных подмножеств  M={M  ,M  ,...,M  ), причем каждое подмножество M   объединяет N   электрически связанных выводов конструктивных элементов из множества R в соответствии с принципиальной электрической схемой.  Кроме того, заданы      расположение групп контактных площадок разъемов  монтажных  отверстий, а также ряд технологических требований. Требуется соединить выводы конструктивных модулей внутри каждого подмножества M     M так, чтобы полученные соединения отвечали выбранному  показателю качества.

      На практике при оптимизации топологии печатного монтажа часто используют следующие критерии качества:

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

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

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

         - минимальная протяженность параллельных  участков  соседних  проводников;

         -    минимум числа изгибов проводников;

         -  минимум  числа слоев металлизации (для многослойных печатных плат с открытыми контактными площадками) и числа  переходов из слоя в слой (для многослойных печатных плат со сквозными металлизированными отверстиями).  Примеры  многослойных  печатных плат (МПП) разных типов приведены на рис. 4.7.1.

      Задачу можно условно представить в виде  четырех  последовательно выполняемых этапов:

         1) определение перечня соединений;

         2) размещение по слоям;

         3) определение порядка соединений;

         4) трассировка проводников.

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

             F =       ( d  )          ,                        (3-7)

         где             - длина j-й связи, принадлежащей подмножеству M  объединяющему N   контактов.

      Данная задача  решается  в САПР путем построения минимальных  штейнеровских деревьев,  допускающих соединения типа  "вывод  -   проводник" и "проводник - проводник".

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

      На третьем этапе производится определение последовательности      выполнения трассировки отдельных соединений. Наличие этого этапа объясняется тем, что отдельные проводники в большинстве случаев конфликтуют  друг с другом,  вследствие чего оптимальность полученного решения задачи трассировки в  значительной  степени определяется тем, в какой последовательности она будет выполнена. Для решения этой задачи в  САПР  применяется  эвристическое правило Айкерса о порядке трассировки проводников, заключающееся в том, что проводники трассируются в порядке их приоритетных номеров. Приоритетный  номер проводника v равен числу контактов в прямоугольнике, имеющем в противоположных углах контакты данного проводника. Примеры решения данной задачи для двух и четырех проводников приведены на рисунке 4.7.2.

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

         - волновые алгоритмы;

         - лучевые алгоритмы;

         - эвристические алгоритмы.

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

         где .     и .         - веса ячеек k-го и (k-1)-го фронтов;

             .                 - весовая функция, являющаяся показателем качества проведения пути, каждый параметр которой (i=1,g) характеризует  путь  с точки зрения одного из критериев      качества.

      Процесс распространения волны продолжается до тех пор,  пока

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

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

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

      Лучевой алгоритм  трассировки,  предложенный Л.Б.Абрайтисом,  заключается в следующем. Задается число лучей, распространяемых  из соединяемых  между  собой точек,  а также порядок присвоения путевых координат. Распространение лучей производят одновременно из обоих источников до встречи двух разноименных лучей в некоторой ячейке C.  Путь проводится из ячейки C и проходит через ячейки, по которым распространялись лучи. Разноименными называются лучи, распространяемые из разных ячеек. Пример решения задачи трассировки  соединений с помощью лучевого алгоритма показан на рисунке 4.7.4.

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

-    -

С О Д Е Р Ж А Н И Е

                                                                                                               Стр.

         4. Алгоритмизация типовых задач конструкторского

            проектирования....................................................................

              4.1. Элементы теории графов, используемые при опи-

                   сании моделей конструкций РЭА................................

              4.2. Типовые задачи конструкторского проектирования

              4.3. Алгоритмы покрытия................................................... var container = document.getElementById('nativeroll_video_cont'); if (container) { var parent = container.parentElement; if (parent) { const wrapper = document.createElement('div'); wrapper.classList.add('js-teasers-wrapper'); parent.insertBefore(wrapper, container.nextSibling); } }