8.1. Задачи плаиирѳваиия кристалла и сжатия топологии

Задача размещения вершин графа на плоскости связана с инженерной задачей, возникающей при проектировании топологии сверхбольших интегральных схем — планированием кристалла СБИС. Это — одна из задач, определяющая качество конструкторского проектирования СБИС. Задача планирования кристалла состоит в назначении данного множества модулей на плоскости с минимизацией суммы площади при размещении заданных прямоугольников и минимизации суммарной длины цепей, которые должны соединять модули. Тогда проблема планирования может быть определена как оптимизационная проблема, и, следовательно, для ее решения можно использовать методы ЭМ.

В [172] данная задача формулируется следующим образом. Дано множество модулей М = {1,2,..., т}. Все модули представляются прямоугольниками. Каждый і-и модуль характеризуется кортежем длины три {Si, Іі, и-і), где Si — площадь модуля, k, Ui — верхние и нижние границы отношения высоты hi к ширине Wi. Здесь Wi х hi = Si и іі ^ hi/wi ^ Ui. Планирование состоит в разбиении плоскости горизонтальными и вертикальными линиями на т непересекающихся областей. Каждая область Гі имеет ширину хі и высоту уі, такие, что Si ^ хі х уі (хі ^ иіі^уі > hi). Результат альтернативного планирования может оцениваться посредством ЦФ, учитывающей общую площадь компонента и суммарную длину соединений. Общая площадь определяется как

а длина соединений определяется по формуле (6.7):

Здесь Cij — число связей, соединяющих 'і-й и j-й модули, dij — расстояние между этими модулями. Для получения математической модели плана кристалла используют так называемую кусочную структуру или «польские

выражения» [172]. На рис. 8.1, а показан план кристалла, па рис. 8.1, б — его кусочная структура и па рис. 8.1, в — «польское выражение». Модели кусочной структуры или «польского выражения» находят применение при решении задач планирования. Эти модели используются при построении популяций в ГА.

