<<
>>

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

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

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

Области трассировки формируются естественным образом на основании размещения блоков. С этой целью по границам блоков проводятся секущие прямые линии (рис. 8.1).

Как уже указывалось выше, основными областями, образую­щимися в результате выполнения этих действий, являются ка­налы и коммутационные блоки. В любом случае область трасси­ровки — это прямоугольник с заданными (определенными после разбиения) пропускными способностями по границам (сторонам прямоугольника). Пропускная способность границы является ре­сурсом, характеризующим максимально возможную суммарную толщину цепей, пересекающих эту границу. Итак, на первом этапе формируется множество областей A = {ai| i = 1,2,... } и множество границ между областями B = {bj| j = 1,2... }. При

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

Рис. 8.1. Области трассировки

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

Алгоритмы глобальной трассировки можно разбить на два класса: последовательные и комбинаторные.

При последовательном подходе цепи распределяются по об­ластям последовательно. В основе большинства из них лежит волновой алгоритм Ли и его модификации [8.2-8.4]. Качество решения во многом определяется порядком трассируемых соеди­нений. Анализ существующих методов упорядочения показывает, что не существует радикального метода, гарантирующего опти­мальную трассировку.

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

Другим недостатком является то, что большинство алгорит­мов использует критерии, в большей степени учитывающие па­раметры соединений (например, общая длина) [8.1] ив меньшей

6 В. М. Курейчик, Б. К.

Лебедев, О. Б. Лебедев

степени — параметры коммутационного поля, что не совсем согласуется с главной целью глобальной трассировки.

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

Для решения задачи распределения соединений по областям в качестве модели коммутационного поля используется граф G = (X, U). Вершины графа xi∈Xсоответствуют областям ai∈A. Если две области aiи aj∙ имеют общую границу Ьк, то вершины xiи Xj, соответствующие этим областям, связываются ребром uk∈U. Для каждого ребра uk, связывающего вершины xiи Xj, задается вес α⅛, равный пропускной способности общей границы Ьк между областями, соответствующими вершинам xiи Xj. Будем считать, что граф G метризован, т. е. каждая вершина xi∈G имеет координаты. Координатам вершины присваивают­ся значения координат центра соответствующей области. Если области имеют один и тот же размер, то граф G представляет собой ортогональную решетку. На рис. 8.2, а представлены обла­сти коммутационного поля, а на рис. 8.2, б — соответствующий граф.

Рис. 8.2. а — области коммутационного поля; б — граф, соответствующий коммутационному полю

Пусть задано множество цепей T = {ti| i = 1,2,... }. Для каждой цепи определяется множество областей коммутационного поля, в которых существуют контакты, связываемые этой цепью. На графе G множеству областей, связываемых цепью ti∈T, со­ответствует множество вершин Xi∈X. Распределить цепь tiпо областям — значит, построить в графе G на множестве вершин Xiсвязывающую сеть. На рис. 8.2, б показана связывающая сеть цепи, а на рис. 8.2, а показано ее распределение по областям. Каждая цепь tiпосле ее реализации, т. е. после распределения

по областям, потребляет определенную часть ресурсов пересека­емых ее границ [8.9].

В качестве исходных данных для каждой цепи tiзадается параметр ^>i, равный ширине цепи плюс расстояние между це­пями. Иногда для одной цепи задаются два параметра: ^>i'при

2i распространении цепи по горизонтали, ^>2 — по вертикали.

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

Пусть Ei∈E — множество связывающих сетей, построенных для множества цепей Ti∈T ,в состав которых входит ребро uj∙. Обозначим через βj∙ сумму ресурсов, необходимых множеству связывающих сетей Eiдля прохождения через ребро uj∙; другими словами, — сумму ресурсов, необходимых цепям множества Ti для пересечения границы bj∙:

Для каждого ребра uj∙ графа Gвведен параметр wj∙ = αj∙ — — βj. Найдем в графе G минимальное значение параметра wj∙ и обозначим его wmin, т. е.

Для нашей задачи цель оптимизации — максимизация пара­метра wmin. Действительно, чем больше остаток ресурсов, тем легче реализовать соединения при детальной трассировке, и аб­солютно неприемлем результат, когда wj имеет отрицательное значение.

8.2.

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

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

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