Реферат: Генетический алгоритм глобальной трассировки
На основе обработки экспериментальных исследований была построена зависимость качества решений от числа генераций.
В качестве аналога для сравнения выбран алгоритм WRST [7], основанный на последовательном построении взвешенных деревьев Штейнера. В алгоритме WRST также как и в рассмотренном в статье, каждая цепь представляется в виде связывающего дерева, построенного алгоритмом Прима, на основе которого последовательно строится дерево Штейнера с учетом веса ребер и динамически изменяющейся в процессе построения среды (коммутационного поля).
В таблице 1. представлены результаты сравнения экспериментальных данных с аналогом для пяти примеров.
В колонках F приводятся усредненные значения критерия F для генетического алгоритма (ГА) и для алгоритма WRST.
В колонке åL приводится суммарная длина, а в колонке t время работы алгоритма.
Как видно из таблицы генетический алгоритм обеспечивает более качественное решение, причем время решения на 10-40% меньше.
Сравнение с алгоритмами, использующими идею волнового алгоритма Ли, не проводилось, так как они дают худшие результаты, чем WRST[83].
Таблица 1.
| № | F | åL | T | |||
| ГА | WRST | ГА | WRST | ГА | WRST | |
| 1 | +2 | 0 | 4212 | 4570 | 33 | 37 |
| 2 | +3 | 0 | 3870 | 4610 | 31 | 34 |
| 3 | +1 | -2 | 5180 | 5900 | 57 | 69 |
| 4 | +3 | +1 | 4256 | 4570 | 59 | 61 |
| 5 | +2 | 0 | 3650 | 4220 | 29 | 34 |
5. Заключение
Приведена формулировка задачи глобальной трассировки. Определены перспективные критерии оптимизации. Разработана структура хромосомы, принципы ее кодирования и декодирования, использующие знания о задаче глобальной трассировки, исключающие возникновение неэффективных решений и повышающих скорость проектирования. Модернизированы и реализованы новые механизмы генетических процедур кроссинговера, мутации, смены популяций. Разработан генетический алгоритм глобальной трассировки на базе новых структур хромосом и модифицированных генетических процедур. Проведены экспериментальные исследования генетического алгоритма глобальной трассировки. Определены оптимальные сочетания значений управляющих параметрами М, Т, Рм , Рк . Проведено сравнение с аналогом показавшее, что разработанный алгоритм позволяет сократить сроки проектирования на 10-40%.
Список литературы
J.Soukup. Fast wise router .Proceedings of 15th Design Automation Conference, pages 100-102 ,1972.
J.Heisterman and T.Lengauer .The efficient solution of integer programs for hierarchical global routing . IEEE Transactions on Computer-Aided Design, CAD 10(6): 748-753, Jane 1991.
C.Chang , M.Sarrafzadeh ,and C.K. Wong .A powerful global router :Based on sterner min-max trees .Proceedings of IEEE International Conference on Computer-Aided Design, pages 2-5 , November 7-10 1989.
S.Burman , H .Chen ,and N. Sherwani . Improved global routing using l- geometry .Proceedings of 29th Annual Allerton Conference on Communications , Computing , and Control .October 1991 .
J.M. Ho , G. Vijayan , and C. K . Wong . A new approach to the rectilinear Sterner tree problem . IEEE Transactions on Computer -Aided Design , 9(2): 185-193 , February 1985 .
СелютинВ.А. АвтоматизированноепроектированиетопологииБИС .-М.:Радиоисвязь , 1983,-112 с .C.Chiang, M.Sarrafradeh, C.K.Wong. A Weighted-Steiner-Tree-Based Global Router, Manuscript, 1992.