Содержание к диссертации
Введение
1. Выбор архитектуры системы автоматизированного проектирования и описание структуры данных в подсистемах 17
1.1. Выбор структуры САПР и принципов организации программного обеспечения 17
1.2. Форма представления исходных данных и промежуточных результатов проектирования 27
2. Разработка методов размещения элементов эва на кп с учетом условий дли канальной трассировки 43
2.1. Постановка задачи размещения. Методы и критерии, используемые при решения задачи 43
2.2. Выбор методов размещения на основе анализа схемы проектируемого устройства 50
2.3. Декомпозиция схемы на основе анализа внутренних цепей 60
2.5. Проверка возможности трассировки и корректировка размещения 90
3. Разработка методов канальной трассировки схем ЭВА 103
3.1. Постановка задачи и характеристика существующих методов трассировки ЮЗ
3.2. Разработка канального алгоритма трассировки на основе расплывчатого представления трасс 110
3.3. Минимизация числа пересечений трасс 120
3.4-. Размещение межслойных переходов 130
3.5. Трассировка цепей, инцидентных внешним выводам схемы и построение эскиза совмещенной трассировки 137
3.6. Дотрассировка нереализованных цепей и контроль соответствия трассировки исходному заданию 156
Заключение 172
Литература 175
Приложение 189
- Форма представления исходных данных и промежуточных результатов проектирования
- Выбор методов размещения на основе анализа схемы проектируемого устройства
- Разработка канального алгоритма трассировки на основе расплывчатого представления трасс
- Трассировка цепей, инцидентных внешним выводам схемы и построение эскиза совмещенной трассировки
Введение к работе
Актуальность проблемы. Электронно-вычислительная аппарату-pa (ЭВА) в настоящее время находит все более широкое внедрение в различных отраслях народного хозяйства. Счетно-решающие и управляющие устройства применяются в производственных процессах, в строительстве, в научных исследованиях, в сфере планирования, учета и управления, в проектно-конструкторских работах. Расширение сферы применения, повышение требований к производи -тельности ЭВА, а также развитие технологии изготовления и элементной базы приводит к необходимости создания новых более со -вершенных устройств.
Наиболее важными характеристиками процесса создания новых и совершенствования известных типов ЭВА являются сроки и качество проектирования, определяющие в конечном счете технический уровень и эффективность разрабатываемой аппаратуры. Повышение сложности и расширение функций разрабатываемых устройств приводит к росту объема проектно-конструкторских работ, а, следовательно, - к увеличению сроков проектирования. При больших сроках проектирования возникает опасность быстрого морального старения технических решений. Снижение трудоемкости проектирования при одновременном повышении качества и сокращении сроков становится возможным только благодаря автоматизации на всех этапах проектирования. В основных направлениях экономического и социального развития СССР на І98І-І985 годы и на период до 1990 года говорится о необходимости совершенствования вычислительной техники, ее элементной базы и математического обеспечения в области автоматизации и научно-исследовательских работ /I/.
Эффективность автоматизации зависит от того, насколько полно она охватывает все этапы проектирования. В связи с этим в настоящее время автоматизации отдельных процедур проектиро -вания предпочитают создание систем автоматизированного проектирования (САПР). Согласно /2/ САПР - организационно-техническая система, состоящая из комплекса средств автоматизации проектирования, взаимосвязанного с подразделениями проектной организации, и выполняющая автоматизированное проектирование. Комплекс средств автоматизации проектирования представляет собой совокупность средств математического, лингвистического, программного, технического, информационного и организационного обеспечения /3/. Создание САПР - трудоемкая, сложная и длительная работа, для выполнения которой требуются большие коллективы высококвалифицированных разработчиков, имеющих в своем распоряжении достаточно мощный комплекс технических средств.
Развитие средств вычислительной техники и технологии изготовления ЭВА, повышение сложности объектов проектирования вызывают необходимость непрерывного совершенствования и развития САПР. Однако ввиду длительности процесса разработки САПР не представляется возможным реагировать на изменения объектов проектирования и технологических ограничений путем создания новых систем. Поэтому актуальной становится проблема создания гибких САПР, структура которых позволяет соблюдать принципы включения, развития, совместимости и информационного единства /2/. При таком подходе становится возможной разработка подсистем или отдельных программ автоматизированного проектирования в небольших проектных организациях с применением малых ЭВМ.
Процесс проектирования ЭВА традиционно разбивается на три основных этапа: системотехнический, схемотехнический и конструкторский /4-9/. Важной задачей является автоматизация конструкторского этапа проектирования, так как именно на этом этапе выполняется большой объем рутинной работы, связанной с преобразованием информации и расчетом различных параметров.
Задачи, возникающие на этапе конструкторского проектирования относятся к классу задач многокритериальной оптимизации, и их точное решение в единой постановке весьма затруднительно /10/. Один из наиболее эффективных путей упрощения решения заключается в применении:, принципа организации подсистем с; разбиением задач на подзадачи на основе метода последовательной субоптимизации /11,12/. При этом в пределах каждой подзадачи отыскивается оптимальное решение по некоторому локальному критерию.
На основе разработанных методов был создан ряд САПР печатного монтажа и БИС. К САПР первого поколения можно отнести "Автограф", "АСП-І", "ЕСАП ЭВМ" и др. Эти системы использовали в качестве центрального процессора ЭВМ второго поколения, от -личающиеся низким быстродействием, малым объемом оперативной памяти и отсутствием возможности организации мультипрограммного режима. Поэтому проектирование производилось в автоматиче -ском режиме, при котором конструктор практически лишен возможности участвовать в процессе проектирования. САПР первого по -коления были достаточно эффективны в масштабах небольших про - . ектных и научно-исследовательских организаций. Однако возрос -ший объем проектных работ и сложность объектов проектирования, совершенствование технологии изготовления ЭВА привели к необ -ходимости разработки новых более современных САПР, ориентиро -ванных на использование современных средств вычислительной техники. Повышение быстродействия ЭВМ и увеличение объема опера -тивной памяти позволили использовать более эффективные алго -ритмы, применять новые модели объектов и критерии оценки качества решения как отдельных задач, так и всей проблемы в целом. Появление современных операционных систем, совершенствование и расширение номенклатуры внешних устройств позволило наряду с автоматическим широко применять интерактивный режим проектирования. При этом появилась возможность использовать в процессе проектирования опыт и интуицию конструктора, которые невозможно в полной мере учесть даже в самых совершенных алгоритмах.
В настоящее время у нас в стране разработаны и успешно эксплуатируются следующие САПР электронных схем: "Рапира", "Прам", САТОП, система интерактивного проектирования на базе ЭВМ М-6000, интерактивная система проектирования І5УТ-4-0І7, АСП-5, ПЛАТА, АЖІАР и др. /50-55/. Из зарубежных САПР наиболее известны: система МД&І& фирмы MotoxoCa \ L!LIO фирмы "ЯМІ ", :;CfiLMO$ , система фирмы "IBM ", система фирмы "Ml Telephone fa і" (США); C/fLM/l,R0BWtLILSOtMIM&E,MILf) (Япония); система G#LDI фирмы " Philips " (Голландия); ЯУЕЯТЯ Фирмы " Siemens " (ФРГ); If МО, PDLIG-ON (Англия); STfiTOS (франция) и др. /50,56-64/.
Для перечисленных САПР характерно наличие банка данных, сочетание автоматического и интерактивного режимов проектирования, возможность выбора программных средств для решения основных задач проектирования, иерархическая структура проектирования на основе фрагментации. Применение современных САПР позволило существенно сократить сроки и повысить качество проектирования.
Однако несмотря на возросшую эффективность САПР, полученные с их помощью решения лишь приближаются по качеству к результатам проектирования, выполняемого опытными конструктора -ми. Это объясняется прежде всего высокой сложностью основных задач проектирования в их традиционной постановке. Большинство задач конструкторского этапа проектирования, как известно /15,20/, относится к классу HP -полных задач, точное решение которых может быть получено только путем полного перебора /65/. Кроме того, критерии, применяемые при автоматизирован -ном проектировании, не позволяют в полной мере учитывать взаимосвязь между отдельными задачами.
Следует отметить, что при проектировании конструктор не в состоянии воспользоваться ни одним из известных алгоритмов автоматизированного проектирования, так как для человека не представляется возможным выполнить вручную соответствующий объем вычислений. Отметим также, что при решении какой-либо частной задачи проектирования конструктор не стремится достичь глобального оптимума по некоторому критерию, а добивается получения условий, достаточных по его мнению для успешного решения последующих задач. Исследование методов, используемых конструктором, позволяет выявить следующие характерные для них особенности: предварительный анализ конструктивно-технологических параметров и схемы проектируемого устройства; декомпозиция схемы на основе выделения функциональных узлов; разбиение общей задачи проектирования на ряд подзадач и установление приоритета критериев; прогнозирование сложностей, возникающих при решении под -задач, на основе анализа промежуточных результатов проектирования; использование метода фрагментации на всех этапах проектирования.
Анализ исходного задания имеет своей целью классификацию схем и выбор соответствующих методов и критериев проектирования. Декомпозиция схемы позволяет существенно снизить размер -ность задачи и, следовательно, упростить ее решение. Отметим, что метод декомпозиции широко применяется в автоматизированном проектировании /20,36/. Анализ промежуточных результатов позволяет конструктору оценить условия, созданные на некоторой предварительной стадии проектирования для решения задач последующих этапов. Использование метода фрагментации позволяет сократить объем информации, обрабатываемой конструктором в процесс реше -ния различных задач проектирования. Метод фрагментации также широко применяется в автоматизированном проектировании, особенно при проектировании БИС /44,50/.
Структура и организация программного обеспечения (ПО) со -временных САПР позволяют применять различные методы решения отдельных задач проектирования /66-68/. Как правило, для решения каждой подзадачи имеется несколько программных модулей, отличающихся друг от друга как быстродействием и требуемым объемом оперативной памяти, так и точностью получаемых решений. Таким образом конструктору предоставляется возможность составлять с помощью управляющей программы различные маршруты проектирования, то есть выбирать те или иные программные модули для решения различных подзадач в зависимости от сложности объекта проектирования, требуемой точности решения, имеющихся ресурсов оперативной памяти и быстродействия используемой ЭВМ.
В связи с продолжающимся ростом объема проектных работ и сложности объектов проектирования, совершенствованием технологии производства ЭВА задача повышения эффективности САПР и ка -чества получаемых решений сохраняет свою актуальность. Один из путей решения этой задачи заключается в разработке и включении в ПО САПР программных модулей, представляющих собой реализацию отдельных приемов проектирования, используемых опытным конструкт тором.
Цель работы. Основная цель диссертационной работы состоит в создании и исследовании комплекса программ автоматизированного проектирования, представляющих собой реализацию неформальных приемов проектирования, используемых .-. опытным конструктором; обеспечении интерактивного режима автоматизированного проектирования на основе анализа особенностей схем проектируемых устройств, предназначенного для выбора оптимальных маршрутов проектирования; сокращении времени решения и требуемого объема оперативной памяти ЭВМ, повышении качества проектирования за счет применения новых моделей и алгоритмов, основанных на декомпозиции схемы и анализе промежуточных результатов.
Для достижения указанной цели необходимо решить следующие задачи:
исследовать принципы построения САПР ЭВА и определить состав программного и информационного обеспечения;
разработать методику анализа схем ЭВА и определения оптимального маршрута проектирования;
разработать новый критерий и на его основе алгоритмы и программы размещения элементов, позволяющие создать оптимальные условия для трассировки канальными методами;
разработать алгоритм трассировки, позволяющий получать более высокий процент реализованных соединений на зтапе канальной трассировки;
построить компактные модели коммутационного поля, позволяющие упростить алгоритмы формирования трасс, число пересечений, размещения межслойных переходов;
разработать методику контроля соответствия полученной трассировки исходной схеме проектируемого устройства.
Методы исследования. Методика исследований основывается на использовании теории множеств, теории графов, методов кодирования информации, проверке теоретических результатов путем реализации разработанных алгоритмов на ЭВМ и решения реальных примеров проектирования ЭВА.
Научная новизна. Научная новизна работы заключается в исследовании и разработке специальных методов автоматизированного проектирования, представляющих собой реализацию неформальных приемов проектирования и позволяющих сократить время и повысить качество проектирования схем ЭВА определенного класса. В диссертации получены новые научные результаты в области автоматизации конструкторского этапа проектирования схем ЭВА:
предложена методика анализа исходной схемы проектируемого устройства, основанная на вычислении значений ряда параметров, определяющих классификацию схем ЭВА и методы решения основных задач проектирования;
введен новый критерий оценки качества размещения, учитывающий тесную связь между задачами размещения и трассировки и позволяющий определить реальные условия, созданные на этапе размещения для последующей канальной трассировки;
разработан новый алгоритм размещения элементов на КП, основанный на декомпозиции схемы с учетом характера внутренних цепей. Предложена методика оценки возможности трассировки и коррекции результатов размещения элементов на КП;
разработан новый алгоритм канальной трассировки, использующий расплывчатое представление трасс, реализующих цепи схемы. В соответствии с принципом фрагментации разработан алгоритм минимизации числа пересечений трасс в каналах, прилегающих к линейке контактов. Предложена методика контроля соответствия по -лученной трассировки исходной схеме соединений;
для решения задач размещения и трассировки построены модели, отличающиеся компактностью и позволяющие упростить реализацию основных проектных процедур.
Практическая ценность. Исследования проводились в рамках госбюджетной и хоздоговорной тематики в соответствии с постановлением Госкомитета СМ СССР по науке и технике В 500 от 21.II. 1975 г., постановлением СМ РСФСР JS 610 от 12.II.1976 г., по планам секции радиоэлектроники и приборостроения "Программы САПР" Минвуза РСФСР. Кроме того, работа велась в соответствие с целевой комплексной программой 0.Ц.027, выполняемой по постановлению ПШТ, Госплана СССР и АН СССР гё 474/250/132 от 12.12.80 г. и В 492/245/164 от 8.12.81 г.
Результаты работы реализованы в виде программных модулей, вошедших в состав систем проектирования двухслойного ("Граф-2Д") и многослойного ("Граф-2М") печатного монтажа.
Расчеты и испытания показали, что предложенные методики и разработанные программы позволяют существенно сократить сроки и повысить качество проектирования устройств ЭВА определенного класса. Предложенные методы находят применение в проектировании БИС на основе использования типовых ячеек.
Реализация работы. Теоретические исследования, алгоритмы и программы, приведенные в диссертации, применяются и используются при проектировании двухслойного и многослойного печатного монтажа в научно-исследовательских и опытно-конструкторских работах завода "Электроаппарат" г.Ростов н/Д, АОМЗ г.Азов, НИИ ОМВС и КБ ТРТИ г.Таганрог и других предприятий. Ряд алгоритмов и программ зарегистрирован в Республиканском фонде алгоритмов и программ (г.Киев).
Результаты, полученные в диссертационной работе использу -ются при подготовке и чтении лекций по курсу "Автоматизация конструирования РЭА и ЭВА", в лабораторных работах, курсовом и дипломном проектировании.
Научные и практические результаты диссертационной работы внедрены на ряде предприятий страны. Копии актов внедрения приведены в приложении. Фактический годовой экономический эффект, определенный на основании актов составляет 75,6 тыс.руб. Апробация работы. Основные результаты работы докладывались, обсуждались и были одобрены на: семинаре "Микроэлектроника в вычислительной технике" (г.Ленинград, 1974 г.); Всесоюзной научно-технической конференции по проблемам совершенствования проектирования, изготовления и контроля интегральных схем (г.Киев, 1976 г.); Всесоюзной школе-семинаре "Современные тенденции в автоматизации конструирования радиоэлектронной и электронно-вычислительной аппаратуры" (Славское,1978 г.); конференциях "Автоматизация конструкторского проектирования РЭА и ЭВА" (г.Пенза, 1977, 1981, 1983 г.г.); Ш-й Всесоюзной конференции "Автоматизация поискового конструирования и под -готовки инженерных кадров" (г.Иваново, 1983 г.), а также на ряде других конференций и семинаров.
Публикации по работе. По материалам диссертации опубликовано 15 работ. Во ВНТИЦ зарегистрировано 12 отчетов по госбюджетным и хоздоговорным научно-исследовательским работам в области автоматизации проектирования ЭВА, выполненным при непосредственном участии автора.
Структура диссертации, диссертационная работа состоит из введения, трех разделов, заключения, списка цитируемой литературы и приложения.
Первый раздел посвящен исследованию и выбору основных принципов построения и организации гибкой САПР ЭВА. В основу системы положен дифференцированный подход к решению задач конструкторского этапа проектирования. Выбор конкретных методов предлагается осуществлять в интерактивном режиме на основе анализа исходной схемы и промежуточных результатов проектирования. Приведена схема вычислительного процесса и структура программного обеспечения, предназначенного для проектирования двухслойного и многословного монтажа. Описана форма представления исходных данных и основных информационных массивов, используемых на различных этапах проектирования.
Во втором разделе приведен краткий аналитический обзор существующих методов размещения элементов на коммутационном поле (КП). Описывается методика анализа исходной схемы, направленного на определение оптимального маршрута проектирования. Разработан метод декомпозиции схемы проектируемого уст -ройства на основе згчета характера цепей схемы. Введена дискретная модель КП и разработан новый критерий оценки качества,.-раз-мещения на основе учета условий, созданных для канальной трассировки. Разработана методика проверки возможности трассировки при полученном размещении и коррекции размещения за счет перераспределения ресурсов КП и перестановки элементов в соответ -ствии с полученными оценками качества размещения.
В третьем разделе рассматриваются вопросы, связанные с трассировкой соединений. Предложен подход к решению задачи трассировки, основанный на применении различных по сложности и эффективности алгоритмов трассировки в разных зонах КП. Разработан алгоритм трассировки канального типа, предусматривающий построение нескольких вариантов трасс для каждой цепи. Описан алгоритм минимизации числа пересечений, использующий специальную модель фрагмента КП. Введена мелкодискретная модель рабочего поля, предназначенная для волновой дотраосировки нереализованных цепей, получения эскиза трассировки, размеще -ния межслойных переходов, контроля и коррекции результатов трассировки. Разработаны алгоритмы трассировки цепей, инцидентных внешним выводам схемы. Предложен алгоритм контроля соответствия полученной трассировки исходной схеме соединений.
В заключении сформулированы основные результаты, полученные в работе. В приложении приводится описание программ, во -шедших в состав систем "Граф-ЗД" и "Граф-2М" и реализующих основные алгоритмы, тексты программ и примеры их работы.
Форма представления исходных данных и промежуточных результатов проектирования
Исходная информация для проектирования представляет собой совокупность параметров и описаний, касающихся конструктивных особенностей разрабатываемого устройства, схемы соединений, технологических ограничений. Различают следующие способы задания исходной информации: словесный, графический, аналитический и матричный.
Словесный способ задания отличается наибольшей универсальностью, так как позволяет описывать не только схему устройства, но и весь комплекс конструктивных и технологических ограниче -ний. Основные недостатки этого способа заключаются в трудоем -кости описания и недостаточной наглядности представления информации.
Графический способ предусматривает вычерчивание схемы соединений, содержащей сведения о внутрисхемных соединениях. При этом конструкторско-технологические ограничения задаются, как правило, словесным способом. Графическое представление схемы отличается большей наглядностью, но в то же время связано с трудоемким процессом вычерчивания схемы.
Аналитическое задание предполагает представление схемы в виде двух множеств t "(Е , Ея, .., пг и Csl i, Czt ..v Gmі Множество Е представляет элементы схемы и группы внешних выводов, а множество С - электрические цепи. Аналитическое задание, как и графическое, требует дополнения в виде описания конструкторско-технологических ограничений. Основные преимущества аналитического метода заключаются в простоте подготовки исходной информации и представлении ее в таком виде, который позволяет применять достаточно простые алгоритмы проектирова -ния, основанные на известных теоретико-множественных операциях. Недостатки способа обусловлены малой наглядностью и большим объемом описания схемы.
Наиболее компактным является матричное задание схемы, отличающееся также сравнительно малой трудоемкостью и позволяю -щее применять достаточно простые алгоритмы проектирования. Основной недостаток матричного способа - малая наглядность.
На практике, как правило, применяются различные комбина ции из перечисленных способов, причем доля участия того или иного способа зависит от конкретной стадии проектирования. Дяя конструктора наиболее удобен графический способ задания информации. Поэтому исходная схема задается в виде чертежа, пред -ставлящего собой стандартный конструкторский документ. Дополнительные сведения о проектируемом устройстве задаются словесным способом. Однако графический и словесный способы явно не -пригодны для внутреннего представления информации в памяти ЭШ. Следовательно необходимо преобразование информации, для чего применяются аналитический и матричный способы.
Форма представления и структура данных во многом определя ют требуемый объем оперативной памяти ЭВМ, а, следовательно, допустимую размерность решаемых задач проектирования /72/. Это относится как к исходной информации, так и к промежуточной. По этому необходимо выбрать наиболее компактную форму представле ния исходной информации о схеме. В то же время необходимо обес печить возможно большую наглядность для удобства подготовки ис ходной информации и исправления ошибок, допущенных при ее со ставлений. Этим требованиям наиболее полно отвечает матрица це пей номер цепи, инцидентной J -му контакту (выводу) с -го элемента схемы. Матрица Т однозначно задает информацию о связях между элементами. Кроме того, матрица / может служить упрощенной моделью схемы на этапе размещения, так как в ней заложена ин -формация о пространственном расположении элементов друг отно -сительно друга. Обозначим через р общее число позиций для размещения элементов на КП, а через 3 - число позиций, расположенных на одной горизонтали (в одной линейке). Схема расположения и порядок нумерации позиций на КП показаны на рис. 1.3. Введем однозначное соответствие между номером позиции на КП и номером строки матрицы Т . Тогда отображение информации о связях некоторого элемента в L -ой строке матрицы / означает, что этот элемент размещен в і- -ой позиции на КП. Отметим, что если некоторая позиция на КП не занята, то соответствующая строка матрицы / содержит только нулевые элементы. Таким образом элемент матрицы ty принимает значение, равное номеру цепи, инцидентной / -му выводу элемента, расположенного в і -той позиции. Учет способа установки элемента схемы в позиции (ориентации) осуществляется с помощью параметра ORIENT , значение которого определяет порядок заполне -ния соответствующей строки матрицы Т . Построенная таким образом матрица Т является удобной моделью для решения таких часто встречающихся на практике задач, как: определение номера электрической цепи, инцидентной определенному выводу определенного элемента схемы; определение множества цепей, инцидентных некоторому эле -менту схемы; определение списка изолированных выводов элемента схемы; перестановка элементов; удаление элементов; добавление новых элементов или цепей; фиксация одного или нескольких элементов в заранее отве -денных позициях на КП; фиксация элементов в заданных подсхемах; переориентация элементов; задание начального размещения элементов; поиск одинаково ориентированных элементов; поиск элементов с одинаковыми абсциссами (ординатами); вычисление координат элементов и их выводов. Существует, однако, ряд процедур, реализация которых на основе матрицы Т представляется затруднительной. Из таких процедур отметим лишь наиболее часто встречающиеся в процессе проектирования: поиск элементов, инцидентных определенной цепи; поиск множества выводов, соединенных одной цепью; удаление некоторой цепи из схемы; упорядочение цепей по числу объединяемых ими выводов.
Выбор методов размещения на основе анализа схемы проектируемого устройства
Задача анализа схемы разрабатываемого устройства в настоя щее время рассматривается как задача определения конструктивных особенностей. Так, в /38/ предлагается осуществлять анализ систем различной физической природы с помощью хорошо исследо -ванных универсальных методов, разработанных для аналогичных систем в САПР радиопромышленности. Это касается электрических, тепловых и механических характеристик схемы, которые могут быть окончательно определены только после завершения трассировки. На этапе размещения интерес представляет анализ схемы соединений с целью выявления и количественной оценки таких пара -метров, которые определяют принадлежность схемы к определенно -му классу. Классификация схем, как уже говорилось, должна определять соответствующую классификацию методов решения задачи. При выборе основных параметров схемы представляется целесооб -разным ориентироваться на опыт ручного проектирования. В соответствии с /6/ исходную схему можно рассматривать как некоторое множество элементов Е {Рі,Рлг../ п} » соеди -ненных между собой электрическими цепями из множества Разъем можно представить как элемент Р0 є , местоположение которого на КП зафиксировано. Множество выводов элементов схемы обозначим через V . Каждому элементу схемы Pi е Е, і- п соответствует подмножество выводов V; V . Цепь СК6С\ к- itm представляет собой подмножество выводов, которые она соединяет. Таким образом, если Ск соединяет элементы Рс и Pjj ij --. Допустим, что все выводы элементов схемы задействованы, т.е. где YK - длина (число выводов) цепи Ск . На этапе размещения не имеет смысла рассматривать цепи или фрагменты цепей, связывающие контакты одного элемента. Поэтому вводится понятие элементного комплекса. Под элементным комплексом С; понимается подмножество элементов из , соединенных цепью J . Таким образом т .
В общем случае С/П С.- / / , так как комплексы могут со / держать общие элементы. Размер комплекса определяется как Очевидно, ЧТО // = jfj . Пусть задано КП площадью Л кп . Зная тип каждого элемента, можно определить площадь S-L (і - 7ji) , необходимую для л его размещения. Определим J7- fkn - TSi . Очевидно, что должно выполняться условие &о О t так как в противном случае трассировка невозможна. Площадь Si опре -деляется геометрическими размерами элемента, но она может быть определена более точно с учетом цепей, инцидентных элементу в[ .. Так, на рис.2.1. показаны два элемента одного типа, но требующие для своего размещения (даже при самом благоприятном рас -пределении цепей) разные площади. Плотность монтажа разрабатываемой схемы зависит от величины b S , а также от числа и характера цепей схемы. Поэтому можно ввести параметр Pf , значение которого будет грубой оценкой плотности монтажа. где й - коэффициент, учитывающий технологические ограниче -ния на ширину проводников, диаметр переходных отверстий и допустимые зазоры. Значение /у может служить ориентиром для определения необходимой точности решения задачи размещения. Важной характеристикой схемы является однотипность ее элементов. Множество Е элементов Е схемы можно разбить на непересекающиеся подмножества уу ,,..; Е t где -число типов элементов. При t получаем так называемые регулярные схемы. Для таких схем КП перед размещением разбивается на п (ґі /Z/ зон или посадочных мест, и задача размещения может быть сведена к задаче назначения.
При t і можно выделить класс схем, для которых эле -менты разных типов имеют кратные размеры, т.е. где А - целое число. В этом случае для элемента р: вводится Я сцепленных зон я и задача сводится к предыдущей. Существует класс схем, при размещении которых для каждого подмножества E L целесообразно выделить укрупненную зону КП. Каждая укрупненная зона разбивается на I El I посадочных мест, а задача размещения - на подзадач. Отметим, что та -кой подход имеет смысл только тогда, когда число связей между элементами одного типа значительно превышает число связей между элементами разных типов. Пусть t і . Представим в виде кортежа, компо -центами которого являются подмножества El і s it f причем При проектировании печатных плат элементы схемы по типам можно разбить на два класса. К первому классу относятся элементы-микросхемы, ко второму - дискретные элементы (резисторы, конденсаторы, диоды и транзисторы). Основные направления анализа однотипности для элементов первого класса были рассмотрены выше. Для элементов второго класса предлагается несколько иной подход. На рис.2.2. представлены различные варианты под -ключения дискретных элементов. Они отличаются прежде всего количеством элементов, подключаемых к микросхеме. Отдельные элементы, связанные с контактом микросхемы и с одной из шин питания (рис.2.2.,а), предлагается не учитывать на этапе начального размещения. Поскольку существует несколько равнозначных вариантов их установки относительно микросхемы, выбор оконча тельного варианта целесообразно осуществлять после начального размещения или даже на этапе трассировки. Отдельные элементы, связанные с контактами разных микро -схем (рис.2.2.,в) целесообразно представить в виде цепи, сое -диняющей эти контакты. Поскольку окончательная конфигурация цепи получится только на этапе трассировки, то именно на этом этапе удобнее выбрать вариант подключения элемента. Элементы, контакты которых принадлежат разным цепям (рис.2.2.,г), также целесообразно размещать, когда уже известна форма цепей и можно выбрать наиболее удачное место подключения.
Разработка канального алгоритма трассировки на основе расплывчатого представления трасс
На этапе построения связывающих деревьев и распределения фрагментов цепей по каналам используются, в основном, два критерия оптимизации: минимум длины связывающего дерева и равно -мерность загрузки каналов. Построение минимального связывающего дерева производится на основе применения волнового алгорит ма. Поэтому, если загрузка каналов не учитывается, то конфигурация дерева однозначно определяется соотношением координат контактов, связываемых соответствующей цепью. Однако для некоторых типов цепей существует два совершенно равнозначных по длине варианта связывающего дерева. Так, если цепь связывает два контакта, расположенных на одной горизонтальной линии, то ь трасса может проходить как в верхнем, так и в нижнем по отно шенйю к этой линии горизонтальном канале. Аналогично для цепи связывающей контакты с одинаковыми координатами по оси д . На этом основана возможность оптимизации по критерию равномернос ти загрузки каналов с учетом их пропускных способностей. В процессе построения связывающего дерева выбирается тот вари ант, который менее другого влияет на изменение загрузки соот ветствующих каналов. Возможности оптимизации по данному крите рию могут быть в значительной мере расширены, если рассматри вать отличные от минимального варианта связывающих деревьев. Необходимо отметить, что из всех вариантов связывающих деревьев выбирается только один, а остальные не рассматривают ся в процессе дальнейшей оптимизации. В таком случае возникает зависимость результата от очередности построения деревьев. Пусть дано подмножество цепей Ск = Cf Ск- ffyf с2 С$ Сц сЛ ш и известно, что трассы, реализующие цепи из С к , могут прохо дить либо в канале К І , либо в канале Kz . Предположим, что цепи C CZlC по критерию минимума длины связывающего де рева необходимо реализовать только в К , а цепи V и $ - в любом из каналов. Тогда, если строить связывающие деревья в порядісе возрастания индексов, то цепи Сі/ и Cs будут реализо-ванн в К . Если же цепи рассматривать в обратном порщще, то в Kj будут реализованы С С2 , з, С f , а в г - только Си , что не соответствует оптимальному распределению цепей с точки зрения равномерности загрузки каналов. Кроме того, по -скольку пропускная способность каналов ограничена, может ока -заться, что часть цепей, распределенных в канал, не может быть реализована. В этом случае применяют итерационную процедуру. На первом шаге определяют перегруженные каналы. На втором шаге для части цепей перегруженных каналов производится повторная трассировка с использованием друтих каналов. Однако в рассматриваемом примере для цепей. C1t Cz, з повторная трассировка не даст результата. Поэтому требуется несколько итераций для достижения оптимального распределения. Причем на каждой итерации для части цепей приходится заново строить связывающие деревья. Представляется целесообразным перенести выбор оптимально го варианта связывающего дерева на этап распределения фрагмен тов цепей по магистралям. С этой целью предлагается в процес се распределения по каналам сохранять все варианты минимальных и близким к минимальным связывающих деревьев. Цепь Q С представляет собой множество фрагментов СІ s-fjfi Ул,/з... fg} Зададим множество каналов К (і 1 1 J , состоящее из двух подмножеств Кг с К и Кр К] 1КГ1, /Kg / - число горизонтальных и вертикальных каналов соответственно. Поскольку С У СІ , задача распределения фрагментов цепей по каналам может быть сведена в разбиению множества @ на под -множества 0 й&)_ ,} с/1(1 по критерию минимума числа нереализованных соединений. Разбиение производится на этапе построения связывающих деревьев и представляет собой приведение на каж -дом шаге в соответствие фрагмента -fje i. cie @ каналу KtK.
Трассировка цепей, инцидентных внешним выводам схемы и построение эскиза совмещенной трассировки
Оптимальное распределение фрагментов цепей по каналам и по магистралям в каналах направлено в первую очередь на получение максимального числа реализованных соединений. Однако даже до -стижение глобального оптимума не гарантирует реализацию всех соединений схемы, так как применение канальных алгоритмов не позволяет рассматривать все возможные конфигурации трасс. Количество реализованных соединений, как уже отмечалось, может быть увеличено за счет применения волнового алгоритма дотрассировки, позволяющего строить трассы любых конфигураций. Волновые алго -ритмы используют, как правило, мелкодискретную модель рабочего поля, состоящую из множества одинаковых по размерам дискретов. Каждый дискрет отображает элементарную площадку на ШІ, центром которой является узел координатной сетки. Такая модель, как известно /20 /, обладает свойствами двумерного эвклидова пространства Z,d"7 , т.е.
Пропускная способность дискрета Я; Z во всех разрешенных направлениях считается равной единице.
Волновой алгоритм позволяет построить трассу между дискре -тами % и Z/ , если фронт волны, распространяемой из 21 , достигнет Я/ . Необходимо отметить, что чем выше плотность на -чальной трассировки, тем больше длина и сложность конфигураций строящихся трасс, а, следовательно, и время решения. Кроме то -го, часто для построения некоторых трасс требуется перетрасси -ровка ранее реализованных соединений, что требует применения сложных итерационных алгоритмов, обладающих низким быстродейст -вием. Поэтому представляется целесообразным предусмотреть воз -можность осуществления дотрассировки вручную. Как показывает практика, при небольшом количестве нереализованных соединений процедура ручной дотрассировки занимает не более 1-1,5 часов и не требует высокой квалификации исполнителя. Для выполнения ручной дотрассировки необходимо предоставить исполнителю информа -цию, наглядно отображающую результат предыдущей трассировки и позволяющую производить его корректировку.
Матрица Ш представляет собой крупнодискретную модель ра -бочего поля и позволяет однозначно определить положение пост -роенных трасс на КН. Однако она не обладает ни свойствами дву -мерного эвклидова пространства, необходимыми для волнового ал -горитма дотрассировки, ни достаточной наглядностью для ручной дотрассировки. Поэтому необходимо на данном этапе построить новую модель рабочего поля и отобразить на ней информацию, полу -ченную в процессе канальной трассировки. Матрица М , описан -ная в 3.4., вполне отвечает приведенным выше требованиям,так как представляет собой мелкодискретную модель рабочего поля,состоящую из дискретов равных размеров, каждый из которых отображает элементарную площадку КН. Нечетные столбцы М отображают вертикальные магистрали, а нечетные строки - горизонтальные магистрали и линейки контактов. Четные строки и столбцы предназначены для отображения зазоров между соседними трассами. Элемент М может приобретать значения , если через отображаемую площадку не проходит I трасса; т. У I, если трасса проходит через площадку; 2, если зафиксировано пересечение двух трасс; 3, если в данном месте КП размещена контактная площадка или межслойный переход.
Выведенная на печать, матрица М представляет собой эскиз трассировки, позволяющий однозначно определить расположение трасс и контактов элементов и разъема на КП,
Переход от матрицы ТМ к матрице М осуществляется на основе следующих соображений. Элемент ТМ представляет собой описа -ние характерной точки некоторой трассы. Под характерной понима -ется точка изгиба или разветвления. Положение точки определяется номером строки (номер горизонтального канала) и номером столбца (вертикальная магистраль), которым принадлежит элемент. Значе -ние элемента ТМ содержит информацию о номере цепи, номере гори -зонтальной и вертикальной (если точка находится в вертикальном канале) магистрали. Кроме того, элемент ТМ содержит закодиро:. -ванную информацию о направлениях, в которых цепь распространяется из данной точки. Кодировка осуществляется на основе следующего правила
