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

МОСКОВСКИЙ ИНСТИТУТ ЭЛЕКТРОННОЙ ТЕХНИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

На правах рукописи Экз. N

УДК 621.3.049.77.001.2:681.3.068

МАКСИМЧУК ТАТЬЯНА НИКОЛАЕВНА

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

05.13.12. - Системы автоматизации проектирования

Авторе ф е р а т диссертации на соискание ученой степени кандидата технических наук

Москва 1995 г.

Работа выполнена в Московском институте электронной техники (Техническом Университете)

Научный руководитель Официальные оппоненты

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

- доктор техниескнх наук, профессор Горячев А,В.

- доктор технических наук, профессор Шнро Г.Э,

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

- ЩШ САПРЛН.

Защита состоится "_"_" 1995 г. па заседании

диссертационного совета Д051.02.01 Московского института электронной техники (ТУ) (Москва, 103498, МИЭТ).

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан "_" , " 1995 г.

Ученый секретарь диссертационного совета К-т.н., профессор Н.В.Воробьев

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

Актуальность проблемы. Решающим средством при разработке новой электронной аппаратуры является применение методов машинного проектирования , позволяющих в короткие сроки создавать высоконадежную МЭА при сравнительно низких затратах. Ежегодно уровень интеграции микроэлехтроиных приборов увеличивается примерно в 1.5-2 раза, поэтому этап проектирования топологии коммутационных плат. (КП) стал узким местом в процессе реализации схемы. При высокой плотности монтажа соединительные проводники должны занимать около 80% от общей площади КП, это значительно усложняет задачу трассировки межсоединений. Таким образом, жесткие требования к реализации проводников на КП привели к необходимости развития новых методов и алгоритмов трассировки.

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

Цель работы. Настоящая работа посвящена разработке метода автоматической трассировки аысокоплотных КП

выполненных по двухслойной или попарно многослойной технологии.

Дня достижения поставленной цели в работе решаются следующие основные задачи:

1) исследование существующих в настоящее время методов и алгоритмов трассировки;

2} разработка модели кодирования КП, позволяющей построить алгоритм, дающий точное решение задачи трассировки;

3) разработка и исследование параллельного алгоритма трассировки КП канальной конструкции;

4) разработка и исследование метода перетра сировки каналов, позволяющего добиться 100%-ной трассируемости наиболее сложных участков КП;

5) разработка программного обеспечения методов параллельной трассировки и перетрассировки коммутационных плат.

Мешды_исследования- При выполнении работы

использован математический аппарат теории множеств, теории графов, элементы комбинаторики и элементы теории алгоритмов.

Новые... научные. результаты... и основные, положения

выносимью на защиту:

1) новая модель кодирования каналов, позволяющая хранить информацию о состоянии КП в максимально сжатом виде;

2) метод параллельной трассировки каналов КП, дающий точное решение задачи трассировки в смысле суммарной длины проводников;

3) оригинальный метод синтеза всевозможных конфигураций соединений, позволяющий определил, перспективное направление ветвления;

4) метод перетрассировки каналов, использующий предложенный параллельный трассировщик.

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

реализованных в виде подсистемы трассировки каналов с двухсторонним и четырехсторонним расположением контактов цепей; метода, прикладных алгоритмов и программы перетрассировки каналов высокоплотных КП, реализованных в виде отдельного программного модуля. Работа выполнена в соответствии с программой Комитета по высшей школе Рссийской Федерации.

Реализация и внедрение результатов исследований.

Теоретические и практические результаты диссертационной работы использованы при проведении двух госбюджетных научно-исследовательских работ с номерами государственной регистрации 373-ГБ-53-ГА и 263-ГБ-53.

Результаты диссертационной работы внедрены на предприятиях МРП.

Отдельные результаты работы внедрены в учебный процесс в Московском Государственном Институте Электронной Техники (Техническом Университете).

Апробация работы. Основные положения диссертационной работы докладывались а обсуждались на следующих научно-технических конференциях!

-научно-техническая конференция "Автоматизированное проектирование радиоэлектронной аппаратуры", г. Каунас, 14 июня 1992 г.;

-научно-техническая конференция "Автоматизированное проектирование РЭА и ЭВА" , г, Пенза, 14-15 октября 1991 г.;

