6.5. Трассировка соединений

Существует большое число работ по канальной трассировке топологии

СБИС [174-179].

Рассмотрим прокладку соединений на основе канальных алгоритмов трассировки. Канальные алгоритмы базируются на представлении о каналах и магистралях. Магистралью называют отрезок прямой, по которой может проходить соединение в преимущественном направлении. Канал — это область прямоугольной формы, на одной или нескольких сторонах которой расположены контакты с системой однонаправленных магистралей. Каждая цепь, т. е. соединение эквипотенциальных контактов, представлена

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

Основная задача канальной трассировки — выбор наименьшей ширины канала, достаточной для размещения в нем всех соединений и назначения соединений на магистрали. Кроме того, необходимо минимизировать суммарную длину соединений (цепей), число переходных отверстий и т. п.

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

Канал описывается двумя последовательностями Тор и Bottom, в которых размещены верхняя и нижняя линейки канала, соответственно. Размер обоих последовательностей равен С — числу колонок в канале. Множество цепей определяется как Net. = {Ni,..., ІѴт}, где т — число цепей.

Рассмотрим следующий пример: Тор = {1,0,3,1,4, 2,3, 2} и Bottom = = {6,4,6,6,3,0,5,5}, где С = 8, п = 6, Net. = {1,2,3,4,5,6}, элемент О в Тор или в Bottom обозначает свободный контакт. На. рис. 6.33 дан эскиз канала с разведенными цепями.

При канальной трассировке не допускаются наложения вертикальных и горизонтальных сегментов цепей. Для решения этой задачи вводятся графы вертикальных и горизонтальных ограничений. Вертикальные ограничения описываются ориентированным графом вертикальных ограничений (рис. 6.34, a) Gy = Еу), где E^et — множество вершин, соответ

ствующих множеству цепей Net., Еу — множество направленных ребер. Ребро (п, т) £ Еу существует тогда и только тогда, когда цепь п должна быть расположена выше цепи т для предотвращения наложений вертикальных сегментов цепей. Например, на. рис. 6.34 в графе вертикальных ограничений существует путь из вершины 1 в вершину 6, это означает, что цепь 1 должна быть размещена выше цепи 6 для того, чтобы не было наложений вертикальных сегментов на. 1 и 6 контактах (см. рис. 6.33). Для того, чтобы задача решалась в рамках классической постановки, граф Gy должен быть ациклическим, в противном случае задача может быть решена

только с введением изломов, а. это противоречит условиям классической постановки задачи канальной трассировки.

Будем использовать расширенный граф вертикальных ограничений (рис. 6.34, б) Grv = (£Wet? ERV), где Net—множество вершин, соответствующих множеству цепей Net, Ецу — множество направленных ребер. Ребро (п, т) G £кѵ существует тогда и только тогда, когда в графе вертикальных ограничений существует путь из вершины п в вершину т. Например, на рис. 6.34 в графе вертикальных ограничений есть путь из вершины 4 в вершину 5 через вершину 3. Следовательно, в расширенном графе вертикальных ограничений существует ребро (4,5).

Горизонтальные ограничения представлены неориентированным графом горизонтальных ограничений (рис. 6.34, в) Он = (Е^&иЕн), где Emt — множество цепей, Ен — множество ребер. Ребро (п, т) £ Ен существует тогда и только тогда, когда магистрали для п и т разные для исключения наложения горизонтальных сегментов п и т. Например, на рис. 6.33 в графе горизонтальных ограничений существует ребро (1,4); это означает, что цепь 1 не может размещаться на одной магистрали с цепью 4 (см. рис. 6.33).

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

Для ГА трассировки принята следующая схема:

1.   Определение размера популяции Np, числа генераций Nq, вероятности кроссиншвера. Р(ОК) и вероятности мутации Р(ОМ).

2.   Задание случайным образом начальной популяции Р° размером Np.

3.   t = 0.

4.   Выбор случайным образом М пар хромосом из популяции Р1 и применение операции кроссиншвера. к каждой паре с заданной вероятностью Р(ОК).

5.   Применение операции мутации к каждой хромосоме популяции Р1 с заданной вероятностью Р(ОМ).

6.   Отбор. Отбор М хромосом с наилучшим значением целевой функции

из получившейся популяции Р1 в новую популяцию Pt+1.

7.   t = t + 1.

