В. В. ВОЙТЮК
Научный руководитель – А. Б. ИСАКОВ к. т.н. доцент
Санкт-Петербургский государственный электротехнический
университет
АЛГОРИТМ ОДНОВРЕМЕННОГО РАЗМЕЩЕНИЯ И ТРАССИРОВКИ ДЛЯ РЯДНЫХ ПЛИС
Представлен алгоритм одновременного размещения и трассировки ПЛИС с рядным дизайном (архитектура Actel). Предлагаемый алгоритм позволяет достичь значительного улучшения характеристик размещения по сравнению с традиционными системами последовательного размещения и трассировки.
Рядные ПЛИС состоят из рядов логических модулей, разделенных каналами. Каждый логический модуль можно сконфигурировать для выполнения различных функций. Ресурсы для горизонтальной трассировки представлены в виде сегментов каналов. Смежные сегменты соединяются при программировании горизонтальных антипрожигаемых перемычек, а порты логических модулей – программированием поперечных антипрожигаемых перемычек. Ресурсы для вертикальной трассировки – проводники, пересекающие каналы, которые тоже могут быть сегментированы.
Проблема, связанная с этой традиционной компоновкой – необходимость выполнить две несовместимые оптимизации: размещение для плотной трассировки и удовлетворение жестких требований к временным характеристикам. В связи с особенностями архитектуры ПЛИС оценка возможности минимизации задержек на этапе размещения очень сложна.
В основу исследования легло предположение, что суть проблемы в том, что размещение, общая и детальная трассировка выполняются как отдельные последовательные шаги. Было предложено выполнять одновременное размещение, общую и детальную трассировку. Хотя такая стратегия выглядит слишком вычислительно трудоемкой, в случае разработки соответствующего алгоритма она может быть эффективной.
Стратегия для эффективного совмещения размещения, а также общей и детальной трассировки включает следующие ключевые элементы:
· Для оптимизации был выбран алгоритм «имитации отжига», как эффективный при решении сходных проблем проектирования.
· В процессе оптимизации можно манипулировать всеми соединениями и ячейками.
· Промежуточная конфигурация компоновки может быть неполной.
· Общая и детальная трассировка выполняются инкрементально.
· Определение критических путей производится на каждом этапе оптимизации.
Проблема «имитации отжига» может быть описана на основе четырех ключевых компонентов: представления состояния текущего решения, набора перемещений из одного состояния в другое, целевой функции для оценки каждого состояния, и «схемы охлаждения», определяющей, как можно перейти от начального поиска к локальной оптимизации.
Набор перемещений в данном случае был ограничен только двумя типами перемещений – случайной перестановкой ячеек и переназначением выводов. Целевая функция отбраковывает неразводимые компоновки, и компоновки с наихудшими временными характеристиками.
Каждая перестановка приводит к изменению значения целевой функции, в частности, к изменению количества не разведенных глобально соединений. Вместо вычислительно неэффективной глобальной трассировки после каждой перестановки, была введена инкрементальная трассировка, основанная на простой эвристике. При перемещении ячейки все соединения, связанные с ней, добавляются к глобально неразведенным соединениям. После каждого перемещения делается попытка развести каждое неразведенное соединение; приоритет отдается наиболее длинным из них. Каждое изменение размещения меняет количество детально разведенных соединений. При инкрементальной детальной трассировке применяется отдельный набор эвристик, и производится косвенная оптимизация длины соединения, т. к алгоритм трассировки выбирает кратчайший путь. Принятие перемещения зависит от окончательного значения целевой функции и его соответствия ограничениям.
При создании прототипа системы одновременного размещения и глобальной и локальной трассировки на базе алгоритма размещения TimberWolf и известных алгоритмов глобальной и детальной трассировки для рядных ПЛИС удалось добиться существенной оптимизации временных характеристик, и некоторого сокращения количества неразведенных трасс по сравнению с последовательным алгоритмом. Однако время работы алгоритма в 3-4 раза превышало время работы последовательного алгоритма. Очевидно, что данный подход имеет ряд преимуществ по сравнению с традиционным подходом. Продолжается работа по повышению быстродействия и техническому улучшению этого метода.
Список литературы:
1. S. Brown, R. Francis, J. Rose and Z. Vranesic, “Field-Programmable Gate Arrays”, Kluwer Academic Publishers, 1992.