-научно-техническая конференция молодых ученых и аспирантов МГИЭТ(ТУ), г. Москва, 10-11 апреля 1994 г.

-научно-техническая конференция молодых учены* и аспирантов МШЭТ(ТУ), г, Москва, 12-13 апреля 1995 г.

Публикации. Материалы по теме диссертации опубликованы в 1-й статье, 3-х тезисах докладов, 1-ом отчете. о НИР.

Структура.диссертациошюй работы. Работа состоит из введения, трех глав, заключения, содержит список литературы из 60 наименований, 39 рисунков, 5 таблиц и приложение.

б

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

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

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

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

-последовательные алгоритмы; -псевдопараллельные алгоритмы; -параллельные алгоритмы. ' .

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

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

Q

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

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

Показано, что получить точное решение сдачи трассировка канала можно только с помощью параллельных . методов оптимизации соединений, которые предусматривают одновременное проложен«® цепей с учетом их взачмиого влшшня, Так как все параллельные методы основаны на принципах перебора, нх реализации требует высоких вычислительных затрат, Снижение вычислительных затрат. предусматривается введением определенных ограничений на работу алгоритма, например, введение ограничения на число изломов одной цепи (число использ} емыя этой цепь» горизонтальных магистралей), ограничение на размер рассиатрие гмога поля трассировки.

Исследованы особенности работы рада параллельных методов трассировки, таких как метод "исключений" (В.Н. Лошаков), метод "сечений" (Г.Э. Широ), метод параллельной трассировки попарно-многослойных печатных плат и другие. Все эти трассировщики дают точное решение в исследуемом классе задач, если только решение вообще существует. Однако, они обладают радом недостатков, ведающих им широкого применения. Так, например, метод "исключений" практически неприменим к классу многоповоротных проводников. Увеличение ширины канала до W>8 ухудшает быстродействие метода "сечений". Метод параллельной трассировки попарномногослойных печатных плат является узкоспециализированных! и рассчитан на определенный конструктив .

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

Проведен анализ степени сложности различных алгоритмов. Отмечено, что задача параллельной трассировки канала относится к классу Г4Р полных задач. Однако, современные требования к степени интеграции МЭА приводят к необходимости развивать именно точные методы трассировки, так как они являются наиболее перспективными в настоящее время, коща все большее развитие получают параллельные ЭВМ, которые хорошо совместимы с параллельными методами САПР.

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

Во второй главе приведено описание векторной .модели кодирования информации , метода параллельной векторной трассировки, основанного на векторном представлена

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

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

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

Рис.1 (а). Фрагмент канала двухслойного КП.

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

координатами начала (Хн.Ун), координатами сонца (Хк,Ук), номером соответствующей горизонтальной или вертикальной магистрали канала а- или 1в и назьшаются ВЕКТОРАМИ.

В. качестве макроячеек используются свободные горизонтальные и вертикальные векторы, которые образуют векторное рабочее поле <ВРП). (рис. 1(6)).

Слой 1 ' Слой 2

• ® ©

<з> ®

РисЛ(б). Векторное рабочее поде.

Тахнм образом» верхний сдой КП представляется * иж множества свободных, горизонтальных аскторов |Н}, а нижний слой - в виде множества жбоот и^шшш шктороа (V). Для миожеста (Н) «* ^ шдаш маожестш {8} • связей между их эавшгжши». Дпз любой вар« векто$юв Ые(Н) к Ь]е{Н) существует если найдете»

хотя бы одни вектор уке{У)и удовлетворяющий условию:

Если да* пары вспорол Ь»«(>1} в Ь|е{Н) существует множество ьектороа {у}е(У)> улошктворшощах данному усиовню, то да* згой пары векторов сушестаует множество связей

Математически ВРП описывается & шмотью графа связности €НН,8), множеством вершка которого шыетса множество свободных горизонтальных векторол 1ЗД» &

ш

множеством дуг - множество связей • {$), как показано на рисунке 2(а).

Ь4

Рис.2(а), Граф связности С(Н,8).

Длиной связи Бу между векторами Ые{Н} и Ь]б(К} считается количество единичных вертикальных ребер графа-сетки проводников между магистралями ьт и а}. Если между парой векторов Ы и Ь] существует множество связей {вц}, то все эти связи имеют одинаковую длину и заменяются в графе С(Н,5) единственной дугой с весом равным их длине, а граф связности С(Н,8) заменяется на взвешенный граф (рис. 2(6)).

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

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