8.   Если t < Nq, to переход к шагу 4.

9.   Вывод хромосомы с наилучшим значением целевой функции.

10.  Конец работы алгоритма,

Здесь используется представление хромосомы, основанное на топологическом описании канала, т. е. хромосома описывает взаимное расположение цепей. Для этого каждой паре цепей (т, п), где гп / п, ставится в соответствие ген, который может принимать три состояния: 0 — если цепь т должна располагаться выше п\ 1 — если цепь т должна располагаться ниже щ и * — если их. взаимное расположение не имеет значения или определяется из взаимного расположения остальных цепей (это происходит, если цепи не имеют горизонтальных ограничений). Для примера, изображенного на рис. 6.33, хромосома будет иметь следующий вид:

где в строке таблицы 6.3, обозначенной как «Ген», записано значение гена в хромосоме, задающей расположение, показанное на рис. 6.33. Очевидно, что длина хромосомы при таком кодировании будет равна

где N — число цепей.

Как видно, длина хромосомы получается достаточно большой (для примера на рис. 6.33 она равна 15), что не приемлемо. Поэтому для уменьшения длины хромосомы используется анализ расширенного графа вертикальных ограничений и графа горизонтальных ограничений. Это получается за счет того, что взаимное расположения некоторых пар цепей уже зафиксировано в расширенном графе вертикальных ограничений, и изменение этого расположения приводит к образованию нарушений в канале, т. е. к наложению вертикальных сегментов цепей, что ведет к образованию нереальной хромосомы (т. е. такой, из которой не может быть получено решение, удовлетворяющее заданным требованиям).

Второй прием, позволяющий уменьшить длину хромосомы, основывается на том, что если цепи не имеют горизонтальных ограничений, то их взаимное положение либо не важно, либо определяется из соотношений с остальными цепями. Такие соотношения отмечены знаком «*». Следовательно, длина хромосомы будет равна L = NGO - NRVO, где NGO — число горизонтальных ограничений, NRVO — число вертикальных ограничений в расширенном графе вертикальных ограничений. В примере для пар цепей (1,6), (2,5), (3,4), (3,5), (3,6), (4,6) взаимное расположение жестко задано расширенным графом вертикальных ограничений, а. взаимное

расположение цепей в парах (1,2), (1,5), (2,4), (2,6), (4,5), (5,6) не имеет значения, поскольку цепи в этих парах не конфликтуют по горизонтали. Поэтому в примере хромосома будет выглядеть следующим образом:

Длина этой хромосомы будет равна 3. Для получения из хромосомы эскиза канала с разведенными цепями используется граф топологии. Граф топологии — это ориентированный граф GV = (Net., Ет), где Net.—множество цепей, Ет — множество направленных ребер, описывающих взаимное расположение цепей в канале. Ребро (ш, п) £ Ет существует тогда, и только тогда., когда, цепь m должна, быть расположена, в канале выше цепи п, т. е. на. магистрали с меньшим номером. Граф топологии строится из хромосомы по следующему алгоритму:

1.   Преобразуем расширенный граф вертикальных ограничений Grv в граф топологии GV-

2.   г = 1.

3.   Если ребро (гпі^Пі) не принадлежит GV, то это ребро добавляется к Gt•

4.   Проверяем для всех вершин к существование пути из вершины гпі к вершине к при условии, что к = 1,..., N, к / тпі и к / щ и не существует ребра, (т*, к) в GV- Существование пути из вершины гпі к вершине к. Если такой путь существует, то добавляем ребро (тпі^к) к GV-

5.   Если і ^ L, то увеличиваем і на. 1 и переходим к шагу 3.

6.   Считаем построение графа, топологии завершенным.

Канал восстанавливается из хромосомы следующим образом:

1.   Строим по хромосоме граф топологии GV-

2.   г = 0.

3.   Находим вершины, у которых есть только исходящие душ. Размещаем их на. магистрали с номером і или на. магистрали с меньшим номером, если это возможно, и удаляем эти вершины из графа..

4.   і = і + 1.

5.   Если граф топологии GV не пустой, возвращаемся к шагу 3.

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

7.   Возвращаем полученный образец размещения цепей в канале шириной і.

Например, пусть задана, хромосома. А=000. На. рисунке 6.33 показан полученный образец трассировки, который является оптимальным решением для примера.. Если А = 010 (отличие от предыдущего решения заключается в том, что цепь 4 располагается выше цепи 1), то эскиз канала, с разведенными цепями для такой хромосомы показан на. рисунке 6.35.

