Трассировка в коммутационном блоке на основе генетических процедур (стр. 3 из 3)
При заполнении 3-й магистрали (рис.6в) резервируются терминалы 21 и 52.Трансформируются: ДС21=(21,22) в ДС21¢=(2¢1,22), ДС5¢=(5¢1,52) в ДС5¢¢=(5¢1,5¢2). Полностью помещается только ДС5¢¢, которое удаляется из Vk.
При заполнении 4-й магистрали (рис.6г) резервируется терминал 41. ДС4=(41,42) трансформируется в ДС4¢=(4¢1,42). При просмотре Vk частично
помещается ДС12¢ и полностью ДС4¢. ДС12¢ трансформируется в ДС12¢¢=(1¢¢2,13), а ДС4¢ удаляется из Vk.
При заполнении 5-й магистрали (рис.6д) резервируются терминалы 31.и 13. ДС31=(31,32) трансформируется в ДС31¢=(3¢1,32), а ДС12¢¢=(1¢¢2,13) в ДС12¢¢¢=(1¢¢2,1¢3). При просмотре Vk полностью помещаются ДС21¢, ДС22¢, ДС31¢, ДС12¢¢, которые удаляются из Vk.
При заполнении 6-й магистрали (рис.6е) полностью помещается ДС32.
При заданных способах кодирования ОТ1 и ОТ2, при декодировании хромосом Hk, соответствующих ОТ1 и ОТ2 и представляемых в виде вышеприведенных матриц Vk, конечные результаты совпали, хотя это и не является обязательным.
Матрица Vk просматривается при заполнении каждой магистрали. Размер матрицы Vk пропорционален числу as содержащихся в ней ДС.
as=ak-an , где ak - число терминалов, расположенных на границах ОТ, и an - число цепей. Отсюда оценка трудоемкости процедуры декодирования пропорциональна O(m*as).
Генетические операторы
Общая структура генетического поиска представлена на рис.7.
Предварительно осуществляется формирование структуры хромосомы. Эта процедура включает разбиение каждой цепи на ДСj, разбиение множества ДС на подмножества, определение числа и размера генов в составе хромосомы: определение состава каждого гена (т.е. определение ДС, входящих в каждый ген). Далее, случайным образом генерируется исходная популяция Пи хромосом размером М. Суть случайного формирования в том, что для каждого гена каждой хромосомы случайным образом устанавливается порядок расположения в нем элементов (ДС). Для каждой хромосомы рассчитывается фитнесс. Расчет фитнесса осуществляется на основе декодирования хромосомы, т.е. фактически решения задачи трассировки.
Целью генетического поиска является нахождение такой хромосомы и с таким расположением элементов в генах, которые обеспечивают при декодировании оптимальное значение фитнесса.
Основными генетическими операторами являются кроссинговер и мутация. В нашем случае операция кроссинговер реализуется путем вероятностного выбора родительской пары хромосом и формирования на ее основе потомков путем взаимооднозначного обмена гомологичными генами. В общем случае хромосомы могут обмениваться группами гомологичных генов. Оператор кроссинговера для выбранной пары выполняется следующим образом.
Задается вероятность кроссинговера Pk. Затем последовательно просматриваются пары гомологичных генов (генов, расположенных в одном и том же локусе хромосом), которые с заданной вероятностью Pk меняются местами. При выборе пары хромосом для кроссинговера используется ²принцип рулетки², при котором вероятность P(Hi) Выбора хромосомы Hi определяется как:
,где Fi - фитнесс хромосомы Hi.
Число пар хромосом W является управляющим параметром процедуры генетического поиска.
В результате выполнения операции кроссинговера формируется дополнительная популяция Пк, которая объединяется с Пи и в дальнейшем подвергается мутации. Для каждой хромосомы популяции Пк рассчитывается фитнесс. Операция мутации заключается в выборе гена, который подвергается мутации и мутации этого гена. Мутация гена заключается в случайном выборе пары элементов, входящих в состав гена, и обмене местами их расположения в гене.
Реализация операции мутации осуществляется следующим образом. Задается вероятность мутации PM, последовательно просматриваются все хромосомы из популяции Пи+Пк, а в хромосоме все гены, и с заданной вероятностью PM ген мутирует. Мутация заключается в случайном выборе в гене пары элементов, которые затем обмениваются местами. Выполнение оператора мутации приводит к формированию дополнительной популяции Пм, для каждой хромосомы которой рассчитывается фитнесс.
Заключительной операцией в пределах одного поколения является селекция расширенной популяции Пт=Пи+Пк+Пм. В результате селекции на основе ²принципа рулетки² отбирается новая популяция Пи лучших решений, которая является исходной для следующей генерации. Число генераций (поколений) Т, размер популяции М и параметры Рк и Рм являются управляющими параметрами, влияющими на эффективность процесса генетического поиска.
3. Экспериментальные исследования
Алгоритм был реализован на языке С++ для ПЭВМ типа IBMPC.
Первой целью экспериментальных исследований - было нахождение наилучшего сочетания значений управляющих параметров таких, как PМ, PК, М и Т, где М - объем популяции.
Исследования проводились следующим образом. Для каждого примера сначала фиксировалось значение РМ и изменялись параметры PК и М. Затем фиксировалось значение PК и изменялись PМ и М. Для каждого набора значений PМ, PК, и М проводилась серия из 10 экспериментов в результате которой определялось среднее, максимальное и минимальное значение Т, при котором не наблюдалось улучшения лучшего решения. Было установлено, что при значении PК=0,4 и PМ=0,1, М=50 и Т=130 обеспечивается нахождение оптимального решения.
Исследования трудоемкости алгоритма показали, что при фиксированных значениях PМ, PК, М и Т она имеет линейную зависимость и пропорциональна O(N), где N - число связываемых контактов.
Заключение
В статье был представлен генетический алгоритм трассировки в коммутационном блоке. При разработке структуры и методов кодирования и декодирования хромосом, генетических операторов использовались специфические знания о проблеме. Исследования показали достаточно высокую эффективность разработки генетических процедур.
Источником усовершенствования может стать правильная настройка параметров управления. Другая возможность состоит в том, чтобы при частичной укладке вводить более двух точек разрыва, что приведет к трансформации укладываемого ДС в несколько ДС.
Понятие верхней и нижней сторон ОТ относительно, поскольку ОТ можно развернуть на 180° и верхняя сторона станет нижней, а нижняя верхней. В связи с этим возможно использовать прием, заключающийся в чередовании порядка заполнения магистралей: первая сверху, первая снизу, вторая сверху, вторая снизу и т.д. При заполнении n-ой сверху магистрали последовательно просматриваются строки матрицы Vk, начиная с первой, а при заполнении n-й снизу магистрали строки матрицы Vk просматриваются в обратном порядке, начиная с последней.
Средством повышения сходимости генетического алгоритма может стать представление решения в виде двух хромосом H1k и H2k . При этом ОТ представляется, как и было показано выше, в виде двух ОТ1 и ОТ2 одновременно. Структура H1k соответствует ОТ1, а структура H2k соответствует ОТ2. Заполнение магистралей производится последовательно и попеременно то в ОТ1, то в ОТ2. При трансформации некоторого ДС в ОТ1 осуществляется соответствующая трансформация в ОТ2, и наоборот.
Представление одного решения в виде двух хромосом, дает возможность использовать генетический оператор комбинирования набором хромосом в одном решении. При этом пара родительских решений дает четыре потомка.
Отметим, что предложенный подход полностью применим для «безсеточной» трассировки соединений разной ширины. Для этого на основе конструктивных параметров (ширина цепи, расстояние между цепями и окнами, размеры переходных контактов) рассчитываются допустимые расстояния между фрагментами. В этом случае задача трассировки сводится не к распределению фрагментов по магистралям, а к упаковке фрагментов. Модернизированная процедура декодирования будет последовательно размещать ДС «прижимая» их на допустимую величину к ранее размещенным. В качестве базиса выбирается верхняя сторона ОТ. Результатом работы будут физические координаты размещенных фрагментов.
Путем модификации процедур укладки, трансформации и резервации можно использовать выше приведенную методику для трассировки с числом слоев больше двух.
Список литературы
W.K.Luk. A greedy switch box router INTEGRATION, the VLCI Journal, 3: pp. 129-149, 1985.
H.Shin and A.Sangiovanni Vincentelli. Mighty: a rip-up and reroute detailed router. Proceedings of IEEE International conference on Computer-Aided Design, pages 2-5, November 1986.
J.P.Cohoon and P.L.Heek. Beaver: A computational geometry based tool for switch box routing. IEEE Transactions on Computer-Aided Design, 7:684-697,June,1988.
M.Marek-Sadowska. Switch box routing: a retrospective. INTEGRATION, the VLCI Journal, 13, pp. 36-65 1992.
Y.L. Lyn, Y.C. Hsu, and Tsai. Silk: A simulated evolution router. IEEE Transactions on Computer-Aided Design, 8:1108-1114,October,1989.
T.Cho, S. Pyo, and J. Heath. Parallex: A parallel approach to switch box routing. IEEE Transactions on CAD of Integrated Circuits and Systems, 13:684-693, June 1994.
Лебедев Б.К. Канальная трассировка на основе генетических процедур. Интеллектуальные САПР. Таганрог: ТРТУ, 1997, N3(6) с. 53-60.