В работе доказано, что путь, построений алгоритмом Ли в графе 0(H,S) является кратчайшим и если этот путь

Ь4

Рис.2(б). Взвешенный граф связности G(H,S).

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

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

Реализация последовательной трассировки на ВРП заключается в последовательном построении пути а графе связности G(H,S) и дальнейшей модификации этого графа. '

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

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

!) организация направленного перебора возможных вариантов реализации соединений;

2) конструирование оценхн для подмножеств вариантов, образовавшихся прн ветвлении.

Задача параллельной трассировки N цепей на ВРП, представленном К горизонтальными векторами сводится к задаче о назначении горизонтальных сегментоз цепей на свободные горизонтальные ' векторы. Организация направленного перебора вариантов заключается а построении всех возможных конфигураций топологии каждой цепи в заданном классе решения задачи.

Прн распределении N цепей по К горизонтальным векторам в классе двухповоротных соединений (цепей, построенных на одном горизонтальном векторе) на первом уровне ветвления максимально может быть получено следующее количество оценок:

р=Ь„=к,

1-1

гае Яц - ¡-я оценка на первом уровне ветвления; количество оценок на первом уровне.

При назначении 1-ой цепи на ¿-ый горизонтальный вектор состояние ВРП меняется, т.е. может измениться и общее количество векторов.

На ш-м уровне ветвления максимально можно получить количество оценок, равное:

Р ы г

К + т-

г

1 -1

К + Ш.Д

гАц

. 1-'

К + т-а

гас Pm - мощность m-ro уровня ветвлений.

Мощность полного дерева ветвления в классе двухповоротных проводников соответственно будет равна:

Р= £р .

ш

I » m

Предложено использовать а качестве начальной оптимистической оценки R0 сумму минимальных возможных длин всех цепей.

R = eL . ,,

О mini'

1-1

где L^j - минимальная длина i-ой цепи ( сумма длин связей этой цепи в оптимальном варианте ее.реализации).

В качестве оценки на некотором m-ом уровне ветвления используется сложный ' параметр Rm, который имеет следующий вид:

где net - максимальное количество построенных цепей;

L - оценка суммарной длины всех цепей, соответствующая данному варианту: ,

L = L + L ,

а а

где Ln - сумма реальных дайн уже построенных цепей;

Lh - оценка суммарной минимальной длины еще непостроенных цепей.

Оценка считается перспективной, если:

-возможно дальнейшее ветвление, то есть, существует подмножество свободных вертикальных н горизонтальных векторов, на которых возможна реализация оставшихся непостроенных цепей;

-оценка имеет минимальный параметр L. Если существует множество оценок с минимальным параметром L,

то перспективной будет считаться та оценка, входящая в это множество, которая обладает максимальным параметром net

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

Класс решения задачи может быть оценен по формуле:

С - VHV(HV)S /2'\

где С - класс решения задачи;

V - вертикальный вектор;

Н - горизонтальный вектор;

s - число поворотов.

Предложено искать решение задачи параллельной трассировки в классах по возрастанию сложности конфигурации цепей:

1-ый класс - построение двухповоротных цепей вида:

VHV(HV)° = VHV.

2-й класс - построение четырехповоротных цепей ввда

VHV(HV)' = VHVHV.

