<<
>>

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

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

Это задача более сложная, чем стандартная задача размещения блоков с фиксированными размерами.

Основной целью оптимизации является минимизация общей площади кристалла.

Задача планирования относится к классу NP. В течение последних лет были предложены различные подходы к реше­нию проблемы планирования. Эти подходы могут быть клас­сифицированы следующим образом: линейное и квадратичное программирование [6.2]; имитация отжига [6.3, 6.4]; основанные на ограничениях [6.5]; сила направленная парадигма [6.6]; ос­нованные на геометрической дуализации списков связей [6.7]; иерархические методы сверху-вниз и снизу-вверх [6.8]; метод кластеризации [6.9]; генетические алгоритмы [6.io, 6.11]; на основе поисковой адаптации [6.12] и др. Анализ существующих

подходов к решению поставленной задачи показал, что удачными являются подходы, основанные на методах моделирования отжи­га и эволюционного моделирования [6.13, 6.14].

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

Проблема планирования формулируется следующим обра­зом [6.1].

Имеется множество модулей M = {mi| i = 1,2,...,n}. Каж­дый модуль характеризуется тройкой (Si, li, ti), где Si— площадь модуля, а параметры liи tiзадают нижнюю и верхнюю границу значения

где hi— это высота модуля, wi— ширина.

В качестве плана кристалла будем использовать план, полу­ченный путем рекурсивного использования «гильотинного разре­за», т. е. последовательного разрезания прямоугольников на две части [6.1].

На рис. 6.1, а представлен план, а на рис. 6.1, б — соответ­ствующее ему дерево D = {dj| j = 1,2,... ,2n — 1} «гильотинно­го разреза», листьями которого являются вершины, соответству­ющие блокам, а внутренние вершины соответствуют разрезам: V— вертикальный, H — горизонтальный.

Рис. 6.1. а — план гильотинного разреза; б — дерево гильотинного разреза

План для множества модулей M представляет собой пря­моугольник R, разрезанный вертикальными и горизонтальными

линиями на множество областей ri, в каждую из которых поме­щается соответственно модуль mi. На дереве цифрами помечены вершины, соответствующие разрезам, причем V— вертикальный разрез, а H — горизонтальный. Буквами помечены вершины, соответствующие областям. Каждая область ri, предназначенная для размещения модуля mi, имеет размеры xiи yi.Очевидно, что размеры области должны соответствовать ограничениям

при одновременном соблюдении ограничений (6.1).

В некоторых случаях задают границы отношения высоты ho к ширине Wo прямоугольника R, т. е.

Площадь области riопределяется как xi∙ yi, общая площадь

Показатель F используется в качестве критерия.

Цельоптимизации — минимизация показателя F, т. е. мини­мизация общей суммарной площади плана Rпри соблюдении ограничений (6.1), (6.2) и (6.3).

6.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. Договор перевозки пассажиров и багажа.