автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование методов автоматизированной трассировки однослойных соединений

ч. московский государственный университет

им. М. В. ЛОМОНОСОВА

г,а* !■: '*'?• Факультет вычислительной математики и кибернетики

(со"' :го-'.чся

^ . . д Кафедра системного программирования

и,::..

На правах рукописи

рагайшис саулюс йоно

исследование методов автоматизированной трассировки однослойных соединений

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

москва -1994

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета имени М.Б.Ломоносова.

Научные руководители: доктор физико-математических наук,

профессор Э.З.Лгобимский кандидат физико-математических наук, доцент А. Ю. Миташюнас

Официальные оппоненты:

доктор физико-математических наук, профессор А.Н.Томшшн

кандидат технических наук В. Ю.Вершубский

Ведущая организация:

Институт Системного Программирования РАН

Защита состоится "

199 ¿года в Ц часов на

заседании Специализированного совета Д.053.05.38 по математике при Московском государственного университете им. М.В. Ломоносова по адресу: 119899, Москва, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан " /О " /УСЯОЙА 1994 года.

Ученый секретарь Специализированного совета профессор сз^Ъ-)

Н.П.Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертация посвящена исследованию методов автоматизированной трассировки однослойных соединений и созданию комплекса программ однослойной трассировки, пригодного для включения в состав промышленных САПР радиоэлектронной аппаратуры.

Актуальность темы,

В настоящее время проектирование радиоэлектронной аппаратуры (РЭА) и вычислительной техники (ВТ) немыслимо без применения компьютеров. Проектируемые изделия постоянно усложняются, резко возрастают обьемы проектирования и время реакции на потребности рынка при ручном проектировании становится неприемлемым. Системы автоматизированного проектирования (САПР) значительно сокращают сроки проектирования, уменьшают количество ошибок и позволяют оперативно корректировать завершенные проекты. Применение средств низкоуровневой автоматизации проектирования, например, специализированных графических редакторов, сокращает время разработки проекта, но требуемые темпы могут быть достигнуты лишь автоматизировав основные процедуры проектирования топологии: размещение ЭРЭ и трассировку соединений. Особенно ярко это выражается с появлением концепции автоматизации всего цикла разработки и производства - CAD / CAE / САМ (Computer Aided Design / Engineering / Manufacturing).

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

Цель работы.

Целью работы является разработка метода однослойной трассировки и, путем объединения методов системного программирования и автоматизированного проектирования топологии радиоэлектронных изделий,

создание комплекса программ однослойной трассировки, пригодного для включения в состав промышленных САПР РЭА.

Научная новизна и практическая ценность работы.

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

Разработан новый метод однослойной гибкой (топологической) макротрассировки, не накладывающий ограничений на форму макродискретов и использующий в качестве макродискретов - любые выпуклые многоугольники.

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

Определены требования к системе автоматизированной однослойной трассировки, включаемой в состав промышленной САПР РЭА, принципы ее построения и на основе разработанных методов гибкой трассировки реализован комплекс программ автоматизированной однослойной трассировки, работающий в составе САПР P-CAD, REDAC, DRAFT.

Созданный комплекс программ однослойной трассировки внедрен на НИИСТ "Банга" (г.Каунас, Литва) и НИИТТ "Рекорд" (г.Александров, Россия) в 1993 году. Система однослойной трассировки используется в цикле автоматизированного проектирования ОПП на базе ПЭВМ, совместимых с IBM PC, совместно с САПР P-CAD и заменяет подсистему трассировки PC-ROUTE этой САПР. Предлагаемая система трассировки может быть внедрена и в других организациях, занимающихся проектированием ОПП, а также с небольшими изменениями подсистем ввода-вывода применена для однослойной трассировки многослойных ПП, изготовляемых методом открытых контактных площадок, некоторого класса интегральных схем и ПП, изготовляемых по технологии поверхностного монтажа.

Апробация и публикации.

По теме диссертации опубликовано 11 работ. Материалы диссертации докладывались на заседании кафедры системного программирования

факультета ВМиК МГУ в 1993 г., на научном семинаре кафедры информатики Математического факультета Вильнюсского Университета в 1993 г., на международной конференции "Workshop on Design Methodologies for Microelectronic and Signal Processing" (Краков, Польша) в 1993 г., на международной конференции "Design Automation Conference АРК'92" (Каунас, Литва) в 1992 г., на всесоюзной научно-технической конференции "Проектирование вычислительных средств" (Каунас) в 1989 г., на республиканской конференции "Программное обеспечение ЭВМ" (Паланга, Литва) в 1989 г., на XXIX, XXX, XXXI и ХХХШ конференциях Литовского математического общества в 1988, 1989, 1990 и 1992 г.г.

