<<
>>

Формулировка проблемы канальной трассировки

Задача трассировки — одна из наиболее трудоемких задач среди задач автоматизированного проектирования СБИС. С мате­матической точки зрения трассировка — наисложнейшая задача выбора из огромного числа вариантов оптимального решения.

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

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

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

7 В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев

Рис. 10.1. Пример канала

При канальной трассировке каждая цепь, связывающая эк­випотенциальные выводы, представляется в виде набора го­ризонтальных и вертикальных фрагментов (участков). На об­ласть трассировки наносится опорная ортогональная сеть, по линиям которой проходят трассы. Вертикальные линии про­ходят через контакты. Горизонтальные линии называют маги­стралями. Задача трассировки в канале рассматривается как задача распределения фиксированного множества горизонталь­ных участков F = {fi| i = 1,2,..., N} на множестве магистралей M = {mj| j = 1,2,..., L}.

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

Ограничения на взаимное расположение горизонтальных участков, связанные с недопущением наложения как верти­кальных, так и горизонтальных участков, задаются с помощью графа вертикальных ограничений (ГВО) Gv = (X, U) и графа горизонтальных ограничений (ГГО) Gh = (X, W). Вершина xiв графе Gvи Ghсоответствует фрагменту fi.Наличие дуги (xi, Xj) в Gvозначает, что fiв канале выше fjдля исключения наложения вертикальных отрезков. Считается, что fiи fjнаходятся в вертикальном конфликте. Ребро (xi, Xj) в Ghозначает, что xiи xj∙ не могут быть размещены в одной магистрали [10.4, 10.5].

Назовем число магистралей в канале шириной канала. Про­ведем через каждый контакт kiвертикальное сечение si.Опре­делим для каждого сечения siчисло diпересекающих его соеди­нений. Максимальная среди всех сечений величина diявляется

плотностью канала и обозначается Dm∀i(Dm ~≥ di).

Величина Dmявляется минимально возможной шириной канала.

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

Способ разбиения является одним из признаков, по которому классифицируются алгоритмы канальной трассировки. Распро­странение получили «безызломные» трассировщики, отличаю­щиеся наличием только одного горизонтального участка, ко­торый вертикальными участками связан с соответствующими контактами. На рис. 10.2 показано сформированное множество горизонтальных фрагментов F = {fi| i = 1,2,... ,14} для канала, представленного на рис. 10.1. Близкими к безызломным явля­ются изломные трассировщики, у которых изломы допускаются в сечениях, проходящих через контакты, связываемые с цепью.

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

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

Gv. На рис. 10.3 показан граф вертикальных ограничений Gy, соответствующий множеству F. Если в графе Gy отсутствуют циклы, то определяется длина Lmмаксимального пути в графе, которая соответствует минимально возможному числу магистра­лей, в которых горизонтальные фрагменты могут быть уложены без нарушения вертикальных ограничений. Таким образом, ниж­ней оценкой ширины канала является оценка ξ = max {Lm, Dm}, т. е. максимальное число из Lmи Dm. Минимизации ширины канала можно добиться минимизацией большей из двух этих оценок.

Рис. 10.3. Граф вертикальных ограничений

На основе переключения соединений между эквивалентны­ми выводами можно минимизировать значение плотности Dm. При фиксированном размещении контактов Dmпостоянна. Если Lm> Dm, то минимизация ξ осуществляется минимизацией Lm.

После построения графа вертикальных ограничений Gy он в первую очередь анализируется на предмет обнаружения цик­лов. Наличие цикла свидетельствует о невозможности трасси­ровки без нарушения ограничений. Для ликвидации циклов осу­ществляется разбиение некоторых фрагментов и строится новый граф Gy. Если после устранения циклов окажется, что Lm больше, чем Dm, то возможно проведение поиска и разбиения фрагментов с целью минимизации Lm[10.4].

Основной задачей, возникающей на этапе внутриканальной трассировки, является распределение участков цепей по маги­стралям. При ограниченности ресурсов каналов основная цель заключается в реализации максимального числа участков цепей.

Сформулируем эту задачу в терминах исследования опера­ций.

Пусть имеется множество участков F = {fi| i = 1,2,..., B}, которое необходимо распределить в множестве магистралей

Введем булеву переменную, равную

Очевидно, чем большее число переменных xijпримет зна­чение 1, тем больше будет реализовано участков. Поэтому при внутриканальной трассировке ставится цель:

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

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

где G— множество пар номеров участков, находящихся в гори­зонтальном конфликте.

Пусть пара участков fiи fjнаходится в вертикальном кон­фликте, причем fiдолжен располагаться в канале над fj. Это значит, что при назначении fiв l-ю магистраль, участок fj не может быть назначен ни в одну из магистралей с 1-го по 1-й номера.

Для учета вертикального конфликта между fiи fjнеобходи­мо выполнение системы ограничений

где V — множество пар номеров участков, находящихся в верти­кальном конфликте.

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

при следующих ограничениях:

Существует большое количество подходов к решению задачи канальной трассировки, таких, как последовательные алгорит­мы [1o.5], алгоритмы на основе методов целочисленной опти­мизации [1o.1,1o.7], генетические алгоритмы канальной трас­сировки [1o.7]. Ниже будет рассмотрен поисковый алгоритм канальной трассировки, основанный на методах коллективной адаптации [1o.8].

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

Еще по теме Формулировка проблемы канальной трассировки:

  1. 3.1. Проблема моделирования рефлексии переводчика
  2. Основные нерешенные проблемы в развитии МИКФ Цели и задачи диссертационной работы
  3. Глава II. Порядок производства в суде надзорной инстанции и проблемы его совершенствования
  4. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  5. ГЛАВА 3. ПРАВОВЫЕ ПРОБЛЕМЫ ОТВЕТСТВЕННОСТИ БАНКОВ ЗА НАРУШЕНИЯ ЗАКОНОДАТЕЛЬСТВА О НАЛОГАХ И СБОРАХ
  6. Алексеевская Екатерина Игоревна. Теоретические и практические проблемы производства в суде надзорной инстанции. Диссертация на соискание ученой степени кандидата юридических наук. Москва - 2008, 2008
  7. Колерко Галина Владимировна. ЭКОНОМИЧЕСКИЕ ПРОБЛЕМЫ ВЗАИМООТНОШЕНИЙ ПРЕДПРИЯТИЙ И ОРГАНОВ МЕСТНОГО САМОУПРАВЛЕНИЯ. Диссертация на соискание ученой степени кандидата экономических наук. Старый Оскол - 2000, 2000
  8. 4. Административно-процессуальные нормы и отношения. Проблема кодификации административно-процессуального права
  9. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  10. § 5. Основания к отмене или изменению судебных постановлений, вступивших в законную силу
  11. Приложение 8.
  12. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  13. СОДЕРЖАНИЕ
  14. ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
  15. § 2. Сущность производства в суде надзорной инстанции
  16. 1.2.1 Вариационные методы