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

На основе обработки экспериментальных исследований была построена зависимость качества решений от числа генераций.

В качестве аналога для сравнения выбран алгоритм 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.