ми обеспечивает размещения элементов в любой комбинации без наложения друг на друга и с учетом конструктивных ограничений (требования электромагнитной и тепловой совместимости). Пусть даны множества элементов А = {ау| у = 1, 2, ..., п} и позиций П ={иг-| 1 = 1, 2, ..., с} на КП. Для размещения всех элементов необходимо выполнение условия с > п. Произвольное определение элементов по позициям представляет собой перестановку Р = р(1), р(2), ..., р(/'), ..., р(с), где р(/') задает номер элемента, который назначен в позицию п. В зависимости от выбранного критерия для оценки результатов размещения вводится целевая функция F(P). Таким образом, задача размещения состоит в отыскании оптимального значения функции F на множестве перестановок Р. Основными известными критериями при размещении [14, 15] являются: суммарная длина связи, длина самой длинной связи, число возможных пересечений, количество изгибов соединений, площадь кристалла и др.
В качестве модели схемы используется граф О = (X, У) или гиперграф Н = (X, Е), где X = {х, | 1 = = 1, 2, ..., п} - множество вершин, моделирующих элементы, а и = {ц |у = 1, 2, ..., 1} - множество ребер. Вершина х1 связана с Ху ребром, если для соответствующих элементов имеется соединение. Множество Е = {ву | вусХ,у = 1, 2, ..., т} объединяет гиперребра, моделирующие цепи, связывающие элементы. Граф адекватно отражает двухтерми-нальные соединения, а гиперграф - многотерминальные.
Расстояние между двумя вершинами с координатами (х, у) и (ху, уу) определяется по формуле йу = = |хг- - ху| + [у, - уу|. В качестве оценки 1у длины цепи tу, моделируемой гиперребром ву, используется длина минимального связывающего дерева. Оно построено на множестве вершин ву с X. Кроме того, применяются длина звездного графа, ребра которого инцидентны вершинам ву с X, а корневая вершина помещена в центре "тяжести" множества вершин ву; длина полупериметра прямоугольника, описывающего множество вершин в у; суммарная длина ребер полного графа, построенного на множестве ву. Исходя из этого, критерий оптимизации имеет вид
F =
I у
1 = 1
Для учета связей между задачами размещения и трассировки эффективны алгоритмы, основанные на оценках числа цепей, пересекающих заданные линии КП. Эти линии могут быть либо прямыми, пересекающими все КП, либо замкнутыми, ограничивающими некоторую область.
Пусть на КП наложена опорная сетка (см. рис. 1). Таким образом, имеется множество ребер сетки О = ^г [ 1 = 1, 2, ..., п^}, разбивающих КП на дискретные площадки (дискреты). Будем считать, что позиции пг располагаются внутри дискретов. В качестве исходных данных для КП задается множество В = {di [ г = 1, 2, ..., пй}, где - пропускная способность ребра gi, т.е. число цепей (трасс), которые могут ее пересечь. Значения определяются размерами ребра и ограничениями на прокладку соединений. Назовем цикл Ьк, составленный из ребер сетки и ограничивающий некоторую область, границей области. Под пропускной способностью РБк границы Ьк будем понимать суммарную пропускную способность ребер сетки, входящих в состав Ьк, т.е. РБк = Idi, (VI | gi е Ьк). Пусть Нк - число цепей, связывающих элементы, размещенные внутри области, определяемой Ьк, с элементами, расположенными вне этой области. Введем характеристику границы области, очерченной контуром
Ук = ^ - Ик)/Р5к.
Чем большее значение имеет ук, тем проще осуществить прокладку связей через границу Ьк. Предположим, что задано некоторое множество областей, для которых определена совокупность границ Ь = {Ьк [ к = 1, 2, ..., кЬ} и имеется некоторое размещение элементов. Найдем среди характеристик границ наименьшую , т.е. Vk[(PSk - Щ/РБк > у^]. Величина F = ут)п используется в качестве критерия оптимизации, целью которой является его максимизация.
Известно, что при одной и той же площади (следовательно, при одном и том же числе позиций) наименьшую длину имеет контур квадратной формы [10]. Следовательно, такая граница будет наиболее чувствительна к пересекающим ее цепям, так как для одного и того же множества элементов будет характеризоваться наименьшей оценкой PSk, а следовательно, - и ук. Поэтому в работе применяется система контуров, имеющих квадратную форму или близкую к ней.
Формирование множества контуров (границ) производится следующим образом. Рассмотрим КП размером Н X Ж, Н < Ж. Единицей измерения служит длина одного ребра опорной сетки (рис. 1). Выбираем контур с размерами с X с, с < Н. Сначала он помещается в левый угол КП, а затем путем сканирования (последовательного сдвига на один шаг вправо или вниз) формируется набор контуров. Число таких контуров определяется так: пк = (Н - с + 1) (Ж - с + 1). Для того чтобы контролировать все ребра gi опорной сетки, т.е. чтобы они входили в состав контуров опорного набора, необходимо соблюдение правила: для КП с
т
размерами H х W, H < W размер контура с < H/2. Чем ближе величины с и H/2, тем меньше контуров в составе L.
С другой стороны, контур, у которого величина с близка к H/2, наиболее чувствителен к перегрузке. Это связано с тем, что на единицу его длины приходится наибольшее число элементов, ограниченных этим контуром.
Создание расширяемого, мощного и устойчивого алгоритма минимизации временной задержки схемы в процессе размещения является ключевой задачей в разработке топологии микросхем. В настоящее время проводятся интенсивные исследования проблемы размещения, управляемого временными задержками. Производительность схемы определяется задержкой наиболее длинного пути, но временные ограничения предельно сложны. Число путей прохождения сигнала растет экспоненциально с ростом размера схемы. Даже схема умеренного размера может иметь огромное количество путей. Более того, на различные пути могут накладываться разные ограничения. Существующие алгоритмы размещения, управляемого временными ограничениями, можно условно разделить на две категории: основанные на путях (path-based) и на цепях (net-based) [16, 17].
Path-based алгоритмы непосредственно минимизируют задержку наиболее длинного пути. Популярные подходы в этой категории включают в себя математическое программирование и оценку критических путей. Широко распространенным приемом является минимизация суммы длин всех путей на некотором множестве критических путей, которое может быть заранее вычислено статическим образом, или способно динамически настраиваться на каждой итерации. Преимущества алгоритмов типа path-based - их точная временная оценка в процессе оптимизационной процедуры. Тем не менее, недостаток заключается в том, что они требуют большие вычислительные ресурсы из-за экспоненциального роста числа путей прохождения сигнала, которые нужно одновременно минимизировать. Более того, в определенных типах алгоритмов размещения, например, нисходящее разбиение схемы, трудно или невозможно обеспечить точный учет задержки.
Алгоритмы net-based в отличие от алгоритмов path-based непосредственно не накладывают ограничения на пути прохождения сигнала. Вместо этого временные ограничения или требования на пути преобразовываются в условия на длину цепей или их веса. Эта информация затем используется алгоритмом минимизации взвешенной длины соединений, с целью получения размещения с лучшей временной задержкой. Полученный вариант размещения рассматривается статическим анализатором, после чего формируется новый набор
временной информации для следующей итерации. Обычно подобный процесс повторяется на нескольких итерациях, до тех пор, пока наблюдается улучшение критерия или не будет выполнено заданное число итераций. По сравнению с алгоритмами path-based алгоритмы типа net-based имеют меньшую временную сложность.
Серьезным недостатком этого класса алгоритмов является то, что планирование задержки обычно проводится на структурном уровне схем без учета реализуемости размещения. В результате недавно было предпринято несколько попыток унифицировать планирование задержек и размещение, где законченное или грубое решение задачи размещения используется, чтобы управлять этапом планирования задержек. Тем не менее, в общем, задача разработки эффективного масштабируемого алгоритма для такой унификации остается трудновыполнимой [18].
2. Поисковые процедуры, основанные на объединении принципов эволюционной и альтернативной адаптации. Методы поисковой адаптации на основе механизмов генетики служат эффективным средством решения оптимизационных задач автоматизированного проектирования сверхбольших интегральных схем (СБИС) [11-20]. Преимущество этих методов в параллельной обработке множества альтернативных решений, представляющей мощное средство выхода из локальных опти-мумов. Такую обработку позволяют делать генетические алгоритмы (ГА), которые являются по своей сути алгоритмами случайного поиска. Однако заложенная в них стратегия эволюционного развития на основе естественного отбора приводит к синтезу решений, близких к оптимальным [21].
Эффективность ГА во многом определяется как учетом специфики решаемой задачи, так и использованием новых и модифицированных процедур поиска. Специфика решаемой задачи учитывается при разработке структуры, принципов кодирования и декодирования хромосом. Наблюдение живых организмов показывает, что адаптация является движущей силой эволюционного развития. Она многогранна и проявляется в виде сочетания генетической адаптации и адаптации на основе самообучения и самоорганизации, причем последняя доминирует в процессе существования и развития конкретного живого организма. Генетическая адаптация - средство развития организма как вида, и ее механизмы реализуются на уровне популяции.
Общий подход к построению поисковых адаптивных процедур опирается на комбинировании принципов адаптации на основе самообучения, самоорганизации и генетического поиска. Особенность адаптивных обучающихся алгоритмов состоит в том, что они легко и достаточно быстро находят оптимальное (локально) решение, лежа-
щее в некоторой достаточно обширной окрестности начальной точки поиска в пространстве решений. При генетическом поиске просматривается множество решений "разбросанных", особенно в начале, по всему прост
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.