Реферат: Трассировка в коммутационном блоке на основе генетических процедур
Исследования проводились следующим образом. Для каждого примера сначала фиксировалось значение РМ и изменялись параметры PК и М. Затем фиксировалось значение PК и изменялись PМ и М. Для каждого набора значений PМ , PК , и М проводилась серия из 10 экспериментов в результате которой определялось среднее, максимальное и минимальное значение Т, при котором не наблюдалось улучшения лучшего решения. Было установлено, что при значении PК =0,4 и PМ =0,1, М=50 и Т=130 обеспечивается нахождение оптимального решения.
Исследования трудоемкости алгоритма показали, что при фиксированных значениях PМ , PК , М и Т она имеет линейную зависимость и пропорциональна O(N), где N - число связываемых контактов.
Заключение
В статье был представлен генетический алгоритм трассировки в коммутационном блоке. При разработке структуры и методов кодирования и декодирования хромосом, генетических операторов использовались специфические знания о проблеме. Исследования показали достаточно высокую эффективность разработки генетических процедур.
Источником усовершенствования может стать правильная настройка параметров управления. Другая возможность состоит в том, чтобы при частичной укладке вводить более двух точек разрыва, что приведет к трансформации укладываемого ДС в несколько ДС.
Понятие верхней и нижней сторон ОТ относительно, поскольку ОТ можно развернуть на 180° и верхняя сторона станет нижней, а нижняя верхней. В связи с этим возможно использовать прием, заключающийся в чередовании порядка заполнения магистралей: первая сверху, первая снизу, вторая сверху, вторая снизу и т.д. При заполнении n-ой сверху магистрали последовательно просматриваются строки матрицы Vk , начиная с первой, а при заполнении n-й снизу магистрали строки матрицы Vk просматриваются в обратном порядке, начиная с последней.
Средством повышения сходимости генетического алгоритма может стать представление решения в виде двух хромосом H1 k и H2 k . При этом ОТ представляется, как и было показано выше, в виде двух ОТ1 и ОТ2 одновременно. Структура H1 k соответствует ОТ1, а структура H2 k соответствует ОТ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.