m-й класс - построение 2т поворотных цепей вида: VHV(HVf,

и так далее. •

Для подсчета мощности дерева ветвления в классе m предполагается, что каждая цепь строится на 2ш+1 горизонтальных вектг х н на 2т вертикальных векторах. Доя i-ro уровня ветвления максимальное количество оценок может быть вычислено по формуле:

1Б

vhv(HV)"1 x 4 '

ras Q - число вертикальных векторов на ВРП. Мощность дерева ветвления для т-го класса 2т поворотных проводников определяется как

■ Р' , s 2 Р.

VHY{HV)a i . ! yHV (HV)ml '

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

Очевидно, что топология цепи зависит от взаимного расположения горизонтальных векторов, на которых эта цепь построена. В работе введено математическое представление взаимного расположения пары векторов s виде графа К(Н,С), в котором множество вершин {HJ множество горизонтальных векторов, участвующих в построении цепи, множество связей {С}-характер относительного расположения пары вершин. Возможны четыре типа относительного расположения пары векторов: •относительное смещение вправо; •относительное смещение влево; -несмещенное расположение векторов; -несвязное расположение векторов. В графе R(H,C) каждому типу расположения пары векторов соответствует направление связи между вершинами. На рисунке 3 показано четыре типа расположения пары векторов, соответствующий этим типам граф R(H,C) и возможная реализация соединений, выполненных на данном подмножестве векторов. Как видн. дз рисунка, каждому типу связей соответствует определенное . подмножество

не

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

Тип 1

Тип 2

Тип 3

Тип 4

Ь2

Ъ2

И2

ьг

ы

ы

М

я 2 в

ё

ы

о-

Ь2

-Г*0

м о-

Ь2 -О

ы си-

иг ->о

ы

о

к

£

о ы е-

1ш

Лт—'

I *

ш

ы

ДО

X

Рис. 3. Взаимное расположение пары векторов.

Координаты начала и конца пары векторов для каждого типа связи в графе ЩН.С) определяются следующими соотношениями.

Тип 1,

(X ^ <Х>;1

I ЛК1>ХКЗ Ът2.

I Н1 < нз

Тип 3.

Vй1 1ут ^ К I К 2

К 2 К I

Тип 4. Хк1<Хт

ХК2<ХШ

Изменяя подискретно координаты начала в конца векторо® в соответствии с заданными неравенствами, можно лепсо получить все варианты топологии соединений в любом классе решения задачи параллельной трассировки. Число вариантов N возможных состояний графа К(Н,С) зависит от количества вершин К в графе и определяется соотношением:

гае С* - число сочетаний из К по два.

Программная реализация метода параллельной векторной трассировки в классах УНУ и УНУНУ показала, что данный метод позволяет получить точное решение задачи рассировки в смысле суммарной длины соединений при 100%-ной реализации коммутации.

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

В_третьей главе предложен новый метод

перетрассировки отдельных участков канала, использующий параллельную векторную оптимизацию трасс и названный методом "Увеличительного стекла".

Метод "Увеличительного стекла", предполагает рассмотрение только тех участков канала, в которых

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

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

Метод "Увеличительною стекла" предполагает следующую последовательность операций.

1. Анализ нер&зведежшх цепей.

2. Разбиение канала на сеченна.

3. Параллельная трассировка в сечениях:

а) нахождение предполагаемого контакта строящейся ценя в боковом сечении канала;

б) старание иевей;

в) шреяепешю минимального возможного класса трзссаровкн;

г) Еарагапеадвэя трассяршка канала с учетом бохосш. контактов;

д> возможное увеличение класса трассировки.

Анализ неразведанных цепей заключается в- выборе разбиваемой па сечения области канала. Границы этой области определяются по кооротватам крайнего левого н крайнего правого контактов 01. шмизируемой цепи:

Гл = тЦгЧе»} . ' Гж = 1зах(КеТ)

где Гл в 1Ъ - као$дат&ти левой в правой границы области;

- адюа&сж» координат оптимизируемой цепи.

В процессе трассировки значения Гл и Гп могут изменяться.

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

V < V

оц э вм

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

Алгоритм установки границ сечения выглядит Следующим образом:

1. Начальная установка границ:

Г -Г Г = г

с л 1 *л»*сп I п' 2. Определение текущей координаты правой границы:

Г =Г +1.

ОТ СП

3. Определение текущей координаты левой границы:

Г =г .

лт с л'

4. Установка Ген:

Г =Г

СП I ПТ*

если существует хотя бы одна свободная ячейка, принадлежащая Гпт, если нет - п. 2.

5. Установка Гсл:

Г «Г

если существует хотя бы одна свободная ячейка, принадлежащая Глт, если нет ;

Г = Г -I

1 ят с л! •

переход к п, 3.

6. Векторное кодирование сечения,- определение Уоц.

7. Если Von < Уэвм - расширение сечения, переход к п. 2, если нет • установка окончательных границ сечения:

Г = Г

СЛ СЛ1-1

г = г

сп СП ¡-1

8. Конец.