В нашем случае задача, заключается в минимизации целевой функции. Принимая во внимание характеристики задачи канальной трассировки, ЦФ определяется следующим образом:

где С — число контактов, программная функция UsedTrack(A) определяет число магистралей, занимаемых каналом, полученным при восстановлении из хромосомы А, а. программная функция TotalVertSeg(A) определяет длину вертикальных сегментов цепей в полученном решении.

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

Например, для канала, на. рисунке 6.33 число занятых магистралей равно 4, длина, вертикальных сегментов равна. 22. Таким образом, целевая функция хромосомы будет равна.

F(А) = (4 + 2) • 8 + 22 = 70, а. для канала,, показанного на. рисунке 6.35, F(А) = 72.

 

Данная методика, определения целевой функции направлена., в первую очередь, на минимизацию ширины канала, и, во вторую, — на минимизацию суммарной длины соединений.

Рассмотрим пример реализации описанного оператора, кроссиншвера:

1. і = 0.

2.   Выбрать хромосому с лучшим значением ЦФ как первого родителя.

3.   Выбрать произвольно второго родителя.

4.   Сгенерировать случайное число rnd в интервале [0,1].

5.   Если rnd < Р(ОК), то применить ОК к выбранным хромосомам и добавить получившихся потомков к популяции.

6.   і = і + 1.

7.   Если г < М, то перейти к шагу 2.

8.   Конец работы алгоритма..

В рассматриваемом алгоритме после анализа, хромосом выбран стандартный двухточечный ОК. Первая и вторая точка, разреза, в двухточечном ОК выбираются случайно. Часть первого родителя перед первой и после второй точки разреза, копируется в аналогичные места, в потомке. Место между первой и второй точкой разреза, во втором родителе копируется в первого потомка.. Второй потомок строится аналогично. Рассмотрим пример реализации двухточечного ОК:

В данном случае получен потомок р3 с лучшим значением ЦФ, чем значение ЦФ родителей. Топология трассировки, соответствующая родителю рі, показана на рисунке 6.35, и родителю р2 — на. рисунке 6.36. Топология трассировки, соответствующая потомку р3, показана, на. рисунке 6.33, а потомок р4 после декодирования хромосомы аналогичен родителю р2- Далее выполняется ОМ. Он произвольно изменяет один ген выбранной хромосомы при помощи случайного изменения значения гена, с вероятностью Р(ОМ), равной норме мутации. Алгоритм применения ОМ в ГА выглядит следующим образом:

1.   г = 0.

2.   Сгенерировать случайное число rnd в интервале [0, 1].

3.   Если rnd < Р(ОМ), то применить ОМ к г-й хромосоме популяции М.

4.   і = і + 1.

5.   Если г < М, то перейти к шагу 2.

6.   Конец работы алгоритма,

Следующий пример показывает реализацию этого механизма.: хромосома. (до применения ОМ): 0 (1) 0 — значение ЦФ: 72; хромосома, (после применения ОМ): 0 (0) 0 — значение ЦФ: 70. Здесь выбранная точка, мутации показана, в скобках. После применения ОМ в данном случае получается хромосома, с лучшим значением ЦФ. На. рисунке 6.35 показана. топология канала, соответствующего хромосоме до применения ОМ, а. на. рисунке 6.33 — после применения ОМ.

Теоретическая временная сложность алгоритма. составляет Nq (ІѴрР(ОК)2)Р(ОМ)х х0(ІѴ2), где Nq — число поколений, Np — размер популяции, Р(ОК)—вероятность крос- синговера, Р(ОМ) — вероятность мутации, 0(N2) — временная сложность декодирования хромосомы, N — число цепей.

Рассмотрим модифицированный генетический алгоритм двухслойной канальной трассировки цепей различной ширины. В работах [178-180] описаны алгоритмы канальной трассировки цепей различной ширины. Новые перспективные технологии проектирования топологии СБИС требуют трассировки цепей различной ширины и учета, большого количества, технологических ограничений. К ним относятся требования трассировки критических цепей (цепей частоты, питания) большего размера., чем у других цепей.

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

