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

объем СВ достигает 10—20 тыс. машинных слов (200— 300 ячеек, имеющих 50—60 контактов разъема); поэто­ му для хранения и обработки списков требуются внеш­ ние запоминающие устройства, что значительно замед­ ляет программу. Поскольку для ячеек задачу размещения нужно решать многократно (их много), желательно иметь разные варианты программы для работы только с оперативной памятью и с использованием внешних запоминающих устройств.

Выполнение размещения для ячейки, содержащей до 30 модулей, с помощью описанной программы зани­ мает на ЦВМ БЭСМ-4 около 5—6 мин машинного вре­ мени *.

3-4. ПРОЕКТИРОВАНИЕ ПЕЧАТНОГО МОНТАЖА

Завершающим этапом конструкторского проектиро­ вания любого элемента ранга п > 2 является составле­ ние монтажной документации. Для решения этой за­ дачи необходимо в соответствии с требованиями кон­ струкции и правилами монтажа выбрать порядок соединения выводов каждой цепи, определить путь и тип проводников, соединяющих каждую пару выводов (произвести трассировку соединений), и выпустить до­ кументы, необходимые для изготовления элемента. Со­ ставление монтажной документации — самая трудоемкая работа при ручном проектировании; в АСП решение этой задачи занимает наибольшее количество машинно­ го времени.

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

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

1. Конструктивные характеристики: размер монтажного поля;1

1 Для ячеек часто оказывается выгоднее совместно решать задачи компоновки и размещения модулей — при этом улучшаются условия для трассировки. Время решения этих задач для ячейки ука­ занных размеров составляет 30—40 мин (на ЦВМ БЭСМ-4).

95

минимальные ширина проводника, зазор между про­ водниками н радиус контактной площадки;

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

расположение выводов элементов на монтажном поле;

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

2. Описание электрической схемы, включающее: размещение элементов на посадочных местах; список связей между выводами элементов.

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

Проектирование печатного монтажа является, пожа­ луй, самой сложной из задач автоматизации проектиро­ вания цифровых устройств. Для ее решения предложено большое количество различных алгоритмов [Л. 46—52], однако ни одни из них не в состоянии соревноваться по качеству трассировки с квалифицированным конст­ руктором, что связано с принципиальными различиями в методах решения задачи человеком и машиной. Наи­ более трудна задача трассировки соединений, поскольку каждое соединение должно обходить как начальные препятствия, так и ранее проложенные соединения дру­ гих цепей. Таким образом, конфигурация каждого про­ водника связана с конфигурацией всех остальных про­ водников, расположенных на данной монтажной плоско­ сти, и для получения оптимального решения следовало бы определять все трассы соединений данной плоскости совместно. Именно так и работает человек. Машина же прокладывает каждое соединение отдельно и не может учесть при этом пути тех соединений, которые еще не проложены. Таким образом, человек видит всю картину монтажа целиком, тогда как машина в каждый момент «видит» лишь ближайшую окрестность прокладываемо­ го соединения.

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

96

( 3-5. МЕТОДЫ ТРАССИРОВКИ ПЕЧАТНЫХ ПРОВОДНИКОВ

Большинство известных в настоящее время программ трассировки используют волновой алгоритм Ли [Л. 46]. При этом монтажное поле разбивается сеткой ортого­ нальных линий на клетки— дискреты (рис. 3-8). Шаг сетки h выбирается так, чтобы в соседних клетках могли

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

Распространение волны продолжается до тех пор, пока очередной фронг не достигнет конечной клетки {х\, у i). При этом волна огибает все встречные препятствия, и если между клетками (х, у) и (xlt y v) есть какой-либо свободный путь, она дойдет до конечной клетки.

После этого начинается построение пути проводника в направлении, противоположном распространению вол-

(номер фронта 0). В зависимости от правила перехода

98

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

ства конструкций составляет от 0,25x0,25 до 0,5X0,5 мм; при этом монтажное поле 100x100 мм содержит 4- 104—

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

1 ритма, частично устраняющие последний недостаток. Они сводятся к попытке найти путь, распространяя вол­ ну не по всему полю, а только вдоль некоторого луча, соединяющего точки А и В. Однако в этом случае нет гарантии, что будет выбран оптимальный путь (и что путь вообще будет найден).

Корпуса многих типов интегральных схем имеют прямоугольную форму; такую же форму имеют разъемы. Стремление к повышению плотности монтажа приводит к расположению элементов на монтажном поле парал­ лельными рядами (рис. 3-6).

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