Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год, страница 44

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

Напомним, что во взвешенном графе каждая цепь представляется полным подграфом, что приводит к неточной опенке числа связей между элементами или частями схемы (см. 8 8.3). Более точной моделью схемы является гиперграф, представляющий схему с точностью до выводов элементов. Реальная длина соединений при установке элемента в позицию монтажного пространства может быть определена точно, если рассчитывать трассы соответствующих соединений. Ясно, что такую оценку можно сделать только дл(( соединений размещаемого элемента с размещенными. Если учесть, что расчет трасс необходимо выполнять для всех возможных вариантов установки каждого неразмещенного элемента или всех возможных перестановок, ясно, что это потребует слишком большого машинного времени.

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

Полупериметры суммируются по всем цепям, связывающим размещаемый элемент с размещенными. Указанные способы не нашли пока широкого применения, так как оценка суммарной длины соединений по (10.3) необходима только для сравнения различных вариантов разл<ещения. Рассмотренные выше алгоритмы размещения могут при соответствующей модификации использовать и другие критерии оптимизации. Однако, как отмечалось выше, ни один из перечисленных в 9 10.1 критериев качества размещения не учитывает в полной мере требования трассировки. Нередко ручное размещение элементов конструктором создает лучшие условия для трассировки, чем машинное. Прн ручном размещении конструктор стремится обычно располагать в соседних позициях наиболее связанные элементы, входящие в функционально законченную группу, следя в то же время за достаточно равномерным распределением соединений по монтажному пространству.

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

При некоторой его модификации можно учесть фактор <равномерного» распределения соединений. тва $10М. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ТРАССИРОВКИ Трассировка заключается в определении конкретной геометрии печатного или проводного монтажа, реализующего соединения меж жду элементами схемы. Исходными данными для трассировки являются список цепей, метрические параметры и топологические свойства типовой конструкции и ее элементов (см. 5 8.3) и результаты решения задачи размещения, по которым находятся координаты выводов элемен. тов. Формальная постановка задачи трассировки и методы ее решения в значительной степени зависят от вида монтажа (проводиой или печатный) и конструктивно-технологических ограничений, определяю1цих метрические параметры и топологические свойства монтажного пространства. В типовых конструкциях, начиная с блока и выше, довольно широко используется проводной монтаж, что объясняется высокой трудоемкостью проектирования и сложностью изготовления печатного монтажа.

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

Т расснровка проводного монтажа. Заключается в определении порядка соединения выводов в соответствии с принципиальной электрической схемой и с учетом заданных ограничений. Критерием качества, как правило, является минимум суммарной длины соединений. Нахождение порядка соединения выводов элементов внутри цепи сводится к задаче построения на фиксированных вершинах минимального ик посх рывающего или связывающего дерева. Будем использовать мод емы в виде графа, в котором выводам элементов сопоставлены вершиель Т ны и на этих вершинах строится полный подграф (см. 5 8 3 рис.

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

е, вершины компонент связности отображены в граф решетки монтажного пространства. Расстояние между каждой парой вершин полного подграфа для проводников, идущих по кратчайшему направлению; (!О.!1) с(, Т. 1 (5,— 51)»-г ((; — (4)», для ортогональной трассировки (10.12) с(нз . !51 — 81( 1- 1(1 — (41. Здесь 5ь (1 и 5И (4 — координаты 1'-й и (чй вершин графа, ЗОР В 5 8.3 отмечалось, что на п вершинах можно построить („пн-т различных деревьев. В связи с этим точное решение задачи построения минимального дерева методом полного перебора нецелесообразно.

Существуют приближенные алгоритмы решения этой задачи, дающие результаты, достаточно близкие к оптимальным. Рассмотрим основные пункты алгоритмов Краскала и Прима. Алгоритм Краскала. 1. Для всех пар вершин полного подграфа б, =-(Х, (/); 1Х ~ — п; Я ..= и1 по (10.1!) илн (10.12) рассчитываем длины соединяющих их ребер; г((иа)=г(ь, где 1- 1, и; !' 1' -,'. 1; й — 1~ т; ги .=- п (п — 1)12. Рнс. 1ОД. Построение минимального лорена алгоритмом Краскала 2.

Упорядочиваем ребра графа по возрастанию их длин: (7' = — (ип, иг„, и; ); дп < г(1т ( ... ( г(о„. 3. Последовательно просматривая множество (7', соединяем вершины теми ребрами, которые не образуют цикла с ребрами, уже вошедшими в дерево. При работе алгоритма возможно появление на каких-то шагах нескольких несвязанных поддеревьев, которые затем соединяются, образуя одну компоненту связности.

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

Исходными данными для работы алгоритма являются матрица расстояний П„= 1)дО 1анн, элементы которой определяются по (10.11) или (10.12), и допустимое количество проводников, подключаемых к выводу гп „. Основные пункты алгоритма. 1. Находим минимальный элемент матрицы г(н „вЂ” — ппп д; В 1, 1 =- 1, и; 1 ч~= !. Номера строки и столбца д и р, на йересеченин которых он находится, определяют номера вершин, соединяемых ребром. 210 2. 3 . Заносим номера вершин в множество Х' (гь и), а построенное ребро в множество (7' — ((7н л), 3. Подсчитываем число ветвей Фн и й,„принадлежащих соединяемым на данном шаге вершинам.

4. ПРовеРЯем Условие 1га «гплол, /гл( игмно ИнДексы веРшин, для которых это условие не выполннетсн, зайносим в множество Х". 5. Находим г(г г - - ппп г(;;; 1Р Х' а ~' ~ Х"; !'-.е= Х', т. е, сРеди еще не вошедших в дерево вершин находим вершину х, минимально удаленную от некоторой вершины дерева à — — — —— г' 6.

Дополняем множества Х' Х'() 0 1 ', лг à — (7'() и„и 7. Проверяем, все лп вершины гра- , '" Я фа соединены ветвями ~(7'1 . (и .— 1), Если условие выполняется, то переходим к и. 8, иначе — к и. 3. 8. Конец работы алгоритма. Трассировка при печатном монтаже. В монтажном пространстве, представляющем собой совокупность коммутаци- Рос. 10.7. Реа еалнааанн соелннеонных плоскостей, определены коорди- ннй н монтажном нространстнг наты конструктивных элементов и их выводов; заданы метрические параметры и топологические свойства монтажного пространства (ширина проводников и зазоров между ними, координаты и размеры контактных площадок, число слоев МПП и переходы со слоя на слой, координаты н размеры областей, запрещенных для трассировки). Множество цепей принципиальной схемы разбивает множество В выводов элементов на непересекающиеся подмножества В; так, что В =- (В;П 1, М ), а В; -- (дьлдг = 1, йг), где М вЂ” число цепей; Фг — число контактов, соединяемых 1-й цепь Н еобходимо реализовать множество В; в виде множества А1 таких областей (рис.