Статья

Название статьи ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ГЛОБАЛЬНОЙ ТРАССИРОВКИ, ОСНОВАННЫЙ НА КОДИРОВАНИИ АЛЬТЕРНАТИВ ПРОКЛАДКИ МАРШРУТА В ГРАФЕ
Автор В.Б. Лебедев, А.А. Шашелов
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 07, 2012
Индекс УДК 681.325
DOI
Аннотация Предложен новый метод решения задачи глобальной трассировки на основе генетического алгоритма. Основная идея алгоритма заключается в кодировании альтернатив прокладки маршрута в вершинах графа. Отличительной чертой является то, что кодируется не реальное размещение соединения по областям, а процедура его построения на коммутационном поле, а кодом является число в двоичной системе вычислений. Процесс построения маршрута заключается в последовательном перемещении по ребрам графа G от вершины к вершине, в соответствии с заданным кодом. Это значительно упрощает выполнение генетических операторов и сокращает объем необходимой памяти. В работе описываются принципы кодирования и декодирования хромосомы в компактной форме. Трудоемкость кодирования и декодирования хромосомы имеет линейную сложность O(L), где L – длина хромосомы. Приводятся разработанные генетические операторы. Экспериментальные исследования проводились на IBM PC. По сравнению с существующими алгоритмами достигнуто улучшение результатов.

Скачать в PDF

Ключевые слова Генетический алгоритм; глобальная трассировка; оптимизация.
Библиографический список 1. Chang Y., Cheng K., Wang L. Electronic Design Automation: Synthesis, Verification, and Test. Elsevier Science, 2009.
2. Bozorgzadeh E., Kastner R., Sarrafzadeh M. Pattern routing: use and theory for increasing predictability and avoiding coupling // IEEE Trans. on CAD. – 2002. – № 21 (7). – P. 777-790.
3. Cho M., Pan D.Z., Puri R., Xiang H. Wire Density Driven Global Routing for CMP Variation and Timing, in Proc. Int. Conf. on Computer Aided Design, 2006.
4. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектировании СБИС. Монография. – Таганрог: Изд-во ТРТУ, 2000. – С. 107-128.
5. Курейчик В.М., Лебедев Б.К. Методы эволюционной адаптации при решении комбинаторных задач // Материалы XV Международной конференции по нейрокибернетике. Т. 2.
– Ростов-на-Дону: Изд-во ЮФУ, 2009. – С. 98-101.
6. Курейчик В.М., Кажаров А.А.Использование роевого интеллекта в решении NP-трудных задач // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 30-36.
7. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 28-32.
8. Лебедев О.Б. Глобальная трассировка на основе муравьиного алгоритма // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 94-102.
9. Лебедев Б.К., Лебедев В.Б.. Глобальная трассировка на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 32-39.
10. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 37-44.
11. Лебедев В.Б., Лебедев О.Б. Генетический алгоритм глобальной трассировки на основе иерархических многохромосомных представлений // Интеллектуальные системы. Коллективная монография / Под ред. В.М. Курейчика. – М.: Физматлит, 2009. – С. 88-105.
12. Лебедев О.Б. Дотрассировка (перетрассировка) соединений на основе гибридизации волнового и муравьиного алгоритмов // Труды конгресса по интеллектуальным системам и информационным технологиям «IS– IT’10». Научное издание в 4-х томах. Т. 2. – М.: Физматлит, 2011. – С. 48-56.
13. Курейчик В.М. Модифицированные генетические операторы // Известия ЮФУ. Технические науки. – 2009. – № 12 (101). – С. 7-15.
14. FGR 1.1. [Online]. Available: http://vlsicad.eecs.umich.edu/BK/FGR.

Comments are closed.