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

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

Исследования показывают [9 ], что реальная длина трас­

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

Если предположить, что удлинение трассы по сравнению с минимальной получается за счет увеличения покрывающего пря­ моугольника, то длины сторон увеличенного прямоугольника

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

PJ ^ P ,

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

S* - часть граничного дискрета, входящая в прямоуголь­ ник, 6 1^ 1.

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

31

ходяшихся на одинаковом расстоянии от одного из контактов, равняется единице. Для этого в множестве дискретов Z)* по­ крытых увеличенным прямоугольником, выделяются подмноже­

ства й са+ь-з • ДискРеты каждого из этих подмножеств находятся на одной диагонали, проведенной в промежутке меж­ ду контактами. Заметим, что все дискреты одного подмноже­ ства внутри неувеличенного прямоугольника находятся на оди*- наковэм расстоянии от одного из контактов. Для обеспечения суммы вероятностей загрузки дискретов одного подмножества, равной единице, вероятностная загрузка дискретов Ые££ опре­ деляется следующим образом:

I. Для дискретов, частично входящих в расширенный пря­ моугольник:

2. Для дискретов, полностью входящих в расширенный пря­ моугольник:

P=~JL+ 2(ihr~ Р ')

(4)

/Я// м ; / - г

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

3 2

определять исследуя только дискреты, содержащие контакты. Ожидаемая загруженность дискрета de D трассами всех цепей определяется суммированием вероятностных загрузок дискре­

груженность можно определить суммированием загруженностей

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

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

3 3

E.G

РН

Рис. I. Оценка загруженности частей сечений

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

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

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

ДА

прямоугольника, покрывающего все контакты цепи. Ожидаемая

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

Вначале исследуем отдельный случай, когда размер обла­ стей равен одному дискрету. По дискрету, если он свободен, можно провести одну трассу, а если занят - ни одной. Одна­ ко, так как ожидаемые загрузки дискретов являются вероят­ ностным^ пропускная способность должна определяться так­ же на вероятностной основе. То есть пропускная способность дискрета должна зависеть не только от того, свободен он или нет, но и D T занятости соседних дискретов.

Пусть Д/ - множество дискретов окружающей дискрет* об­ ласти. На пропускную способность w y дискрета У влияет не только состояние самого дискрета ctj H D и занятость дискре­ тов области ZV. Занятый соседний дискрет должен уменьшить пропускную способность исследуемого дискрета. При этом на пропускную способность больше влияние тех дискретов, котс*-

3 5

рые ближе к d. Поэтому в множестве Dj выделяются под­ множество дискретов 1-соседства, 2-соседства, .... I -сосед­ ства. Влияние дискретов С -соседства можно выразить через

суммированием влияний подмножеств дискретов отдельных со­ седств :

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

В отдельном случае, если при определении пропускной спо­ собности дискретов ofей или a'etr принять 4 = ^ то и будут равны, соответственно, числу свободных дискретов в от­ резках сечений h или

36

Как отмечалось раньии, для равномерной загруженности МП соединениями необходимо исследовать загруженность от­ дельных областей МП или отрезков сечений относительно их пропускных способностей, т.е. рассмотреть их относительную загруженность. Тогда относительную загруженность дискрета c t области D / и отрезков сечений (горизонтальных и верти­ кальных) соответственно можно определить следующим обра­ зом:

Kpj1Tjepjni_ равнэмернэго размещешгя. Используя предложен­ ные методы определения загруженности отдельных участков МП, т.е. отдельных областей и частей сечений МП, можно строить критерии, оптимизируемые алгоритмами размещения элементов. Так как преследуется цель получить такое раз­ мещение, при котором соединения были бы равномерно распре­ делены по всему МП, при размещении необходимо стремиться к получению одинаковой загруженности отдельных участков МГ1.

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

Пусть МП разбито на ряд областей, покрывающих все мон­ тажное пространство. Размер области может быть от одного дискрета до всего МП. Не теряя общности, будем считать,что область - это дискрет. Только в зависимости от размеров об­ ластей их загруженность будет подсчитываться по (13) или (14), Тогда множество областей МП обозначим через множе­ ство дискретов D={&}.

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

37

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

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

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

(13), (14), (15), не позволяют судить о перегруженности отдельных частей МП. Поэтому перегруженными будем счи­ тать такие части МП, загруженность которых превышает не­ которое заданное значение. Это может быть средняя загружен­ ность области

или средние загруженности горизонтальных и вертикальных от­ резков сечений:

•г.е.

*Lc(<:i>ca(i> а°р ) ,

а через Н 1 и ] /'- множества перегруженных частей сечений:

М сН '(аА >а*р ) и У-усУ'С

Срецняя загруженность перегруженных областей - это

3 8

Средняя загруженность перегруженных частей сечений,

Число перегруженных областей - это

Число перегруженных горизонтальных и вертикальных отрезков сечений

F6 ^/H'/+ /1/7.

Взвешенная суммарная загруженность областей определя­ ется следующим образом:

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

Эксперимент проводился следующим образом. В качестве главного поочередно рассматривались все критерии То есть оптимизация размещения проводилась только по одно­

му критерию с использованием алгоритмов парных перестано­ вок. Параллельно подсчитывались значения остальных крите­ риев (оценок) размещения и ожидаемая суммарная длина со­ единений (/£). Кроме того, каждый раз проводилась трасси­ ровка соединений, В качествеисходного использовалось раз­ мещение, полученное с минимизацией суммарной длины соеди­ нений. Для проведения эксперимента было отобрано 30 реаль­ ных схем ЭВА и РЭА.

3 9

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

И

Рис. 2. Диаграмма оптимизации /у в процессе переразмещения

Рис. 3. Диаграмма изменения !% при оптимизации по критерию^