Содержание к диссертации
Введение
1. Характеристика автоматизированных систем конструирования РЭА.
1.1 Обзор научных достижений в области создания систем автоматизированного проектирования 8
1.2 Организация процесса проектирования в системах автоматизированного проектирования 27
1.3 Научные положения, решаемые в диссертационной работе 36
2. Методы анализа коммутационных плат 45
2.1 Моделирование факторов, влияющих на трассируемость цепей электрической схемы 45
2.1.1 Трассировка проводников на мелкодискретном рабочем поле двусторонней печатной платы 48
2.1.2 Трассировка проводников на мелкодискретном рабочем поле односторонней платы ЧЯ
2.1.3 Трассировка проводников на мелкодискретном рабочем поле многослойной печатной платы
2.1.4 Трассировка проводников на подложках интегральных схем ИС с многоуровневой коммутацией 50
2.2 Интегральный метод анализа коммутационных возможностей плат . 52
2.3 Прогнозирование количества нетрассируемых цепей электрической схемы 65"
2.4 Метод локальных оценок соединений ?/
2.5 Методы анализа плат с неортогональной трассировкой проводников g7
2.6 Сравнение методов анализа коммутационных плат 94
3. Методы топологического синтеза проводящих покрытий. 97
3.1 Использование интегрального метода анализа
3.2 Использование метода локальных оценок проводников
в алгоритмах трассировки плат
3.3 Синтез проводящих покрытий по критерию минимизации количества рёбер остовного графа
3.4 Сравнение методов синтеза проводящих покрытий
4. Система автоматизированного проектирования, использующая анализ и синтез укладок графов 135
4.1 Моделирование рабочего поля для трассировки 136
4.2 Хранение промежуточных данных -Щ8
4.3 Лингвистическое обеспечение системы 150
4.4 Программное обеспечение /53
4.5 Техническое и информационное обеспечение системы 15$
4.6 Вопросы экспериментального исследования автоматизированных систем 16Ц
Заключение 172
Литература 175
- Обзор научных достижений в области создания систем автоматизированного проектирования
- Моделирование факторов, влияющих на трассируемость цепей электрической схемы
- Использование интегрального метода анализа
- Моделирование рабочего поля для трассировки
Введение к работе
Разработка современной аппаратуры для телевидения, радио, вычислительной техники и спецтехники в настоящее время немыслима без использования автоматических и полуавтоматических систем проектирования. В первую очередь это объясняется возрастающей сложностью самой аппаратуры, увеличением её функциональных возможностей и микроминиатюризацией, которая, в свою очередь, требует повышения точности и повторяемости технологических процессов проектирования, общей культуры производства,
В решениях ХХУ, ХХУІ съездов КПСС указывалось на необходимость внедрения автоматических систем на базе электронно-вычислительной техники в промышленность, что должно дать существенное увеличение производительности труда и эффективности производства. "... увеличить производство приборов, оборудования, средств автоматизации, реактивов и препаратов для проведения научных исследований. Расширять автоматизацию проектно-конструкторских и научно-исследовательских работ с применением электронно-вычисли-тельной техники." - говорится в Основных направлениях экономического и социального развития СССР на 1981 - 1985 годы и на период до 1990 года.
Для решения этих задач необходимо дальнейшее развитие вычислительной техники, совершенствование её элементной базы, программного и математического обеспечения. Большую роль в этом должно сыграть внедрение мини- и микро-ЭЕМ, а также промышленных роботов. "... развивать производство и обеспечить широкое применение * "Правда", № 64 от 05.03.81. автоматических манипуляторов промышленных роботов , встроенных систем автоматического управления с использованием микропроцес-соров и микро-ЭВМ."
Вычислительная техника за последнее время пополнилась рядом новых высокопроизводительных машин. Особенно сильное развитие получили системы больших и малых ЭШ (ЕС ЭВМ и СМ ЭВМ) . Пополнился и парк периферийного оборудования к этим ЭВМ. Шире стали использоваться координатографы, графические дисплеи, быстродействующие накопители на гибких магнитных дисках и магнитной ленте кассетного типа. Появились растровые координатографы, позволяющие значительно сократить цикл получения фотошаблонов печатных плат и микросборок. "Уже созданы научные основы построения систем автоматизированного проектирования САПР , и на головных предприятиях ряда отраслей они находят практическое применение. Бли-жайшая задача - их широкое внедрение."
Одним из наиболее трудоёмких этапов создания электронной аппаратуры является конструкторская проработка стоек, блоков и отдельных узлов. С середины 70-х годов создание аппаратуры ведётся с помощью комплексных подразделений, включающих в себя специалистов по схемотехнике, технологов и конструкторов, для того, чтобы полнее охватить круг вопросов, решаемых при создании аппаратуры. Сложность управления такими подразделениями создаёт предпосылку к внедрению автоматических и полуавтоматических систем проектирования, где ряд схемотехнических и конструкторско-технологических задач решается с применением ЭЕМ. Этому способ- * "Правда", W 64 от 05.03.81. '* "Правда", Р 83 от 24.03.82. ствует появление обширного парка устройств и станков с числовым программным управлением.
Развитие систем автоматизированного проектирования ведётся по трём направлениям. Во-первых, создаются полуавтоматические системы в которых в-основном решаются задачи технологического характера. Эти системы позволяют сократить трудоёмкость изготовления блоков и узлов путём применения станков с ЧПУ, координатографов, установок контроля и пр. Проектирование с помощью таких систем представляет обычно преобразование графической информации, выполняемое в интерактивном режиме. Используются в-основном ми-ни-ЭЕМ, но существуют автоматизированные системы, построенные на основе больших ЭШ. Во-вторых, параллельно с созданием полуавтоматических систем, ведётся разработка систем, в которых большая часть задач решается полностью без вмешательства человека. Такие системы требуют применения больших ЭЕМ с высоким быстродействием и большим объёмом оперативной памяти. В-третьих - появление средств машинной графики и развитие малой вычислительной техники создало предпосылку к появлению автоинтерактивных систем автоматизированного проектирования, в которых решение задач конструирования основано на взаимодействии человека и ЭЕМ. Наиболее трудоёмкие операции, и операции, легко формализуемые, выполняются в автоматическом режиме подобно системам второго типа. Управление ходом решения задач осуществляется человеком.
Несмотря на продолжительные научные исследования, направленные на создание систем автоматизированоого проектирования, пока ещё не удалось полностью решить все вопросы, необходимые для внедрения этих систем в эксплуатацию. Наиболее существенными из нерешённых вопросов являются вопросы организации процесса проектиро- вания в автоинтерактивных системах, а также состав их программного и математического обеспечения.
Появление в конце 70-х годов автоматизированных рабочих мест (АРМ) с развитым периферийным оборудованием, состыкованного в единый комплекс, сделало актуальной задачу перехода от систем, работающих в режиме интерактивного преобразования графической информации к системам автоинтерактивного типа.
Основная трудность при конструировании печатных узлов с помощью автоматизированных систем состоит в трассировке цепей электрической схемы на коммутационном поле платы. Сложность математических моделей при нахождении решения этой задачи настолько велика, что исключает возможность какого-либо перебора при поиске оптимального решения. Это оправдывает применение эвристических методов. Однако и эвристические методы в своём большинстве не удовлетворяют требованиям, предъявляемым к человеко-машинным системам, особенно автоинтерактивным. Их основной недостаток еос-тоит в том, что для их реализации требуется большое быстродейг ствие от ЭЕМ и значительные объёмы оперативной памяти.
Настоящая работа посвящена математическому и программному обеспечению автоинтерактивных систем проектирования печатных плат.
Обзор научных достижений в области создания систем автоматизированного проектирования
Принято считать, что первой работой в области автоматизированного проектирования была работа [і] , в которой описана программа для ЭШ по анализу логических схем, компоновки схемы по конструктивным узлам и выдачи результатов в виде распечатки таблиц необходимых соединений.
С начала 60-х годов системы автоматизированного проектирования стали развиваться в нескольких направлениях, образуя подсистемы мало связанные друг с другом. Одно из этих направлений было связано с автоматическим конструированием печатных плат и подложек интегральных микросхем. Разделение круга решаемых вопросов на схемотехнические и конструкторские было вызвано несовершенством вычислительной техники и периферийного оборудования. Работы, публиковавшиеся в 60-70-х годах в-основ-ном были посвящены попыткам создания систем автоматического проектирования на основе эвристических алгоритмов трассировки проводников и размещения элементов на платах [2-I0J. Наиболее полно вопросы построения систем нашли отражение в монографиях [II-23] . К этому времени сформировались и выделились подзадачи, решаемые в каждой автоматизированной системе тем или иным методом. Многочисленность методов решения подзадач позволило получать различные по своему назначению и характеру работы системы автоматизированного проектирования путём использования различных вариантов решения подзадач. Классификация таких подзадач приведена на рис. j-l.
Совершенствование вычислительной техники и использование смежных разделов математики, таких, как теория графов, теория формальных систем, теория автоматов и формальных грамматик позволило выделить и по-новому решить ряд проблем, общих для всех автоматизированных систем. К этим проблемам относится техническое обеспечение, информационное, лингвистическое обеспечение и др. Этим вопросам посвящено значительное количество публикаций [2,4,6,9,11,12,15,19,20,23-32] .
Рассмотрим основные подзадачи и методы их решения, возникающие при построении систем автоматизированного проектировав; . ния.
Моделирование факторов, влияющих на трассируемость цепей электрической схемы
Факторы, влияющие (косвенно или непосредственно) на полноту трассировки цепей электрической схемы отличаются большим многообразием и в общем случае являются следствием применённых моделей и алгоритмов. Полная трассировка платы зависит также от конструктивно-технологических требований к печатному монтажу. Алгоритмы трассировки проводников, отличаясь многообразием, используют различные модели рабочего поля и печатных элементов, свойства которых не адекватны моделям,использующимся при "ручном" проектировании.
Для того, чтобы проанализировать влияние указанных факторов, необходимо сравнить возможности для прокладки проводников в автоматизированных системах и при "ручном" проектировании.
Определим "ручное" проектирование как процесс, выполняемый человеком на основе эвристических решений частных подзадач, таких как размещение контактных площадок, трассировка одного проводника из заранее заданного списка, перетрассировка одного или более проводников, и так далее. Такое проектирование ведётся на непрерывной модели платы с учетом заранее заданных конструктивно-технологических ограничений.
Основные приёмы, позволяющие повысить количество проведённых проводников при "ручном" проектировании, следующие:
трассировка печатных проводников может осуществляться в любом направлении плоскости платы;
форма печатных проводников может быть произвольной, в том числе сам проводник может иметь различную ширину на своём протяжении;
контактные площадки для отверстий под выводы электрорадиоэлементов могут иметь произвольную форму, причем они не обязательно должны быть симметричными.
При использовании вышеперечисленных приёмов соблюдаются конструктивно-технологические ограничения, из которых наиболее существенные при дальнейшем рассмотрении следующие:
соблюдение заранее заданных необходимых зазоров между печатными элементами;
соблюдение установленных ограничений на ширину проводников и на размеры контактных площадок под металлизированные от-верстия и пленарные выводы электрорадиоэлементов.
Применение и использование приёмов "ручного" проектирования и ограничений зависят от моделей рабочего поля платы, лишь до некоторой степени адекватно отражающей реальные контактные площадки, проводники и плату для трассировки. Это приводит к тому, что операции, широко применяемые в "ручном" проектировании, становятся невозможными в автоматизированном.
Использование интегрального метода анализа
Величина количества нереализуемых проводников и цепей электрической схемы может быть использована для оптимального синтеза токопроводящих покрытий. Для этого воспользуемся выражением где Е - множество цепей электрической схемы, контакты которых находятся внутри области блокировки S ; in - количество областей блокировок на плате, равное количеству независимых контуров модифицированного графа 6
Количество независимых контуров графа G -(В ,F ) определяется выражением: где CctrdCF ) - количество рёбер графа G ; Card ( 8 ) - количество его вершин; У - количество компонент связности графа & .
Величина ftf J есть цикломатическое число графа G , или первое число Бетти С5 ,6Г, 66,3.
Пусть трассировка проводников осуществляется многошаговым алгоритмом, на каждом шаге которого трассируется один проводник между двумя узлами координатной сетки платы.
Пронумеруем все шаги алгоритма, введя переменную XЄ N , где А/ - множество целых неотрицательных чисел. Пределы изменения Т лежат от нуля до некоторого значения М , опре деляемого выражением
Будем считать оптимальным алгоритмом трассировки такой, при котором
Поясним условие оптимальности, определяемое соотношением (3-І). Пусть в начале трассировки нет таких пар контактов, которые нужно соединить и которые лежали бы в различных областях блокировки. Это означает, что Кн(Р) = 0 . В процессе трассировки не происходит увеличения количества нереализуемых соединений, так как выполняется условие возможности построения трассы между произвольными контактами платы. Таким образом, при выполнении условия (3-І) будет обеспечена полная трассировка платы. В этом случае М = Мо Метод трассировки, для которого справедливо условие (3-І), может быть представлен в виде последовательного циклического алгоритма с проверкой величины Кц в конце каждого цикла.
При использовании условия (3-І) в системах автоматизированного проектирования может быть применён практически любой алгоритм построения трассы проводника, относящийся к первой группе. Это следует из того, что определение количества нереализуемых соединений не зависит от алгоритма трассировки.
Моделирование рабочего поля для трассировки
Как указывалось выше, основная трудность при составлении модели рабочего поля для трассировки состоит в том, что для построения модели проиходится решать ряд взаимно-противоречивых требований. Основные из этих требований приведены ниже.
Во-первых, модель поля платы должна обеспечивать проектирование плат размером до 500 сиг. Во-вторых, при реализации модели на ЭШ должно быть затрачено минимум оперативной и внешней памяти. В-третьих, модель рабочего поля должна быть построена таким образом, чтобы обеспечивалась простая адресация к участкам модели, независимость её от применяемой технологии изготовления плат, простота кодирования и декодирования информации, содержащейся в модели.
Некоторые вопросы, связанные с моделированием рабочего поля рассмотрены в работах [15 ,20,21] . В работах [і2,20,2Hj показано, что оптимальной по многим требованиям моделью рабочего поля является мелкодискретная модель, которая строится следующим образом. Поле платы "разрезается" на квадратные ячейки с постоянным шагом п . Каждой ячейке платы соответствует некоторое поле в памяти ЭШ. Это поле упорядочивается таким образом, чтобы нахождение участка памяти, соответствующего произвольной ячейке платы не сопровождалось значительными вычислительными затратами.
Если количество ячеек платы в направлении оси X равно И , а в направлении оси / - т , то адрес An ячейки с координатами 1у% можно вычислить по формуле:где Ло - адрес начала поля памяти, отведенное под рабочую модель І Обычно шаг "рарезки" платы берется равным шагу координатной сетки платы, т.е. 1,25 мм.
При таком моделировании состояние ячейки поля платы может быть функционально отражено в область целых положительных чисел. Действительно, если область памяти, соответствующая ячейке платы занимает CJ, двоичных разрядов, то в эту область памяти можно записать числа от нуля до 2. - і . Каждое состояние ячейки платы отражается в область целых неотрицательных чисел в диапазоне 0 5 2. А J .Состоянием ячейки платы может быть - наличие проводника на одном из слоев платы, центр металлизированного отверстия, пересечение проводников и т.д.
Для многослойных плат рабочее поле для каждого из слоев создают либо по отдельности, либо, увеличивая поле для записи информации об состоянии ячейки, записывают туда информацию о каждом из слоев. Для двухслойных плат в основном применяют совмещенное рабочее поле, записывая информацию об состоянии ячейки первого и второго слоя в смежные участки памяти.
