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

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

Существует несколько классов алгоритмов трассировки: волновые, лучевые, канальные [1, 3]

Идея волг вого алгоритма за ключается в распространении числовой волны поиска кратчайшего соединения на дискретах модели монтажного пространства или дискретном рабочем поле. Дискреты называются занятыми, если по ним прошли ранее построенные участки трасс, запрещенными - если из технологических условий в них нельзя прокладывать трассы, и соседними, если они имеют общее ребро. В Л-й фронт волны включаются все свободные дискреты, соседние с дискретами {k - 1)-го фронта, а сами дискреты помечаются целыми неотрицательными числами F = F (ci/i + Cg/g + --.+ Cnfn). где fi - (-Й крите-

2-57

рий построения трассы (длина трассы, число пересечений, число переходов со слоя на слой и т. п.), а ci - весовой коэффициент 1-го критерия, характеризующий степень его приоритета над критериями fj на = {1, 2, .... п}, ]ф1) Формирование фронтов волны осуществляется до тех пор, пока в очередной фронт не будет включен искомый дискрет. На этом процесс распространения числовой волны поиска искомого дискрета заканчивается. Второй этап работы алгоритма называется проведением пути. Заключается он в обратном прохождении дискретов по правилу монотонного убывания записанных в них чисел. После обратного просмотра по всем возможным путям, соединяющим искомые дискреты, выбирается путь, имеющий меньшее число дискретов, т. е кратчайший Аналогичная процедура раснэостранения волны и считывания пути повторяется до получения полного решения Класс волновых алгоритмов является универсальным в отношении критериев проложения пути, обладает возможностями модификаций, простотой и стройностью математической модели. К наиболее существенны1м недостаткам относятся значительный объем требуемой оперативной памяти ЭВМ и большие затраты машинного времени.

Разработка алгоритмов трасси ровки с повышенным быстродей ствием привела к созданию класса лучевых алгоритмов. Пусть в простейшем случае необходимо найти кратчайший путь из с в rf

Устанавливается количество лучей, исходящих из с и d. В зависи мости от этого различают двухлуче вые и четырехлучевые алгоритмы Распространение лучей происхо дит одновременно из обоих источ НИКОВ до встречи в дискрете t. Пуп проводится от дискрета t через дис креты, по которым прошли оба луч; до встречи. Для увеличения воз можностей двухлучевых алгорит мов целесообразно разрешение про ведения нескольких одноименных лучей по одному дискрету. Для исключения блокировки лучей можно возвращать луч из заблокированных дискретов в соседние, по

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

Получают распространение канальные алгоритмы трассировки, основанные на прокладке трасс по укрупненным дискретам рабочего поля, в качестве которых служит система горизонтальных и вертикальных каналов. Ширина каждого канала регламентирует количество магистралей в канале. Прн этом любое соединение будет представлять совокупность объединенных в одну цепь участков iwarncT-ралей. Реализация канального алгоритма предполагает выполнение двух процедур: распределения соединений по каналам с учетом их оптимальной загрузки и оптимизации расположения соединений на магистралях каналов. Для заданной конструктивно-технологической базы изготовления печатных плат каждому каналу монтажной плоскости монсно поставить в соответствие число, называемое пропускной способностью канала и обозначающее максимально допустимое количество проводников, проходящее через сечение канала с выполнением технологических ограничений. При этом процедура оптимального распределения соединений по каналам, в простом случае, сводится к равномерной их загрузке, а в более сложных случаях дополнительно осуществляет учет фактора электромагнитной и тепловой совместимости соседних проводников. Целью выполнения второй процедуры - оптимизации расположения соединений на магистралях каналов - является минимизация переходных отверстий с одного слоя Монтажной плоскости на другой.

Класс канальных алгоритмов трассировки выгодно отличается от волновых повышенным быстродействием, меньшим расходом памяти ЭВМ, однако он менее универ-

сален, что накладывает определенные ограничения на класс конструктивно-технологических решений.

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

После окончания трассировки, особенно для БИС, важна проверка соответствия между исходной электрической схемой и ее топологи-

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

Структура системы автоматизированного проектирования РЭА

Развитие системы автоматизированного проектирования (САПР) РЭА включает сложный и разнообразный комплекс технических средств, в котором можно выделить две основные части: центральный вычислительный комплекс (ЦВК) и

Рис. 8.13. Состав технических средств САПР

интерактивная графическая мини-система [12]. Типичный состав технических средств развитой САПР приведен на рис. 8.13 и состоит из трех уровней: ЦВК на базе мощной ЭВМ, коммутатора периферийного оборудования и средств связи с рабочими местами разработчиков.

Рабочие места разработчиков в соответствии с этапами проектирования разделены на два типа:

- рабочее место проектирования монтажного рисунка печатной платы и топологии БИС;

- рабочее место изготовления фотошаблонов печатных плат и БИС.

Прикладное математическое обеспечение САПР имеет блочную структуру (рис. 8.14) и состоит из нескольких самостоятельных подсистем, объединяемых в систему диспетчером. Управление подсистема.ми осуществляется местными блоками управления, которые имеют двухстороннюю связь с диспетчером, пультами управления и между собой.

Подсистема подготовки входной информации предназначена для проверки текстов кодирования исходных данных и их транслирования во внутреннее представление системы. Подсистема работает в двух режимах: 1) проверка текстов кодирования на синтаксис и семантику вводимого языка и 2) трансляция

Прикладное rran?em/77uvecKOP оеесиечекие ко fW, Ш

(вэт-е,щ то и

Системное name/iamvjecuoe cSecneveuue на /УМ,/Уа

AimcMumu-------U cvu~

Радвчее песта првектирод-щина твлвлвгии

Powii/mamBp машин

РаЛ/ЧЕВ места изгвтвВления фатошадлвнав