ЭВРИСТИКИ БЕССЕТОЧНОЙ ДОРАЗВОДКИ НЕПРОТРАССИРОВАННЫХ ЦЕПЕЙ В КОММУТАЦИОННОМ БЛОКЕ
,
Таганрогский государственный радиотехнический университет, nev@tsure.ru
Новый подход к бессеточной трассировке коммутационного блока (switchbox, SB) с трассами различной ширины в процессе физического проектирования СБИС был представлен в [1]. Общий метод включает три алгоритма: эвристический трассировщик (А1), генетический трассировщик (А2) и трассировщик для непротрассированных цепей (А3). Алгоритм А1 предварительно трассирует отдельные фрагменты цепей, алгоритм А2 основан на специальных схемах кодирования и декодирования решений и использует модификации известных генетических операторов. Алгоритм А3 имеет дело с цепями, оставшимися непротрассированными, и делает попытку трассировать их на основе использования оригинального представления фрагментов трасс в каждом слое трассировки SB в виде прямоугольных областей, называемых тайлами (tile – плитка). Алгоритм А3 детально описан в настоящей статье.
Алгоритм А3 может использоваться после алгоритмов А1 и А2, если выделенный на трассировку лимит времени позволяет это сделать. Алгоритм А3 обеспечивает эвристическую доразводку непротрассированных цепей и включает следующие базовые процедуры:
· упорядочение непротрассированных цепей,
· выбор очередной цепи (I) для доразводки,
· создание дуальной модели трассировки (ДМТ),
· трассировка цепи I на ДМТ (поиск пути в графе маршрутизации; маршрутизация непротрассированных соединений; метризация соединений).
Рассматриваемый алгоритм должен работать только в том случае, когда предшествующие алгоритмы А1 и А2 дали неполные результаты трассировки SB. Цепи, подлежащие доразводке, должны быть упорядочены по определенным критериям. Главный критерий – приоритет цепи, учитывающий присутствие критических цепей. Кроме него использованы еще два критерия. Первый критерий – расстояние (D) между соединяемыми точками. Цепи с одинаковым приоритетом следует упорядочить по убыванию значения D. Второй критерий – расстояние (DC) между центром цепи и центром SB. Цепи с одинаковым приоритетом следует упорядочить по убыванию значения DC. Пользователь также может установить порядок проверки дополнительных критериев.
Топология трасс может быть представлена достаточно просто в виде множества наборов тайлов цепей. Тайл представляет собой прямоугольный фрагмент трассы в одном слое топологии SB. Тайлы не разрешается перекрывать в пределах слоя. Элементы топологии помечены как блочные тайлы. Блочный тайл может использоваться для представления сегментов слоя металла или поликремния. Область топологии, не содержащая блоков, является свободным пространством. Преобразование свободной области в набор свободных тайлов может быть сделано посредством расширения верхней и нижней границ каждого блока по горизонтали влево и вправо до достижения другого блока или границы топологии SB [2]. На этом плане свободные тайлы представляются максимальными горизонтальными полосами – стрипами (strip) (рис.1). Дуальный план тайлов может быть создан расширением левой и правой границ каждого блока по вертикали вверх и вниз до достижения другого блока или границы топологии SB, как показано на рис.1.
На дуальном плане тайлы представляются с помощью максимальных вертикальных стрипов (рис. 2).
Некоторые группы стрипов могут быть объединены в общие стрипы для обеспечения прохождения широкой трассы. Оба плана представляют ДМТ для построения графа организации процесса трассировки. Каждому слою трассировки соответствует отдельная ДМТ. Тогда для SB с тремя слоями металла и слоем поликремния потребуется четыре ДМТ, с помощью которых реализуются переходы между слоями. Вершина графа соответствует вертикальному или горизонтальному стрипу или тайлу. Если некоторые вертикальные и горизонтальные стрипы перекрываются, то соответствующие вершины графа соединяются ребром. Вес ребра равен минимальной ширине перекрываемых стрипов, как показано на рис. 3.
Рис. 1. Горизонтальные стрипы
Рис. 2. Вертикальные стрипы
Рис. 3. Пример перекрываемых стрипов
Примеры вертикального и горизонтального плана тайлов представлены на рис.1, 2. Список ребер графа ДМТ для этих примеров имеет следующий вид:
(h1, v1); (h1, v2); (h1, v3); (h1, v4); (h1, v5); (h1, v6);
(h2, v1);
(h3, v3); (h3, v4);
(h4, v1); (h4, v3); (h4, v4); (h4, v7); (h4, v8);
(h5, v1); (h5, v7);
(h6, v4);
(h7, v6);
(h8, v4); (h8, v6); (h8, v10);
(h9, v1); (h9, v4); (h9, v6); (h9, v7); (h9, v9); (h9, v10).
Процесс трассировки между двумя или более контактами представляет собой поиск дерева соединений (цепи) на графе. Процесс поиска реализован на базе идей Е. Дейкстры и лабиринтной трассировки [3] посредством двух следующих шагов. Первый шаг представляет построение дерева соединений. Второй шаг реализует точное определение каждого фрагмента цепи в пределах соответствующих стрипов графа ДМТ. В данном случае производится уточнение конфигурации трассы в пределах полученной на предыдущем этапе области ее возможных положений.
После распространения волны, для обычного волнового алгоритма, использующего дискретное рабочее поле (ДРП), прокладка соединений не вызывает трудностей. В нашем случае проблема, (и преимущество ) в том, что форма и размеры блоков связаны с метрикой не самой цепи, а окружающего пространства. При рассмотрении метризации цепей нас будут интересовать, прежде всего, вопросы, связанные с главной целью трассировки – максимизацией процента реализованных соединений. Это вопрос экономии ресурсов рабочего поля и уменьшения вероятности блокировки соединений.
Включенный в кратчайший путь блок может быть значительно шире цепи. В общем случае, для участка трассы между двумя поворотами нет определенной формы границ. Поэтому рассмотрим сначала обстоятельства, которые мало с ней связаны.
При нахождении маршрута в графе маршрутизации получается последовательность горизонтальных и вертикальных блоков. Каждый переход к новому блоку – это поворот. Таким образом, мы имеем последовательность поворотов, внутри которых нужно расположить трассу. Если говорить о поворотах, речь может идти о правом или левом положении трассы при входе в поворот и выходе из него. Возникает вопрос, на что и каким образом может повлиять прижимание трассы к той или иной стороне блока. Для текущей цепи поворот на самом деле является перекрестком.
При рассмотрении перекрестка (рис.4, а-б) видно, насколько разной может быть эффективность его использования. Причём легко заметить, что наибольшее влияние на возможность использования того же перекрестка другими трассами оказывает прижимание трассы на входе в поворот, определяемое на предыдущем повороте.
Рис. 4. Перекресток: а) дальнее прижимание, б) ближнее прижимание
Рассмотрим двойной поворот, как основной элемент трассы (рис.5). Для него ещё более важно то самое прижимание, о котором говорилось выше. Если для поворота это было прижимание, определяемое предыдущим поворотом, то для двойного поворота оно определяется межповоротным пространством. Важность этого прижимания высока потому, что от межповоротного пространства зависит не только разнообразие возможностей использования поворотов другими трассами, но и связь поворотов этими трассами. С другой стороны, прижимание, определяемое поворотом предшествующим двойному, важно в основном как межповоротное пространство предыдущего двойного поворота. Ниже приведена классификация поворотов.
.
Рис. 5. Двойной поворот
1. Считая основным элементом трассы двойной поворот, можно выделить два класса двойных поворотов: однонаправленный и разнонаправленный (рис.6, а-б).
Рис. 6. Два класса двойных поворотов: а) однонаправленный, б) разнонаправленный
2. Для одностороннего поворота можно выделить два типа: ближний и дальний – по положению межповоротной части трассы относительно входного поворота (рис.7, а, б).
Рис. 7. Два типа одностороннего поворота: а) ближний, б) дальний
3. Каждый из этих типов и классов распадается на три вида: односторонний, внутренний, разносторонний. Они отличаются друг от друга положением входной и выходной частей (рис.8, а-в).
Рис. 8. Три вида одностороннего поворота: а) односторонний, б) внутренний, в) разносторонний
Имеет смысл облегчить использование тех же межповоротных областей и перекрестков другими цепями. Назовем это увеличением степени связности (СС).
Выберем правило расчета степени связности для двойного поворота. В двойном повороте можно выделить два перекрестка и семь примыкающих к ним межповоротных зон. С точки зрения увеличения СС, предпочтительнее тот вид прокладки, который отсекает от перекрестка наименьшее число межповоротных областей. Для учета этого преимущества рассчитаем СС как сумму чисел, не отсеченных от перекрестков межповоротных областей. Рис. 5-7 показывают, что этого недостаточно. На рис.5 СС = 4+2 = 6, на рис.6 СС = -7, на рис.7 СС = 6.
Явно выделяется рис.5. Здесь остается возможной прокладка трассы через оба перекрестка. Вообще, предпочтительнее случай с большим количеством областей, имеющих доступ друг к другу. Это преимущество и особенность рис.5 учитывает следующий метод расчета CC: Sp = ån(n-l), где n – число связных межповоротных областей, Sp – степень связности двойного поворота.
Легко заметить, что односторонние повороты значительно лучше по разработанным оценкам, чем разносторонние, а ближние лучше дальних. Полученные выводы могут служить основой алгоритма метризации соединений. Остаётся только решить, каким образом перейти от степени связности одного двойного поворота к характеристике всей трассы. Просто рассчитать степень связности для всей трассы, значит рассчитывать, прежде всего, на параллельную текущей прокладку других трасс. Представляется маловероятным следование произвольной трассы всем изгибам уже проложенной. Даже если такое соединение существует, ему могут помешать более часто встречающиеся трассы, использующие отдельные участки соседнего с проложенной трассой пространства. Поэтому рассчитаем степень связности трассы (St) как сумму степеней связности всех её двойных поворотов.
Для выработки правил метризации рассмотрим различные сочетания видов двойных поворотов.
Для случая «разнонаправленный поворот – однонаправленный поворот», например: влево, вправо, вправо (л, п, п.) оптимальным по первому параметру будет прижимание трассы к стороне однонаправленного поворота (рис.9). Высокая оценка однонаправленного поворота вынуждает игнорировать изменения оценки однонаправленного поворота (18-20), вызванные ранее принятыми решениями.
Рис. 9. Прижимание трассы к стороне однонаправленного поворота
Случай (л, л, п, п) показан на рис.10. Очевиден конфликт между двумя однонаправленными поворотами, один из них должен стать односторонним. Как и везде, конфликт между разнонаправленным (18-20) и однонаправленным (30-42) поворотами, решается в пользу последнего.
Рис. 10. Случай (л, л, п, п)
Последовательность однонаправленных поворотов (л, л, л, л). Прижимание к стороне поворота даёт максимальную оценку.
Последовательность разнонаправленных поворотов (л, п, л, п, л, п.) показана на рис.11. В этом случае всегда возможен выбор лучшего вида прокладки в зависимости от ранее принятых решений.
Рис. 11. Последовательность разнонаправленных поворотов (л, п, л, п, л, п.)
Так как до метризации трассы определяются лишь классы поворотов, то приведённых случаев вполне достаточно. Учитывая сделанные ранее замечания, запишем алгоритм метризации соединения.
1. Проходя по цепочке поворотов, ищем первое повторение (л, л) или (п, п). Если такое повторение есть, на всех предыдущих поворотах прижимаем трассу к стороне найденного одностороннего поворота.
2. Если двойных поворотов нет, то трасса всегда прижимается к стороне чаще встречающегося поворота.
3. Проходя до конца последовательности двойных поворотов, определяем направление, на которое переходили чаще. Все двойные повороты должны быть ближнего типа, но при смене их направления трасса прижимается к стороне определяемого направления. При выполнении данного условия двойные повороты, к которым переходим чаще, будут ближнего типа, внутреннего вида. Остальные двойные повороты – ближнего типа, одностороннего вида.
4. При выходе из двойного поворота сторона прижимания сохраняется до следующего двойного поворота.
5. Сторона прижимания при переходе к двойным поворотам определяется направлением двойного поворота. Переход к пункту 2.
Далее рассмотрим два примера определения пути на графе ДМТ для соединения типа «контакт-контакт» (рис.12) и соединения типа «фрагмент-фрагмент» (рис.13).
Рис. 12. Соединение типа «контакт-контакт»
На рис. 12, 13 вертикальные тайлы представлены тонкими линиями, а горизонтальные тайлы – толстыми линиями. Пересечение вертикальных и горизонтальных тайлов позволяет обеспечить повороты трасс. На рис.12 соединение контактов А-А реализовано с помощью тайлов v1-h1-v2-h2-v3 в одном слое. На рис.13 показано, что соединение «фрагмент-фрагмент» B-B реализовано с помощью тайлов v1-h1-v2-h2-v3 тоже в одном слое. На фрагменте точка для соединения выбрана так, чтобы обеспечить минимальную длину трассы.
Рис. 13. Соединение типа «фрагмент-фрагмент»
Рассмотренные примеры показывают возможности нашего подхода реализации этапа эвристической доразводки непротрассированных цепей. Выбранная структура ДМТ позволяет обеспечить прокладку трасс различной ширины.
В отличие от существующего метода для конструкции графа ДМТ [2] предлагаемый подход имеет следующие особенности:
· максимальное расстояние между трассами рассчитывается при построении графа ДМТ. Оно дает нам выигрыш в процессе трассировки и проигрыш в процессе перестройки ДМТ для трассировки трасс, имеющих другое расстояние между трассами;
· предлагаемая ДМТ позволяет иметь произвольное число соединений тайлов по сравнению с подходом К. Сечена [2]. Это увеличивает размер ДМТ, но позволяет находить более качественные решения;
· можно конструировать дополнительные объединенные тайлы для трассировки более широких трасс и более эффективной трассировки трасс с различной шириной и расстоянием между трассами;
· каждый тайл предлагаемой ДМТ локализован в определенном слое топологии SB. Пересечения горизонтальных и вертикальных тайлов позволяют реализовать переходы между несколькими слоями.
Если после работы предшествующих алгоритмов оказалось, что трассировка SB не завершена, необходимо использовать процедуру частичного удаления фрагментов трасс и повторной перетрассировки [2-16]. Подобная процедура может быть реализована на основе эвристического итерационного алгоритма для отдельных частей непротрассированных цепей. Можно выделить три главных типа непротрассированных цепей:
· цепи, оставшиеся непротрассированными после работы эвристического, генетического и адаптивного алгоритмов;
· части пар перекрывающихся цепей;
· части (фрагменты) цепей, которые после работы предшествующих алгоритмов трассировки стали изолированными друг от друга.
Представляется целесообразным использовать следующие операции [3, 4]:
· «удаление магистрали» (частичное удаление и перетрассировка в локальной области SB);
· парная перестановка магистралей; групповая перестановка магистралей;
· перераспределение магистрали.
Все эти операции представлены на графе ДМТ. Для налагающихся частей пар трасс используются три процедуры:
· удаление части первой трассы и ее перетрассировка;
· удаление части второй трассы и ее перетрассировка;
· удаление частей обеих трасс и их перетрассировка.
Набор тестов для описанного выше алгоритма трассировки включал тесты проверки качества программной реализации всех его компонент (упорядочение непротрассированных цепей, выбор очередной цепи для доразводки, построение ДМТ, доразводка соединений «точка-точка» и «сегмент» и др.), а также комплексные тесты проверки работоспособности и качества функционирования программы данного алгоритма в составе общей программы бессеточной трассировки. Результаты тестирования подтвердили эффективность предлагаемого подхода.
ЛИТЕРАТУРА
1. Kureichik V. M., Lebedev B. K., Nuzhnov E. V. Approach To Genetic Switchbox Gridless Routing // Известия ТРТУ. Тематический выпуск «Материалы Международной научно-технической конференции «Интеллектуальные САПР-1998»». – Таганрог: Изд-во ТРТУ, 1999. – №3. – С. 89-96.
2. Tseng H.-P., Sechen K. A Gridless Multi-layer Channel Router Based on a Combined Constraint Graph and Tile Expansion Approach // ISPD-96, 1996. – P. 210-217.
3. Shervani N. Algorithms for VLSI Physical Design Automation. Second edition. – Kluwer Academic Publishers, 1995. – 538 p.
4. Marek-Sadowska M. Switchbox routing: a retrospective // INTEGRATION. The VLSI Journal, 1992. – № 13. – P. 39-65.
5. Pyke R. B. A Gridless Switchbox Router // IEEE Custom Integrated Circuits Conference, 1987. – P. 629-632.
6. Davidenko V. N., Kureichik V. M., Miagkikh V. V. Genetic Algorithm for Restrictive Channel Routing Problem // Proceeding of the seventh IC on GA, USA, 1997. – P. 636-642.
7. Lienig J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits // Evolutionary Computation, 1994. – № 1(4). – P. 293-311.
8. Kagan-Guerkaynak F. A Discussion of Current Routing Area Minimization Techniques. Advanced VLSI Design Tools and Techniques Final Project, 1996. – P. 1-15.
9. Braunt D. et all. Chameleon: A New Multilayer Channel Router // Proceedings of the 23th Design Automation Conference, 1986. – P. 495-502.
10. Khoo K.-Y., Cong J. An Efficient Multilayer MCM Router Based on Four-Via Routing // Proceedings of the 30th Design Automation Conference, 1993. – P.590-595.
11. Schemelinin V. M., Danilin A. Operator Method for Switchbox Routing // Известия ТРТУ. Тематический выпуск «Материалы Международной научно-технической конференции «Интеллектуальные САПР-1996»». – Таганрог: Изд-во ТРТУ, 1997. – № 3. – C. 204-210.
12. Lebedev. B. K. Channel Routing on Base Genetic Procedures // Известия ТРТУ. Тематический выпуск «Материалы Международной научно-технической конференции «Интеллектуальные САПР-1996»». – Таганрог: Изд-во ТРТУ, 1997. – № 3. – C. 53-60.
13. Taniguch N. et all. An Approach to Channel Routing Using Genetic Algorithms // Bulletin of Faculty of Engineering, Tokushima University, 1993. – № 38. – P. 99-112.
14. Reed J., Sangiovanni-Vincentelly A., Santomauro M. A New Symbolic Channel Router: YACR2 // IEEE Transactions on CAD, vol. CAD-4, 1985. – № 3. – P. 208-219.
15. Rahmani A. T., Ono N. A genetic algorithm for channel routing problems // Proceedings of the Fifth International Conference on Genetic Algorithms. – San Matco. CA: Morgan Kaufmann, 1993. – P. 494-498.
16. Yoshimura T., Kuh F. S. Efficient algorithm for channel routing // IEEE Transactions on Computer-Aided Design, 1982. – № 1(1). – P. 25-35.
