Генетический алгоритм глобальной трассировки

О.Б. Лебедев

1 Введение

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

Большинство алгоритмов, глобальной трассировки осуществляют последовательное построение соединений на укрупненной модели КП (волновые, лучевые, базирующиеся на построении деревьев Штейнера). [1,2,3,4,5,6,7]. Хотя на каждом шаге для каждого текущего состояния среды алгоритмы дают неплохие результаты, «камнем преткновения» является последовательность трассируемых соединений. Цепи, проложенные раньше ,могут блокировать цепи ,прокладываемые позже.

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

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

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

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

Для решения задачи глобальной трассировки используется графовая модель G = (X, U). Коммутационное поле разбивается на области. Вершины графа x_i Î Х соответствуют областям на КП. Если области соседние, то вершины x_i и x_к , соответствующие этим областям, связываются ребром u_j . Пусть задано множество цепей Т={t_i | i = 1, 2, ...}. Для каждой цепи определяется множество областей, в которых существуют контакты, связываемые этой цепью. На графовой модели G, множеству областей, связываемых цепью x_i , соответствует подмножество вершин Х_i Ì Х. Для каждого ребра u_i ,связывающего вершины, задается вес a_j , равный пропускной способности между областями, соответствующими вершинам x_i и x_{­ k} . Будем считать, что граф G метризирован, то есть каждая вершина имеет координаты. Координаты вершины принимаются равными координатам центра соответствующей области. Если области имеют один и тот же размер, то граф G представляет собой ортогональную решетку.

Далее для каждой цепи t_i на множестве вершин Х_i графа G строится минимальное связывающее дерево D_i с помощью алгоритма Прима D_i ={r_k | k=1,2, … ,n_k }, где r_k – ребро минимального связывающего дерева.

Для каждого ребра r_k ÎD_i формируется набор V_k вариантов v_ik маршрутов, связывающих на графе G соответствующие вершины. Формирование возможных маршрутов осуществляется следующим образом. Для ребра r_k ÎD_i , связывающего x_n ÎG и x_m ÎG, определяется множество вершин Х_k ÌX, смежных вершинам х_n и х_m ребра r_k ,. Через множество вершин Х_к , а так же через вершины x_n и x_m проводятся новые вертикальные и горизонтальные линии.Отметим, что эти линии проходят по ребрам ортогонального графа G. В узлах пересечения этих линий лежат некоторые вершины х_i Î Х. Эти вершины являются узловыми для формирования вариантов. Будем считать, что варианты маршрутов проходят по тем ребрам графа G, которые лежат на этих линиях, рис 1.

Например: сформируем набор вариантов для ребра г_к , связывающего вершины х_i и х_j . Пронумеруем узлы пересечения вертикальных и горизонтальных линий. Вершина х_i лежит в узле 3, а вершина х_j в узле 10. Для данного ребра г_k существует 10 вариантов прохождения маршрута V_k = {v_{k 1} , v_{k 2} , v_{k 3} , v_{k 4} , v_{k 5} , v_{k 6} , v_{k 7} , v_{k 8} , v_{k 9} , v_{k 10} }

v_{k 1} = {3, 2, 5, 8, 11, 10}; v_{k 2} = {3, 6, 5, 8, 11, 10}; v_{k 3} = {3, 6, 9, 8, 11, 10}; v_{k 4} = {3, 6, 9, 12, 11, 10}; v_{k 5} = {3, 2, 1, 4, 7, 10}; v_{k 6} = {3, 2, 5, 4, 7, 10}; v_{k 7} = {3, 6, 5, 4, 7, 10}; v_{k 8} = {3, 2, 5, 8, 7, 10}; v_{k 9} = {3, 6, 5, 8, 7, 10}; v_{k 10} = {3, 6, 9, 8, 7, 10}

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

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

варианты формируются, чтобы обеспечивалось максимально возможное совпадение вариа