Структура и обьемдиг ~ёртационной работы.

Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений. Основной (без приложений) текст составляет 98 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

Перваяхлава посвящена обзору и анализу существующих методов автоматизированной трассировки соединений. Обсуждаются отдельные подзадачи общей задачи трассировки. Более подробно разбираются методы определения порядка трассировки, так как проблема очередности особенно актуальна дая однослойной трассировки.

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

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

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

Во иторой_главе подробно рассматривается разработанный метод гибкой однослойной трассировки.

В § 1 приводится определение ДТРП. Все монтажно коммутационное поле Б проектируемого узла разделяется на две области: свободную Рс и запрещенную Область ¥г составляют контактные площадки, внешние выводы, запретные для трассировки зоны и заранее проведенные трассы.

Рс = Р \ ¥г

Область Рс разбивается на макродискреты внутри которых нет элементов Гг. Множество ребер макродискретов множества {} состоит из ребер \г, составляющих край Рс, и внутренних ребер Ус = \ У2, которые не должны пересекаться. Топологическая ситуация описывается плоским графом С^ (Х^ в котором множество Х( соответствует характерным точкам области определяющим изломы краев и наиболее узкие промежутки. Для представления метрических параметров ДТРП вводятся системы пропускных способностей М( и растояний [4.

В обсуждении макродискретов показывается, что макродискреты -треугольники, использованные в практических разработках Р.П.Базилевича, создают дополнительные препятствия для трассировки.

С целью получения макродискретов какой-то определенной формы, например, прямоугольников, которые используются в разработках других авторов, в множество Х( вводятся дополнительные точки, несоответствующие характерным точкам области Г"2. Введение таких точек создает

"искусственное" ограничение пропускных способностей некоторых участков области трассировки. Количество дополнительных точек прямо зависит от регулярности размещения ЭРЭ. Для ПП с нерегулярным размещением ЭРЭ количество таких точек существенно сокращается, используя обобщенные прямоугольники (многоугольники прямоугольной формы), на сторонах которых могут находиться характерные точки области Р7. Такие макродискреты ранее не использовались, поэтому в диссертации была исследована возможность их применения.

Самой общей реализацией модели ДТРП являются макродискреты -любые выпуклые многоугольники и применение их способствует созданию наилучших условий для гибкой трассировки.

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

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

В § 3 выделяются основные этапы гибкой трассировки:

- создание элементов модели ДТРП (покрытие платы макродискретами);

- топологическая (макро) трассировка (собственно гибкая трассировка);

- геометрическая (микро) трассировка (крепление гибких трасс).

В диссертации разработан и экспериментально исследован метод гибкой однослойной трассировки на многоугольниках прямоугольной формы. На этой основе разработан метод трассировки на любых выпуклых многоугольниках. В § 4, § 5, § 6 рассматривается работа обоих методов на каждом этапе гибкой трассировки.

В § 4 обсуждается решение задачи покрытия платы макродискретами. Желательно, чтобы макродискреты были по возможности большими, что прямо связано с быстродействием алгоритма и близкими к" "правильным". Под правильностью нетреугольного макродискрета понимается его близость

к многоугольнику, вписанному в окружность. Это требование связано с равномерностью распространения волны и оценкой пропускных способностей макродискретов. Пропускные способности "правильного" многоугольника определяются пропускной способностью его ребер.

Существуют два принципиально различных подхода к решению задачи покрытия ПП макродискретами: сразу строить окончательные макродискреты или сначала покрыть ПП какими то минимальными, а потом расширять их.

Разработаны два метода покрытия платы многоугольниками прямоугольной формы, основанные на различных подходах. Экспериментальные исследования на ряде промышленных ОПП показали, что принятое обобщение прямоугольников до макродискретов прямоугольной формы доя ПП с нерегулярным размещением ЭРЭ является недостаточным, неизбежно появляются "искусственные" вершины, несовпадающие с заранее определенными точками множества Х(, и создаются дополнительные метрические ограничения.

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

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

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

угол. Таким свойством обладает триангуляция Делоне. В методе окрестностей строится триангуляция Делоне с ограничениями из множества У7 на основании диаграммы Вороного: для каждой точки множества X; строится окрестность, для всех геометрических точек которой эта точка является ближайшей из всех точек множества Х{. Ребрами соединяются точки Х{ из окрестностей, имеющих общее ребро. Так как существуют ограничения и некоторые четверки точек множества Х( могут принадлежать одной окружности, то результатом является не триангуляция, а покрытие выпуклыми многоугольниками, большинство из которых треугольники. На следующем этапе ведется их расширение. Экспериментальные исследования показали, что метод окрестностей строит лучшее начальное покрытие чем метод расширения треугольников, но работает не так эффективно и качество покрытия после расширения примерно такое-же как визуально, так и по результатам трассировки.

Создавая метод ближайшей точки была предпринята попытка формализовать деятельность человека, решая задачу покрытия платы макродискретами. Контроль должен осуществляться в "узких" местах, т.е. между наиболее близко расположенными точками Х(, поэтому выбирается начальная точка и соединяется отрезком с ближайшей к ней точкой множества Х{. Этот отрезок является ребром и началом контуров двух макродискретов. К нему присоединяется следующая ближайшая точка Х^ и наращиваются контуры. Два отрезка составляют два, если они лежат на одной прямой, или три незакрытых контура. Выделяются одиночные, конечные и внутренние точки. Две последние характеристики определяются относительно какого то контура и статус точки меняется во время работы. Основным недостатком метода является сложность эффективной программной реализации, так как одновременно строится все множество контуров.

В методе окружностей две точки множества Х( соединяются ребром лишь в том случае, если в окружности, диаметром которой является это ребро, нет других точек множества Х(. Такой критерий не позволяет строить "плохих" макродискретов, например, тупоугольных треугольников. Основной недостаток заключается в том, что критерий окружностей не является необходимым условием проведения ребра, т.е. не гарантирует выпуклость построенных многоугольников, поэтому введен этап проверки выпуклости многоугольников и при необходимости деления их на выпуклые.

Экспериментальные исследования на ряде промышленных ОПП показали, что все четыре метода строят покрытия любыми выпуклыми многоугольниками пригодные для практического использования. В

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

В § 5 рассматривается собственно гибкая трассировка и решение подзадач составления списка соединений, коррекции связей эквивалентных выводов ЭРЭ и определения порядка трассировки.

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

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

Разрабатывая метод автоматизированной трассировки, ключевыми вопросами являются выбор пути для трассы и определение ее допустимости. Метод гибкой трассировки определяет допустимость трассы исходя из растояния между препятствиями и количества трасс, проведенных в исследуемом промежутке. Гибкость трасс состоит в том, что они могут перемещаться в промежутках между препятствиями, освобождая путь для последующих трасс, но не меняя топологии. Качество пути должно оцениваться исходя из требований трассировки предстоящих соединений и вопрос о выборе пути тесно связан с очередностью проведения трасс, особенно для однослойной трассировки

В §5.1 рассматривается задача определения порядка трассировки. Экспериментальные исследования с рядом ОПП показали, что при должной очередности проведения трасс, которая иногда подбиралась вручную, разработанный метод гибкой трассировки даже на многоугольниках прямоугольной формы способен дать 100% разводимость в сложных

ситуациях. Принципиально то, что очередность'устанавливалась статически до начала трассировки.

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

В § 5.2 обсуждается разработанный метод гибкой трассировки на многоугольниках прямоугольной формы: обсуждается техника распространения волны, определение веса волны, модификация макродискретов, режимы трассировки. Как уже отмечалось, экспериментальные исследования метода на промышленных ОПП показали, что обобщение прямоугольников до макродискретов прямоугольной формы является недостаточным для ПП с нерегулярным размещением ЭРЭ.

§ 5.3 посвящен методу гибкой трассировки на любых выпуклых многоугольниках. В процессе исследования работоспособности метода гибкой трассировки реализован ряд режимов трассировки и все режимы опробованы на промышленных ОПП. Здесь обсудим лишь некоторые из режимов. Наиболее явно на конечные результаты влияет выбор из режимов трассировки соединениями или целыми цепями и трассировка, используя каждый из них, дала результаты лучше примерно для половины исследованных ОПП. Исследования показали, что целесообразно ограничить корректировку соединений во время трассировки, запретив подсоединение к отдельной (не принадлежащей ни одной трассе) контактной площадке трассируемой цепи, если она не входит в соединение, трассируемое на данном шаге. Это особенно важно в тех случаях, когда не удается достигнуть 100% разведенности. В противном случае обычно проводится "сложная" трасса, которая становится препятствием для дальнейшей трассировки, поэтому в такой ситуации трассировка текущего соединения откладывается. Экспериментально показано, что, используя разработанный метод гибкой трассировки на выпуклых многоугольниках, приемлемые результаты могут быть получены, ограничив проверку пропускных способностей макродискретов проверкой пропускной способности их ребер.

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

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

В § 6 рассматриваются методы крепления гибких трасс. Результатом гибкой трассировки являются непересекающиеся трассы, расположение которых определено с точностью ребер макродискретов. На этапе крепления трасс проводится микротрассировка внутри макродискретов, в результате которой определяется окончательное геометрическое расположение трасс. Метод гибкой трассировки не накладывает ограничений на геометрию окончательных трасс, но нынешняя технология проектирования и производства ПП определяет в основном использование трасс, проходящих но узлам заданной дискретной сетки.

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

В диссертации предложена новая модель ДРП. Для проведения трассы необходимо знать, по каким из восьми направлений трасса может следовать из текущего узла дискретной сетки. Поэтому существенно в модели данных отображать не сами узлы дискретной сетки, а их соединяющие элементарные отрезки. Для отображения ситуации могут быть использованы два подхода: отрезок "видит" препятствия или препятствия блокируют отрезок. Контактные площадки и заранее проведенные трассы являются препятствиями лишь доя трасс других электрических цепей, поэтому, используя первый подход, доя каждого отрезка необходимо иметь список всех его блокирующих препятствий. Во втором подходе, использованном в предложенной модели ДРП, достаточно знать количество препятствий, блокирующих отрезок. По сравнению с традиционной дискретной моделью требуемый обьем памяти возрастает примерно 4 раза, но гарантируется 100% адекватность представления ситуации в макродискрете. Из-за требуемого обьема информации такая модель не может быть использована для самой трассировки геометрическими методами и глобального спрямления трасс на всей ПП.

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

Третья глава посвящена вопросам разработки автоматизированной системы однослойной трассировки.

В § 1 определяются требования к системе автоматизированной трассировки, включаемой в состав промышленной САПР РЭА, приводится состав реализованной системы, названной VUTRACE, схема взаимодействия ее модулей, обосновываются принятые решения. Система VUTRACE состоит из пяти основных частей, реализованных в виде отдельных программ: ввода начальных данных, покрытия платы макродискретами, гибкой трассировки, крепления гибких трасс и вывода результатов. Для обьединения этих программ и обеспечения возможности конфигурирования системы VUTRACE разработана управляющая программа. Система автоматизированной однослойной трассировки реализована на языке программирования TURBO PASCAL и функционирует на персональных компьютерах, совместимых с IBM PC, в срйДе операционной системы MS-DOS.

В § 2 рассматривается интерфейс разработанной системы трассировки с промышленными САПР РЭА и интерфейс пользователя. На основании анализа статистических данных по применению САПР РЭА и автоматизации проектирования ПП на Каунасском НИИСТ "Баша" и Александровском НИИТТ "Рекорд", в качестве базовой САПР была использована САПР P-CAD. Разработаны также интерфейсные программы с САПР REDAC и DRAFT. В диссертации обсуждается технология создания проекта ПП в САПР P-CAD, приводится схема взаимодействия ее составных частей. Разработанная система однослойной трассировки не требует дополнительной подготовки проекта ПП и в цикле проектирования заменяет модуль автоматизированной трассировки PC-ROUTE системы P-CAD. В

диссертации анализируется формат PDIF, используемый для обмена данными между системой VUTRACE и САПР P-CAD. В процессе разработки системы выявлен минимальный набор данных, участвующий в обмене между системой VUTRACE и обобщенной САПР при проектировании ПП.

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

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

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

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

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

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

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

Проведены эксперименты с целью сравнения работоспособности и эффективности разработанной системы VUTRACE и трассировщика САПР P-CAD PC-ROUTE. Основным критерием оценки результатов однослойной трассировки является процент разведенных соединений. В диссертации лредставляются результаты серии экспериментов на десяти ОПП и трех ДПП, предложенных конструкторами во время опытной эксплуатации разработанной системы. Основным результатом является то, что экспериментально подтверждена мощность разработанного метода гибкой трассировки на макродискретах - любых выпуклых многоугольниках и лригодность для однослойной трассировки в автоматизированном 1роектировании ОПП. Результаты трассировки, используя систему VUTRACE, для 9 ПП серии явно лучше, чем используя трассировщик 3C-R0UTE. Кроме того, применение системы VUTRACE значительно джращает время трассировки.

В § 5 обсуждается процесс внедрения разработанной системы штоматизированной однослойной трассировки' в промышленную зксгшуатацию на Каунасском НИИСТ "Банга" и Александровском НИИТТ 'Рекорд". Процесс разработки системы трассировки тесно связан с САПР и техническими средствами, которые использовались в этих организациях. 1ервая версия системы автоматизированной однослойной трассировки, ¡снованная на макродискретах прямоугольной формы, была реализована на 1зыке программирования FORTRAN. Она функционировала на- ЭВМ серии 5С в среде операционной системы СВМ и использовалась совместно с САПР 3RAFT, работавшей на мини-компьютере Quest Star. Потом эта версия

системы была перенесена на ПК, совместимые с IBM PC, и разработан интерфейс с САПР REDAC. Опытная эксплуатация выявила недостатки разработанной системы однослойной трассировки, основным из которых является заметное снижение качества результатов при трассировке сложных ПП с нерегулярным размещением ЭРЭ. Для их устранения разработана система автоматизированной трассировки, основанная на макродискретах -любых выпуклых многоугольниках. Как уже отмечалось, последняя версия системы автоматизированной однослойной трассировки была в основном ориентирована на совместное использование с САПР P-CAD.

В заключении приводятся основные результаты работы:

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

2. Теоретически и экспериментально исследован метод гибкой однослойной трассировки на основе многоугольников прямоугольной формы и выявлены принципиальные недостатки: ограничения формы макродискретов создают дополнительные препятствия и уменьшают работоспособность гибкой трассировки.

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

4. На базе предложенных алгоритмов гибкой трассировки разработана автоматизированная система однослойной трассировки.

5. Созданная автоматизированная система однослойной трассировки внедрена на НИИСТ "Банга" (г.Каунас, Литва) и НИИТТ "Рекорд" (Г.Александров, Россия) и используется в цикле автоматизированного проектирования односторонних печатных плат совместно с САПР P-CAD.

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

По теме диссертации опубликованы следую'щие работы:

1. Рагайшис С., Глямжа А., Миташюнас А. Крепление гибких трасс в автоматизированном проектировании односторонних печатных плат. XXIX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1988, с. 201-202.

2. Глямжа А., Миташюнас А., Рагайшис С. Автоматизация размещения разногабаритных элементов на печатной плате. Республиканская конференция "Программное обеспечение ЭВМ". Тезисы докладов, Паланга, 1989, с. 126-127 (на литовском языке).

3. Глямжа А., Миташюнас А., Рагайшис С. Плотное размещение разногабаритных радиоэлементов на печатной плате. XXX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1989, с. 219 (на литовском языке).

4. Глямжа А., Миташюнас А., Рагайшис С. Плотное размещение разногабаритных элементов. Всесоюзная научно-техническая конференция "Проектирование вычислительных средств". Тезисы докладов, Каунас, 1989, с. 210-211.

5. Глямжа А., Янкаускас Р., Майсеюс А., Миташюнас А., Рагайшис С., Жагунас И. Особенности реализации размещения разногабаритных элементов на печатной плате. XXX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1989, с. 235 (на литовском языке).

6. Лейпус В., Рагайшис С. Конверторы PCAD - ЯГТИ, ЯГТИ - PCAD. XXX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1989, с. 228 (на литовском языке).

7. Лейпус В., Рагайшис С., Жагунас И. Конвертор PCAD - DRAFT. XXX конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1989, с. 229 (на литовском языке).

8. Рагайшис С. Анализ интерфейсов САПР ПП. XXXI конференция Литовского математического общества. Тезисы докладов, Вильнюс, 1990, с. 158 (на литовском языке).

9. Ragaisis S. Flexible routing method for one sided PCB. XXXIII Conference of Lithuanian Mathematician Society. Proceedings, Vilnius, 1992, vol. II, p. 60.

10. Ragaisis S. Flexible routing method for one sided PCB. Design Automation Conference APK' 92. Proceedings, Kaunas, 1992, pp. 105-107.

11. Ragaisis S. Flexible routing method for single sided PCB. Workshop on Design Methodologies for Microelectronic and Signal Processing. Proceedings, Cracow, 1993, pp. 243-247.