Во втором цикле составляется новая матрица связей, соответствующая полученному размещению, и вычисляется новая матрица приращений

0 0 2 2 1 114 2 3 4 2 О О 3

Так как AZ-i не содержит отрицательных элементов, то размещение на рис. 1.15, б является окончательным и улучшить его нельзя.

Рассмотренный алгоритм не требует анализа такого большого числа ситуаций, как при переборе вариантов размещения. Задача решается в течение небольшого количества циклов. Однако алгоритм имеет весьма серьезные недостатки. Его применение вызывает необходимость в большом объеме памяти ЗУ и выполнение каждого цикла требует большого машинного вре мени. Так только для хранения оперативной информации, заложенной в матрицах, необходимо использовать-(5iV- 1) ячеек

памяти, что для среднего размера плат с семьюдесятью модулями составляет 12 215 ячеек. Для вычисления матрицы прираще-

ний необходимо в каждом цикле выполнить

N (т - 1)

операций

умножения и

N{N -V)(2N +\)

операций сложения, что для плат

с 70 модулями примерно 350 ООО сложений.

равно 17 000 умножений и около

Алгоритм последовательного размещения узлов на печатной плате

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

В силу того, что выделение очередного модуля из множества Неразмещенных производится по принципу связности, данный

ввод координат фиктробаииьк точек

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

Рассматриваемый алгоритм решает задачу размещения за N шагов, причем «а каждом шаге выделяются один из неразмещенных модулей и соответствующее ему место на плате.

Структурная схема алгоритма прбдставлена на рис. 1.16.

1. Ввод координат фиксированных точек на плате. Перед началом решения задачи размещения модулей на плате фиксированными точками являются контакты разъема, которые при принятой модели платы размещены в заранее определенных местах и связаны с модулями.

Таким образом, по мере решения задачи размещения сначала заполняется зона, прилегающая к разъему, а затем все более удаленные от него области пространства платы.

2. Коэффициент связности для множества неразмещенных модулей

вычисляется тю следующей фор- муле:

Таким

=2-/- 2 о- (1-9)

образом, коэффициент связности модуля Е" показывает,

насколько больше сумма связей его- с размещенными модулями суммы его связей с неразмещенными.

3. С помощью блока 3 выделяется наиболее связанный с фиксированными (размещенными) модулями свободный модуль.

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

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

Рис. I.I6. Структурная схема алгоритма последовательного размещения узлов на печатной плате

(1.10)

5. Из множества незанятых точек на плате для размещения определенного блоком 3 модуля выделяется такая, для которой величина L(* минимальна.

Если еще не все модули размещены, то начинается следующий шаг алгоритма по выделению и размещению модуля

Рассмотренные алгоритмы являются в настоящее время основными алгоритмами размещения узлов на плате.

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

Методы и алгоритмы автоматического проектирования соединений на плате

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

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

1. Соединения должны соответствовгггь принципиальной схеме.

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

предпосылками. Кроме того, очевидно, что проводники меньшей длины занимают меньшее число элементов платы, следовательно, оставля-

ют больше возможностей для проведения других соединений.

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

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

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

I. 63