ризоытальыых и вертикальных сегментов. Выводы, принадлежащие одной цепи, должны быть соединены в соответствии с налагаемыми ограничениями. Эта постановка не является классической, когда каждая цепь имеет только один горизонтальный сегмент и несколько вертикальных сегментов, соединяющих горизонтальный сегмент с контактами цепи.

Для проведения трассировки доступны два слоя. Возможны два варианта назначения слоев:

•    в одном слое располагаются только вертикальные сегменты цепи, в другом — горизонтальные (ѴН-топопология);

•    в обоих слоях возможно любое ортогональное направление (как горизонтальное, так и вертикальное).

Соединения между горизонтальными и вертикальными отрезками делаются через переходные отверстия. Им является квадрат со стороной, равной ширине цепи, проходящей через это переходное отверстие (рис. 6.37). Не допускаются пересечения различных цепей друг с другом в одном слое.

Хромосома в данном алгоритме состоит из двух матриц (для верхнего и нижнего слоев), как показано на рис. 6.38, где и dij — гены хромосомы, і = 1 m, j = 1 п. Число т соответствует числу магистралей в данном канале, п — числу выводов в канале. Каждый ген хромосомы представляет в топологии канала прямоугольник со сторонами Bxrom[0][i] и Bxrom[l][j] (горизонтальные и вертикальные максимумы).

Возможны три значения гена в хромосоме:

•    j >0 — в данном прямоугольнике проходит цепь с номером ді^;

•    j =0 — данный прямоугольник пустой;

