Статья

Название статьи МНОГОУРОВНЕВЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ ТРАССИРОВКИ ПО ВСЕМУ ЧИПУ С ИСПОЛЬЗОВАНИЕМ МОДИФИКАЦИЙ МУРАВЬИНОГО АЛГОРИТМА
Автор Б.К. Лебедев, Е.И. Воронин
Рубрика РАЗДЕЛ II. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2011
Индекс УДК 681.3.001.63
DOI
Аннотация Предлагается метод многоуровневой трассировки СБИС, включающей две стадии: укрупнение и детализация. На стадии укрупнения множество областей (ячеек) итеративно группируется, и соответственно группируются узлы на многоуровневом графе. На стадии детализации множество объединенных ячеек итеративно разгруппируется. На каждом уровне выполняется глобальная, а затем детальная трассировка локальных соединений с использованием модификаций муравьиного алгоритма, как для глобальной, так и для детальной трассировки Основными критериями оптимизации являются трассируемость – процент проложенных соединений. Для моделирования процесса поиска используются графовые модели. Использование муравьиного алгоритма позволяет учитывать несколько критериев при поиске оптимального решения. Сравнение с известными алгоритмами показало улучшение качества решений до 3 %.

Скачать в PDF

Ключевые слова Многоуровневый подход; СБИС; муравьиный алгоритм; трассировка; оптимизация.
Библиографический список 1. Лебедев Б.К., Лебедев В.Б. Поисковые процедуры канальной трассировки, базирующиеся на моделировании адаптивного поведения роя частиц в пространстве решений с неупорядоченным лингвистическим шкалированием // Известия ЮФУ. Технические науки. – 2009. – № 12 (101). – С. 15-22.
2. Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации. – М.: Физмалит, 2009.
3. Курейчик В.В., Курейчик В.М., Родзин С.И. Концепция эволюционных вычислений, инспирированных природными системами // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 16-25.
4. Литвиненко В.А., Ховансков С.А., Норкин О.Р. Оптимизации мультиагентной системы распределенных вычислений // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 226-235.
5. Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar.Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009.
6. Chang Y.-W. and Lin S.-P., MR: A new framework for multilevel full-chip routing // IEEE Trans Computer-Aided Design. – 2004. – № 23 (5). – Р. 793-800.
7. Cong J., Fang J., Xie M. and Zhang Y. MARS–A multilevel full-chip gridless routing system // IEEE Trans Comput.-Aided Design Integr. Syst. – 2005. – Vol. 24, №. 3. – Р. 382-394.
8. Tai-Chen Chen, Yao-Wen Chang. Multilevel Full-Chip Gridless Routing With Applications to Optical-Proximity Correction // IEEE Trans Comput.-Aided Design Integr.Syst. – 2007. – Vol. 26, № 6. – Р. 1041-1053.
9. Лебедев О.Б. Трассировкавканалеметодоммуравьинойколонии // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 46-52.
10. Лебедев Б.К., Лебедев В.Б. Глобальная трассировка на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2010. – № 7 (108) – С. 32-39.
11. Лебедев Б.К., Воронин Е.И. Гибридный алгоритм разбиения на основе муравьиной колонии // Труды Конгресса по интеллектуальным системам и информационным технологиям “AIS-IT’09”. T. 3. – М.: Изд-во Физматлит, 2009. – C. 213-214.
12. Мак Коннелл Дж. Основысовременныхалгоритмов. – М.: Техносфера, 2004.

Comments are closed.