На рисунке 4(а) предст?"лен фрагмент канала в котором при трассировке осталась неразведанной цепь с номером "7". Метод "Увеличительного стекла" начинает перетрассировку этого фрагмента канала с определения границ сечения, как показано на рисунке 4(6).

1 221 33464367

1 6

5 5 6

Рис.4(а). Фрагмент канала с неразведенной цепью.

Метод "Увеличительного стекла" предполагает изменение установленных границ ссчешш в зависимости от результатов параллельной векторной трассировки сечения.

) •о □ о о □ а а а а а < 1

[ ]_ о а а. □ о I )

Гл Гп

Рис.4(б), Установка границ сечения.

Выбор боковых контактов оптимизируемых соединений из множества возможных точек (Р), принадлежащих границам сечения основан на переборе элементов множества {Р|. Если в сечении канала невозможно построить искомую цепь без изменения конфигураций других соединений, то предлагается в пределах сечения стирать фрагменты уже построенных цепей' и проводить оптимизацию нескольких цепей одновременно. Стирание цепей производится в зависимости от степени влияния их на искомое соединение.

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

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

Если параллельная трассировка' сечения невозможна и при увеличении класса трассировки, предполагается изменение установленных границ сечения, т. е. увеличение , уменьшение размеров сечения и сдвиг сечения в канале.

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

- модуль обработки входных данных;

- модуль параллельной трассировки канала в классе VHV;

- модуль, реализующий перетрассировку методом "Увеличительного стекла";

модуль параллельной трассировки канала с четырехсторонним расположу ием контактов цепей.

Модули подсистемы реализованы на языке СИ. Объем требуемой для работы оперативной памяти ЭВМ зависит от класса и размеров решаемой задачи и лежит в пределах от 2000 до 10000 Кбайт. Подсистема предусматривает связь с другими САПР посредствам выходных файлов.

В работе преде плены результаты трассировки примера Берштейна (Burstein's difficult channel). Метод "Увеличительного стекла" позволил получить лучшие результаты в смысле суммарной длины связей, чем

обобщенный greedy алгоритм, что позволяет говорить о высокой эффективности представленных методов.

В заключении приведены основные результаты диссертационной работы, характеризующие научную новизну и практическую ценность.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

1. В результате анализа существующих методов и ялтпитмов трассировки показано, что для решения задачи №a°/i-HQui трассируемости изделия целесообразно развивать

параллельные методы трассировки.

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

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

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

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

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

7. Разработано программное обеспечение метода параллельной векторной трассировки и метода "Увеличительного стекла" на базе персональной ЭВМ IBM PC/AT. .

8. Получены результаты трассировки отдельных примеров, доказывающие эффективность переложенного метода параллельной векторной трассировки и метода "Увеличительного стекла".

работы:

1. A.B. Горячев, Т.Н. Махсимчук, A.C. Лупин. Векторный алгоритм трассировки ортогонально-двухслойных плат. "Элехтронная техника", Серия 10 - "Микроэлектронные устройства", вып. 3,4 (93,94), 5-11 с.

2. Максимчук Т.Н., Лупин С.А. Вехторный алгоритм трассировхи ортогонально-двухслойной коммутации. /В сб. тезисов докладов конференции: Автоматизация проектирования РЭА и ЭВА./ - Пенза: ППИ, 1991, 50 с.

3. Максимчук Т.Н., Лупин С.А. Абрамов В.Н. Вехторный алгоритм трассировки ортогонально-двухслойных плат. /В сб. тезисов докладов конференции: Автоматизация проектирования РЭА./ - Каунас: КПИ, 1992, 100-104 с.

4. Отчет о выполнении НИР. Разработка метода параллельной векторной трассировки ортогонально-двухслойной коммутации. /Ном. гос. регистрации 01940002941, науч. руководитель Максимчук Т.Н./ - Москва: МГИЭТ, 1994.

5. Лупин С.А., Максимчук Т.Н., Минаева Е.В. Перетрассировка двухслойных каналов БИС методом "Увеличительного стекла". /В сб, тезисов докладов конференции молодых ученых и аспирантов МГИЭТ ТУ / г. Москва 12-13 апреля 1995 г.

Заказ 171 . Тираж 100. Объем 0,9 уч.нзд.-л. Бесплатно

Отпечатано в типографии МИЭТ(ТУ).