Структура ГА для решения данной задачи описывается следугош,им образом. Сначала создается одна или несколько популяций решений, что соответствует Fq, = {paijPa2j • • • jPak}, к^п/2,щеп — ЧИСЛОэлсментов(моду- лей), Рь = {pbijPb2j • • • и т. д. Популяции, как уже отмечалось выше, создаются случайным, направленным или направленно-случайным образом. Следует заметить, что в популяции будут оставаться только реальные решения. При наличии сети ЭВМ каждую генерацию можно параллельно реализовывать на своем процессоре. Рассмотрим случай наличия нескольких популяций. Произведем сортировку хромосом в каждой из популяций. Затем применим описанные схемы селекции для выбора родительских пар, причем в каждой паре родители должны быть из разных популяций. В [172] описаны четыре модифицированных ОК. Для повышения качества решения кроме рассмотренных генетических операторов используются все описанные выше модифицированные операторы. Например, пусть заданы хромосомы (планы кристалла). Применяя к ним модифицированные операторы кроссинговера, транслокации, мутации и др. получим следуюш,ий результат (хромосомы р[, pf,, р”,р”):

Каждой хромосоме соответствует определенный план кристалла. Основная задача генетических операторов — найти строительные блоки с лучшими характеристиками для копирования их в потомки. С этой точки зрения для задач планирования эффективными оказались операторы сегрегации, мутации и модифицированной инверсии.

Трудоемкость алгоритма ориентировочно определена так:

где Тм — трудоемкость реализации модели, например, в виде польской записи; — трудоемкость селекции; іок — трудоемкость оператора кроссинговера; tp — трудоемкость построения одной хромосомы в популяции; tom — трудоемкость оператора мутации; іои — трудоемкость оператора инверсии, toe — трудоемкость оператора сегрегации; Nq — число генераций, Np — размер популяции, ТѴп — число полученных потомков.

Задачи планирования кристалла тесно связаны с оптимизационными задачами упаковки и сжатия. После выполнения планирования кристалла часто решаются вопросы сжатия топологии СБИС. Сжатие топологии заключается в конвертировании элементов электрических схем в соответствующие элементы топологии и минимизации площади кристалла [117, 159].

Проектировщики сталкиваются с тремя противоречивыми требованиями:

•    спроектировать минимизированную по площади топологию;

•    максимизировать функциональные возможности СБИС;

•    минимизировать время и стоимость проектирования.

Проблема сжатия топологии связана с методологиями топологического проектирования (размещение компонентов и проводников) и геометрического проектирования (физическое размещение элементов топологии). Задачи сжатия обычно решаются на основе символической топологии.

Символическая топология дает возможность проектировщику анализировать такие компоненты СБИС, как транзисторы, проводники, ячейки и т. п. Символическая топология обычно транслируется в топологию в виде прямоугольников различного размера. В САПР такая топология представляется в виде диаграмм, представляющих проводники и элементы как различного рода компоненты. Следовательно, использование методов сжатия на основе символической топологии и диаграмм позволяет менять геометрию топологии с минимизацией площади кристалла. В работе [173] дан детальный обзор и классификация методов сжатия. Проблемы сжатия, как и остальные проблемы проектирования топологии, относятся к классу комбинаторно-логімеских задач и являются NP-ПОЛНЫМИ.

Алгоритмы сжатия обычно классифицируются по двум направлениям. Первое направление показывает, как движутся элементы в процессе сжатия. К этому классу относятся алгоритмы одноразмерного сжатия (1-Д), двухразмерного (2-Д), трехразмерного (3-Д) и специального сжатия типа (1,5-Д). Сжатие типа 1-Д обычно выполняется только в s или t направлениях, как показано на рис. 8.2, а, б. Проблема 1-Д-сжатия NP-полная. Реализация 2-Д

 

сжатия происходит одновременно по осям s и t. Второе направление показывает, каким образом производится размещение компонентов. Здесь выделяют три класса алгоритмов. Это — алгоритмы сжатия на основе графов ограничений, виртуально решетчатые алгоритмы и алгоритмы иерархического

сжатия. Основными алгоритмами здесь являются: алгоритмы сжатия на основе графа прямоугольников, алгоритм Айкерса или алгоритм «тени» [173].

Иерархические алгоритмы заключаются в многоуровневом сжатии. Элементы топологии, подлежащие сжатию, обычно описываются в виде прямоугольников: ЭТ^ = = ('Ші,Si, ti, Ші), здесь — ширина прямоугольника; hj — высота;

— декартовы координаты; — номер элемента (1 ^ ^ ш). Расстояния между элементами на плоскости измеряются по формулам (6.5, 6.6). Задача состоит в размещении прямоугольников таким образом, чтобы они не пересекались и площадь, где они расположены, была минимизирована. В такой постановке задачи сжатия перекликаются с задачами планирования кристалла, а также с задачами разбиения.

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

В работе [173] показана возможность сжатия символической топологии с применением ГА. Сжатие представляется как задача 2-Д. Множество прямоугольников размещается на плоскости, удовлетворяя заданным ограничениям и минимизируя стоимостную функцию площади кристалла. Прямоугольники размещаются на плоскости согласно списку элементарных ограничений. Набор списков, полученных случайно, представляет собой популяцию для реализации ГА. Селекция популяции производится случайно. Выполняются стандартные операторы кроссинговера и мутации. Алгоритм выполняется в двух иерархических уровнях (поверхностный и глубокий). Здесь используется селекция для сравнения списков ограничений. Достоинством алгоритма является простота реализации. Недостатки связаны с предварительной сходимостью алгоритма и невысокими результатами по минимизации площади.

Алгоритм 2-Д-сжатия топологии на основе моделирования отжига сначала уменьшает размер исследуемой поверхности, а затем на основе моделирования отжига выбирает множество ограничений. Основной недостаток состоит в том, что начальное решение выбирается случайно, а оно, в основном, влияет на конечный результат. Сложность алгоритма лежит в пределах 0(п2)-0(п4).

В той же работе описано решение задачи 2-Д-сжатия на основе ГА. Целевая функция определяется как максимум средней заполняемости заданной

плоскости. Достоинством алгоритма является введение нового ОК, ориентированного на решение задач сжатия. Данный оператор кроссинговера напоминает оператор сегрегации, выполненный направленным образом.

Стохастический метод для решения 1-Д-сжатия представляет собой объединение генетического поиска с процедурами моделирования отжига. Основная идея этого метода — повышение скорости моделирования отжига за счет использования простых стандартных операторов ГА. Для получения популяции решений используются две стратегии — «жадная» и случайная. Основной недостаток — требование больших затрат на вычислительные процедуры отжига, а также быстрая сходимость алгоритма с попаданием в локальный оптимум.

Предлагается иерархическая процедура решения задач сжатия топологии с использованием параллельного генетического поиска. Опишем кратко схему генетического поиска. Как и во всех описанных ранее алгоритмах, первоначально производится конструирование некоторого множества (четырех) популяций, в качестве элемента популяции выбирается порядок (реальный) расположения фрагментов топологии и соединений на плоскости, причем каждое соединение представляется прямоугольником, как и размещаемый элемент. Другими словами, каждая популяция будет представлять собой набор списков размещенных элементов и их соединений. Первая популяция будет конструироваться случайным образом, вторая — на основе «жадной» стратегии, третья — на основе последовательных эвристик и четвертая популяция — смешанная (направленно-случайная). В четвертой популяции половина элементов выбирается случайно, а вторая — используя знания о решаемой задачи. Согласно схеме, описанной выше, производим сортировку элементов популяций Рі- Р4 согласно выбранной целевой функции. ЦФ выбрана как стоимостная функция, минимизация которой уменьшит среднюю площадь, занятую компонентами топологии и их соединениями. Производится элитная селекция родителей из каждой популяции. Далее применяются три ОК. Операторы ОК применяются таким образом, чтобы каждый раз получались реальные решения. После выполнения ОК производится сортировка и устранение такого числа наихудших элементов популяций, чтобы размер популяций оставался постоянным. При получении удовлетворительных результатов процесс завершается. В противном случае возможно управление процессом поиска за счет перехода на другой оператор или изменения вероятности применения оператора. Данные процедуры выполняются итерационно и число генераций зависит от наличия вычислительных ресурсов. Трудоемкость алгоритма ориентировочно определена как

временная сложность алгоритма лежит в пределах 0{п log n)^O(n^).

Таким образом, увеличить вероятность получения оптимального решений задач планирования и сжатия топологии можно за счет управления процессом генетического поиска, путем изменения (определенного увеличения до попадания в локальный оптимум) размера популяций, количества

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