Файл: Ландау И.Я. Применение ЦВМ для проектирования ЦВМ.pdf

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

Лучшие решения задач 1—3 получаются при исполь­ зовании оценок типа (3-1), учитывающих кроме длины ■соединений количество пересечений каждого соединения с соединениями других цепей. В этом случае критерием для построения оптимального связывающего дерева ■является не минимум суммарной длины соединений,

а минимум их суммарной оценки D = Yi d;, где Я —

i£=H

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

1. Для цепей, соединяющих три и более выводов, строим таблицу всевозможных соединений (ТС).

2. Относим к множеству Я все цепи, соединяющие два вывода, распределяя их между заданными слоями монтажа так, что каждое соединение попадает на тот слой, на котором оно имеет минимальную оценку (при вычислении оценки пересечения считаются только с сое­ динениями, уже принадлежащими Я ).

3.Выбираем из ТС список соединений очередной цепи и вычисляем для каждого из них оценки на всех слоях монтажа. Запоминаем минимальные оценки вме­ сте с номером слоя, на котором они получены, и упоря­ дочиваем список по возрастанию оценок.

4.Выбираем из списка минимальный набор отрезков, необходимый для реализации дайной цепи, и включаем его в Я. Выбор этот производится следующим образом. Пусть цепь связывает т выводов. Тогда минимальный набор соединений, необходимый для ее реализации, содержит т— 1 отрезок, причем он не должен содержать замкнутых контуров. Этот набор можно получить, вы­ брав из первых т соединений первые т —1 так, чтобы очередное выбираемое соединение не образовало замк­ нутого контура с уже выбранными. Поскольку список был упорядочен по возрастанию оценки, выбранный таким образом набор имеет минимальную оценку на

множестве Я.

107

5.Повторяем пп. 3, 4 до исчерпания ТС, в резуль тате получаем оценку разбиения для Н.

6.Выполнение пп. 3—5 продолжается до тех пор, пока разность оценок двух последовательных итераций не станет меньше заданного предела.

Оценки, полученные на этом этапе, используются и при трассировке: она производится в порядке возраста­ ния оценок. Это позволяет раньше проложить соедине­ ния с меньшей оценкой (их легче провести и они не мешают другим соединениям).

3-7. СРАВНЕНИЕ РАЗЛИЧНЫХ АЛГОРИТМОВ ТРАССИРОВКИ

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

1 Это видно, в частности, из табл. 3-7.

103

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

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

Для плат с нерегулярным расположением выводов, особенно если на них кроме стандартных элементов установлены и нестандартные (например, обычные ра­ диодетали), наиболее эффективны алгоритмы поиска пути в лабиринте. Таких элементов много в блоках управления оперативной памяти и периферийных элек­ тромеханических устройств.

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

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

Нп одни из методов машинного проектирования пе-^ чатного монтажа не гарантирует трассировки всех сое­ динений; как правило, какая-то часть соединений (от 2 до 10%) остается не разведенной. Часть этих соедине­ ний (а иногда и все) может быть разведена путем изменения конфигурации протрассированных ранее про­ водников (как показано на рис. 3-14). Человек подоб­ ную корректировку делает легко, для машины же это очень трудная задача, поскольку она не может «уви­ деть» все монтажное поле сразу, а должна поочередно двигать каждое препятствие. Даже в простейшем при­ мере (рис. 3-14) для корректировки нужно одновременно изменить конфигурацию двух проводников, при этом

109

3-8, ПРОЕКТИРОВАНИЕ ПРОВОДНОГО МОНТАЖА

Проектирование проводного монтажа представляет собой сравнительно простую задачу прежде всего по­ тому, что для нее (в отличие от печатного монтажа) имеются точно формулируемые и легко реализуемые на ЦВМ правила выполнения соединений. В большинстве случаев эти правила формулируются следующим об­ разом:

1.Суммарная длина проводов должна быть мини­ мальной.

2.Число подключений к каждому выводу не должно превышать заданной величины.

3.Для каждого провода должны быть определены путь (в соответствии с заданными особенностями кон­ струкции) и марка провода (в зависимости от длины или типа соединения).

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

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

Рассмотрим программы, характерные для обоих типов провод­ ного монтажа. Эти программы [Л. 14] применялись для составления и выпуска монтажной документации на блоки и генеральный монтаж устройств вычислительного комплекса М-4000 АОВТ. Исходной ин­

укреплены по 8 ячеек (рис. 3-15). На торцах блока находятся разъ­ емы внешних связей (Ш1, LLT2) и контрольных точек (ШЗ). Соеди­ нения выводов ячеек и разъемов проводятся внутри блока по пря­ мой. К каждому выводу разрешается подключать не более двух проводов.

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

111

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

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

112

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

1. Соединяем подряд все выводы каждого ряда. При этом пре­ небрежем расстоянием между ячейками, расположенными на разных сторонах блока — это не увеличит длины, так как расстояние меж­ ду ними намного меньше длины разъема, а соединения между со­ седними выводами одной ячейки встречаются редко.

2. Соединив выводы в рядах, рассмотрим все варианты соеди­ нения между рядами и выберем ореди них вариант с минимальной длиной — получим искомое дерево соединений.

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

Блок-схема программы приведена на рис. 3-16; назначение от­ дельных блоков понятно из рисунка.

Генеральный монтаж шкафа выполняется жгутами. Поскольку объем исходной информации здесь превышает размер оперативной па'мятн ЦВМ «Минск-22», для хранения списков соединений исполь­ зовались магнитные ленты. Правилами монтажа для задней стенки разрешалось до трех подключений к каждому контакту разъема.

Работа программы проходит в два этапа:

1.Накопление исходной информации (списков соединений) и запись ее на магнитные ленты (МЛ). При этом заводятся две ленты: МЛ! п дублирующая ее МЛ2. Список соединений имеет формат СЗ. па рис. 3-5. В начало МЛ1 и МЛ2 заносится каталог списка, со­ держащий название шкафа, количество зон на ленте, занятых спис­ ком, и номер первой свободной зоны.

2.' Сортировка списка соединений по номеру цепи, выделе

списков цепей и трассировка соединений.

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

Сортировка исходного списка и трассировка производятся так: считывается та зона МЛ1 (или МЛ2), в которой начинается нерасеортированная часть списка. Переписанная информация помещается в оперативную память на исходное поле (ИП). Затем из ячеек этой части списка последовательно выделяются номера цепей. Цепь, номер которой не совпадает ни с одним из ранее выбранных, записывается

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

а в соответствующем поле РП формируется новая ячейка списка. После того как все ИП просмотрено, оставшаяся на нем ин­ формация записывается в соответствующую зону МЛЗ, а на это