ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 2, с. 117-133
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
УДК 681.3.001.63
ТРАССИРОВКА СОЕДИНЕНИЙ В КАНАЛЕ НА ОСНОВЕ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ МУРАВЬИНОЙ КОЛОНИИ*
© 2015 г. В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев
г. Ростов-на-Дону, Южный федеральный ун-т Поступила в редакцию 01.03.14 г., после доработки 12.11.14 г.
На основе сравнительного анализа существующих подходов и методов для решения задачи трассировки, дотрассировки и перетрассировки соединений сверхбольших интегральных схем использованы мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании адаптивного поведения муравьиной колонии. Рассматриваемая задача представлена в виде набора компонент муравьиного алгоритма. Разработаны эвристики поведения муравья при перемещениях в графе поиска решений. Отличительной особенностью приведенного алгоритма является возможность учета ряда показателей, таких как распределение ресурсов, создание помех (блокировки), число переходов из слоя в слой, число изгибов, и другие, которые весьма затруднительно учесть при распространении волны. Тестирование разработанного алгоритма трассировки и его сравнение с известными алгоритмами производилось на бенчмарках. В сравнении с существующими алгоритмами достигнуто улучшение качества решений до 3%. Перспективными путями улучшения алгоритма является использование расширенной области трассировки, допускающей незначительное увеличение длины маршрута в пользу минимизации помех. Повышения эффективности алгоритма можно добиться путем адаптивного управления управляющими параметрами.
БО1: 10.7868/80002338815020092
Введение. Одной из важнейших задач при построении интеллектуальных систем автоматизированного проектирования (САПР) сверхбольших интегральных схем (СБИС) является трассировка соединений. В связи с постоянным уменьшением геометрических размеров элементов и соответственно увеличением их числа на кристалле задача все больше усложняется. Переход к нанометровым технологиям производства интегральных схем (ИС) породил новые ограничения, накладываемые на данную задачу [1, 2]. Подавляющее большинство известных методов для решения задачи трассировки используют двухэтапный подход, включающий глобальную [3] и детальную трассировки [1, 4]. В процессе глобальной трассировки все коммутационное поле делится на области трассировки (клетки, ячейки), и между этими областями прокладываются соединения.
Наиболее известными видами детальной трассировки являются трассировка в канале (channel routing) [4—6], трассировка коммутационных блоков (switch-box routing) [7, 8] и так называемая трассировка по всему чипу (full-chip routing). Последняя является наиболее интересной с точки зрения исследований и разработки новых алгоритмов [9—12].
Основным критериям оптимизации является трассируемость — процентное количество проложенных соединений в общем количестве соединений (в идеале должно быть равно 100%) [13, 14]. Ни один из подходов к решению задачи трассировки при использовании современных технологий производства СБИС, в частности при технологии менее 35 нм, не обеспечивает 100%-ную прокладку соединений. Выходом в данном случае является организация процесса трассировки в две стадии. На первой стадии осуществляется трассировка соединений с ограничениями на их форму. Это, например, трассировка в канале, трассировка коммутационных блоков, при трассировке по всему чипу применяются шаблоны соединений — трассировка производится образцами, при этом применяются только простые формы соединений (L-форма и Z-форма). Алгоритмы, используемые на первой стадии (как правило, комбинаторные), позволяют для заданной постановки проложить большинство соединений (если не все). Однако в силу ограничений на форму соединений, несмотря на наличие ресурсов, отдельные соединения остаются частично
* Работа выполнена при финансовой поддержке РФФИ (гранты № 12-01-00100; 13-01-00596; 13-07-12091-0ФИМ).
HM
1
1
2
3
4
5
6
Номера цепей 12 4 5
7 6
4 8
] ] ] р* ] ] РУ ] ff6 P l Pf8 ] ] ]
Í2 f4
f9 fu
f3 f7
f10
f12
] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ]
12 9 2 3 10 3
9 11 10 6 7 4 10 10 11 12 Номера цепей
6 5 4 3 2 1
t
HM
Рис. 1. Оптимальное решение задачи трассировки в канале
или полностью не протрассированными. Для таких соединений на второй стадии используют волновые алгоритмы дотрассировки, отличительная особенность которых заключается в том, что они позволяют найти маршрут, если он существует [1, 2].
Дотрассировка — это сложная задача, для которой пока нет однозначного способа решения, гарантирующего оптимальный результат [1]. В связи с этим разработка новых алгоритмов на сегодняшний день является актуальной. В настоящее время интенсивно разрабатывается научное направление с названием "Природные вычисления" (Natural Computing), объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. К таким методам можно отнести, прежде всего, методы моделирования отжига, методы эволюционного моделирования, генетические алгоритмы (ГА), методы эволюционной адаптации, алгоритмы роевого интеллекта, а также муравьиные (Ant Colony Optimization — ACO) и пчелиные (Bee Colony Optimization — BCO) алгоритмы [12—20]. Отдельные попытки [1, 15, 21—23] применения эволюционного моделирования к задаче канальной трассировки были достаточно успешными. Однако предложенные структуры ГА фактически являются "слепыми" поисковыми структурами с присущими им недостатками: генерация решений с нарушениями, что требует дополнительного контроля; генерация большого количества подобных решений; генерация большого количества "плохих" решений.
Резкое повышение функциональной сложности СБИС стимулирует разработку новых эффективных методов и средств их проектирования. В статье предлагаются новые технологии, принципы и механизмы решения задачи канальной трассировки, дотрассировки и перетрассировки, основанные на моделировании процессов адаптивного поведения муравьиной колонии [24—27]. Предложенный подход полностью применим для "бессеточной" трассировки соединений разной ширины. По сравнению с существующими алгоритмами достигнуто улучшение результатов.
1. Постановка задачи канальной трассировки. Канал представляет собой область, ограниченную двумя линейками контактов [1]. Нижний ряд контактов B = [b¡ |i = 1, nb}, верхний ряд контактов T = [t¡ |i = 1, nt}. К контактам подходят цепи: к нижнему ряду соответственно множество цепей
Cb = [cbi |i = 1, nb} а к верхнему — соответственно множество цепей Ct = [cti |i = 1, nt}, Cb u Ct = C.
На область трассировки наносится опорная ортогональная сеть, по линиям которой проходят трассы. Горизонтальные линии называют магистралями. Вертикальные линии проходят через контакты (рис. 1).
При канальной трассировке каждая цепь, связывающая эквипотенциальные выводы, представляется в виде набора горизонтальных и вертикальных фрагментов (участков). Горизонтальные участки размещаются на магистралях. Конфигурация вертикальных участков, связывающих горизонтальные участки с нижней и верхней линейками контактов, полностью определяется месторасположением горизонтальных участков. Горизонтальный участок рассматривается как горизонтальный фрагмент, связанный вертикальными участками с соответствующими контактами
3
9 10 7
4
8
12
Рис. 2. Граф вертикальных и граф горизонтальных ограничений
одной и той же цепи. Существуют различные подходы к формированию горизонтальных фрагментов. В простейшем случае цепь имеет один горизонтальный фрагмент, к которому инцидентны вертикальные фрагменты. Трассировка, при которой цепи содержат только один горизонтальный фрагмент, называется безызломной. На практике в местах контакта вертикальных и горизонтальных фрагментов возможны изломы, т.е. горизонтальные участки возникают между парой соседних контактов одной цепи. В общем случае задача трассировки в канале (ЗКТ) рассматривается как задача размещения с соблюдением ограничений множества горизонтальных
участков F = \fj\i = 1, п} на множестве магистралей М = [т] |у = 1,пт} [1]. Ограничения заключаются в запрете наложения друг на друга вертикальных или горизонтальных фрагментов различных цепей. Для учета этих ограничений используются ориентированный граф вертикальных ограничений (ГВО) = (V, Е) и неориентированный граф горизонтальных ограничений (ГГО) бн = (V, V), где V— множество вершин, соответствующих горизонтальным фрагментам (рис. 2). Направленное ребро ек = (V;-, V) ^ Е существует тогда и только тогда, когда фрагмент V должен быть расположен выше фрагмента V для предотвращения наложений вертикальных сегментов цепей. Например: направленное ребро между вершинами 1 и 2 в графе (см. рис. 2) информирует о том, что фрагмент У должен быть расположен выше фрагментаУ2 (см. рис. 1). Ребро ык = (V-, Vj) е V существует тогда и только тогда, когда для исключения наложения друг на друга горизонтальные фрагменты VI и V должны размещаться в разных магистралях. Соблюдение ограничений гарантирует разнесение соединений в два слоя без пересечений и наложений в пределах слоя [1].
Чтобы задача решалась в рамках классической постановки, граф должен быть ациклическим. В общем случае допускаются изломы горизонтальных фрагментов. Предполагается, что путем ввода изломов фрагментов в ГВО исключены все циклы [1, 2].
Основная цель канальной трассировки заключается в размещении множества F горизонтальных фрагментов в минимальном числе магистралей, в соответствии с ограничениями бн и Введем обозначения: ¡1 — левый конец фрагментаг{ — правый конец. Пусть х(1;), х(г) — координаты позиционирования ¡1 и на оси X, распространяющейся вдоль ряда контактов.
Рассмотрим линейный алгоритм размещения в магистралях множества горизонтальных фрагментов, заданного в виде списка F. Последовательно, начиная с первой, выбираются магистрали для заполнения фрагментами цепей. Если текущая магистраль заполнена, а множество еще не размещенных фрагментов не пусто, то выбирается следующая по порядку магистраль. Первая м
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.