Статья

Название статьи МНОГОУРОВНЕВЫЙ ВОСХОДЯЩИЙ ГИБРИДНЫЙ ПОДХОД ТРАССИРОВКИ ПО ВСЕМУ ЧИПУ
Автор Б.К. Лебедев, А.А. Шашелов
Рубрика РАЗДЕЛ II. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И САПР
Месяц, год 01, 2014
Индекс УДК 681.3.001.63
DOI
Аннотация Рассмотрена одна из важных задач конструкторского проектирования СБИС – задача трассировки схем. Она относится к классу NP-сложных и трудных задач. Предлагается многоуровневый подход к решению задачи трассировки по всему чипу. Описана структура графа глобальной трассировки. Разработан принцип разбиения графа глобальной трассировки на подграфы при многоуровневом подходе. Приведена общая схема многоуровневого подхода. Описан генетический алгоритм глобальной трассировки, основная идея которого заключается в кодировании альтернатив построения маршрута в вершинах графа. Приведен алгоритм глобальной трассировки методом муравьиной колонии, отличительной особенностью которого является концепция конкуренции колоний за коммутационное поле. Описан бессеточный волновой алгоритм детальной трассировки. Приведен принцип построения графа соединений для детальной трассировки. Описан принцип анализа занятости вершин в графе соединений. Разработана структура гибридизации глобальной трассировки с детальной трассировкой. Экспериментальные исследования проводились на IBM PC. По сравнению с существующими алгоритмами достигнуто улучшение результатов.

Скачать в PDF

Ключевые слова Генетический алгоритм; алгоритм муравьиной колонии; глобальная трассировка; детальная трассировка; глобальная дотрассировка; многоуровневая трассировка по всему чипу; оптимизация.
Библиографический список 1. Cong J., Xie M., Zhang Y. An Enhanced Multilevel Routing System // Proc. ICCAD. – 2002. – P. 51-58.
2. Chang Y.-W., Lin S.-P. A novel framework for multilevel routing considering routability and performance // Proc. ICCAD. – 2002. – P. 44-50.
3. Tai-Chen Chen, Yao-Wen Chang. Multilevel Full-Chip Gridless Routing Considering Optical Proximity Correction // Proc. ASPDAC. – 2005. – P. 1160-1163.
4. Bozorgzadeh E., Kastner R., Sarrafzadeh M. Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling // Circuits and Systems. – 2002. – Vol. 21, № 7. – P. 777-790.
5. Воронин Е.И., Лебедев Б.К. Многоуровневый подход к решению задачи трассировки по всему чипу с использованием модификаций муравьиного алгоритма // Известия ЮФУ.
Технические науки. – 2009. – № 7 (120). – С. 73-80.
6. Лебедев В.Б., Шашелов А.А. Генетический алгоритм глобальной трассировки основанный на альтернативах построения маршрута // Известия ЮФУ. Технические науки.
– 2012. – № 7 (132). – С. 55-62.
7. Воронин Е.И., Лебедев Б.К. Генетический алгоритм распределения соединений по слоям при многослойной глобальной трассировке СБИС // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 14-21.
8. Лебедев Б.К., Шашелов А.А. Волновой алгоритм детальной трассировки основанный на неявном графе соединений // Конгресс по интеллектуальным системам и информационным
технологиям (IS&IT’12). – М.: Изд-во “Физматлит”, 2012. – Т. 3. – С. 155-160.
9. CSE Department. Testing and Verification of Circuits (CS60089, 3-1-0). [Online].
http://www.facweb.iitkgp.ernet.in/~isg/TESTING/. (Дата обращения: 14.05.2013).

Comments are closed.