•    j <0 — в данном прямоугольнике находится межслойный переход, цепи с номером \g{j |

Первая строка матрицы R\ соответствует верхним контактам канала, последняя строка матрицы R\ соответствует нижнему набору контактов.

Рассмотрим на примере декодирование хромосомы (рис. 6.39).

Декодируем матрицы хромосомы R\ и R2. Получаем топологию канала в двух слоях (рис. 6.40).

ГА канальной трассировки может быть описан следующим кортежем: (Р7, D,<3), где Р' — является множеством всех решений для данной задачи, D — ограничения, накладываемые на множество Р' для получения допустимых решений, и Q — целевая функция, с помощью которой можно определить наилучшее (оптимальное) решение. Для задачи канальной трассировки этот вектор можно интерпретировать следующим способом: Р' — множество всех решений (хромосом) из всех популяций, причем эти хромосомы могут также представлять собой недопустимые решения или решения, являющиеся не 100-процентной трассировкой канала.

Пусть Pt - некоторая популяция на шаге t, тогда Р' = UP*, t = I^Nq; Pl — {pj}, j = 1 -г- Np, где Nq — количество итераций алгоритма, Np — количество хромосом в популяции Р1. Ограничения D: цепи не могут пересекаться, горизонтальные сегменты цепей проводятся в одном слое, вертикальные в другом, т. е. накладываются ограничения D(hij) на множество Pf(hij) такие, что в множестве допустимых решений S С Р! не могут существовать такие хромосомы рп, гены которых gi - имеют номера двух цепей одновременно (т. е. пересекаются), или значения нескольких горизонтальных (вертикальных) генов ...     ... при і = const (... gi_1j, g{ j, gi+1j ... при j = const) имеют одинаковый номер цепи в нижнем (верхнем) слое (т. е. ограничение на недопустимость проведения горизонтальных участков цепей в нижнем слое, а вертикальных участков — в верхнем).

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

Габаритные размеры канала определяются:  число межслойных переходов вычисляется:

а. суммарная длина цепей имеет вид:

здесь п — количество столбцов в канале (т. е. ширина канала), т — количество строк в канале (т. е. высота канала), ВгѴіѵ — массив ширины цепей, gi j — текущий ген в хромосоме.

Общая ЦФ вычисляется суммированием

где кі—кз — коэффициенты при локальных критериях, с помощью которых можно регулировать влияние того или иного критерия на качество решения. Они принимают значения в интервале (ОД).

Процесс оптимизация сводится к минимизации критерия Q, т. е. Q(P’)—> —» min Q(hom) = min Q(hij), где Нц С S.

Для того, чтобы определить ширину и высоту прямоугольного участка топологии канала соответствующего гена, используются два массива горизонтальных и вертикальных максимумов. Они вычисляются для каждой конкретной хромосомы и используются в дальнейшем для определения ширины и высоты части проводника цепи (рис. 6.41). В массивах хранятся целые положительные числа, которые определяют максимальный размер вертикали или горизонтали в хромосоме (канале). Для того, чтобы вычислить конкретные размеры ячейки, т. е. гена, необходимо знать номер столбца и строки и затем, с помощью соответствующих значений из массива, определяем ширину и высоту ячейки.

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

канала. Хромосома служит для отображения канала без учета ширины цепей. Таким образом, задав ширину, одинаковую для всех цепей, можно получить частный случай — канал без учета ширины цепей. Декодируя хромосомы, вместе с расшифровкой каждого гена в обоих слоях получим канал с различной шириной цепей (рис. 6.41).

Алгоритм формирования массивов горизонтальных и вертикальных максимумов (для массива вертикальных максимумов) представлен на рис. 6.42.

Поясним структурную схему алгоритма:

1.   Обнуляется массив вертикальных максимумов Brxrom[0] (для горизонтальных максимумов — Brxrom[l][]).

2.   Начинается цикл по столбцам, т. е. рассматривается сначала первый столбец, затем второй и так далее, для каждого столбца присваивается максимальная ширина maxbr, которая определяется на шаге 3.

3.   Цикл по магистралям. Просматривается весь столбец и находится цепь с самой большой шириной (из массива ширины цепей — ВгѴіѵ[]) в нижнем слое (1) или верхнем слое (2), причем если это будет межслойный переход, его тоже надо учитывать (3).

4.   Переход к пункту 2 для рассмотрения следующего столбца до тех пор, пока не будут рассмотрены все столбцы и не сформирован массив вертикальных максимумов Вгхгопі[0].

Рассмотрим модифицированный оператор кроссиншвера, ориентированный на задачу трассировки. Два родителя выбираются независимо друг от друга. Пусть, например, ра и р@ — копии родителей (рис. 6.43); р7 — полученный в результате применения ОК потомок.

Сначала произвольно выбирается точка кроссиншвера или, другими словами, продольное сечение хс между двумя какими-либо выводами, причем 1 ^ хс ^ ;rm(j, где хт& — число возможных сечений канала. Затем в р1 из индивида ра наследуется трассировочная структура, удовлетворяющая следующим двум условиям:

•    расположена на участке (xa,yaj z) при 1 ^ ха ^ хс, 1 ^ уа ^ ут(\ ІУтА — число магистралей), 1 ^ ^ 2 (z — номер слоя);

•    не пересекает сечение хс.

Аналогичным образом наследуется трассировочная структура из индивида pp. Связи родителей ра и р@ , пересеченные сечением хс, просматриваются, пока их точки Штейнера или выводы не будут достигнуты (рис. 6.44). Оставшиеся участки цепей наследуются в р1 (рис. 6.45). Если трассировочная структурара (или р@), которая должна быть передана в р7, содержит магистрали уш\а (ут&р), не занятые горизонтальными отрезками или точками Штейнера, то они удаляются. Начальное число магистралей в р7 есть уі11(|7 = шах(уіП(іа, 2/ind/3) • Часть индивида-родителя, содержащая

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

Трассировка оставшихся несоединенных в р1 цепей осуществляется следующим образом: пусть Na — множество всех точек Штейнера и выводов ра (концевые точки сегмента); соответственно Np — множество аналогичных точек pp. Если Na содержит более, чем один вывод цепи, то эти точки (если это возможно) соединяются друг с другом в произвольном порядке на основе стратегии случайной трассировки, рассмотренной выше. Соединенные точки цепи из списка Na удаляются, за исключением одной произвольно выбранной. Аналогичная «внутренняя» трассировка производится и с элементами Np. Далее точки из Na выбираются произвольно и сравниваются с точками из Np. Если точка той же цепи найдена в Np, то они соединяются произвольной случайной трассой. Процесс продолжается, пока все цепи канала не будут соединены.

Часто возникает ситуация, когда произвольная трассировка между двумя точками не приводит к связям после проведения і-числа итераций заданных заранее, тогда канал расширяется в произвольной позиции ужпри условии 1 ^ уаdd ^ Umd'y • Если j расширений канала (j — начальное число магистралей р7) не обеспечивают соединение, то потомок р7 удаляется и процесс продолжается снова с выбора местонахождения продольного сечения родительских хромосом.

В приведенном примере одно из возможных решений представлено на рис. 6.45 (потребовалось одно расширение канала).

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