Статья

Название статьи РОЕВОЙ АЛГОРИТМ ТРАССИРОВКИ В ПРИКАНАЛЬНОЙ НАДЪЯЧЕЕЧНОЙ ОБЛАСТИ
Автор O.Б. Лебедев, О.А. Пурчина
Рубрика РАЗДЕЛ III. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 06, 2015
Индекс УДК 681.325
DOI
Аннотация Представлен алгоритм синтеза эскиза однослойной трассировки в надъячеечной области (НЯО) топологии СБИС. Разработаны новые механизмы решения задачи трассировки, использующие математические методы, в которых заложены принципы природных механизмов принятия решений. Для синтеза эскиза однослойной трассировки используется новая парадигма комбинаторной оптимизации муравьиное дерево (trees ant colony optimization (T-ACO)), основанная на идеях адаптивного поведения муравьиной колонии и в первую очередь на идее непрямого обмена – cтигмержи (stigmiergy), позволяющая осуществлять синтез дерева. В отличие от канонической парадигмы муравьиного алгоритма муравьем на специальном графе поиска решений G=(X,U) строится решающее дерево. Рассматривается структура и методика формирования специального графа поиска решений G=X,U). Описываются принципы интерпретации полученного муравьями решения в виде эскиза однослойной трассировки. Задача решается в различных постановках, отличающихся типом границ области трассировки. Программа трассировки в НЯО была реализована на языке С++ для IBM PC. Во всех перечисленных постановках был получен результат, близкий к оптимальному. Трудоемкость программы имеет вид О(n2), где n – число фрагментов. При использовании “ломаных” границ, процедуры “прилипания” и последовательной трассировки НЯО удавалось дополнительно снизить общую плотность каналов до 40%. Предложенный трассировщик полностью применим для “беcсеточной” трассировки соединений разной ширины. Экспериментальные исследования проводились на IBM PC. Временная сложность алгоритма (ВСА), полученная экспериментальным путем, практически совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет (ВСА≈О(n2)). Для проведения объективных экспериментов были использованы известные тестовые задачи, представленные в литературе и в Интернет. Для составления достоверных выводов был проведен не один, а серия опытов-экспериментов. По сравнению с существующими алгоритмами достигнуто улучшение результатов на 2–3%.

Скачать в PDF

Ключевые слова Роевой интеллект; муравьиная колония; адаптивное поведение; муравьиное дерево; трассировка; надъячеечная область; оптимизация.
Библиографический список 1. Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar. Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009.
2. Roy J.A. High-Performance routing at the nanometer scale // IEEE Trans.Comput.-Aided Design Integr. – Syst. June 2008. – Vol. 27, issue. 6. – P. 1066-1077.
3. Лебедев Б.К., Лебедев В.Б.. Поисковые процедуры канальной трассировки базирующиеся на моделировании адаптивного поведения роя частиц в пространстве решений с неупорядоченным лингвистическим шкалированием // Известия ЮФУ. Технические науки. – 2009. – № 12 (101). – С. 15-22.
4. Лебедев О.Б. Трассировка в канале методом муравьиной колонии // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 46-52.
5. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. – Таганрог: Изд-во ТРТУ, 2003.
6. Dorigo M. and Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
7. Dorigo M., Stьtzle T. Ant Colony Optimization: Overview and Recent Advances. M. Gendreau and Y. Potvin, editors, Handbook of Metaheuristics, 2nd edition. Vol. 146 in International Series in Operations Research & Management Science. Springer, Verlag, New York, 2010. – P. 227-263.
8. Лебедев Б.К., Лебедев В.Б. Оптимизация методом кристаллизации россыпи альтернатив // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 11-17.
9. Лебедев О.Б. Модели адаптивного поведения муравьиной колониив в задачах проектирования. – Таганрог: Изд-во ЮФУ, 2013.
10. Лебедев О.Б. Покрытие методом муравьиной колонии // Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2010. Труды конференции. Т. 2. – М.: Физматлит, 2010. – С. 423-431.
11. Лебедев Б.К., Лебедев В.Б. Построение кратчайших связывающих сетей на основе метода муравьиной колонии // Нечеткие системы и мягкие вычисления: сб. ст. Третьей Всероссийской научной конференции. В 2 т. Т .II. Волгоградский гос. техн. университет. – Волгоград, 2009. – С. 42-50.
12. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адаптивного поведения биологических систем // Нейрокомпьютеры: разработка, применение. – 2010. – № 2. – С. 28-34.
13. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 37-44.
14. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 27-35.
15. Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивного поведения муравьиной и пчелиной колоний // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 41-47.

Comments are closed.