<<
>>

Проблемная формулировка, термины, определения

При двухслойной трассировке СБИС обычно реализуется сле­дующий подход. Вначале одним из алгоритмов разрабатывается совмещенный эскиз трассировки межсоединений, удовлетворяю­щий следующим ограничениям [11.1-11.4]:

— не допускаются наложения цепей друг на друга;

— отсутствуют точки касания цепей;

— в одной точке пересекаются не более двух цепей.

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

Исключить точки пересечения цепей, т.

е. обеспечить правильное функционирование СБИС, возмож­но только путем разнесения пересе­кающихся фрагментов цепей в раз­ные слои с введением дополнитель­ных межслойных переходов (МП).

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

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

Существуют два основных подхода к решению поставленной задачи [11.5]. При первом подходе на эскизе трассировки отыс­киваются месторасположения минимально необходимого числа узлов, в которых размещаются межслойные переходы, обеспе­чивающие размещение совмещенного эскиза трассировки. Отме­тим, что определение конфигурации участков и их разнесение по слоям осуществляется после ввода межслойных переходов [11.5, 11.6].

При втором подходе путем ввода заранее избыточного числа узлов цепи разбиваются на участки. Каждый участок ограничен парой узлов. Узел соответствует разрезу соединения и является местом возможного расположения в нем межслойного перехо­да. Затем находится такое допустимое разнесение участков по слоям, при котором число межслойных переходов минимально. Итак, при втором подходе сначала участки разносятся по слоям, а потом в некоторых узлах вводятся необходимые межслойные переходы, обеспечивающие это разнесение [11.5].

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

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

11.4, а смежные грани A и Bнечетны, поэтому разнести участки 1, 2, 3, 4, 5в два слоя невозможно.

После ввода межслойных переходов на соединении (трассе) 5, разделяющего грани Aи B,появляется участок 6(рис. 11.4, б). Грани A и B становятся четными, а участки 1 ÷ 6 разносятся в два слоя.

Рис. 11.4. а — исходный эскиз с нечетными гранями Aи B, б — эскиз после введения межслойного перехода

Построим для эскиза трассировки двойственный граф D (рис. 11.5). Вершины графа соответствуют граням эскиза. Реб­рами связываются вершины, соответствующие смежным граням. Вершины графа D, соответствующие нечетным граням, помеча­ются.

Для графа D задача отыскания минимума межслойных пере­ходов эквивалентна следующей задаче.

Введем понятие покрывающего ребра. Если ребро графа D выбрано в качестве покрывающего, то это определяет введениемежслойного перехода на соединении, разделяющем смежные грани, что влечет за собой разбиение этого соединения на две части. Это приводит к тому, что у смежных граней увеличи­вается на единицу число ограничивающих их соединений. При этом четная грань становится нечетной, и наоборот. Вершины, инцидентные ребру покрытия в графе D, трансформируются. Непомеченная вершина становится помеченной и наоборот. Граф D необходимо покрыть минимальным числом ребер так, чтобы все вершины были непомеченными, т. е. все грани были четными. Существуют различные подходы к решению этой задачи [11.5]. На рис. 11.6 представлено покрытие графа D. Покрывающий набор состоит из четырех ребер (выделены жирным шрифтом). Отсюда следует, что для разнесения соединений по слоям необ­ходимы четыре межслойных перехода, которые располагаются на соединениях, соответствующих покрывающим ребрам. На по­следнем этапе на каждом из выбранных соединений необхо­димо определить позиции для помещения в них межслойных переходов. Позиции должны соответствовать технологическим ограничениям.

Рис. 11.5. Двойственный граф D эскиза трассировки

Рис. 11.6. Покрытие графа D

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

В работе [11.7] задача разнесения на основе второго подхо­да сведена к задаче псевдобулевого программирования. Введена булева переменная xi= 0, если i-й участок в первом слое и xi= 1, если i-й участок — во втором. Построена целевая функ­ция (число межслойных переходов), зависящая от значений xi, и множество ограничений. Решением задачи являются значения переменных xi, обеспечивающих оптимальное значение целевой функции, при выполнении ограничений. Использование класси­ческих методов исследования операций неприемлемо ввиду боль­шой размерности задачи [11.7, 11.8].

В настоящей работе используется второй подход, при этом процедура расслоения соединений представляется в виде адап­тивной системы [11.9, 11.10].

11.2.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Проблемная формулировка, термины, определения:

  1. Определение твердости по Бринеллю
  2. Определение твёрдости
  3. Определение прочности на растяжение
  4. 3.4.3 Определение удельного сопротивления монокристаллов германия.
  5. Определение предела прочности при поперечном изгибе
  6. Определение секущих модулей и коэффициентов поперечных деформаций при отсутствии трещин
  7. 1. Понятие и правовое положение органа исполнительной власти
  8. 1.1. Классификация оптических аномалий в кристаллах.
  9. Приложение 8.
  10. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  11. § 5. Основания к отмене или изменению судебных постановлений, вступивших в законную силу
  12. § 1. Понятие и правовая природа банка
  13. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  14. § 2. Сущность производства в суде надзорной инстанции
  15. 1. Производство по делам об административных правонарушениях: общая характеристика
  16. 1. Понятие государственного управления
  17. 3. Классификация органов исполнительной власти. Факторы, влияющие на построение системы органов
  18. 3. Основы административно-правового статуса граждан