Содержание к диссертации
Введение
Гл. I Проблемы автоматизации решения задач размещения и трассировки при проектировании РЭА 16
Гл. 2 Алгоритм размещения с моделированием конфигурации межэлементных связей 33
Гл. 3 Модель коммутационного поля и адаптация подсистем трассировки к изменениям конструктивно-технологических ограничений 46
Гл. 4 Алгоритмы трассировки связей 66
Гл. 5 Система автоматизированного конструирования печатных плат 90
Заключение 127
Список литературы 130
- Проблемы автоматизации решения задач размещения и трассировки при проектировании РЭА
- Алгоритм размещения с моделированием конфигурации межэлементных связей
- Модель коммутационного поля и адаптация подсистем трассировки к изменениям конструктивно-технологических ограничений
- Алгоритмы трассировки связей
- Система автоматизированного конструирования печатных плат
Введение к работе
В настоящее время общепризнано, что уровень развития электроники и вычислительной техники является одним из главных факторов ускорения темпов научно-технического прогресса. В то же время отмечено, что сложность радиоэлектронной аппаратуры (РЭА) постоянно растет, удваиваясь каждые 10 лет. Противоречие между ростом сложности РЭА и требованием сокращения сроков ее разработки и изготовления можно разрешить единственным известным в настоящее время способом - автоматизацией всех этапов создания РЭА. Необходимость развития автоматизированных методов и внедрения их в практику отражены в ряде важных государственных решений, рассчитанных на долголетнюю перспективу.
Одним из этапов, от которого в значительной степени зависят все характеристики изделия, является этап проектирования. Независимо от назначения РЭА в процессе проектирования наступает момент, когда принципиальная электрическая схема устройства должна быть воплощена в реальную конструкцию при ограничениях, диктуемых назначением устройства и технологией его изготовления. Решается следующая задача: разместить элементы схемы, жестко зафиксировав их друг относительно друга, и реализовать все межэлементные связи в соответствии с принципиальной электрической схемой. Эта задача является наиболее трудоемкой из всех задач проектирования. Комбинаторный характер этой задачи, необходимость учитывать множество дополнительных конструктивно-технологических ограничений и большой объем рутинной работы требуют длительных усилий опытных специалистов. Вместе с тем, любые ошибки на этом этапе приводят впоследствии к большим затратам времени и средств на их исправление в уже _ 4 - готовом узле РЭА.
Актуальность автоматизации решения задач размещения и трассировки оперделяется общим экономическим эффектом (сокращением сроков и улучшением качества), который можно получить от автоматизации проектирования РЭА, включающем в себя в качестве наибольшей составляющей эффект от автоматизации процесса размешения и трассировки. Как результат завершения этого процесса автоматически может быть получен комплект конструкторской документации и управляющей информации для станков с числовым программным управлением (ЧПУ), изготавливающих узел РЭА и контролирующих безошибочность его изготовления. Важным дополнительным эффектом от автоматизации процесса размещения и трассировки является улучшение условий работы конструктора, освобожденного от рутинного, требующего особой внимательности, труда.
Целью диссертационной работы является исследование и разработка алгоритмов и программ для ЭВМ, позволяющих повысить эффективность автоматизированного решения задач размещения и трассировки. В частности, в качестве целей поставлены задачи обеспечения взаимодействия этапов размещения и трассировки с помощью единых оценочных критериев; разработки метода автоматической адаптации алгоритмов и программ трассировки к конструктивно-технологическим изменениям узлов РЭА; повышения быстродействия и снижение потребностей в памяти базовых алгоритмов реализации межэлементных связей на этапе трассировки. Выбор этих задч и подходы к их решению обусловлены следующими причинами.
Несмотря на комбинаторный характер единой задачи физической реализации принципиальной электрической схемы в виде узла
РЭА, ее решение с помощью алгоритмов, основанных на глобальном переборе вариантов, практически неосуществимо ни сейчас, ни в обозримом будущем. Объясняется такое положение слишком большой размерностью тех математических задач, к которым можно было бы свести многие конкретные задачи размещения и трассировки. До сих пор не удавалось получить удовлетворительного решения такой задами и другими методами. Единственный доступный в настоящее время подход к решению задачи состоит в разбиении единой задачи на две: размещения элементов и трассировки связей.
Тогда задача размещения могла бы быть сформулирована как задача отыскания для каждого размещаемого элемента такого местоположения на коммутационном поле, котшрое обеспечит 100%-ю трассировку на заданном количестве слоев. В такой постановке задачу размещения до сих пор никому решить не удалось: точных алгоритмов решения этой задачи, реализация которых была бы возможна на ЭВМ, не существует. Вместо сформулированной решается задача размещения, для которой положение каждого размещаемого элемента определяется с помощью косвенных критериев, имеющих эвристическое происхождение.
Задача трассировки решается уже после фиксации всех размещаемых элементов, и в процессе трассировки никак нельзя повлиять на результат размещения, т.е. трассировка рабоаает независимо от размещения и не учитывает предположений о будущих трассах, сделанных на этапе размещения. Таким образом, искусственное разделение единой задачи на слабо взаимодействующие подзадачи - одна из главных причин отставания качества алгоритмического решения задачи размещения и трассировки от качества решения этой же задачи конструктором.
Следовательно, представляется актуальной задача нахожде- ния таких критериев размещения элементов, которые моделировали бы реализацию связейв будущей трассировке, а сам процесс трассировки мог бы использовать результаты моделирования. В этом случае обе задачи решались бы взаимосвязанно с одними и теми же критериями и целевыми функциями. Такой алгоритм размещения и предлагается в диссертации.
В настоящее время существует множество конструктивно-технологических методов физической реализации принципиальной электрической схемы, выбираемых в зависимости от назначения устройства РЭА и условий его применения. Широкий класс конструктивно-технологических методов, включающий в себя, в частности, реализацию схемы в виде печатных плат, микросборок, некоторых типов интегральных схем, а также конструкций верхнего уровня, позволяет представлять вышеупомянутую задачу как размещение элементов в заданной области плоскости и реализацию межэлементных связей на совокупности параллельных плоскостей (слоев) с запрещением пересечений связей в одном слое и различными ограничениями на межслойные переходы. При попытке формализовать эту задачу для конкретного метода изготовления выясняется сильная зависимость математической модели от всевозможных конструктивно-технологических ограничений, заставляя разработчиков САПР придумывать принципиально отличающиеся алгоритмы для "похожих" условий. Особенно остро проявляется эта проблема в условиях промышленной эксплуатации САПР: во-первых, часто возникает ситуация, когда при выполнении очередного задания на конструирование узла РЭА невозможно эффективно использовать алгоритмические методы из-за незначительных качественных отличий в конструкции или в ограничениях на технологию изготовления; во-вторых, при попытке тиражировать программное обеспечение САПР выясняется, что для успешной работы в условиях заказчика программы САПР должны быть переработаны из-за тех же небольших отличий в конструкции узлов РЭА и технологических ограничений, что часто приводит к большим затратам времени и средств и как правило требует привлечения разработчиков САПР. Наиболее сложно решать эту проблему для алгоритмов и программ трассировки, работающих с более детальной информацией, чем алгоритмы размещения.
Следовательно, представляется актуальной задача построения таких алгоритмов, в частности, алгоритмов трассировки, которые слабо зависели бы от изменений конструктивно-технологических ограничений на изготовления узлов РЭА. В диссертации предлагается алгоритм построения модели коммутационного поля для алгоритмов трассировки, преобразующий разнородные данные о конструктивно-технологических ограничениях в один и тот же набор параметров модели, т.е. вьшолняется параметрическая адаптация алгоритма трассировки. Взаимодействие между моделвю и алгоритмом трассировки организовано так, что последний оказывается независимым от качественных изменений во входных данных, поступающих на вход алгоритма построения модели.
В САПР, где получение окончательного результата трассировки, удовлетворяющего всем требованиям конструктора, основано на алгоритмическом решении, более 90% всего времени занимает сам процесс реализации межэлементных связей. Если учесть, что обычно цикл проектирования требует от нескольких часов до десятков часов времени работы процессора ЭВМ, а алгоритмы трассировки являются критическими по отношению к потребностям па- мяти ЭВМ, следует считать актуальной проблему повышения быстродействия и сокращения потребностей в памяти базовых алгоритмов реализации связей, в частности, алгоритмов важнейшего класса алгоритмов, основанных на идее распространения волны.
В диссертации предложены алгоритмы реализации связей, ос-нованнные на идее распространения волны на плоскости, выигрыш в быстродействии которых по сравнению с другими алгоритмами обусловлен групповой обработкой ячеек дискретного рабочего поля (ДРП) и более эффективной организацией данных. Предложено также обобщение волнового алгоритма на произвольное число источников волны с весовой функцией общего вида при трехбитовом (минимальном) кодировании состояний ячеек ДРП. Последний алгоритм допускает естественную и эффективную реализацию на многопроцессорной ЭВМ.
Таким образом, на основе анализа различных методов и алгоритмов размещения элементов и трассировки связей и их приложений к проектированию узлов РЭА с различными коструктивно-технологическими условиями поставлены и решены следующие задачи:
1. Разработать алгоритм размещения элементов разной формы и размеров, в котором местоположение элементов определяется на основе моделирования процесса реализации связей с учетом их реальной конфигурации, а результаты моделирования могут быть использованы на этапе трассировки в качестве управляющей информации .
2. Разработаь алгоритм построения модели коммутационного пространства, автоматически адаптирующийся к изменениям кон структивно-технологических требований и предназначенный для алгоритмов трассировки, работающих с дискретным рабочим полем.
Разаработать алгоритмы реализации связей на дискретном рабочем поле с повышенным быстродействием и меньшими потребностями в оперативной памяти ЭВМ.
На основе предложенных алгоритмов разработать программы для САПР печатных плат с целью экспериментальной проверки эффективности предложенных решений в части адаптируемости алгоритмов и экономичности использования ресурсов ЭВМ при решении задач большой размерности.
Говоря о практической ценности результатов, полученных в диссертации, можно отметить, что комплекс предложенных алгоритмов размещения и трассировки могут стать основой для адаптируемых САПР, предназначенных для монтажно-коммутационного проектирования узлов РЭА на различной конструктивной основе, в частности, печатных плат и интегральных схем с различной степенью интеграции.
Все алгоритмы прошли экспериментальную проверку, в том числе в промышленных условиях, в составе САПР печатных плат, разработанной в Институте проблем управления.
Система внедрена на ряде предприятий с годовым экономическим эффектом 80 тыс. руб.
Основные результаты работы докладывались и обсуждались на всесоюзных и зарубежных конференциях, в том числе: на II Всесоюзном совещании "Автоматизация проектирования и конструирования" (Ленинград, 1983), на Всесоюзном совещании-семинаре "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации САПР РЭА (Москва, 1981), на X Всесоюзном совещании-семинаре "Теория, методы и программные комплексы ав- томатизации проектирования современных ЭВМ и их элементов" (Крымская область, 1982), на УІ Международной конференции по исследованиям в промышленности (Нови-Сад, Югославия, 1981), на 29 Международном коллоквиуме Высшей технической школы в Ильме-нау (Ильменау, ГДР, 1984), на ІУ Международном коллоквиуме "Интертехно-81" (Будапешт, ВНР, 1981).
По теме диссертации опубликовано 10 работ.
Диссертация состоит из введения, пяти глав, заключения и списка литературы.
Первая глава диссертации посвящена обзору алгоритмических методов решения задач размещения и трассировки при автоматизированном конструировании РЭА. Значительное внимание уделено организации взаимодействияяалгоритмов размещения и трассировки и выбору критериев качества размещения, обеспечивающих такое взаимодействие. Показано, что существующие критерии качества размещения, на основе которых строится прогноз о ходе последующей трассировки, не обеспечивает точности, необходимой для выполения этого прогноза на этапе трассировки. Показывается также, как влияет на качество трассировки варьирование конфигурации связей, оцениваемых на этапе размещения, и выбор стратегии трассировки, зависимой и независимой от алгоритма размещения. На основе проведенного анализа делается вывод о необходимости более тесного взаимодействия алгоритмов размещения и трассировки и учета реальной конфигурации связей на этапе размещения для повышения качества конструирования в автоматическом режиме.
В качестве одной из важнейших задач рассматривается задача адаптации алгоритмов конструирования, в особенности алгоритмов трассировки, к различным конструктивно-технологи- - II - ческим требованиям. Показано, как решение этой задачи влияет на такие важные характеристики САПР, как уровень автоматизации проектных процедур, вожможность тиражирования, стоимость эксплуатации и развития системы.
При анализе алгоритмов трассировки выделяется проблема их взаимодействия с алгоритмами размещения и распределения функций между ними и, как одна из важнейших, задача повышения эффективности процедур проведения связей, актуальность которой обусловлена постоянно возрастающими размерностями задач и ограничениями на время ответа САПР при конструировании в интерактивном режиме.
Во второй главе предлагается алгоритм размещения разногабаритных элементов с моделированием конфигурации межэлементных связей при выборе на очередном шаге элемента - кандидата на размещение и выборе для него расположения на коммутационном поле. Описан процесс моделирования, основанный на рассмотрении возможных конфигураций связей и областей для них, необходимых для разрешения конфликтов между связями. Показано, как в процессе моделирования получить разбиение связей на двухконтактные фрагменты (если базовые алгоритмы трассировки этого требуют) , распределить их по слоям, назначить области межсойных пе-реходв. Рассмотрены вопросы представления процесса трассировки как последовательности шагов, на каждом из которых реализуется единственный фрагмент в области коммутационного поля, ограниченной для этого фрагмента на этапе размещения, и вытекающей отсюда возможностью декомпозиции задачи трассировки с целью сокращения ее размерности.
В третьей главе рассматриваются вопросы построения модели коммутационного пространства для трассировки, обеспечива- ющей адаптацию алгоритмов трассировки к изменениям конструктивно-технологических требований. К таким требованиям относятся в первую очередь требования, сводимые к геометрическим ограничениям, а именно, задание координат контактов, не кратных какому-либо допустимому значению дискрета координатной сетки; варьирование размеров и формы контактных площадок элементов; задание различных значений ширины трасс для различных связей; ограничения на организацию межслойных переходов трасс и т.п.
Для построения адаптируемой подсистемы трассировки в САПР РЭА процесс трассировки организован как взаимодействие двух алгоритмов: алгоритма построения модели коммутационного пространства и алгоритма реализации связей. Алгоритм построения ... модели обеспечивает интерфейс с внешней средой для алгоритма реализации связей и выполняет функции преобразования разнообразных данных о конструктивно-технологических ограничениях в набор параметров модели, который остается постоянным в широком диапазоне внешних условий. Алгоритм реализации связей в этом случае оперирует только терминами модели, не проверяя никаких качественных или количественных ограничений и не завися от них.
В четвертой главе рассматриваются впросы построения эффективных алгоритмов трассировки связей. На основе предложен-ног в диссертации подхода к размещению отнесена часть функций, традиционно выполняемых на этапе трассировки связей, таких, как распределение связей по слоям, определение порядка реализации связей, разбиение связей на двухконтактные фрагменты, определение точек межслойных переходов и т.п. Таким образом, алгоритм трассировки имеет четкие предписания относительно каждого фрагмента связи, и в задачу трасиировки входит реализация каж- - ІЗ - дой связи на указанном слое (или слоях) с заданными конструктивно-технологическими ограничениями. Выполение последнего требования обеспечивается алгоритмом построения модели коммутационного пространства. Эффективная реализация связей подразумевает требования к быстродействию алгоритма и необходимому объему оперативной памяти ЭВМ. В диссертации предложены алгоритмы групповой обработки ячеек дискретного рабочего поля, в несколько раз увеличивающий скорость распространения волны, и алгоритм, являющийся обобщением волнового алгоритма с произвольным числом источников волны на случай весовой функции общего вида. Для всех алгоритмов предожены эффективные варианты программной реализации, включая организацию данных и сделаны выводы об эффективности предложенных решений.
В пятой главе рассматриваются вопросы применения предложенных методов в автоматизированном конструировании печатных плат и приводятся результаты экспериментальных исследований. Описана стрктура САПР печатных плат, разработанная на основе предложенных в диссертационной работе алгоритмов размещения и трассировки, в которой большое внимание уделяется взаимодействию между этапами размещения и трассировки, а также достижению высокой эффективности использования основных ресурсов ЭВМ и адаптируемости системы к условиям эксплуатации. В серии экспериментов и при конструировании реальных плат был проведен сравнительный анализ алгоритмов размещения и трассировки связей, который показал эффективность предложенных в диссертации алгоритмов и методов их программной реализации.
На защиту автором выносятся:
I. Алгоритм размещения разногабатирных элементов с моде- лированием процесса прокладки связей как средства для оценки качества выбора элементов и определения их местоположения и обеспечения взаимодействия алгоритма размещения с алгоритмом трассировки связей.
Метод обеспечения адаптируемости алгоритмов и программ трассировки к изменениям конструктивно-технологических требований и алгоритм построения модели коммутационного поля для алгоритмов трассировки.
Алгоритм реализации связей при трассировке на дискретном рабочем поле, основанный на идее групповой обработки ячеек в процессе распространения волны и обеспечивающий высокое быстродействие при еменыпенных потребностях в оперативной памяти ЭВМ.
Алгоритм реализации связей при трассировке на дискретном рабочем поле, являющийся обобщением волнового алгоритма с произвольным числом источников волны на случай весовой функции общего вида и структур данных, необходимых для эффективной реализации его на ЭВМ.
Программное обевпечение подсистем размещения и трассировки в системе автоматизированного конструирования печатных плат.
По теме диссертации опубликованы следующие работы:
Б.А.Кузьмин, А.А.Эйдес, Б.С. Иругов. Адаптируемые системы автоматизированного проектирования печатных плат.-М.: Радио и связь, 1984.-140с.
Б.А.Кузьмин. Применение волнового алгоритма для решения задач трассировки большой размерности.-В сб. Автоматизация проектирования систем управления, под ред. В.А.Трапезникова.-вып.4, М.:Финансы и статистика, 1982, с. 156-167.
Б.А.Кузьмин. Универсальность САПР. Проблемы и решения.-Приборы и системы управления, № I, 1979, с. 7-9.
Кузьмин Б.А., Эйдес А.А. О критериях качества размещения.- Управляющие системы и машины, 1982, № 3, с. 53-56.
А.А.Дорохин, Б.С.Иругов, Б.А.Кузьмин, А.А.Эйдес. Проблемы разработки тиражируемых систем автоматизированного проектирования печатных плат.- В сб. Теория и техника управления.-М.: Институт проблем управления, 1980, с. 47-51.
Б.А.Кузьмин, А.А.Эйдес. 0 методах адаптации САПР РЭА к изменениям конструктивно-технологических решений.- В сб. тезисов докладов II Всесоюзного совещания "Автоматизация проектирования и конструирования", Ленинград, 1983, с. 118—119.
А.А.Дорохин, Б.С.Иругов, Б.А.Кузьмин, А.А.Эйдес. Автоматизированная система конструкторско-технологической подготовки производства в микроэлектронном приборостроении. Материалы ІУ Международного коллоквиума "Интертехно-81", ВНР, Будапешт, 198I, с. 82-91, Ин-т выч. техн. и автоматики АН ВНР.
Кузьмин Б.А., Эйдес А.А. Адаптация систем автоматизации проектирования к изменениям характеристик проектируемых объектов.- Теория автоматов и ее приложения, труды семинара.-Берлин, ГДР, Университет им. Гумбольдта, 1984, с. 45-64.
9. 3.S.I %U
10. A-A. ЯочоШп, BS.Ixuijo^ 6.Д.Киг'ті/г,А.А.Шей. Pickens of JBerefytuf /Ws-pox№& Punted Cttctut Soard САЇЇ Systems.- VI MexvaticnaC Conference en Products Reieaich, A'wi-Sad} Уиуо&бігсй,, Аид. 2*1-19, 1981\ pp. /S7~ 165,
Проблемы автоматизации решения задач размещения и трассировки при проектировании РЭА
Задачу реализации принципиальной электрической схемы в виде блока устройства можно сформулировать как задачу нахождения для каждого элемента схемы такого положения в пространстве, а для каждой связи такой конфигурации проводника, при которых будут выполнены все конструктивно-технологические ограничения. На практике это означает, что (чаще всего) элементы схемы должны быть размещены на одной плоскости, а связи должны располагаться на одном или нескольких слоях без пересечений в одном слое. Если бы элементы схемы имели пренебрежимо малые размеры, а проводники, реализующие межэлементные связи, не имели ширины, то для однослойной конструкции, например, задача была бы эквивалентна задаче планарной укладке графа. Но даже эта задача в настоящее время не имеет удовлетворительного решения. В общем случае даже не известно, существует ли решение при конкретных условиях. Неизмеримо возрастает сложность задачи, когда приходится учитывать геометрические размеры и форму всех элементов конструкции блока, а также ряд ограничений электромагнитного характера. Большинство ограничений на условия задачи приводят к плохо формализуемым комбинаторным задачам, которые неразрешимы методом перебора ни на одной из существующих ЭВМ для размерностей задач, отражающих потребности практики (число размещаемых элементов от 100 и более, число связей порядка нескольких тысяч). Тем не менее, важность автоматизации решения поставленной задачи, обусловленная ее ключевым значением для ускорения всего процесса проектирования устройств РЭА, ее трудоемкостью и рутинным характером работы конструктора при ее разрешении, привлекали и привлекают к ней внимание специалистов по автоматизации проектирования РЭА. За более чем 20-летнюю историю попыток ее решения предложены сотни алгоритмов, проведено множество экспериментов. Но и сейчас нельзя сказать, что качество алгоритмического решения задачи приближается к качеству решения этой же задачи конструктором.
Сложность поставленной задачи с самого начала вынуждает разработчиков САПР РЭА разбивать единую задачу на две подзадачи: размещения элементов и трассировки связей. Задача размещения могла бы быть сформулирована как задача отыскания для каждого размещаемого элемента такого местоположения на коммутационном поле, которое обеспечит 100%-ю трассировку на заданном количестве слоев. В такой постановке задачу размещения до сих пор никому решить не удалось: точных алгоритмов решения этой задачи, реализация которых была бы возможна на современных ЭВМ, не существует. Вместо сформулированной решается задача размещения каждого элемента так, чтобы оптимизировать его положение на коммутационном поле по отношению к выбранным критериям качества. Сами критерии являются эвристическими и отражают общее понимание проблемы разработчиком САПР. Все недостатки такого подхода ярко проявляются на этапе трассировки, когда неудачно размещенные элементы приводят к невозможности реализовать некоторые связи. (Следует отметить, что даже для идеального размещения трудно найти то положение проводников, которое реализует все связи схемы). Следовательно, нужны такие критерии качества размещения, которые отражали бы потребности последующей трассировки и при этом реализация размещения на ЭВМ была бы возможна при допустимых затратах времени и памяти ЭВМ. В диссертации (гл.2) сделана попытка рассмотреть на этапе размещения возможные конфигурации будущих трасс с целью такого выбора расположения каждого элемннта, чтобы минимизировать число конфликтующих трасс. По окончании размещения определен порядок прокладки трасс и области их проведения с учетом положения фрагментов трасс на заранее заданном количестве слоев. Эта информация является указанием для алгоритма трассировки. Таким образом, обе задачи - размещения и трассировки рассматриваются как взаимосвязанные посредством одних и тех же критериев, и как показали експерименти, на этапе трассировки были исключены ситуации, типичные при других подходах, когда любая трасса, проведенная на этапе трассировки с нарушением прогноза, становится препятствием для последующих трасс, которые затем занимают случайно свободные участки коммутационного поля.
Алгоритм размещения с моделированием конфигурации межэлементных связей
Как уже указывалось в гл. І, в качестве исходных данных при решении задачи размещения должны быть заданы: данные о конфигурации и размерах коммутационного поля; число и геометрические размеры конструктивных элементов, подлежащих размещению; список связей между размещаемыми элементами; некоторые начальные условия, содержащие, в частности, ограничения на взаимное расположение некоторых элементов, список и местоположение директивно размещенных элементов. В соответствии с требованиями к моделям межэлейентных связей, сформулиюованным в 1.2.I, добавим к исходным данным координаты контактов элементов, значение ширины проводников, реализующих связи, и допустимые зазоры между проводниками и, если это необходимо, схемотехнические ограничения на способы соединения контактов ( 1.2.I).
Введем некоторые определения и обозначения. Будем считать, что задано множество Еа-{&і3 -гу7Єк\ элементов, элементы могут иметь различную форму и размеры. Пусть для размещения выбрана модель коммутационного поля для разногабаритных элементов и один из алгоритмов начального размещения, точнее, основная процедура укладки элементов на коммутационном поле. Для определенности будем считать, что алгоритм укладки последовательный, на каждом шаге алгоритма решаются две задачи: выбор следующего элемента для размещения и выбор местоположения элемента на коммутационном поле.
Цепь - список контактов, сопротивление медцу которыми согласно электрической схеме равно нулю ( на рис. 2.1 показаны две цепи АвСд и EFG- и вариант соединения контактов цепей проводниками).
Фрагмент - часть цепи, состоящая либо из двух контактов, либо из контакта и межслойного перехода, либо из двух межслой-ных переходов (очевидно, что от выбора разбиения цепи на фрагменты существенно зависит результат трассировки, например, на рис. 2.2 показаны два варианта такого разбиения; если удалить фрагмент АЬ и провести, как пойазано пунктиром, фрагмент АС , то трассировка обеих цепей на одном слое невозможна).
Модель коммутационного поля и адаптация подсистем трассировки к изменениям конструктивно-технологических ограничений
Среди множества подходов к построению алгоритмов трассировки, предложенных за годы развития методов автоматизации решения задачи трассировки, наиболее эффективными оказались два. Один из них основан на волновом алгоритме [ 51,57], другой, более поздний, - на идее трасссировки в каналах [ I, 68]. Следует подчеркнуть, что канальные алгоритмы своим возникновением обязаны, в первую очередь, недостаткам волнового алгоритма, а именно, относительно малым быстродействием и большими потребностями в оперативной памяти ЭВМ. (Строго говоря, канальные алгоритмы и алгоритмы трассировки, построенные на основе волнового алгоритма, противопоставляются еще и по стратегии трассировки. Применение первых разбивается на два этапа: распределение связей по каналам и трассировка в каналах. На первом этапе конфигурация связей не фиксируется. Алгоритмы же трассировки на базе волнового алгоритма ассоциируются с последовательной реализацией связей,. Однако, в последние годы многие проблемы стратегического характера устранены, в частности, работами автора [ 77,46 ]) С точки же зрения качества решения и возможностей адаптации волновой алгоритм имеет существенные преимущества перед канальными алгоритмами. Отметим также, что канальные алгоритмы очень чувствительны к изменениям конструктивно-щехнологических требований, а наилучшие результаты с его помощью могут быть получены при регулярном разбиении поля трассировки на каналы, характерном при регулярном размещении однотипных радиоэлементов О,2,50J , а при конструировании РЭА для схем с разнотипными и разногабаритными элементами ряд проблем еще не решен.
Приведенными соображениями объясняется выбор в качестве базовой процедуры волнового алгоритма, для которого были предложены новые решения, позволившие существенно повысить его быстродействие при приемлемых потребностях в оперативной памяти ЭВМ (см. гл. 4).
Выбор волнового алгоритма определяет следующие требования к абстрактной модели, выполнение которых обеспечивает справедливость основной теоремы о существовании и оптимальности решения 51 ] .
Пусть С - множество элементов, называемых ячейками: С в { с\ С2,... J . Для каждой С1 Є С определяется подмножество N(с1) С С называемое единичной окрестностью ячейки Сс : А/(С) « [с/, С ,..., С . Для ячеек-соседей С должны выполняться следующие правила:
1) В каждой единичной окрестности должно быть точно П ячеек, где П t п.ъ 1 есть некоторое заранее определенное число, зависящее от конкретной модели.
2) Если с е А/(с ) , то с & ЛҐ(С ). Единичная окрестность может рассматриваться как функция с областью определения С и областью значений в множестве подмножеств С Для каждой из единичных окрестностей определяются П, функций df, dz ,..., dn (d; : С =? с) » определяемые следующим образом:
Таким образом, d (clj является ячейкой единичной окрестности С1 по координате k .
Пусть S - конечное множество синволов: S = fs/, ,.-. ,SmJ. Назовем $ алфавитом пространства !, Пусть Г - отображение С на С S , а именно, Vc e С Г(су- (clfsJ)fs e S . В общем случае можно записать ffcO-fc tS (с1)) . Таким образом, каждой ячейке С G С ставится в соответствие некоторый символ s (с )в S Отображение выбирается в зависимости от условий конкретной задачи построения пути.
Пусть С с J - две различные ячейки в С . Путь р(с ,с ) определяется как множество ячеек (или цепь) р(.с%1с ) \солС1 с1 C ...,c"Vc /, такое, что с 1е ЛҐ(с{) для всех і = О/,...f rn-1, Обозначим также Ж (се с ) множество всех путей из ячейки с1 в ячейку С .
Пусть М - отображение {я(с(,с )І = { 1 Любой путь p(cl,cJ) , такой, что М (p(c ,cJ)) =1 называется допустимым путем, а р(с1,с ) М(р(с1,с ))т О - недопустимым. Множество всех допустимых путей обозначим Jr (cftcJ).
Алгоритмы трассировки связей
В работе 51 J предложено решение задачи нахождения пути минимального веса на графе, удовлетворяющем специальным требованиям, изложенным в гл.З. В приложениях этого алгоритма, названного волновым, к задачам трассировки связей при автоматизации конструирования РЭА выявились следующие недостатки алгоритма:
1) малое быстродействие из-за необходимости в множестве операций поиска в массивах фронтов волны и необходимости анализа пг Ы+\ вершин графа для достижения цели, находящейся на расстоянии П от вершины-источника (коммутационное поле представлено ортогональным решетчатым графом);
2) большие потребности в оперативной памяти ЭВМ для представления коммутационного поля (число вершин графа порядка 10 Ю5).
В последующие годы были предложены новые алгоритмы, основанные на той же идее, но более практически приемлемые. Так, в [ 2 ] показано, что при некоторых условиях можно уменьшить число состояний каждой ячейки коммутационного поля (т.е. вершины соответствующего графа) до четырех. Однако, быстродействие алгоритма осталось прежним, а уменьшение числа состояний ячеек привело к тому, что алгоритм стал пригоден только для полей с одинаковыми ячейками и одного и того же веса. (Ради справедливости следует отметить, что это самый распространенный случай на практике). В работе Г 57 ] доказано, что весовую функцию алгоритма можно дополнить таким образом, что направление поиска будет преимущественно в сторону цели, а зона поиска нового алгоритма не более, чем алгоритма, описанного в [ 51 J. Действительно, экспериментальная проверка этого алгоритма показала сокращение зоны поиска, однако, это сокращение заметно увеличивает быстродействие алгоритма при относительно простом лабиринте препятствий на ДРП и достаточно сложной функции исходного алгоритма (немодифицированного). Кроме того, при нетривиальной весовой функции много времени уходит на поиск в массиве фронтов ячеек с весом, равным заданному порогу значений. Последнее обстоятельство и значительные потери времени, обусловленные поиском минимума значений, были учтены в алгоритме, предложенном в [ 19 ] , названном авторами "алгоритм слежения за целью", основная идея которого состояла в выборе такой весовой функции, которая обеспечивала поиск на ДРП в направлении цели, а исследуемые ячейки ДРП можно было бы выбирать из массива без дополнительного поиска. Однако этот алгоритм хотя и имеет при относительно простой конфигурации препятствий на ДРП зону поиска, меньшую, чем в [" 57 ] , в некоторых случаях строит неприемлемые пути, вес которых по отношению к весу оптимального пути не ограничен. Например, на рис. 4.1 показано ДРП и путь, построенный алгоритмом слежения за целью (сплошная линия), а также оптимальный путь (штриховая линия). Альтернативное решение предложено в [ 58 J, где использование системы стеков помогает распределить ячейки по значениям весовой функции. Здесь уместно сказать, что для задач трассировки практически не важно, гарантирует ли алгоритм получение оптимального пути (в частности, пути минимальной длины), так как оптимальность отдельно взятого пути (т.е. трассы) не гарантирует оптимальности множества путей (в частности, минимума суммарной длины всех трасс). Важно лишь, чтобы отклонение пути от оптимального было ограничено. Желательно также, чтобы алгоритм всегда находил путь, если он существует.
Система автоматизированного конструирования печатных плат
Обзоры в работах [ 96,1, 50,126J дают общее представление об организации систем автоматизированного конструирования печатных плат и о методах решения задач размещения и трассировки. По этим материалам можно отметить следующие тенденции в развитии систем. Как и ранее, в процессе конструирования выделяется ряд относительно самостоятельных функций (ввод и контроль данных, размещение, трассировка, получение документов, функции, обеспечивающие диалог и т.п.), но в отличие от систем более раннего периода, в настоящее время программы, реализующие эти функции, в большинстве систем (более Ъ0%) используют центральную базу данных. Однако, для относительно простых систем еще сохраняется метод организации данных в виде системы буферных файлов, когда выход одной программы системы является входом следующей. С точки зрения взаимодействия с оборудованием и операционной системой системы конструирования обычно представляют собой прикладную программу, работающую под управлением операционной системы. Это, в частности, означает, что система представляет собой готовую к загрузке и выполнению программу, прошедшую стадии компиляции составляющих ее модулей и редактирования межмодульных связей, полностью определяющие структуру системы и условия ее функционирования. Как правило, объем оперативной памяти, требуемой для для загрузки САПР, превышает объем ОЗУ ЭВМ. Для разрешения этой проблемы существует несколько способов, определяемых свойствами и возможностями операционной системы. Один из них -построение оверлейной программы, другой - использование виртуальной памяти в сочетании со свопингом, обычно используемым в операционных системах с разделением времени. Во всех перечисленных случаях общим является то, что для включения новых функций в систему при ее развивши и адаптации требуются этапы компиляции (по крайней мере ведущей программы системы) и повторное редактирование связей. Отметим, что такие изменения могут быть выполнены только системными программистами и часто требуют отладки на уровне языка программирования, на котором написаны программы системы.
В зависимости от состава и возможностей оборудования ЭВМ и требуемого режима работы САПР организуется взаимодействие с конструктором. Существует два основных режима работы. Если САПР реализована на мини- или супермини-ЭВМ, то основной режим работы - разделение времени с числом терминалов, зависящим от мощности ЭВМ - от 2-х до 40. В таких САПР имеются достаточно развитые средства диалога с удобными инструментами ввода графической информации и ее отображения. Программы размещения и трассировки относительно просты и рассчитаны на тесное взаимодействие с конструктором. Другой режим работы - рабочая станция или автоматизированное рабочее место (АРМ), автономная или связанная с мощной центральной ЭВМ. Для таких САПР разработаны достаточно сложные алгоритмы размещения и трассировки. Следует отметить, что в СССР такие САПР появились только недавно, а программное обеспечение АРМ еще не обладает до - 92 статочными возможностями при реализации функций конструирования, в частности, невысок уровень автоматизации решения задач размещения и трассировки, особенно для печатных плат с произвольными наборами радиоэлементов и разнообразием конструктивно-технологических требований. За рубежом автономные рабочие станции для автоматизированного конструирования печатных плат строятся на базе супермини-ЭВМ (32-разрядные слова, 1-Ю млн. опер./сек, 1-Іб Мбайт оперативной памяти и 160-300 Мбайт дисковой памяти). В СССР ЭВМ с аналогичными характеристиками, допускающие их использование в качестве АРМ, пока не производятся.
Многообразие САПР печатных плат за рубежом (только в США более 50 поставщиков систем) частично решает проблему адаптации к конструктивно-технологическим требованиям пользователя. Очень часто выбор САПР опЭрделяет технологию изготовления плат, а относительно низкая стоимость аппаратных средств САПР во многих случаях снимает проблему адаптации программного обеспечения к смене ЭВМ и периферийного оборудования. Однако, по мере усложнения и относительного удорожания программного обеспечения систем эта проблема обостряется. В СССР, по крайней мере на ближайшие несколько лет, наиболее актуальной задачей в области САПР будет создание тиражируемой САПР печатных плат, относительно простой и экономичной, которая сможет адаптироваться либо автоматически, либо с участием пользователей, к составу оборудования ЭВМ и, самое важное, к изменениям конструктивно-технологических требований.
